120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[[2],
[3,4],
[6,5,7],
[4,1,8,3]]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
数字三角形，动态规划中最简单最基本的一种题型。
采用自底向上的方法，从倒数第二行开始逐步更新triangle数组中的值
状态转移方程为：triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
最后只需直接return triangle[0][0]即可~~//同学们，这是道送分题啊~~（拍黑板ing…
|
|
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { for(int i = triangle.size() - 2; i >= 0; i--) { for(int j = 0; j <= i; j++) { triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]); } } return triangle[0][0]; } }; |
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
分析：nums数组表示每个house所含有的钱的数量，设 n 为 house 的个数，从0开始为第一家，数组下标域为0~n-1。
1.当 n == 0 时，return 0
2.当 n == 1 时，return nums[0]
3.当 n >= 2 时，创建数组 dp[n]表示从0~n-1家能够抢到的最大值
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]);
要不然选择上上家(dp[i-2])和这家(nums[i])的和，要不然当前这家不抢，抢上一家(dp[i-1])。
此时最优解为 return dp[n-1]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; vector<int> dp(n, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for(int i = 2; i < n; i++) { int temp = dp[i - 2] + nums[i]; dp[i] = max(temp, dp[i - 1]); } return dp[n - 1]; } }; |
213. House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
这题是上一题的升级版~~新加了环形的街道biu biu biu~~
所以就会考虑到，最后一个和第一个房子是不能够同时进入的~要不然会告诉警察叔叔~~
所以分为两种情况~
0.不包括最后一个屋子~就抢劫0~n-2号屋子~
1.不包括第一个屋子~就抢劫1~n-1号屋子~
这样的话，return上面两种情况的最大值就好了~调用两次子函数求值，主函数取其最大值返回~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; if(n == 2) return max(nums[0], nums[1]); return max(func(nums, 0, n-2), func(nums, 1, n-1)); } int func(vector<int>& nums, int begin, int end) { int n = end - begin + 1; vector<int> dp(n); dp[0] = nums[begin]; dp[1] = max(nums[begin], nums[begin+1]); for(int i = 2; i < n; i++) { int temp = dp[i - 2] + nums[begin+i]; dp[i] = max(temp, dp[i-1]); } return dp[n - 1]; } }; |
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
分析：prices数组是每只股票的当天的价格
遍历整个prices数组
minvalue 中保存从0到当前所有股价中最低的价格
ans 中保存minvalue到当前所有股价中能卖掉的最高的价格
最后 return ans;
|
|
class Solution { public: int maxProfit(vector<int>& prices) { int minvalue = 99999999, ans = 0; for(int i = 0; i < prices.size(); i++) { minvalue = min(minvalue, prices[i]); ans = max(ans, prices[i] - minvalue); } return ans; } }; |
303. Range Sum Query – Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
分析：根据题意，要多次调用 sumRange 函数
事实上多次调用的时候会重复计算区间内数的和
然而，（a,b）区间内数的和可以等于0~b的和 – 0~a 的和
所以可以用一个数组v[i]存储入所有0~i的和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class NumArray { private: vector<int> v; public: NumArray(vector<int> &nums) { if(nums.size() == 0) return ; v.push_back(nums[0]); for(int i = 1; i < nums.size(); i++) { v.push_back(v[i - 1] + nums[i]); } } int sumRange(int i, int j) { if(i == 0) return v[j]; return v[j] - v[i - 1]; } }; // Your NumArray object will be instantiated and called as such: // NumArray numArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2); |
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
update: v2.0： //可以把递归改成更简单易懂的递推：
分析：当楼层数等于0或1的时候都是1种方法，所以dp[0] = 1, dp[1] = 1;
其余情况下，当前楼层有两种方法，一个是从上一层楼层过来，一个是从上上层楼层过来，所以dp[i] = dp[i-1] + dp[i-2];
|
|
class Solution { public: int climbStairs(int n) { vector<int> dp(n + 1); dp[0] = 1, dp[1] = 1; for(int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } }; |
递归的方法：
分析：每一次爬楼梯可以选择爬1步或者2步
想知道n层楼梯有多少种方法，只需知道退一层后的n-1层楼梯有多少种爬法，和退两层后的n-2层楼梯有多少种爬法。
想知道退一层后的n-1层楼梯有多少种爬法，只需知道退1层后的n-2层有多少种爬法，和退2层后的n-3层有多少种爬法…
想知道退两层后的n-2层楼梯有多少种爬法，只需知道退1层后的n-3层有多少种爬法，和退2层后的n-4层有多少种爬法…
…
直到退到n==0的时候，表示这一种楼层的爬法已经完全，属于1种，ans+1。
|
|
class Solution { public: int ans = 0; int climbStairs(int n) { if(n == 0) { ans++; return ans; } if(n >= 1) { climbStairs(n - 1); } if(n >= 2) { climbStairs(n - 2); } } }; |
338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
分析：要求解0~num所有数的二进制中1的个数，每求前一个就可以根据前一个来推出后一个，所以无需每一个数字逐个运算。
具有最优子结构和重叠子问题。所以采用动态规划的方法。用数组v表示返回的vector结果
可以找到规律发现：
1.v[0] = 0
2.v[i] = v[i << 1] + i % 2
所以for循环递推，即可解得vector v里面所有的值。
上面所说的规律是这样发现的：
假设构造一颗二叉树，根节点为1，从左到右从上到下分别是1，2，3，4…的二进制，可以发现如下规律：左子树是给根节点在末尾加0，右结点是给根节点在末尾加1，可得10和11；
后来，10成为根节点，它左子树是100，右子树是101；11为根节点的树，左子树是110，右子树是111，同样是左边加0，右边加1…也就是当前数为偶数就在左子树，加0；如果当前数是奇数就在右子树，加1。
所以v[i]的值可以由 v[i << 1] + i % 2得到。——该灵感来自@男票
|
|
class Solution { public: vector<int> countBits(int num) { vector<int> v(num + 1); v[0] = 0; for(int i = 1; i < num + 1; i++) { v[i] = v[i >> 1] + i % 2; } return v; } }; |
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?//这题目还有个萌萌的小插图，如下~：
分析：从左上角走到右下角，mxn的方格，只能向下或者向右，问有多少种不同的走法。
因为题目说了m和n不会大于100，那就直接建立一个100×100的数组a存储当前格子的种类。
首先可知当i==0 || j==0的时候，说明在地图的最上边或者最左边，这个时候只有一种走法，就是直走走过来的，所以a[i][j] = 1;
如果i和j都不是0，说明这个格子在中间不是在边上，所以当前第i行第j列的走法a[i][j]能有从左边来的一种解法和从上面来的一种解法，所以a[i][j] = a[i – 1][j] + a[i][j – 1]；
用递推公式一直推到当前要求的a[m – 1][n – 1]的值的时候return该值。
|
|
class Solution { public: int uniquePaths(int m, int n) { int a[100][100]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 || j == 0) a[i][j] = 1; else a[i][j] = a[i - 1][j] + a[i][j - 1]; } } return a[m - 1][n - 1]; } }; |
63. Unique Paths II
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
这道题是上一道题的升级版~加了障碍物~
加不加障碍物差别就在于，当当前地域有障碍物的时候，a[i][j] = 0
其余的不变：
0.a[0][0] = 1;
1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以a[i][j] = a[i][j-1];
2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以a[i][j] = a[i-1][j];
3.其余情况，当前方格能由左边和上边两个方向过来，所以a[i][j] = a[i-1][j] + a[i][j-1];
最后直到一直递推输出到终点(m-1, n-1)的时候return a[m-1][n-1];
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); int a[100][100]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(obstacleGrid[i][j] == 1) { a[i][j] = 0; } else if(i == 0 && j == 0) { a[i][j] = 1; } else if(i == 0) { a[i][j] = a[i][j-1]; } else if(j == 0) { a[i][j] = a[i-1][j]; } else { a[i][j] = a[i-1][j] + a[i][j-1]; } } } return a[m-1][n-1]; } }; |
64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
这道题呢，又是上两题的升级版~上面两题是求一共有多少种~这道题是求带权值的地图的最小值~
用一个dp二维数组标记当前方格的最小值~
0.当i == 0 && j == 0的时候，dp[i][j] = grid[i][j];
1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以dp[i][j] = dp[i][j-1] + grid[i][j];
2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以dp[i][j] = dp[i-1][j] + grid[i][j];
3.其他情况下，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
最后直到一直递推输出到终点(m-1, n-1)的时候return dp[m-1][n-1];~~~~~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); if(m == 0 || n == 0) return 0; vector<vector<int>> dp(m, vector<int>(n)); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) { dp[i][j] = grid[i][j]; } else if(i == 0) { dp[i][j] = dp[i][j-1] + grid[i][j]; } else if(j == 0) { dp[i][j] = dp[i-1][j] + grid[i][j]; } else { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } } return dp[m-1][n-1]; } }; |
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
分析：特例是，当所有数都为负数的时候，要返回一个最小的负数，而非返回0。
设temp的初始化值为nums[0]，i从1一直遍历到len-1：
0.ans始终为temp和ans值中较大的那一个。
1.当当前temp的值为正数的时候，来者nums[i]加temp。//此时如果nums[i]为负数对临时总和temp无贡献，则不会更新ans的值，我们临时把它收入temp的总和当中以备后用。如果nums[i]是正数，对临时总和temp有贡献，那就会更新ans的最大值。
2.当当前temp的值为负数的时候，temp的值直接+nums[i]。//之前的临时总和temp是个负数，对于来者nums[i]来说不管怎样nums[i]如果+temp都是在减少nums[i]，还不如直接将temp=0舍弃前面的负数和，取nums[i]当作当前的临时总和的值。
3.temp如果为0不用考虑怎样都行~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int maxSubArray(vector<int>& nums) { int len = nums.size(); if(len == 0) return 0; int ans = nums[0], temp = nums[0]; for(int i = 1; i < len; i++) { if(temp > 0) { temp = temp + nums[i]; } else { temp = nums[i]; } ans = max(ans, temp); } return ans; } }; |
96. Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
二分查找树的定义是，左子树节点均小于root，右子树节点均大于root~~~
所以可以用递推的方法，把v[i]表示i个数能够构成的二叉搜索树的个数~~
初始化边界值是 v[0]=1,v[1]=1,v[2]=2~~~
当i>=3的时候，若以j为root结点，v[j-1]等于root结点左边的j-1个结点能构成的BST个数~~
v[i-j]等于root结点右边i-j个结点能构成的BST个数~//j+1~i的种数和0~i-j的种数一样。。所以就是v[i-j]~
所以v[j-1] * v[i-j]等于以j为root结点能构成的BST种数~~~
j可以取1~i中的任意一个值，把这些所有计算出来的总数相加就是v[i]的值~~~~
所以 for(int j = 1; j <= i; j++) {
v[i] += v[j-1] * v[i-j];
}
最后返回的值是v[n]的值，表示1~n能组成的BST的个数~~~~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int numTrees(int n) { vector<int> v(n+1); v[0] = 1; for(int i = 1; i <= n; i++) { v[i] = 0; if(i <= 2) { v[i] = i; } else { for(int j = 1; j <= i; j++) { v[i] += v[j-1] * v[i-j]; } } } return v[n]; } }; |
300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
update v2.0: //更高效的O(nlogn)方法~
维护一个数组vector v~~
将nums[0]加入数组，对于每一个来的数nums[i]，如果大于v.back()，就将它push入数组~~
否则，就找到第一个比这个数大的位置，将该位置的数字替换为nums[i]~~~~
最终返回v数组的长度~~~就是最长字串的长度啦~~~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> v; v.push_back(nums[0]); for(int i = 1; i < n; i++) { if(nums[i] > v.back()) { v.push_back(nums[i]); } else { *lower_bound(v.begin(), v.end(), nums[i]) = nums[i]; } } return v.size(); } }; |
v 1.0：
建立一个和nums数组等长的dp数组
dp数组dp[i]的值表示nums[i]处可以构成的最长字串的长度~~
也就是说，在i下标前面的所有nums值当中，找到所有比nums[i]小的，且dp值最大的那个值，然后加1~~
然后最长递增子序列的长度为所有dp[i]当中最大的值~~~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> dp(n); dp[0] = 1; int ans = 1; for(int i = 1; i < n; i++) { int temp = 0; for(int j = i - 1; j >= 0; j--) { if(nums[j] < nums[i]) { temp = max(temp, dp[j]); } } dp[i] = temp + 1; ans = max(ans, dp[i]); } return ans; } }; |
304. Range Sum Query 2D – Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.
啊喂，不要看下面代码这么长就关闭页面啊。。。。逻辑还是十分简明清晰的。。。
先用一个和方阵一样大小的方阵存储入所有它的左上角所有方块上数字的总和~~
然后每次调用只要大方块减去两个多余的小方块再加上重复减去的小方块就是要求的总和啦~~
还是很好想象滴~~~
记得要注意边界条件matrix.empty()、i == 0、j == 0的时候~~~
当时写了很多代码写完就直接submit solution竟然直接AC了。。。//#这也能AC系列#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class NumMatrix { public: vector<vector<int>> v; NumMatrix(vector<vector<int>> &matrix) { int m = matrix.size(); if(matrix.empty()) return ; int n = matrix[0].size(); v = vector<vector<int>> (m, vector<int>(n)); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) { v[i][j] = matrix[0][0]; } else if(i == 0) { v[i][j] = v[i][j-1] + matrix[i][j]; } else if(j == 0) { v[i][j] = v[i-1][j] + matrix[i][j]; } else { v[i][j] = v[i-1][j] + v[i][j-1] + matrix[i][j] - v[i-1][j-1]; } } } } int sumRegion(int row1, int col1, int row2, int col2) { if(row1 == 0 && col1 == 0) { return v[row2][col2]; } else if(row1 == 0) { return v[row2][col2] - v[row2][col1-1]; } else if(col1 == 0) { return v[row2][col2] - v[row1-1][col2]; } else { return v[row2][col2] - v[row1-1][col2] - v[row2][col1-1] + v[row1-1][col1-1]; } } }; // Your NumMatrix object will be instantiated and called as such: // NumMatrix numMatrix(matrix); // numMatrix.sumRegion(0, 1, 2, 3); // numMatrix.sumRegion(1, 2, 3, 4); |
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.
分析：和爬楼梯的那道题leetcode 70. Climbing Stairs有类似之处~~~~
建立一个与String等长的dp数组~~
0.如果说当前s[i]不等于0,那先令dp[i] = dp[i-1]
1.如果s[i-1]与s[i]能够构成1~26里面的数字，那就把s[i-1]与s[i]构成一个整体，dp[i] += dp[i-2];
最后返回数组的最后一个值dp[len-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int check(char a) { return a != '0'; } int func(char a, char b) { return a == '1' || a == '2' && b <= '6'; } int numDecodings(string s) { int len = s.length(); vector<int> dp(len, 0); if(len == 0 || s[0] == '0') return 0; if(len == 1) return check(s[0]); dp[0] = 1; dp[1] = check(s[1]) + func(s[0], s[1]); for(int i = 2; i < len; i++) { if(check(s[i])) dp[i] = dp[i-1]; if(func(s[i-1], s[i])) dp[i] += dp[i-2]; } return dp[len-1]; } }; |
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
分析：建立一个n+1长度的数组dp，dp[i]表示i这个数构成平方和需要数字的最小个数。
当j*j<i的时候，temp中保存j从1开始每加1得到的dp[i-j*j] + 1的最小值
当j*j=i的时候，dp[i]的值就直接为1
从2一直到n可以计算出dp[i]的所有值。。
最后return dp[n]的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int numSquares(int n) { vector<int> dp(n+1); dp[1] = 1; for(int i = 2; i <= n; i++) { int temp = 99999999; for(int j = 1; j * j <= i; j++) { if(j * j == i) { temp = 1; break; } temp = min(temp, dp[i-j*j] + 1); } dp[i] = temp; } return dp[n]; } }; |
