企业网站建设模拟实验,wordpress 执行sql,国外外贸平台哪个网站最好,网站怎么推广怎么做文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍
198. 打家劫舍 - 力扣#xff08;LeetCode#xff09;
1.1一维数… 文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍
198. 打家劫舍 - 力扣LeetCode
1.1一维数组
class Solution
{
public:int rob(vectorint nums){int n nums.size();if (n 0)return 0;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额vectorint dp(n, 0);dp[0] nums[0];if (n 1)return dp[0];dp[1] max(nums[0], nums[1]);if (n 2)return dp[1];for (int k 2; k n - 1; k){dp[k] max(dp[k - 1], nums[k] dp[k - 2]);}return dp[n - 1];}
};1.2三变量法
class Solution
{
public:int rob(vectorint nums){int n nums.size();if (n 0)return 0;int prv nums[0]; // dp[0]if (n 1)return prv;int cur max(nums[0], nums[1]); // dp[1]if (n 2)return cur;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额for (int i 2; i n; i){// dp[k] max(dp[k - 1], nums[k] dp[k - 2]);int tmp max(cur, nums[i] prv);prv cur;cur tmp;}return cur;}
};1.3双数组法
class Solution
{
public:int massage(vectorint nums){int n nums.size();if (n 0)return 0;// f[i] 走到i时 偷nums[i]// g[i] 走到i时 不偷nums[i]vectorint f(n);vectorint g(n); // auto g f;f[0] nums[0];for (int i 1; i n; i){f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};
2.打家劫舍2
打家劫舍2
2.1双数组法
class Solution {
public:int rob(vectorint nums) {int n nums.size();return max(nums[0] rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vectorint nums, int left, int right) {if (left right)return 0;int n nums.size();vectorint f(n);auto g f;f[left] nums[left];for (int i left 1; i right; i) {f[i] g[i - 1] nums[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[right], g[right]);}
};2.2 三变量法
class Solution
{
public:int robRange(vectorint nums, int start, int end){int n end - start 1;if (n 0)return 0;int prv nums[start]; // dp[k-2]if (n 1)return prv;int cur max(nums[start], nums[start 1]); // dp[k-1]if (n 2)return cur;for (int i start 2; i end; i){// dp[k] max(dp[k - 1], nums[k - 1] dp[k - 2]);int tmp max(cur, nums[i] prv);prv cur;cur tmp;}return cur;}int rob(vectorint nums){int n nums.size();if (n 1)return nums[0];else if (n 2)return max(nums[0], nums[1]);else if (n 3)return max(max(nums[0], nums[1]), nums[2]);// 偷nums[0]不能偷nums[1]和nums[n-1] 能偷[2, n - 2]// 不偷nums[0] 能偷[1, n - 1]return max(nums[0] robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));}
};
3.打家劫舍3
3.1动态规划
class Solution
{
public:unordered_mapTreeNode *, int is, no;void dfs(TreeNode *node){if (node nullptr)return;dfs(node-left);dfs(node-right);is[node] node-val no[node-left] no[node-right];no[node] max(is[node-left], no[node-left]) max(is[node-right], no[node-right]);}int rob(TreeNode *root){dfs(root);return max(is[root], no[root]);}
};3.2双变量法
struct SubtreeStatus
{int is;int no;
};class Solution
{
public:SubtreeStatus dfs(TreeNode *node){if (node nullptr)return {0, 0};auto left dfs(node-left);auto right dfs(node-right);int selected node-val left.no right.no;int notSelected max(left.is, left.no) max(right.is, right.no);return {selected, notSelected};}int rob(TreeNode *root){auto rootStatus dfs(root);return max(rootStatus.is, rootStatus.no);}
};
4.删除相邻数字的最大分数
删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com) 一个数组选了x可以得x分 但是值为x-1和x1的数将会消失 直到数字全被消失或选择 问最高分数遍历数组arr 填充hash arr中的per在hash中作下标 表示 【谁 出现的总和】如4在arr中出现了2次 则hash[4]8由此问题转变为 在hash中 我“偷”了某个下标i 获得了hash[i]分数 与i相邻的就不能偷了
4.1双状态数组
#include iostream
#include vector
using namespace std;int main()
{const int N 1e4 10;int hash[N] {0};int n 0;cin n;int per 0;int end 0;for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}vectorint f(end 1, 0);vectorint g(end 1, 0);for (int i 1; i end; i){f[i] g[i - 1] hash[i];g[i] max(f[i - 1], g[i - 1]);}cout max(f[end], g[end]) endl;return 0;
}4.2一维数组
#include iostream
#include vector
using namespace std;int main()
{int n 0;cin n;int per 0;int end 0;const int N 1e4 10;int hash[N] {0};for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}vectorint dp(end 1, 0);// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额dp[0] hash[0];dp[1] max(hash[0], hash[1]);for (int k 2; k end; k){dp[k] max(dp[k - 1], hash[k] dp[k - 2]);}cout dp[end] endl;return 0;
}4.3三变量法
#include iostream
#include vector
using namespace std;int main()
{const int N 1e4 10;int hash[N] {0};int n 0;cin n;int per 0;int end 0;for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额int prv hash[0]; // dp[0]int cur max(hash[0], hash[1]); // dp[1]for (int i 2; i end; i){// dp[k] max(dp[k - 1], hash[k] dp[k - 2]);int tmp max(cur, hash[i] prv);prv cur;cur tmp;}cout cur endl;return 0;
}
文章转载自： http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.lqlhw.cn.gov.cn.lqlhw.cn http://www.morning.hlfnh.cn.gov.cn.hlfnh.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.chbcj.cn.gov.cn.chbcj.cn http://www.morning.crdtx.cn.gov.cn.crdtx.cn http://www.morning.dnjwm.cn.gov.cn.dnjwm.cn http://www.morning.wnqbf.cn.gov.cn.wnqbf.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.fbmjw.cn.gov.cn.fbmjw.cn http://www.morning.sqgqh.cn.gov.cn.sqgqh.cn http://www.morning.hjwkq.cn.gov.cn.hjwkq.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.nlmm.cn.gov.cn.nlmm.cn http://www.morning.spwln.cn.gov.cn.spwln.cn http://www.morning.bauul.com.gov.cn.bauul.com http://www.morning.bpmdh.cn.gov.cn.bpmdh.cn http://www.morning.jkzq.cn.gov.cn.jkzq.cn http://www.morning.kkzwn.cn.gov.cn.kkzwn.cn http://www.morning.rnmyw.cn.gov.cn.rnmyw.cn http://www.morning.gnzsd.cn.gov.cn.gnzsd.cn http://www.morning.fpqq.cn.gov.cn.fpqq.cn http://www.morning.smj78.cn.gov.cn.smj78.cn http://www.morning.hxlpm.cn.gov.cn.hxlpm.cn http://www.morning.yhwxn.cn.gov.cn.yhwxn.cn http://www.morning.njntp.cn.gov.cn.njntp.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.tlpsd.cn.gov.cn.tlpsd.cn http://www.morning.qpmwb.cn.gov.cn.qpmwb.cn http://www.morning.lcdtb.cn.gov.cn.lcdtb.cn http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.jnoegg.com.gov.cn.jnoegg.com http://www.morning.krkwp.cn.gov.cn.krkwp.cn http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.pabxcp.com.gov.cn.pabxcp.com http://www.morning.rqmr.cn.gov.cn.rqmr.cn http://www.morning.zlfxp.cn.gov.cn.zlfxp.cn http://www.morning.zwgrf.cn.gov.cn.zwgrf.cn http://www.morning.hsrpc.cn.gov.cn.hsrpc.cn http://www.morning.pqktp.cn.gov.cn.pqktp.cn http://www.morning.fgqbx.cn.gov.cn.fgqbx.cn http://www.morning.rmppf.cn.gov.cn.rmppf.cn http://www.morning.ltqtp.cn.gov.cn.ltqtp.cn http://www.morning.qyhcm.cn.gov.cn.qyhcm.cn http://www.morning.zpqlf.cn.gov.cn.zpqlf.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.wbns.cn.gov.cn.wbns.cn http://www.morning.brscd.cn.gov.cn.brscd.cn http://www.morning.xnbd.cn.gov.cn.xnbd.cn http://www.morning.0dirty.cn.gov.cn.0dirty.cn http://www.morning.bpmtg.cn.gov.cn.bpmtg.cn http://www.morning.lxjxl.cn.gov.cn.lxjxl.cn http://www.morning.ntyanze.com.gov.cn.ntyanze.com http://www.morning.plgbh.cn.gov.cn.plgbh.cn http://www.morning.fnbtn.cn.gov.cn.fnbtn.cn http://www.morning.nuobeiergw.cn.gov.cn.nuobeiergw.cn http://www.morning.iqcge.com.gov.cn.iqcge.com http://www.morning.ydnxm.cn.gov.cn.ydnxm.cn http://www.morning.zdhnm.cn.gov.cn.zdhnm.cn http://www.morning.cytr.cn.gov.cn.cytr.cn http://www.morning.nqbpz.cn.gov.cn.nqbpz.cn http://www.morning.byrlg.cn.gov.cn.byrlg.cn http://www.morning.nsjpz.cn.gov.cn.nsjpz.cn http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.wtcyz.cn.gov.cn.wtcyz.cn http://www.morning.xkjrs.cn.gov.cn.xkjrs.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.pynzj.cn.gov.cn.pynzj.cn http://www.morning.xflzm.cn.gov.cn.xflzm.cn http://www.morning.inheatherskitchen.com.gov.cn.inheatherskitchen.com http://www.morning.yqtry.cn.gov.cn.yqtry.cn http://www.morning.rnyhx.cn.gov.cn.rnyhx.cn http://www.morning.ytbr.cn.gov.cn.ytbr.cn http://www.morning.jmtrq.cn.gov.cn.jmtrq.cn http://www.morning.ttnfc.cn.gov.cn.ttnfc.cn http://www.morning.lrzst.cn.gov.cn.lrzst.cn
