西安网站制作工程师,辅助购卡网站怎么做,wordpress媒体库远程上传,350做网站深圳专题10#xff1a;动态规划
题目509#xff1a;斐波那契数#xff08;NO#xff09;
解题思路#xff1a;动态五部曲
动态五部曲#xff1a;这里我们用一个一维数组来保存递归的结果 确定dp数组以及下标的含义 dp[i]的定义为#xff1a;第i个数的斐波那契数值是dp[i]…专题10动态规划
题目509斐波那契数NO
解题思路动态五部曲
动态五部曲这里我们用一个一维数组来保存递归的结果 确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数值是dp[i] 确定递推公式 这道题已经把递推公式直接给了状体转移方程dp[i]dp[i-1]dp[i-2]; dp数组如何初始化 这题题目把如何初始化也直接给了 dp[0]0; dp[1]1; 确定遍历顺序 从递归公式**dp[i]dp[i-1]dp[i-2]**中可以看出dp[i]是依赖dp[i-1]和dp[i-2],那么遍历顺序一定是从前到后遍历的。 列举推导dp数组 按照这个递推公式dp[i]dp[i-1]dp[i-2]我们来推导一下当N为10的时候dp数组应该是如下的数列0 1 1 2 3 5 8 13 21 34 55 如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是否一致的。
题目
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。
class Solution {
public:int fib(int n) {if(n1){return n;}vectorintdp(n1);dp[0]0;dp[1]1;//这里实际的个数会是n1for(int i2;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
};题目70爬楼梯NO
解题思路依旧是动规5步曲。
确定dp数组以及下标的含义
dp[i]表示爬到第i层楼梯有dp[i]种方法
这里来推导一下dp[1]1,dp[2]2;dp[3]3dp[4]5;这样递推又会得到和上题一样的答案
确定递推公式
dp[i]dp[i-1]dp[i-2]
dp数组如何初始化
因为dp[0]是没有任何意义的所以不用对其进行初始化只需要知道dp[1]1;dp[2]2就可以了
确定遍历顺序
从递推公式dp[i]dp[i-1]dp[i-2]可以看出遍历顺序一定是从前往后遍历的
列举dp数组
上面列举过了。
class Solution {
public:int climbStairs(int n) {if(n1) return n;vectorintdp(n1);dp[1]1;dp[2]2;for(int i3;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
};疑惑点为什么可以用dp[i]dp[i-1]dp[i-2]作为到达i层的方法数呢
具体解释如下
到达第 i 层楼梯的最后一步 想要到达第 i 层楼梯最后一步只有两种可能
从第 i-1 层爬一步。从第 i-2 层爬两步。
方法数的累加
从第 i-1 层爬一步方法数为 dp[i-1]因为到达第 i-1 层有 dp[i-1] 种方法。从第 i-2 层爬两步方法数为 dp[i-2]因为到达第 i-2 层有 dp[i-2] 种方法。
总方法数 由于最后一步只有这两种可能所以到达第 i 层楼梯的总方法数就是这两种情况的方法数之和即 dp[i] dp[i-1] dp[i-2]。
简单来说dp[i] 就是把所有到达第 i 层楼梯的最后一步可能情况的方法数加起来。
举个例子
假设我们要爬到第 4 层楼梯。
到达第 4 层的最后一步可以是
从第 3 层爬一步方法数为 dp[3]。从第 2 层爬两步方法数为 dp[2]。
因此到达第 4 层的总方法数为 dp[4] dp[3] dp[2]。
总结
dp[i] dp[i-1] dp[i-2] 这个公式体现了爬楼梯问题的递推关系它将到达第 i 层楼梯的方法数分解为两种最后一步可能情况的方法数之和从而简化了问题的求解过程。
题目746使用最小花费爬楼梯YES
解题思路动规5步曲
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 确定dp数组的含义 这里的dp[i]表示到达第i层所需要的最少的花费。 确定递推公式 dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]); 如何初始化dp数组 根据题目就可以知道dp[0]0 ,dp[1]0; 确定遍历的顺序 这里毫无疑问必然是从前往后因为dp[i]需要用前面的两个数才能确定。 列举出dp数组 这里的本质意义是方便调试但是这里比较动态不好推导不用列举也行。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {/*这题依旧是动规5步曲1.确定dp数组的含义dp[i]表示到达第i层最低的开销2.确定递推公式dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])3.dp数组如何初始化dp[0]0 dp[1]0; 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。这句话表示不需要花费*/int ncost.size();vectorintdp(n1);if(n1){return 0;}dp[0]0;dp[1]0;for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];}
};
题目392判断子序列YES
解题思路这题就是要判断s再t中顺序的出现过了所以只要对t进行一次for只要出现了s的元素s的指针就前进比较下一个。
给定字符串 s 和 t 判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
class Solution {
public:bool isSubsequence(string s, string t) {int count0;if(s){return true;}else if(t){return false;}for(int i0;it.size();i){if(s[count]t[i]){count;}if(counts.size()){return true;}}return false;}
};专题11贪心算法
题目680验证回文串||NO
解题思路这题的解题思路是再普通验证回文数的方法上进行叠加的如果left和right不相等就判断左边去掉一位left或者右边去掉一个right–后的字符是否是回文数。这个是回文数的特性。
给你一个字符串 s最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串如果能返回 true 否则返回 false 。
class Solution {
public://自己封装一个接口用来判断是否是回文字符串bool isPalindrome(string s,int left,int right){int lens.size();if(len0) false;if(len1) true;while(leftright){if(s[left]!s[right]){return false;}left;right--;}return true;}bool validPalindrome(string s) {int left 0, right s.size() - 1;while (left right) {char c1 s[left], c2 s[right];if (c1 c2) {left;--right;} else {return isPalindrome(s, left, right - 1) || isPalindrome(s, left 1, right);}}return true;}
};题目860柠檬水找零NO
解题思路这题一上来想到的就是哈希表因为能开苏查找是否有钱当是给5元时直接收钱就行当给10元时需要退5元当要给20时退15而这15有两种分配方法105和555。分别看这些情况能否满足要求即可。
在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。
每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。
注意一开始你手头没有任何零钱。
给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。
class Solution {
public:bool lemonadeChange(vectorint bills) {//使用哈希表来存钱unordered_mapint,intmap;for(int i0;ibills.size();i){switch(bills[i]){case 5://直接收钱map[5];break;case 10://需要找5元查找是否有5元if(map[5]){//有map[5]--;map[10];}else{return false;}break;case 20://需要找15元//情况1105if(map[10]map[5]){map[10]--;map[5]--;map[20];}else if(map[5]3){map[5]-3;map[20];}else{return false;}break;}}return true;}
};题目942增减字符串匹配NO
解题思路I就放剩余数字中的最小数D就放剩余数字中的最大数。这个其实也不好想
由范围 [0,n] 内所有整数组成的 n 1 个整数的排列序列可以表示为长度为 n 的字符串 s 其中:
如果 perm[i] perm[i 1] 那么 s[i] ‘I’ 如果 perm[i] perm[i 1] 那么 s[i] ‘D’ 给定一个字符串 s 重构排列 perm 并返回它。如果有多个有效排列perm则返回其中 任何一个 。
官方题解
class Solution {
public:vectorint diStringMatch(string s) {int n s.length(), lo 0, hi n;vectorint perm(n 1);for (int i 0; i n; i) {perm[i] s[i] I ? lo : hi--;}perm[n] lo; // 最后剩下一个数此时 lo hireturn perm;}
};
题目1005K次取反后最大化的数组和YES
解题思路这个k表示又这么多的负号这些符号应该优先将负数变为正数后面如果k不为0则拿最小的正数来处理这个k。
给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后返回数组 可能的最大和 。
myself(这个代码我调试的时候打了一下调试信息)
class Solution {
public://冒泡排序void bubble_sort(vectorintnums){int lennums.size();for(int i0;ilen-1;i){for(int j0;jlen-i-1;j){if(nums[j]nums[j1]){int tempnums[j];nums[j]nums[j1];nums[j1]temp;}}}}int largestSumAfterKNegations(vectorint nums, int k) {//这个k实际就是又多少个负号//先进行排序bubble_sort(nums);int sum0;//统计最大值int current_minINT_MAX;//记录正数的最小值int current_min_index0;//记录最小值的下表for(int i0;inums.size();i){//这次遍历先处理数据//将所有的负数变成正数if(nums[i]0k0){nums[i]abs(nums[i]);k--;}//统计最小值if(current_minnums[i]){current_minnums[i];current_min_indexi;}}for(int i0;inums.size();i){std::coutnums[i] ;}std::coutstd::endl;std::coutkkstd::endl;std::coutmincurrent_minstd::endl;//上面这次遍历又两种情况//一种是k0那这种就直接加就行//另一种是k!0说明现在nums全部都是正数则拿一个最小正数来处理这个就行int ans0;if(k0){for(int i0;inums.size();i){ansnums[i];}}else{for(int i0;inums.size();i){if(icurrent_min_index){//用这个来处理剩下的kif(k%21){nums[i](-nums[i]);}}ansnums[i];}}return ans;}
};专题12二分查找
题目278第一个错误的版本NO
解题思路使用二分查找二分查找的本质就是每次都比较中间的数根据中间数的情况进行变化。
你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
官方题解
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {//看似写的简单但是这个官方题解边界处理的很好int left 1, right n;while (left right) { // 循环直至区间左右端点相同//这里防溢出的原因是如果right很大你在使用(leftright)/2有溢出的风险//用减法代替加法很巧妙int mid left (right-left) / 2; // 防止计算时溢出if (isBadVersion(mid)) {right mid; // 答案在区间 [left, mid] 中} else {left mid 1; // 答案在区间 [mid1, right] 中}}// 此时有 left right区间缩为一个点即为答案return left;}
};这里的int mid left(right-left)/2防溢出处理是非常巧妙的设想一下如果你使用int mid(leftright)/2有什么不妥的地方呢。编译一下你就会发现leftright是可能溢出的因为right可以是INT_MAX。所以用减法代替加法非常巧妙。
题目367有效的完全平方数YES
解题思路这里使用的是二分查找使用二分查找麻烦的地方是害怕溢出尤其这次主要比较的还是mid*mid所以我控制溢出第一个点就是int rightnum/21;任何数不可以比自己一半平方还大。第二点是乘法既然如此容易溢出那直接除法代替乘法这和int mid;减法代替加法思想是一样的。
给你一个正整数 num 。如果 num 是一个完全平方数则返回 true 否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数如 sqrt 。
myself
class Solution {
public:bool isPerfectSquare(int num) {//二分查找if(num1){return true;}int left1;int rightnum/21;while(leftright){//还是一样使用防止溢出的策略int midleft(right-left)/2;//不丢失精度if(num%mid0 midnum/mid){return true;}else if(midnum/mid){//小了leftmid1;}else{rightmid;}}return false;}
};题目374猜数字大小YES
解题思路使用二分法查找
我们正在玩猜数字游戏。猜数字游戏的规则如下
我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了我会告诉你我选出的数字比你猜测的数字大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果返回值一共有三种可能的情况
-1你猜的数字比我选出的数字大 即 num pick。 1你猜的数字比我选出的数字小 即 num pick。 0你猜的数字与我选出的数字相等。即 num pick。 返回我选出的数字。
myself
class Solution {
public:int guessNumber(int n) {//依旧使用二分查找int left1;int rightn;while(leftright){//防溢出策略int mid left(right-left)/2;if(guess(mid)0){return mid;}else if(guess(mid)-1){//向下判断rightmid-1;}else {leftmid1;}}return left;}
};稍微整理一下二分查找的思路
在二分查找中通过不断调整left和right的值来确定目标值的位置。在每次迭代中通过计算中间索引mid将搜索范围缩小一半以便更快地找到目标值。 确定mid值通过 mid left (right - left) / 2 计算得到中间索引mid。 判断mid位置根据 mid 处的值与目标值的关系可以分为三种情况
如果 mid 值等于目标值则找到目标返回 mid如果 mid 值小于目标值则目标值只可能在 mid 的右侧mid 1 到 right如果 mid 值大于目标值则目标值只可能在 mid 的左侧left 到 mid - 1。
缩小搜索范围根据上述判断结果调整left和right的值
如果 mid 处值小于目标值则更新 left mid 1排除 mid 位置如果 mid 处值大于目标值则更新 right mid - 1排除 mid 位置。
通过这种方式不断地缩小搜索范围并根据mid处的值来判断目标值可能的位置可以确保在搜索过程中不会漏掉任何一种情况。最终当left和right相遇时找到的位置就是目标值的位置。这种方法能够高效地定位目标值避免遗漏或重复搜索。
题目744寻找比目标字母大的最小字母NO
解题思路还是二分查找不过如何处理二分细节还是不容易。
给你一个字符数组 letters该数组按非递减顺序排序以及一个字符 target。letters 里至少有两个不同的字符。
返回 letters 中大于 target 的最小的字符。如果不存在这样的字符则返回 letters 的第一个字符。
class Solution {
public:char nextGreatestLetter(vectorchar letters, char target) {int left0, rightletters.size()-1;int ret 0;while(left right){int mid left (right-left)/2;if(letters[mid] target){//小了或相等都是需要前进left mid 1;}else{//假如大了right-1导致结束的话说明原来就是比他稍大的那个ret mid;right mid - 1;}}return letters[ret];}
};题目1385两个数组间的距离值YES
解题思路暴力解,直接两层for
给你两个整数数组 arr1 arr2 和一个整数 d 请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目对于元素 arr1[i] 不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| d 。
myself
class Solution {
public:int findTheDistanceValue(vectorint arr1, vectorint arr2, int d) {//最容易想到应该是暴力解int ans0;for(int i0;iarr1.size();i){bool signtrue;for(int j0;jarr2.size();j){if(abs(arr1[i]-arr2[j])d){signfalse;break;}}if(sign){ans;}}return ans;}
};
