题目描述给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 解法 //解法：动归 //状态定义： dp[i][j] 到（i，j）位置的最小路径和 //状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j] //状态初始化： // dp[0][0..m] = [num[0][0], dp[0][0] + num[0][1], ...] // dp[0..n][m] =...

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 解法 //解法：后序遍历+减枝 // 时间O(N) 空间O(N) bool IsBalanced_Solution(TreeNode* pRoot) { if (pRoot == nullptr) return true; return RecIsBalanced(...

题目描述给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。 解法 //解法：深度优先搜索 // 逐点进行DFS. 一次DFS即搜索所有连通的1，并把1翻转为0，防止下次重复搜索。 // 时间O（N*M) 空间（N*M） int solve(vector<vector<char> >& grid) { int nr = grid.size(); if (nr == 0) retur...

题目描述给定一个无序单链表，实现单链表的排序(按升序排序)。 解法 //解法1：归并排序 // 时间O(NlogN) 空间O（logN) ListNode* sortInList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; //二分 //注意：需要做到：a->b 能断开 //ListNode *fast = head, *slow = head; ListNode *fa...

题目描述假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。 解法 //解法：模拟法 // 1. 高->低位 链表， 反转为，低->高位链表. // 2. 模拟两数相加：从低到高，逐位相加进位。 //时间：O(N)， 空间O（1） ListNode* addInList(ListNode* head1, ListNode* h...

题目描述对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。 给定字符串A以及它的长度n，请返回最长回文子串的长度。 解法 //以left,right的中心，向两边扩展的回文串长度 int expandCenter(string & s, int left, int right) { if (left < 0 || left > right || right >= s.size()) return 0; int l = left, r = right; while (l >=0 &amp...

题目描述给出一个转动过的有序数组，你事先不知道该数组转动了多少(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。假设数组中不存在重复项。 解法 //解法：二分查找 // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段 // 接下来再判断 target 是在 mid 的左边还是右边，从而来调整左右边界 lo 和 hi //时间：O（logN） 空间O（1） int search(int* A, int n, int tar...

题目描述给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。注意：三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）解集中不能包含重复的三元组。例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20) 解法 //双指针 //时间O（N*N） 空间O（1） vector<vector<int> > threeSum(vector<int> &nums) { int n = n...

题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n≤39 解法 //解法：动归 // dp[i]: f(i) 斐波那契数 // dp[i] = dp[i-1] + dp[i-2] // dp[0] = 0, dp[1] = 1 // 时间：O（n） 空间O(1) int Fibonacci(int n) { if (n == 0 || n == 1) return n; int f2 = 0, f1 = 1; int ans =...

题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 解法 //解法：回溯法 // 时间O（n*n!） 空间O（1） //从pos..n的排列 void dfs(string & str, int pos, set<string> & ans) { if (pos == str.size() - 1) { ans.insert(str); ...

题目描述合并 k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。 解法 ListNode *mergeTwoLists(ListNode* a, ListNode* b) { if ( !a || !b ) return a? a: b; ListNode dummy(0); ListNode* tail = &dummy, *aPtr = a, *bPtr = b; while(aPtr && bPtr){ if (aPtr->val < ...

题目描述将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。 解法 ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if ((!a) || (!b)) return a ? a : b; ListNode dummy(0); ListNode *tail = &dummy, *aPtr = a, *bPtr = b; while (aPtr && bPtr) { if ...

题目描述给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。 解法 //解法：模拟 //时间复杂度O（n*m）,空间O（1） vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> ans; if (matrix.empty())return ans; int up = 0, down = matrix.size() - 1; int l = 0, r = mat...

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 解法 def reConstructBinaryTree(self, preorder, inorder): if not preorder or not inorder: return None if len(preorder) != len(inorder): ...