2. 两数相加 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ // 模拟 class Solution { public: ListNode* addTwoNumb...

62.不同路径 class Solution { public: int uniquePaths(int m, int n) { // dp[i][j] 表示在这个位置共有多少种路径 // dp[i][j] = dp[i-1][j] + dp[i][j-1] // dp[i][0] == dp[0][j] == 1 vector<vector<int>> dp(m, vector<int>(n, 1)); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = ...

509. 斐波那契数 class Solution { public: int fib(int n) { // 1、dp数组的含义：dp[i]表示每个斐波那契数 // 2、递推公式：dp[i] = dp[i-2] + dp[i-1] // 3、初始化：dp[0] = 1, dp[1] = 1 // 4、遍历顺序：从前到后 // 5、打印dp数组（debug） if (n == 0) return 0; else if (n == 1 || n == 2) return 1; vector<int> dp(n, 0); dp[0] = 1; dp[1] = 1; for (int i...

452. 用最少数量的箭引爆气球 class Solution { public: bool static cmp (vector<int>a, vector<int>b) { return a[0] < b[0]; } int findMinArrowShots(vector<vector<int>>& points) { int res = 1; // 最少需要一支箭 if (points.size() == 0) return res; sort(points.begin(), points.end()); for (int ...

1005. K 次取反后最大化的数组和 class Solution { public: bool static cmp(int a, int b) { return abs(a) > abs(b); } int largestSumAfterKNegations(vector<int>& nums, int k) { sort(nums.begin(), nums.end(), cmp); for (int i = 0; i < nums.size(); i++) { if (k > 0 && nums[i] < 0) { nums...

122. 买卖股票的最佳时机 II把所有正数相加 class Solution { public: int maxProfit(vector<int>& prices) { int res = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] - prices[i-1] > 0) { res += prices[i] - prices[i-1]; } } return res; } }; 55. 跳跃游戏 class Solution { public: // 就去看覆盖范围！！！ bool c...

455. 分发饼干 class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int res = 0; int startIdx = 0; for (int i = 0; i < g.size(); i++) { for (int j = startIdx; j < s.size(); j++) { if (s[j] >= g[...

106.从中序与后序遍历序列构造二叉树补更，二叉树构造！！这个非常重要！！分六部分： // 1、后序数组为空，返回空节点 // 2、后序数组最后一个元素，为节点元素。数组大小为1，返回节点。 // 3、以上一节点元素作为切割点，寻找中序数组的位置 // 4、切割中序数组 // 5、切割后序数组 // 6、递归处理左右区间  class Solution { public: // 1、后序数组为空，返回空节点 // 2、后序数组最后一个元素，为节点元素 // 3、以上一节点元素作为切割点，寻找中序数组的位置 // 4、切割中序数组 // 5、切割后序数组 // 6、递归处理左右区间 TreeNo...

106.从中序与后序遍历序列构造二叉树这道题是之前二叉树没来得及写的，今天补上 class Solution { public: // 1、后序数组为空，返回空节点 // 2、后序数组最后一个元素，为节点元素 // 3、以上一节点元素作为切割点，寻找中序数组的位置 // 4、切割中序数组 // 5、切割后序数组 // 6、递归处理左右区间 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (postorder.size() == 0) return NULL; /...

93.复原IP地址 class Solution { public: vector<string> res; // pointNum 记录“.”的数量，有三个就结束 void backtracking(string& s, int startIdx, int pointNum) { if (pointNum == 3){ if (isValid(s, startIdx, s.size() - 1)) { res.push_back(s); return; } return; } for (int i = startIdx; i < s.size(); i++) { i...

39. 组合总和 class Solution { public: vector<vector<int>> res; vector<int> path; int sum = 0; void backtracking(vector<int> candidates, int target, int startIdx) { if (sum == target) { res.push_back(path); return; } else if (sum > target) { // sum大于target也需要返回！！！ return; } for...