代码随想录算法训练营Day48 | 198.打家劫舍，213.打家劫舍II，337.打家劫舍III | Day 20 复习

198.打家劫舍

文章链接  |  题目链接  |  视频链接

C++解法

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp (nums.size(), 0);if (nums.size() == 0){return 0;}if (nums.size() == 1){return nums[0];}dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++){dp[i] = max(dp[i-1], dp[i-2]+nums[i]);}return dp[nums.size()-1];}
};

Python解法

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:return 0if len(nums) == 1:return nums[0]dp = [0] * len(nums)dp[0] = nums[0]dp[1] = max(dp[0], nums[1])for i in range(2, len(nums)):dp[i] = max(dp[i-1], dp[i-2]+nums[i])return dp[len(nums)-1]

213.打家劫舍II

文章链接  |  题目链接  |  视频链接

C++解法

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size()-2);int result2 = robRange(nums, 1, nums.size()-1);return max(result1, result2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp (nums.size(), 0);dp[start] = nums[start];dp[start+1] = max(dp[start], nums[start+1]);for (int i = start+2; i <= end; i++){dp[i] = max(dp[i-1], dp[i-2]+nums[i]);}return dp[end];}
};

Python解法

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:return 0if len(nums) == 1:return nums[0]result1 = self.robRange(nums, 0, len(nums) - 2)result2 = self.robRange(nums, 1, len(nums) - 1)return max(result1, result2)def robRange(self, nums: List[int], start: int, end: int) -> int:if end == start:return nums[start]prev_max = nums[start]curr_max = max(nums[start], nums[start + 1])for i in range(start + 2, end + 1):temp = curr_maxcurr_max = max(prev_max + nums[i], curr_max)prev_max = tempreturn curr_max

337.打家劫舍III

文章链接  |  题目链接  |  视频链接

C++解法

/*** 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 rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* curr){if (curr == nullptr) return vector<int> {0, 0};vector<int> left = robTree(curr->left);vector<int> right = robTree(curr->right);int val1 = curr->val + left[0] + right[0];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

Python解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def rob(self, root: Optional[TreeNode]) -> int:dp = self.traversal(root)return max(dp)def traversal(self, curr: Optional[TreeNode]) -> list[int]:if curr is None:return (0, 0)left = self.traversal(curr.left)right = self.traversal(curr.right)val1 = curr.val + left[0] + right[0]val2 = max(left) + max(right)return (val2, val1)

Day 20 复习

654.最大二叉树 

/*** 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:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if (nums.empty()) {return nullptr;}auto it = max_element(nums.begin(), nums.end());TreeNode* root = new TreeNode(*it);vector<int> left(nums.begin(), it);vector<int> right(it + 1, nums.end());root->left = constructMaximumBinaryTree(left);root->right = constructMaximumBinaryTree(right);return root;}
};

617.合并二叉树 

/*** 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:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == NULL && root2 == NULL){return nullptr;} else if (root1 == NULL){return root2;} else if (root2 == NULL){return root1;} else {TreeNode* root = new TreeNode(root1->val+root2->val);root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;}}
};

700.二叉搜索树中的搜索 

/*** 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:TreeNode* searchBST(TreeNode* root, int val) {while (root){if (root->val == val){return root;} else if (root->val > val){root = root->left;} else {root = root->right;}}return root;}
};

98.验证二叉搜索树 

/*** 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:TreeNode* pre = NULL;bool isValidBST(TreeNode* root) {if (root == NULL){return true;}bool left = isValidBST(root->left);if (pre != NULL && pre->val >= root->val) return false;pre = root;bool right = isValidBST(root->right);return left && right;}
};