思路:
第三个元素之后,选择与否取决于选择之后和如果不选那种方案值最大
class Solution { public: int rob(vector213. 打家劫舍 II 代码/思路& nums) { if(nums.size() == 1) { return nums[0]; } int f[101]; f[0] = nums[0]; f[1] = max(nums[0], nums[1]); for(int i = 2; i < nums.size(); i++) { f[i] = max(f[i - 2] + nums[i], f[i - 1]); } return f[nums.size() - 1]; } };
思路:
- 最后一个元素选择与否,取决于第一个元素选择与否
- 在打家劫舍I 的基础上增加一维
- dp[i][0] 代表第0个元素不选
- dp[i][1] 代表第0个元素选择
- 最后返回这两种情况的最大值即可
class Solution { public: int rob(vector91. 解码方法 代码/思路& nums) { int n = nums.size(); int dp[110][2]; //dp[i][0] 代表第0个元素不选 //dp[i][1] 代表第0个元素选择 if(n == 1) { return nums[0]; } if(n == 2) { return max(nums[0], nums[1]); } dp[0][0] = 0; dp[0][1] = nums[0]; for(int i = 1; i < n; i++) { for(int j = 0; j < 2; j++) { if(i == 1) { //如果第0个元素没有选 if(j == 0) { //那么最大值就是 0 + nums[1] dp[i][j] = nums[1]; } //如果第 0 个元素选了 else { //那么第一个元素就不能选 //所以到dp[1][1] 的最大值就是nums[0] dp[i][j] = nums[0]; } } //当遍历到最后一个元素并且在第0个元素选择了的情况下 else if(i == n - 1 && j == 1) { //到最后一个元素为止,最大的值就是到倒数第二个元素的最大值 //因为最后一个元素已经不能选择了 dp[i][j] = dp[i - 1][j]; } //其他情况按照一般处理即可 else { dp[i][j] = max(dp[i - 1][j], dp[i - 2][j] + nums[i]); } } } return max(dp[n - 1][0], dp[n - 1][1]); } };
思路:
class Solution { public: int numDecodings(string s) { int n = s.size(); vector1869. 哪种连续子字符串更长 代码/思路f(n + 1); f[0] = 1; for(int i = 1; i <= n; i++) { if(s[i - 1] != '0') { f[i] += f[i - 1]; } if(i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)) { f[i] += f[i - 2]; } } return f[n]; } };
思路:
- 分别统计 0 和 1 的最长字串
- 看 1 的子串是否大于 0 的字串
class Solution { public: bool checkZeroOnes(string s) { int count1 = 0; int count0 = 0; int diff1 = 0; int diff2 = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == '1') { diff2 = 0; diff1++; count1 = max(diff1, count1); } else { diff1 = 0; diff2++; count0 = max(diff2, count0); } } return count1 > count0; } };724. 寻找数组的中心下标 代码/思路
思路:
- 先计算前缀和
- 枚举每个分界的下标 i
- 看是否符合 当前下标 i 左边的和(presum[i] - nums[i]) 是否等于 i 右边的和(presum[n - i] - presum[i]);
- 相等则返回 i 否则返回 -1
class Solution { public: int pivotIndex(vector优化& nums) { int n = nums.size(); int presum[n]; presum[0] = nums[0]; for(int i = 1; i < n; i++) { presum[i] = presum[i - 1] + nums[i]; } for(int i = 0; i < n; i++) { //当前下标的元素不包含,需要减去 //presum[n - 1] - presum[i]表示后缀和 if(presum[i] - nums[i] == presum[n - 1] - presum[i]) { return i; } } return -1; } };
只用找到总和sum的一半的i的坐标返回即可
class Solution { public: int pivotIndex(vector&nums) { int total = accumulate(nums.begin(), nums.end(), 0); int sum = 0; for (int i = 0; i < nums.size(); ++i) { if (2 * sum + nums[i] == total) { return i; } sum += nums[i]; } return -1; } };