前言
一个本硕双非的小菜鸡,备战24年秋招,计划刷完hot100和剑指Offer的刷题计划,加油!
根据要求,每一道题都要写出两种以上的解题技巧。
一、198. 打家劫舍(HOT100)
198. 打家劫舍
Note:动态规划解题
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1) return nums[0];
//1.确定dp数组
//能偷取的最高金额
vector<int> dp(len);
//2.确定递推公式
//dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
//3.确定dp数组初始化
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
//4.确定遍历顺序
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
//5.确定dp数组
return dp[nums.size() - 1];
}
};
Note:设置两个变量,分别对数组的奇数和偶数元素求和。当这一段的最优解没有另一边好时,就复制对面的最优解过来,最后比较这两个和谁更大,谁就是最优解。
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1) return nums[0];
int oddNums = 0;
int EvenNums = 0;
for (int i = 0; i < len; i++) {
if (i % 2 == 0) {
EvenNums += nums[i];
EvenNums = max(EvenNums, oddNums);
} else {
oddNums += nums[i];
oddNums = max(EvenNums, oddNums);
}
}
return max(EvenNums, oddNums);
}
};
二、18. 重建二叉树(剑指Offer)
Note:递归法,简单来说就是寻找切割点,前序遍历中顺序为根左右,中序遍历顺序为左根右。所以在中序遍历中根据前序遍历的根节点进行切割,左边的就是左子树,右边的就是右子树,然后递归的进行构造。
/**
* 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 {
private:
TreeNode* traversal (vector<int>& preorder, int preorderBegin, int preorderEnd, vector<int>& inorder, int inorderBegin, int inorderEnd) {
//1.停止条件
if (preorderBegin == preorderEnd) return NULL;
//2.寻找当前中间节点,即是前序遍历头
int rootValue = preorder[preorderBegin];
TreeNode* root = new TreeNode(rootValue);
//叶子节点
if (preorderEnd - preorderBegin == 1) return root;
//3.找切割点
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
//切割中序遍历
//中序遍历左区间
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
//中序遍历右区间
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
//切割前序遍历
//前序遍历左区间
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;
//前序遍历右区间
int rightPreorderBegin = preorderBegin + 1 + delimiterIndex - inorderBegin;
int rightPreorderEnd = preorderEnd;
root->left = traversal(preorder, leftPreorderBegin, leftPreorderEnd, inorder, leftInorderBegin, leftInorderEnd);
root->right = traversal(preorder, rightPreorderBegin, rightPreorderEnd, inorder, rightInorderBegin,rightInorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == NULL || inorder.size() == NULL) return NULL;
return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());
}
};
Note:迭代法。不太好理解,推荐画图试试。
用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点(前序遍历的第一个节点),指针指向中序遍历的第一个节点;
依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点,那么不断地弹出栈顶节点并向右移动 index,并将当前节点作为最后一个弹出的节点的右儿子;如果 index 和栈顶节点不同,将当前节点作为栈顶节点的左儿子;
无论是哪一种情况,最后都将当前的节点入栈。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (!preorder.size()) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> stk;
stk.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.size(); ++i) {
int preorderVal = preorder[i];
TreeNode* node = stk.top();
if (node->val != inorder[inorderIndex]) {
node->left = new TreeNode(preorderVal);
stk.push(node->left);
}
else {
while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
node = stk.top();
stk.pop();
++inorderIndex;
}
node->right = new TreeNode(preorderVal);
stk.push(node->right);
}
}
return root;
}
};
总结
祝大家都能学有所成,找到一份好工作!