【057-Insert Interval(插入区间)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5]...
#include<math.h>
class Solution {
private:vector<string> solution;vector< vector <int>> result;vector<int> columns;
public:bool check(int row, int col){for(int r=0; r<row; r++)if(columns[r] == col || (row-r) == abs(columns[r]-col))returnfalse;returntrue;}void backtracking(int n, int row){if(row == n){result.push_back(columns);return;} for(int col=0; col<n; col++){columns.push_back(col);if(check(r...
本来想写完递归再写这个专栏的,但是老师给了一个贪心的题目,没办法只能开一个板块了简介在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。与这个局部最优解相对应的全局最优解会在动态规划里面展现出来。例题先来一道经典的贪心热热手,跳跃游戏就算是一个比较经典的贪心题思路一开始看到这个题目不知不觉开始用动态规划在写了 (°ー°〃)仔细一看返回值...
1、题目 – Sqrt(x)Implement int sqrt(int x).Compute and return the square root of x.题目意思很简单,就是求出x的平方根。分析:一看这题目,感觉很简单,很容易想到的是二分法,我最开始的解法是从1、2、4、8 … 2 * n,计算出n < x < 2n,然后再在 n 和 2n间,用二分法,找到平方根结果。这种方法比较麻烦的一点是,乘积是有可能越界的,要处理乘积越界的情况,代码可读性不强。class Solution {
public:int sqrt(int x) {i...
【024-Swap Nodes in Pairs(成对交换单链表的结点)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 题目大意 给定一...
Given a binary tree, find all leaves and then remove those leaves. Then repeat the previous steps until the tree is empty. Example:
Given binary tree 1/ 2 3/ \ 4 5
Returns [4, 5, 3], [2], [1]. Explanation:
1. Remove the leaves [4, 5, 3] from the tree1/ 2
2. Remove the leaf [2] from the tree 1
3. Remove the leaf [1] from the tree [...
看到题目,一个变种的八皇后,在矩阵中寻找路径。 关于回溯的思路在博客: Burst Balloons(leetcode戳气球,困难)从指数级时间复杂度到多项式级时间复杂度的超详细优化思路(回溯到分治到动态规划 ) 中有非常详细的描述。 本题优化时间复杂度的关键在于剪枝,当越界、字符不匹配、路径已走过时立即停止搜索并返回,进行可行性剪枝。publicboolean exist(char[][] board, String word) {int strPoint = 0;int xL...
【114-Flatten Binary Tree to Linked List(二叉树转单链表)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given a binary tree, flatten it to a linked list in-place. For example, Given 1/ 2 5/ \ 3 4 6 The flattened tree should look like: 1 2 3 4 5 6题目大意 给定一棵二叉树,将它转成单链表,使用原地算法。 解题思...
问题描述:将给定的单链表L: L 0→L 1→…→L n-1→L n,重新排序为: L 0→L n →L 1→L n-1→L 2→L n-2→…要求使用原地算法,并且不改变节点的值例如:对于给定的单链表{1,2,3,4},将其重新排序为{1,4,2,3}.Given a singly linked list L: L 0→L 1→…→L n-1→L n,reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…You must do this in-place without altering the nodes‘ values.For example,Given{1,2,3,4}, reorder...
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
leetcode 原题第一题,主要采用C#写,小白进阶,暴力法解决~~~public class Solution { public int[] TwoSum(int[] nums, int target) { for(int i = 0;i<nums.Lengt...
解法代码来源 :https://blog.csdn.net/whdAlive/article/details/81084793算法来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree 实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。示例:Trie trie = new Trie();trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie...
【009-Palindrome Number(回文数)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Determine whether an integer is a palindrome. Do this without extra space. 题目大意 判断一个数字是否是回访字数,不要使用额外的空间。 解题思路 为了不使用额外的空间,参考了其它的解决,那些解法看起来在isPalindrome方法中没有使用额外参数,但是却使用了方法调用,这个比一个整数消耗的空间更多 ,并没有达到...
题目:单词搜索给定一个二维网格和一个单词,找出该单词是否存在于网格中。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例:board =[ [‘A‘,‘B‘,‘C‘,‘E‘], [‘S‘,‘F‘,‘C‘,‘S‘], [‘A‘,‘D‘,‘E‘,‘E‘]]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false 提...
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。 代码:class Solution: def __init__(self): self.res = [] def partition(self, s: str) -> List[List[str]]: self.helper(s,[]) return self.res def helper(self,part_of_s,answerList): if not part_of_s: self.res.append(answerList) for i in range(1,len(part...
0 解题步骤回溯法解题时通常包含3个步骤:1. 针对所给问题,定义问题的解空间;2. 确定易于搜索的解空间结构;3. 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。对于问题的解空间结构通常以树或图的形式表示,常用的两类典型的解空间树是子集树和排列树。当所给的问题是从n个元素的集合S中找到S满足某种性质的子集时,相应的解空间树称为子集树。例如,n个物品的0-1背包问题所对应的解空间树是一棵子集树,这类...