Tag - red

red    2022-11-16 23:33:16    53    0    0

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
来源:https://leetcode.cn/problems/remove-duplicate-letters/

去掉一部分,使得字典序最大(最小),是一种很著名的单调栈题型。
其解法相对较为固定的部分是:保证单调栈是单调增加的。如果不单调增,则要删掉栈顶的那个“太大”的元素(往往有一定条件)
在本题中,其条件为:该字符在后面至少还有一次出现(否则就删没了)
此外,还需要考虑删除少了的情况。在本题中的方法为:如果前面已经出现过了这个元素,那么无条件删除后续要加进去的元素(相当于做了从后往前的删除)。有些时候,也可能是诸如“直接截断出前xxx个元素”

有一个对这类题型的很好归纳,见:https://leetcode.cn/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/

此外,有一点python上的技巧,例如末尾数组用stack[-1]。

  1. from functools import reduce
  2. from operator import add
  3. class Solution:
  4. # //去掉一部分,使得字典序最大(最小),是一种很著名的单调栈题型。
  5. # //其解法相对较为固定的部分是:保证单调栈是单调增加的。如果不单调增,则要删掉栈顶的那个“太大”的元素(往往有一定条件)
  6. # //在本题中,其条件为:该字符在后面至少还有一次出现(否则就删没了)
  7. # //此外,还需要考虑删除少了的情况。方法为:如果前面已经出现过了这个元素,那么无条件删除后续要加进去的元素(相当于做了从后往前的删除)
  8. def removeDuplicateLetters(self, s: str) -> str:
  9. stack = []
  10. hasadd = set()
  11. ccount = {} # 到了当前位置后,“后面”还剩下
red    2022-04-12 21:33:00    86    0    0

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

基本思路其实就是:统计每一位中出现的1的个数,对3求模即可。

递推公式推导见:
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/

  1. class Solution {
  2. public:
  3. //需要求得递推公式: one = one^n&!two
  4. // two = two ^ n &!one
  5. int singleNumber(vector<int>& nums) {
  6. int one=0,two=0;
  7. for(int num:nums)
  8. {
  9. one=(one^num)&(~two);
  10. two=(two^num)&(~one);
  11. }
  12. //由于只有0,1有意义,因此最终出现的two一定为0。
  13. return one; //这就是最终答案.
  14. }
  15. };
red    2022-04-06 23:19:21    83    0    0

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

输入: [3,30,34,5,9]
输出: "3033459"

太Tricky了。到现在也想不明白,只要将原数组sort一下,sort的标准是x + y < y + x(第一个数连接第二个数小于第二个数连接第一个数),就视为第一个数应该排在前面。

  1. bool compare(const string &x, const string &y) //if x+y < y+x, then x is smaller
  2. {
  3. return x + y < y + x ;
  4. }
  5. class Solution {
  6. public:
  7. string minNumber(vector<int> &nums) {
  8. vector<string> a;
  9. for (int num: nums) {
  10. a.push_back(to_string(num));
  11. }
  12. sort(a.begin(),a.end(), compare);
  13. string result;
  14. for (string idx: a) {
  15. result += idx;
  16. }
  17. return result;
  18. }
  19. };
red    2022-04-06 21:27:29    63    0    0

https://leetcode-cn.com/problems/chou-shu-lcof/

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

非常巧妙,确实是动态规划。但是,如何确定上一个要被乘的数是谁?要乘上2,3,5中的哪个?
解决的方式,用指针标记上个被乘上2,3,5的数。每次用O(3)判断一下应该乘上谁即可。

实现中的易错点:对于判定“重复”,也就是p2++, p3++, p5++的时候,一定不能if else, 而是每个if进行分开判定。这样就间接实现了“去重”。

  1. class Solution {
  2. public:
  3. //非常巧妙,确实是动态规划。但是,如何确定上一个要被乘的数是谁?要乘上2,3,5中的哪个?
  4. //解决的方式,用指针标记上个被乘上2,3,5的数。每次用O(3)判断一下应该乘上谁即可。
  5. int nthUglyNumber(int n) {
  6. int dp[n+1];
  7. dp[0]=1;
  8. int p2=0;
  9. int p3=0;
  10. int p5=0;
  11. for(int i=1;i<=n;i++)
  12. {
  13. int num1=dp[p2]*2;
  14. int num2=dp[p3]*3;
  15. int num5=dp[p5]*5;
  16. dp[i]=min(min(num1,num2),num5);
  17. if(dp[i]==num1)
  18. {
  19. p2++;
  20. }
  21. if(dp[i]==num2)
  22. {
  23. p3++;
  24. }
  25. if(dp[i]==num5)
  26. {
  27. p5++;
  28. }
  29. }
  30. return dp[
red    2022-04-05 20:44:16    130    0    0

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

如果只有一个数字,显然将全部数字异或即可。现在有两个数字,其实是要想办法将两个数字分到“两部分”中,每部分中其余数字依旧是偶数个。

假设这两个出现一次的数字是a,b。
方法:将所有的数字异或起来,即得到的是a^b的值。那么用什么标准,如何将a和b精准地分开?假设a^b的某一位的值为1,那么说明a和b在这一位上不相等。那么以这一位为标准,为1的分为一堆,为0的分为另外一堆。将这两堆的内容分别异或,即可完成。

  1. class Solution {
  2. public:
  3. vector<int> singleNumbers(vector<int>& nums) {
  4. int ab=nums[0];
  5. for(int i=1;i<nums.size();i++)
  6. {
  7. ab=ab^nums[i];
  8. }
  9. int result=ab;
  10. int mask=1;
  11. while(result) //查找不为0的位的位置
  12. {
  13. if(result&mask)break;
  14. mask=mask<<1;
  15. }
  16. //在mask这个位上,以其为标准分开两个数。
  17. bool hita=false;
  18. int a;
  19. bool hitb=false;
  20. int b;
  21. for(int now:nums)
  22. {
  23. if(now&mask)
  24. {
  25. a=hita?a^now:now;
  26. hita=true;
red    2022-03-11 16:53:52    135    0    0

犯了非常弱智的错误,WA了很多次且排查不到原因。

首先是边界条件的初始化,可不能无脑初始化为dp数组为0,其实,dp[0][j]=把j数组全部删除掉后的距离=j。

其次就是很弱智的错误了,我们已经定义了dp[i][j]为前i个元素以及前j个字符的最小编辑距离,但是其实对应了word1[i-1]和word2[j-1]。都做了这么多题了还能犯刚学c语言的弱智错误。

red    2022-03-11 14:14:51    93    0    0

数值的整数次方

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

第一次学习快速幂。
需要注意的是,对于x%2,可以直接写成x&1。

red    2022-03-09 20:47:01    65    0    0

https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/

常规的剪绳子使用动态规划即可,这里不再赘述。
有意思的是,对于“某个数拆分成若干个和,使得他们的乘积最大”的最优解,可以在数学上得到(也即贪心算法);其实是:尽可能将数分割成若干个3。 看看余数:如果没有余数,皆大欢喜。如果余数为2,不再改动,如果余数为1,那应当把一个*3拆成2+1,也就是最终变成(n-1)个3*2。

本题的另一个重要的关注点是幂指数求余。已经掌握的通用方法有常规的逐次取模。其实还有以下快速幂取余方法:

title

建议学一下。

red    2022-03-09 16:00:45    101    0    0

在一个 n * m
的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

  来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处

很基础,很重要的一道题

这道题脑子还是没转过来,盲目想到了二分查找。

其实本题的顺序是从右上角开始的。假设位置为i,j,其实i标记了小于i行内的元素一定因为太小不符合要求,(由于初始位置是在最右边并且i是从上到下移动的),同样,j标记了大于j列的元素一定不符合要求。更好理解的想法:从右上角开始,每次可以通过和target比较,来排除整整一行或者整整一列,相当于每次长方形在不断缩小。如果当前元素小于target,那么当前整行肯定不符合要求,划去,i++。如果当前元素大于target,那么当前一整列都不符合要求(下面的一定会更大),划掉一整列,j--。如此反复操作即可。

由矩形的对称性可知,其实从左下角开始也是可行的,道理完全相同。

red    2022-03-08 19:47:22    107    0    0

https://leetcode-cn.com/problems/3sum/

大致的思路猜出来了,但是“双指针”的过头了。事实上,只可以省略掉其中的一重循环。

对于这种三个侯选位置i,j,k,只能用O(N^2)区遍历i和j的所有位置,对于k而言,可以不用遍历,而是在发现nums[j]+nums[k]过大的时候,主动减小k即可,一直减小到更小为止。

本题的另一个亮点是如何去重。事实上,这个想法很朴素:在遍历i,j的时候,如果i,j和上一个i-1,j-1相等,那么直接跳过这个元素即可。

  1. for (int first = 0; first < n; ++first) {
  2. // 需要和上一次枚举的数不相同
  3. if (first > 0 && nums[first] == nums[first - 1]) {
  4. continue;
  5. }
  6. }

直白简单,无可言说。

1/2