2.5#
在排序数组中查找元素的第一个和最后一个位置 (掌握程度：中)#
二分两次，但是边界处理有点没记住
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = search(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1};
}
int end = search(nums, target + 1) - 1;
return {start, end};
}
最小栈
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};最小栈 (掌握程度：高)#
维护双栈，一个存元素，一个存当前栈长度内的最小值，栈顶的就是最小的那个
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (st *MinStack) Push(val int) {
st.stack = append(st.stack, val)
if len(st.minStack) > 0 {
top := st.minStack[len(st.minStack) - 1]
st.minStack = append(st.minStack, min(top, val))
} else {
st.minStack = append(st.minStack, val)
}
}
func (st *MinStack) Pop() {
st.stack = st.stack[:len(st.stack) - 1]
st.minStack = st.minStack[:len(st.minStack) - 1]
}
func (st *MinStack) Top() int {
return st.stack[len(st.stack) - 1]
}
func (st *MinStack) GetMin() int {
return st.minStack[len(st.minStack) - 1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/求根节点到叶节点数字之和 (掌握程度：中)#
不是很难的树的题，唯一难的是要想到到了叶节点不能继续走了，要返回
/**
* 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:
int dfs(TreeNode* node, int sum) {
if (node == nullptr) return 0;
sum = sum * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) {
return sum;
}
int left = dfs(node->left, sum);
int right = dfs(node->right, sum);
return left + right;
}
int sumNumbers(TreeNode* root) {
return dfs(root, 0);
}
};对称二叉树 (掌握程度：高)#
刷了很多次又是简单题
/**
* 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:
bool isSame(TreeNode* node1, TreeNode* node2) {
if (node1 == nullptr || node2 == nullptr) return node1 == node2;
return isSame(node1->left, node2->right) && isSame(node1->right, node2->left) && node1->val == node2->val;
}
bool isSymmetric(TreeNode* root) {
return isSame(root->left, root->right);
}
};字符串解码 (掌握程度：中)#
之前面试日常实习的时候写过，现在有点记不太清了，中间的部分处理
class Solution {
public:
string decodeString(string s) {
stack<int> numStack;
stack<string> charStack;
int num = 0;
string ans = "";
int n = s.size();
for (int i = 0; i < n; i++) {
if (isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
} else if (s[i] == '[') {
numStack.push(num);
charStack.push(ans);
ans = "";
num = 0;
} else if (s[i] == ']') {
int times = numStack.top();
numStack.pop();
string preStr = charStack.top();
charStack.pop();
string temp = "";
for (int i = 0; i < times; i++) {
temp += ans;
}
ans = preStr + temp;
} else {
ans += s[i];
}
}
return ans;
}
};组合总和 (掌握程度： 中)#
回溯，选与不选但是可以重复选，所以i可以保持不变的
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& candidates, int target, int i, int n) {
if (i == n || target < 0) return ;
if (target == 0) {
ans.push_back(path);
return;
}
dfs(candidates, target, i + 1, n);
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i, n);
path.pop_back();
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0, candidates.size());
return ans;
}
};最小路径和 (掌握程度：中)#
多维动态规划，不是很难，也可能是做了很多遍，但是初始化还是写错了，应该初始化成最大值，限制范围
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp (m + 1, vector<int> (n + 1, INT_MAX));
dp[0][1] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
}
}
return dp[m][n];
}
};用 Rand7() 实现 Rand10() (掌握程度：中)#
通用解法：等概率+ 拒绝部分不等概率的
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
int rand10() {
int x;
do {
x = (rand7() - 1) * 7 + rand7();
} while (x > 40);
return 1 + (x - 1) % 10;
}
};二叉树的最大深度 (掌握程度：中)#
有点不太熟练的二叉树递归
/**
* 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:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return max(left, right) + 1;
}
};最长连续序列 (掌握程度：中)#
中间的循环，没有判断上一个值是否存在，存在就不需要重新开始，剪枝了，要不然会超时
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set(nums.begin(), nums.end());
int ans = 0;
for (int num : set) {
if (!set.count(num - 1)) {
int curN = num;
int curL = 1;
while (set.count(curN + 1)) {
curL++;
curN++;
}
ans = max(ans, curL);
}
}
return ans;
}
};