C++刷leetcode（打家劫舍系列题3道）【动态规划】

糖逗 · 发表于 2020-4-14 13:15:27

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由糖逗于 2020-5-8 17:33 编辑

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
  偷窃到的最高金额 = 2 + 9 + 1 = 12 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int>& input){
int len = input.size();
if(len == 0) return 0;
vector<int> temp (len+1, 0);
temp[0] = 0;
temp[1] = input[0];
for(int i = 2; i < len+1; i++){
temp[i] = max(temp[i-1] , temp[i-2] + input[i-1]);
}
return temp[len];
}
int main(void){
vector<int> input;
int number;
while(cin >> number){
input.push_back(number);
}
cout << solution(input) << endl;
return 0;
}

复制代码

参考链接：https://leetcode-cn.com/problems ... she-by-guanpengchn/

糖逗 · 发表于 2020-4-14 13:59:10

题目：213. 打家劫舍 II
题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
  偷窃到的最高金额 = 1 + 3 = 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

#include <iostream>
#include <vector>
using namespace std;
int dp(vector<int>&input){
int len = input.size();
if(len == 0) return 0;
if(len == 1) return input[0];
vector<int> temp(len+1, 0);
temp[1] = input[0];
for(int i= 2; i < len + 1; i++){
temp[i] = max(temp[i-1], temp[i-2] + input[i-1]);
}
return temp[len];
}
int solution(vector<int>& input){
if(input.size() == 0) return 0;
if(input.size() == 1) return input[0];
//三种情况
vector<vector<int> > temp;
vector<int> temp1(input.begin() + 1, input.end() - 1);
vector<int> temp2(input.begin(), input.end()-1);
vector<int> temp3(input.begin()+1, input.end());
temp.push_back(temp1);
temp.push_back(temp2);
temp.push_back(temp3);
int res = 0;
for(auto c : temp){
res = max(res, dp(c));
}
return res;
}
int main(void){
vector<int> input;
int number;
while(cin >> number){
input.push_back(number);
}
cout << solution(input) << endl;
return 0;
}

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... i-gui-hua-by-happy/

糖逗 · 发表于 2020-4-14 14:52:22

题目：337. 打家劫舍 III
题目描述：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
  3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){
}
};
TreeNode* CreateTree(vector<int> input){
TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
res[i].val = input[i];
res[i].left = NULL;
res[i].right = NULL;
}
for(int i= 0; i < input.size(); i++){
if(2*i+1 < input.size()){
res[i].left = &res[2*i+1];
}
if(2*i+2 < input.size()){
res[i].right = &res[2*i+2];
}
}
return res;
}
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res[depth][insert] = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res[i].size();j++){
if(res[i][j] == 0){
cout << " ";
}
else{
cout << res[i][j];
}
}
cout << endl;
}
cout << "------------------" << endl;
}
vector<int> dp(TreeNode* root){
vector<int> res(2, 0);
if(root == NULL) return res;
vector<int> left = dp(root -> left);
vector<int> right = dp(root -> right);
res[1] += root -> val + left[0] + right[0];
res[0] += max(right[0], right[1]) + max(left[0], left[1]);
return res;
}
int solution(TreeNode*root){
vector<int> res = dp(root);
return max(res[0], res[1]);
}
int main(void){
vector<int> input1;
cout << "send numbers for the tree" << endl;
int number1;
while(cin >> number1){
input1.push_back(number1);
}
TreeNode* root = CreateTree(input1);
PrintTree(root);
cout << solution(root) << endl;
return 0;
}

复制代码

注意事项：
1.树状的动态规划。
2.参考链接：https://leetcode-cn.com/problems ... ua-wen-ti-by-corch/
3.res中有两个int，第一个int记录不选该节点的情况下最大取值，int记录选该节点的情况下的最大取值。

账号		自动登录	找回密码
密码			立即注册

[技术交流] C++刷leetcode（打家劫舍系列题3道）【动态规划】

马上注册，结交更多好友，享用更多功能^_^

评分

本帖被以下淘专辑推荐:

浏览过的版块