class Solution { public: int rectCover(int n) { if (n == 0 || n == 1 || n == 2) return n; int a = 1; int b = 2; int sum; for (int i = 3; i <= n; ++i) { sum = a + b; a = b; b = sum; } return sum; } };

class Solution { public: int jumpFloorII(int number) { int res[25] = {0}; res[0] = 1; res[1] = 1; for (int i = 2; i <= number; ++i) { res[i] = 2 * res[i-1]; } return res[number]; } };

膜拜大佬题解https://www.bilibili.com/video/BV1CK411c7gx?p=16过程分析str的长度是m，pattern的长度是nF(i,j)的含义表示：str的前i位str[0,i-1]pattern的前j位pattern[0,j-1]是匹配的情况：p[j-1] = . 或者 p[j-1]= x ，x表示任意一个小写字母，假如x=a。此时只要S[i-1]=a或者p[j-1]=.就可以转换成子问题 如果S[i-1] != a直接返回false如果p[j-1] = *，则需要考虑到p[j-2]  如果S[i-1] == p[j-2]，或者 p[j-2] == .则需要...

递归 class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } }; 空间压缩 class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; int a1 = 1; int a2 = 1; int a3 = 0; for (int i = 3; i <= n; ++i) { a3 = a1 + a2; a1 ...

递归 class Solution { public: int jumpFloor(int n) { if (n == 1) return 1; if (n == 2) return 2; return jumpFloor(n-1) + jumpFloor(n-2); } }; 动态规划 class Solution { public: int jumpFloor(int n) { int dp[50]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[...

#include <cstring> class Solution { public: vector<int> FindGreatestSumOfSubArray(vector<int>& array) { vector<int> result; int size = array.size(); vector<int> dp(size, 0); dp[0] = array[0]; int maxn = array[0]; int L = 0, R = 0; int result_L = 0, result_R = 0; for (in...

class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int max_val = INT_MIN; int cur = 0; for (int i = 0; i < array.size(); ++i) { cur += array[i]; max_val = max(max_val, cur); cur = cur < 0 ? 0 : cur; } return max_val; } };

class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int l = 0; int r = rotateArray.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; if (rotateArray[mid] > rotateArray[r]) { l = mid + 1; } else if (rotateArray[mid] < rotateArray[r]) { r = mid; } else {...

class Solution { public: bool Find(int target, vector<vector<int> > array) { int row = array.size(); int col = array[0].size(); int i = 0; int j = col-1; while (i < row && j >= 0) { if(array[i][j] == target) { return true; } else if(array[i][j] > target) { --j; } else { ++i; } }...

轮询 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { if (data.empty()) return 0; int cnt = 0; for (int i = 0; i < data.size(); ++i) { if (k == data[i]) { cnt++; } } return cnt; } }; 二分 #include <vector> class Solution { public: int GetNumberOfK(vector<int> dat...

#include <string> class Solution { public: int findNthDigit(int n) { if (n < 10) return n; int start = 1; int end = 10; long long bit = 1; // 小于10的数字一位数，1～9，共9个数字，9位； // 小于100的数字两位数，10～99，共90个数字，180位； // 小于1000的数字三位数，100～999，共900个数字，2700位； // 定位区间 while ((long long) n >= (end - start)*bi...

#include <vector> class Solution { public: vector<vector<int> > result; vector<vector<int> > combinationSum2(vector<int> &num, int target) { if (num.empty()) return result; sort(num.begin(), num.end()); vector<int> tmp; back_tracking(num, tmp, 0, 0, target);...

#include <vector> class Solution { public: bool hasPath(vector<vector<char> >& matrix, string word) { if (matrix.empty()) return false; int rows = matrix.size(); int cols = matrix[0].size(); vector<vector<bool> > state(rows, vector<bool>(cols, false)); for (int i ...