相亲网站源码php模版,wordpress会议,百度网站是用什么软件做的,商务汽车网站建设题目列表
2824. 统计和小于目标的下标对数目
2825. 循环增长使字符串子序列等于另一个字符串
2826. 将三个组排序
2827. 范围中美丽整数的数目
一、统计和小于目标的下标对数目 这题直接暴力求解#xff0c;时间复杂度是O(n^2)#xff0c;代码如下
class Solution {
pu…题目列表
2824. 统计和小于目标的下标对数目
2825. 循环增长使字符串子序列等于另一个字符串
2826. 将三个组排序
2827. 范围中美丽整数的数目
一、统计和小于目标的下标对数目 这题直接暴力求解时间复杂度是O(n^2)代码如下
class Solution {
public:int countPairs(vectorint nums, int target) {int nnums.size(),ans0;for(int i0;in;i){for(int ji1;jn;j){if(nums[i]nums[j]target)ans;}}return ans;}
}; 那么时间复杂度能不能优化呢
我们再仔细阅读一下题目就会发现其实ij这个条件是没必要的因为只要我们找到符合要求的数字对将它们的下标排个序就可以算作答案即数据的顺序可以改变而两数之和相关的题目很容易让我们想到排序双指针/二分这里当然是选择双指针因为更快总的时间复杂度是O(nlognn)代码如下
class Solution {
public:int countPairs(vectorint nums, int target) {int nnums.size(),ans0;sort(nums.begin(),nums.end());int left0,rightn-1;while(leftright){int sumnums[left]nums[right];if(sumtarget){ansright-left;left;}else{right--;}}return ans;}
}; 二、循环增长使字符串子序列等于另一个字符串 这题关键是把题目意思弄明白即我们可以选择str1中若干个下标让这些字符循环递增一次使得str2成为str1的子序列。代码如下
class Solution {
public:bool canMakeSubsequence(string str1, string str2) {for(int i0,j0;istr1.size();i){char x(str1[i]-a1)%26a;//得到循环递增之后的字符if(str1[i]str2[j]||str2[j]x)j;if(jstr2.size())return true;}return false;}
};
三、将三个组排序 这题其实也有点绕题目说是让你将0~n-1个数分配到三个组中进行排序本质还是要你通过改变nums数组中的元素将nums数组中的123按照非递减顺序排好
我们要找的最小步数其实可以转化成为n - 最长非递减子序列的长度因为非递减子序列的元素是不用变化的只要改变不在非递减子序列里的元素即可很显然问题从找最小步数转换成了找最长非递减子序列的长度代码如下
class Solution {
public://f[i]代表以i为结尾的最长非递减子序列长度//f[i]max(f[j]1) (nums[i]nums[j])int minimumOperations(vectorint nums) {int nnums.size();int f[n],len1;for(int i0;in;i){f[i]1;for(int ji-1;j0;j--){if(nums[i]nums[j]){f[i]max(f[j]1,f[i]);}}lenmax(len,f[i]);}return n-len;}
};//时间复杂度更优的做法
class Solution {
public:int minimumOperations(vectorint nums) {int nnums.size();vectorint g;for(autox:nums){auto itupper_bound(g.begin(),g.end(),x);//二分查找找到大于x的第一个数if(itg.end())g.push_back(x);else *itx;}return n-g.size();}
};
但是这个问题的转化不是那么容易想到的那么还有什么做法遇到对数组元素进行修改我们还可以用递归来想一想为了方便转成递推我们依旧从后往前思考
1.确定递归的参数和返回值我们需要后面的元素值来判断该位置的元素是否需要修改所以需要两个参数dfs(i,j)i表示当前元素下标j表示后一个元素值返回值为前i个元素中的最小步数
2.确定递归的表达式
当nums[i]j时dfs(ij)dfs(i-1j)
当nums[i]j时dfs(ij)dfs(i1j)1
当nums[i]j时dfs(ij)max(dfs(i-1nums[i])dfs(i-1j)1)
3.确定递归的边界和入口
边界当i0时返回0即没有元素需要修改了
入口dfs(n-1,3)
代码如下
//递归---不记忆化也能过
class Solution {
public:int minimumOperations(vectorint nums) {int nnums.size();functionint(int,int) dfs[](int i,int j){if(i0)return 0;if(jnums[i])return dfs(i-1,j);if(jnums[i])return dfs(i-1,j)1;elsereturn min(dfs(i-1,j)1,dfs(i-1,nums[i]));};return dfs(n-1,3);}
};//转成递推
class Solution {
public:int minimumOperations(vectorint nums) {int nnums.size();int f[n1][4];memset(f,0,sizeof(f));for(int i0;in;i){for(int j1;j3;j){if(jnums[i])f[i1][j]f[i][j];else if(jnums[i]) f[i1][j]f[i][j]1;else f[i1][j]min(f[i][j]1,f[i][nums[i]]);}}return f[n][3];}
};//优化空间
class Solution {
public:int minimumOperations(vectorint nums) {int nnums.size();int f[4];//用几个常量代替也可以空间复杂度为O(1)memset(f,0,sizeof(f));for(int i0;in;i){for(int j1;j3;j){if(jnums[i])f[j]f[j];else if(jnums[i]) f[j]f[j]1;else f[j]min(f[j]1,f[nums[i]]);}}return f[3];}
};
四、范围中美丽整数的数目 这题是个很典型的数位dp主要看你有没有写过这个类型的题目这种题的套路基本上很固定就是dfs每一位上填哪个数字即我们来构造数字具体细节看代码实现如下
//dfs
class Solution {
public:int calc(int high,int k){string sto_string(high);int ns.size();functionint(int,int,int,bool,bool)dfs;//这里解释一下函数参数含义//i代表第i位val代表奇偶数字出现的次数奇数--val,偶数val下面对val的计算可以看看挺巧妙的作用一样//mod代表%k之后的数下面关于mod的计算运用了取模运算符的性质不清楚的可以去百度一下//islimit代表这个位置之前的数字是否和high的前几位相同用来判断该位置能取的最大值//isnum代表它前面的位上有没有选数字即这个数字有没有开始构造dfs[](int i,int val,int mod,bool islimit,bool isnum)-int{if(in)return isnumval0mod0;//是一个数并且奇偶数目相同并且是k的倍数int res0;if(!isnum)resdfs(i1,val,mod,false,false);int upislimit?s[i]-0:9;//看当前位置的值最大为几for(int j1-isnum;jup;j)resdfs(i1,valj%2*2-1,(mod*10j)%k,islimitupj,true);return res;};return dfs(0,0,0,true,false);}int numberOfBeautifulIntegers(int low, int high, int k) {return calc(high,k)-calc(low-1,k);}
};//dfs记忆化搜索
class Solution {
public:int calc(int high,int k){string sto_string(high);int ns.size();int memo[n][2*n1][k];memset(memo,-1,sizeof(memo));//为了避免mod为负数就将mod的初始值变成了n方便记忆化搜索functionint(int,int,int,bool,bool)dfs;dfs[](int i,int val,int mod,bool islimit,bool isnum)-int{if(in)return isnumvalnmod0;//是一个数并且奇偶数目相同并且是k的倍数if(isnum!islimitmemo[i][val][mod]!-1)return memo[i][val][mod];int res0;if(!isnum)resdfs(i1,val,mod,false,false);int upislimit?s[i]-0:9;//看当前位置的值最大为几for(int j1-isnum;jup;j)resdfs(i1,valj%2*2-1,(mod*10j)%k,islimitupj,true);if(isnum!islimit) //只有符合这两个条件的时候才需要记忆化因为其他情况只会出现一次没必要记忆化memo[i][val][mod]res;return res;};return dfs(0,n,0,true,false);}int numberOfBeautifulIntegers(int low, int high, int k) {return calc(high,k)-calc(low-1,k);}
};
