2.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 widthOfBinaryTree(TreeNode* root) {
typedef unsigned long long ull;
if (root == nullptr) return 0;
queue<pair<TreeNode*, ull>> q;
q.push({root, 1});
ull ans = 0;
while (!q.empty()) {
int n = q.size();
ull left = q.front().second, right = left;
while (n--) {
auto [node, pos] = q.front();
q.pop();
right = pos; // 更新当前的最右编号
if (node->left != nullptr)
q.push({node->left, pos * 2});
if (node->right != nullptr)
q.push({node->right, pos * 2 + 1});
}
ans = max(ans, right - left + 1);
}
return ans;
}
};二叉树的直径 (掌握程度：高)#
简单题，不过这个dfs的处理有点不太一样
/**
* 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 ans = 0;
int dfs(TreeNode* node) {
if (node == nullptr) return 0;
int left = dfs(node->left);
int right = dfs(node->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
};寻找峰值 (掌握程度：中)#
另类的二分，循环条件和变得值跟其他的二分不太一样，其他的一般都是 while(left <= right) 然后 left = mid + 1 right = mid - 1的，这个却是 left = mid + 1 right = mid，可能是因为他对mid值不敏感吧
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (right + left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};最大数 (掌握程度：低)#
一样是一道我基本上没看到过其他公司出过的另类题
class Solution {
public:
string largestNumber(vector<int> &nums) {
sort(nums.begin(), nums.end(), [](const int &x, const int &y) {
return to_string(x) + to_string(y) > to_string(y) + to_string(x);
});
if (nums[0] == 0) {
return "0";
}
string ret;
for (int &x : nums) {
ret += to_string(x);
}
return ret;
}
};乘积最大子数组 (掌握程度：低)#
只有一点印象，记得是要两个dp的，但是不会写
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> dpMax(n), dpMin(n);
dpMax[0] = dpMin[0] = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] >= 0) {
dpMax[i] = max(nums[i], dpMax[i - 1] * nums[i]);
dpMin[i] = min(nums[i], dpMin[i - 1] * nums[i]);
} else {
dpMax[i] = max(nums[i], dpMin[i - 1] * nums[i]);
dpMin[i] = min(nums[i], dpMax[i - 1] * nums[i]);
}
}
return *max_element(dpMax.begin(), dpMax.end());
}
};路径总和 II (掌握程度：中)#
一个回溯和二叉树题，如果他不是要所有的路径，就是一个二叉树的题
/**
* 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<vector<int>> ans;
vector<int> path;
void dfs(TreeNode* node, int targetSum) {
if (node == nullptr) return;
path.push_back(node->val);
targetSum -= node->val;
if (node->left == nullptr && node->right == nullptr && targetSum == 0) {
ans.push_back(path);
}
dfs(node->left, targetSum);
dfs(node->right, targetSum);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root, targetSum);
return ans;
}
};不同路径 (掌握程度：高)#
写的较为熟练的一道多维动态规划了
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
dp[0][1] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1];
}
}
return dp[m][n];
}
};和为 K 的子数组 (掌握程度：低)#
hot100的一道题，前缀和 + 哈希表之前就不太会写
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> map;
map[0] = 1;
int sum = 0, ans = 0;
for (int num : nums) {
sum += num;
if (map.count(sum - k)) {
ans += map[sum - k];
}
map[sum]++;
}
return ans;
}
};打家劫舍 (掌握程度：中)#
搞混了以为是二，那个围成一圈的，一就是比较简单了
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 2);
for (int i = 0; i < n; i++) {
dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]);
}
return dp[n + 1];
}
};路径总和 (掌握程度：高)#
非常简单的一道题，是上面的路径总和的退化版，不仅不需要输出路径只需要展示存不存在一条链路就行
/**
* 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 hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return false;
// 到达叶子节点
targetSum -= root->val;
if (root->left == nullptr && root->right == nullptr) {
return targetSum == 0;
}
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
};