938. 二叉搜索树的范围和
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
int sum = 0;
stack<TreeNode*> Sta;
while(!Sta.empty() || root) {
while(root) {
Sta.push(root);
root = root->left;
}
root = Sta.top();
Sta.pop();
if(root->val >= low && root->val <=high) {
sum += root->val;
}
if(root->val > high)
break;
root = root->right;
}
return sum;
}
};1011. 在 D 天内送达包裹的能力
class Solution {
public:
bool test(vector<int>& weights, int D, int mid) {
int count = 0;
for(int i = 0, sum = 0; i < weights.size(); count++, sum = 0) {
while(i < weights.size() && sum + weights[i] <= mid) {
sum += weights[i];
++i;
}
}
return count <= D;
}
int shipWithinDays(vector<int>& weights, int D) {
int max = -1, sum = 0;
for(int i = 0; i < weights.size(); ++i) {
sum += weights[i];
if(max < weights[i])
max = weights[i];
}
int l = max, r = sum;
while(l < r) {
int mid = l + (r - l) / 2;
if(test(weights, D, mid))
r = mid;
else
l = mid + 1;
}
return r;
}
};368. 最大整除子集
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> f(n, 0);
vector<int> g(n ,0);
for(int i = 0; i < n; ++i) {
f[i] = 1;
g[i] = i;
for(int j = 0; j < i; ++j) {
if(nums[i] % nums[j] == 0) {
if(f[j] + 1 > f[i]) {
f[i] = f[j] + 1;
g[i] = j;
}
}
}
}
int max = -1, idx = -1;
for(int i = 0; i < n; ++i) {
if(f[i] > max) {
max = f[i];
idx = i;
}
}
vector<int> ans;
while(ans.size() != max) {
ans.push_back(nums[idx]);;
idx = g[idx];
}
return ans;
}
};91. 解码方法
字符串的动态规划
对于每一个字符要考虑两个情况：
- 该字符本身能否算作转换为一个数字？
- 该字符和前一个字符能否一起转换为一个数字？
dp数组
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
s = " " + s;
vector<int> f(n + 1, 0);
f[0] = 1;
for(int i = 1; i <= n; ++i) {
int a = s[i] - '0';
int b = (s[i - 1] - '0') * 10 + s[i] - '0';
if(a >= 1 && a <= 9)
f[i] = f[i - 1];
if(b >= 10 && b <= 26)
f[i] += f[i - 2];
}
return f[n];
}
};滚动数组
class Solution {
public:
// 使用滚动数组，节约空间
int numDecodings(string s) {
int n = s.size();
s = " " + s;
vector<int> f(3, 0);
f[0] = 1;
for(int i = 1; i <= n; ++i) {
f[i % 3] = 0; // 到第i个元素时，该f[i % 3]应该初始化为0.
int a = s[i] - '0';
int b = (s[i - 1] - '0') * 10 + s[i] - '0';
if(a >= 1 && a <= 9)
f[i % 3] = f[(i - 1) % 3];
if(b >= 10 && b <= 26)
f[i % 3] += f[(i - 2) % 3];
}
return f[n % 3];
}
};28. 实现 strStr()
class Solution {
int n, m;
public int strStr(String haystack, String needle) {
n = haystack.length();
m = needle.length();
if(m == 0)
return 0;
return KMP(haystack.toCharArray(), needle.toCharArray());
}
public int KMP(char[] text, char[] pattern) {
int [] match = buildMatch(pattern);
int s = 0, p = 0;
while(s < n && p < m) {
if(text[s] == pattern[p]) {
s++;
p++;
} else {
if(p == 0) {
s++;
} else {
p = match[p - 1] + 1;
}
}
}
return p == m ? (s - m) : -1;
}
public int[] buildMatch(char[] pattern) {
int[] match = new int[m];
match[0] = -1;
int pre;
for(int j = 1; j < m ; ++j) {
pre = match[j - 1];
while(pre >= 0 && pattern[pre + 1] != pattern[j]) {
pre = match[pre];
}
if(pattern[pre + 1] == pattern[j]) {
match[j] = pre + 1;
} else {
match[j] = -1;
}
}
return match;
}
}220. 存在重复元素 III
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
set<int> rec;
for (int i = 0; i < n; i++) {
auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);
if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
return true;
}
rec.insert(nums[i]);
if (i >= k) {
rec.erase(nums[i - k]);
}
}
return false;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。198. 打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0)
return 0;
else if(n == 1)
return nums[0];
else if(n == 2)
return max(nums[0], nums[1]);
int first = nums[0], second = max(nums[0], nums[1]);
for(int i = 2; i < n; ++i) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
};213. 打家劫舍 II
动态规划 根据题意 不能偷窃相邻的房屋，因此要特别处理首尾两个屋子，所以可以先计算出(0,n-2)和(1,n-1)区间的最优解。再选择出最佳答案。
class Solution {
public:
int robRange(vector<int>& nums, int l, int r) {
int first = nums[l], second = max(nums[l], nums[l + 1]);
for(int i = l + 2; i <= r; ++i) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1)
return nums[0];
else if(n == 2)
return max(nums[0], nums[1]);
else
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
};
783. 二叉搜索树节点最小距离
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> A;
void inorder(TreeNode* root) {
if(root->left)
inorder(root->left);
A.push_back(root->val);
if(root->right)
inorder(root->right);
}
int minDiffInBST(TreeNode* root) {
inorder(root);
int minX = INT_MAX;
for(int i = 1; i < A.size(); ++i) {
minX = min(minX, A[i] - A[i - 1]);
}
return minX;
}
};179. 最大数
题解推理出来的
class Solution {
public:
string largestNumber(vector<int> &nums) {
sort(nums.begin(), nums.end(), [](const int &x, const int &y) {
long sx = 10, sy = 10;
while (sx <= x) {
sx *= 10;
}
while (sy <= y) {
sy *= 10;
}
return sy * x + y > sx * y + x;
});
if (nums[0] == 0) {
return "0";
}
string ret;
for (int &x : nums) {
ret += to_string(x);
}
return ret;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/largest-number/solution/zui-da-shu-by-leetcode-solution-sid5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。264. 丑数 II
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n + 1);
int p2 = 1, p3 = 1, p5 = 1;
dp[1] = 1;
for(int i = 2; i <= n; ++i) {
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);
if(dp[i] == num2)
p2++;
if(dp[i] == num3)
p3++;
if(dp[i] == num5)
p5++;
}
return dp[n];
}
};263. 丑数
class Solution {
public:
bool isUgly(int n) {
if(n == 0)
return false;
if(n == 1)
return true;
if(n % 2 == 0)
return isUgly(n / 2);
if(n % 3 == 0)
return isUgly(n / 3);
if(n % 5 == 0)
return isUgly(n / 5);
return false;
}
};154. 寻找旋转排序数组中的最小值 II
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int mid = l + (r - l) / 2;
if(nums[mid] < nums[r])
r = mid;
else if(nums[mid] > nums[r])
l = mid + 1;
else
r--;
}
return nums[l];
}
};153. 寻找旋转排序数组中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = n - 1;
while(l < r) {
int mid = l + (r - l) / 2;
if(nums[mid] < nums[r]) {
r = mid;
} else if(nums[mid] >= nums[l]) {
l = mid + 1;
}
}
return nums[l];
}
};
81. 搜索旋转排序数组 II
因为数组有重复元素，所以无法找到一个正确的划分点,所以应该在33. 搜索旋转排序数组代码基础上增加一个删除重复元素的操作。而且判定nums[mid]在哪个区间的条件不再是根据数组第一个元素确定，而是由nums[l]和nums[mid]的大小关系确定的。
if(nums[l] == nums[mid] && nums[mid] == nums[r]) {
l++;
r--;
} class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size();
if(!n || n == 1 && nums[0] != target)
return false;
int l = 0;
int r = n - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(nums[mid] == target)
return true;
if(nums[l] == nums[mid] && nums[mid] == nums[r]) {
l++;
r--;
} else if(nums[l] <= nums[mid]) {
if(nums[l] <= target && target <nums[mid])
r = mid - 1;
else
l = mid + 1;
} else {
if(nums[mid] < target && target <= nums[n - 1])
l = mid + 1;
else
r = r - 1;
}
}
return false;
}
// 脑子一热系列 一顿敲码猛如虎，一看结果0/5.
// bool search(vector<int>& nums, int target) {
// bool flag = false;
// int k = 0;
// for(int i = 1; i < nums.size() - 1; ++i) {
// if(nums[i - 1] > nums[i]) {
// k = i;
// break;
// }
// }
// if(BinarySearch(nums, target, 0, k - 1) || (BinarySearch(nums, target, k, nums.size() - 1)))
// return true;
// else
// return false;
// }
// bool BinarySearch(vector<int>& nums, int target, int l, int r) {
// int mid = l + (r - l) / 2;
// while(l < r) {
// if(nums[mid] < target)
// l = mid + 1;
// else if(nums[mid] > target)
// r = mid - 1;
// else
// return true;
// }
// return false;
// }
};33. 搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if(!n || n == 1 && nums[0] != target)
return -1;
int l = 0;
int r = n - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(nums[mid] == target)
return mid;
if(nums[0] <= nums[mid]) {
if(nums[0] <= target && target <nums[mid])
r = mid - 1;
else
l = mid + 1;
} else {
if(nums[mid] < target && target <= nums[n - 1])
l = mid + 1;
else
r = r - 1;
}
}
return -1;
}
};80. 删除有序数组中的重复项 II
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return process(nums, 2);
}
int process(vector<int>& nums, int k) {
int c = 0;
for(auto x : nums) {
if(c < k || nums[c - k] != x)
nums[c++] = x;
}
return c;
}
};88. 合并两个有序数组
根据题意nums1的长度等于合并后的数组总长度，应不需要再额外借数组来存放中间数据，直接利用nums1数组后面的空闲位置即可。
双指针解法，从后面开始扫描
因为从后面开始扫描的原因且是再nums1这个数组本身上进行操作，while循环结束时m == -1 or n == -1;
当m == -1时，意味着nums2数组剩下的数都比新的nums1中已经有序的元素都要小，所以直接将nums2遍历完复制到nums1前面。
当n == -1时，意味着while循环还没遍历过nums1的一些元素，但是因为这个while的修改操作主要是在nums1数组上进行的，所以无需再做任何操作。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// int i = m + n - 1;
// m--;
// n--;
// 更简洁的编写
int i = m-- + n-- -1;
while(m >= 0 && n >= 0) {
nums1[i--] = nums1[m] >= nums2[n] ? nums1[m--] : nums2[n--];
}
// while(m >= 0)
// nums1[i--] = nums1[m--];
while(n >= 0)
nums1[i--] = nums2[n--];
}
};781. 森林中的兔子
先将answer数组排序，ans加入每一种颜色兔子的总个数，然后跳过有相同颜色的兔子，直到遇到不同颜色的兔子，这样就能满足上面描述的两种情况。
class Solution {
public:
int numRabbits(vector<int>& answers) {
sort(answers.begin(), answers.end());
int n = answers.size();
int ans = 0;
for(int i = 0; i < n; i++) {
int curT = answers[i];
ans += curT + 1;
//跳过有相同curT值的兔子
int k = curT;
while(k-- && i + 1 < n && answers[i] == answers[i + 1])
i++;
}
return ans;
}
};1143. 最长公共子序列
经典动态规划问题
列出状态转移方程就行
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] Matrix = new int[m + 1][n + 1];
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(text1.charAt(i - 1) == text2.charAt(j - 1))
Matrix[i][j] = Matrix[i - 1][j - 1] +1;
else
Matrix[i][j] = Math.max(Matrix[i - 1][j], Matrix[i][j - 1]);
}
}
return Matrix[m][n];
}
}class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m + 1,vector<int>(n + 1));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(text1[i - 1] == text2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
}
}
return dp[m][n];
}
};面试题 17.21. 直方图的水量
class Solution {
public:
int trap(vector<int>& height) {
stack<int> Sta;
int n = height.size();
int ans = 0;
for(int i = 0; i < n; ++i) {
while(!Sta.empty() && height[Sta.top()] < height[i])
{
int cur = Sta.top();
Sta.pop();
if(Sta.empty())
continue;
int w = i - Sta.top() + (1 - 2);
int h = min(height[i],height[Sta.top()]) - height[cur];
ans += w * h;
}
Sta.push(i);
}
return ans;
}
};1006. 笨阶乘
class Solution {
public:
int clumsy(int N) {
stack<int> Sta;
Sta.push(N);
N--;
int i = 1;
while(N) {
if(i % 4 == 1) {
Sta.top() *= N;
}
else if(i % 4 == 2) {
Sta.top() /= N;
}
else if(i % 4 == 3) {
Sta.push(N);
}
else if(i % 4 == 0) {
Sta.push(-N);
}
i++;
N--;
}
int ans = 0;
while(!Sta.empty()) {
ans += Sta.top();
Sta.pop();
}
return ans;
}
};class Solution {
public int clumsy(int N) {
if (N == 1) {
return 1;
} else if (N == 2) {
return 2;
} else if (N == 3) {
return 6;
} else if (N == 4) {
return 7;
}
if (N % 4 == 0) {
return N + 1;
} else if (N % 4 <= 2) {
return N + 2;
} else {
return N - 1;
}
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/clumsy-factorial/solution/ben-jie-cheng-by-leetcode-solution-deh2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。