Trapping Rain Water题目描述代码实现Spiral Matrix题目描述代码实现Jump Game II题目描述代码实现
题目地址： https://leetcode.com/PRoblems/trapping-rain-water/?tab=Description Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
这道题目就是给一系列的整数，由这些数字围成的水槽可以容纳多少的水。
说道盛水，那么很容易想到的就是它需要两边都是要大于0的高度的柱子才能盛水。那么我们就构造这样的形状。如果我们从两边往里面走，那么就可以构造出这样的形状，计算更短的那一边，从外面向里面靠拢，计算水量的时候是每个数字计算一次而不是一次性计算完。
class Solution {public: int trap(vector<int>& height) { int cnt = 0, right = height.size() - 1, left = 0, maxl = 0, maxr = 0; while(left < right) { if(height[left] <= height[right]) { if(maxl > height[left]) cnt += maxl - height[left]; else maxl = height[left]; left++; } else { if(maxr > height[right]) cnt += maxr - height[right]; else maxr = height[right]; right--; } } return cnt; }};Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example, Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]You should return [1,2,3,6,9,8,7,4,5].
按照顺序使用了一个dir变量确定接下来要走的方向。
class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { int m = matrix.size(), n = m?matrix[0].size():0, cnt_row = 0, cnt_col = -1; int dir = 0, cnt = m*n, min_row = 0, min_col = 0; vector<int> res; while(true) { if(cnt <= 0) break; if(!dir) { while(++cnt_col < n) { res.push_back(matrix[cnt_row][cnt_col]); cnt--; } dir = 1; min_row++; cnt_col--; } else if(dir == 1) { while(++cnt_row < m) { res.push_back(matrix[cnt_row][cnt_col]); cnt--; } n--; dir = 2; cnt_row--; } else if(dir == 2) { while(--cnt_col >= min_col) { res.push_back(matrix[cnt_row][cnt_col]); cnt--; } m--; dir = 3; cnt_col++; } else { while(--cnt_row >= min_row) { res.push_back(matrix[cnt_row][cnt_col]); cnt--; } min_col++; dir = 0; cnt_row++; } } return res; }};看到了一个很简洁的写法：
class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int m = matrix.size(), n = matrix[0].size(); vector<int> spiral(m * n); int u = 0, d = m - 1, l = 0, r = n - 1, k = 0; while (true) { // up for (int col = l; col <= r; col++) spiral[k++] = matrix[u][col]; if (++u > d) break; // right for (int row = u; row <= d; row++) spiral[k++] = matrix[row][r]; if (--r < l) break; // down for (int col = r; col >= l; col--) spiral[k++] = matrix[d][col]; if (--d < u) break; // left for (int row = d; row >= u; row--) spiral[k++] = matrix[row][l]; if (++l > r) break; } return spiral; }};Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note: You can assume that you can always reach the last index.
这里使用步骤是比较简单的方法，基本上是暴力破解了。
class Solution {public: int jump(vector<int>& nums) { int res = 0, nlen = nums.size(); vector<int> step(nlen, 0); for(int i = 0; i < nlen; i++) { if(nums[i] > 0) { for(int j = 1; j <= nums[i]; j++) if(j+i < nlen) step[j+i] = step[j+i]?min(step[j+i], step[i]+1):step[i]+1; } } return step[nlen-1]; }};对代码做了修改，只要遇到了马上就返回值，但是还是超时了。
class Solution {public: int jump(vector<int>& nums) { int res = 0, nlen = nums.size(); vector<int> step(nlen, 0); if(nlen <= 1) return 0; for(int i = 0; i < nlen; i++) { if(nums[i] > 0) { for(int j = 1; j <= nums[i]; j++) { if(j + i >= nlen - 1) return step[j+i]?min(step[j+i], step[i]+1):step[i]+1; if(j+i < nlen) step[j+i] = step[j+i]?min(step[j+i], step[i]+1):step[i]+1; } } } return step[nlen-1]; }};贪心算法可以解得：
class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); if( n < 2) return 0; int i = 0, j = 1, cnt = 0, mx; while (i < n - 1 && i + nums[i] < n - 1) { for (mx = j; j <= i + nums[i]; j++) { mx = (mx + nums[mx] <= j + nums[j]) ? j : mx; } i = mx; cnt++; } return ++cnt; /* One more step to last index. */ }};诡异的做法之BFS：
2 3 1 1 4 , is2||3 1||1 4 ||class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); if( n < 2) return 0; int level=0, currentMax=0,i=0, nextMax=0; while(currentMax-i+1>0){ //nodes count of current level>0 level++; for(;i<=currentMax;i++){ //traverse current level , and update the max reach of next level nextMax=max(nextMax,nums[i]+i); if(nextMax>=n-1) return level; // if last element is in level+1, then the min jump=level } currentMax=nextMax; } return 0; }};新闻热点
疑难解答
