LeetCode每日一题

摘要:

公元2021年3月31日,立下每日一题之flag,遂得此文,望能持之以恒。

刷题思路:第一遍先按照tag来刷,由易到难。第二遍的事情第二遍再说……

双指针

题目141 环形链表

  • 时间: 3月31日
  • 难度: 简单
  • 心得: 一开始想了十分钟左右没有思路,脑子里虽然知道是双指针问题但是不知道如何使用双指针,只有又想了下能不能用暴力解法也没有想出来,最后放弃开始看题解。题解给出的方法是设置一个快指针和一个慢指针,快指针每次向前移动两个节点,慢指针移动一个节点,如果存在环,快指针最终总是会追上慢指针(茅塞顿开)。如果题目还要问环的长度是多少,那就在第一次相遇之后开始计数,两次相遇之间移动的次数就是环的长度。

题目125 验证回文串

  • 时间: 4月1日
  • 难度: 简单
  • 心得: 很简单直接的双指针,没注意到细节debug半天……

题目88 合并两个有序数组

  • 时间: 4月1日
  • 难度: 简单
  • 心得: 最简单的方法是先将两个数组合并然后再排序,但是时间复杂度较差。第二种方法是先将nums1中的元素拷贝到另一个数组中,然后通过双指针将元素有序地转移到nums1中。最好的方法是从nums1的末尾从后往前插入。

题目86 分隔链表

  • 时间: 4月1日
  • 难度: 中等
  • 心得: 比较顺利 提交的第二次就ac了,链表题还是画一下图比较好。第一次提交是因为没有考虑链表为空的情况,之后应该注意一下。

题目424 替换后的最长重复字符

  • 时间: 4月4日
  • 难度: 中等
  • 心得: 没做出来。一开始想的是左指针定位不动,右指针从左指针处开始,向右移动,如果右指针的字符与左指针相同,就当前重复串长度加一,如果右指针字符与左指针字符不同,如果大于0就k减一,当前重复串长度加一。这样外循环是左指针,内循环是右指针,遍历整个串。但是有一个问题,如果串是ABBBA这种,如果k是1,得到的答案会是4,但是正确答案是5.最后还是去看了解析。解析中是使用左指针和右指针维护了一个窗口,通过一个长度为26的数组去保存所有当前出现在窗口中的字符出现的次数,max保存当前所有字母中出现的最多的次数,当窗口长度 > max + k时,左指针右移,否则的话左指针不变,右指针右移。

题目61 旋转链表

  • 时间: 4月5日
  • 难度: 中等
  • 心得: 十分钟秒杀。首先通过遍历算出来链表的长度len,k = k % len。因为链表是循环的,所以只需要移动k次即可。之后总是维护指针指向链表最后一个节点以及倒数第二个节点,进行一些指针的操作即可。我的方法每次旋转后都需要找到倒数第二个节点,方法是从头遍历,比较耗内存。看了解析发现了更好的办法,不需要总是寻找倒数第二个节点,那就是将链表的末尾指针指向head从而成为一个环之后,每次执行旋转操作的时候,都不再将这个环断开,只需要将指针在这个环上移动,直到最后再将环断开。

题目1004 最大连续1的个数 III

  • 时间: 4月5日

  • 难度: 中等

  • 心得: 看上去和424那道题思路一样,一开始使用了和424一开始一样的方法,就是一个左指针,一个右指针,两层for循环,以为能秒杀,结果超时了。超时的主要原因我觉得是因为两层的for循环,时间复杂度为n方。改进方法为使用滑动窗口,时间复杂度可以降低为n。我的代码如下。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
    int longestOnes(vector<int>& A, int K) {
    int len = A.size();
    if(len == 0 || len == 1) {
    return len;
    }
    int head = 0, tail = head, max = 0, one = 0;
    for(tail = 0; tail < len; tail++) {
    if(A[tail] == 1) {
    one++;
    } else if(tail - head + 1 > one + K) {
    if(A[head] == 1) {
    one--;
    }
    head++;
    tail--;
    }
    max = (tail - head + 1) > max ? (tail - head + 1) : max;
    }
    return max;
    }
    };

    题解中给出的代码如下。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
    int longestOnes(vector<int>& A, int K) {
    int res = 0, zeros = 0, left = 0;
    for (int right = 0; right < A.size(); ++right) {
    if (A[right] == 0) ++zeros;
    while (zeros > K) {
    if (A[left++] == 0) --zeros;
    }
    res = max(res, right - left + 1);
    }
    return res;
    }
    };

    我认为题解中给出的代码更加简洁。作者将这种滑动窗口的题目称为“虫取法”,也就是像虫子一样,先后脚不动前脚移动,然后前脚不动后脚移动。题解中记录的是0的数量,其实与我记录1的数量没有很大不同。不同的地方在于for循环中的那个while循环,在这个while循环中,left可能会移动多次,直到窗口中只剩下K个0。我认为这个是优于我的代码的,因为我的代码中那个tail–其实也是要实现一样的功能,但是先tail–再通过for循环使得tail++从而保持tail不变实在有点蠢。

题目18 四数之和

  • 时间: 4月9日

  • 难度: 中等

  • 心得: 思路是比较简单的。使用四个指针(a<b<c<d)。固定最小的a和b在左边,c=b+1,d=_size-1 移动两个指针包夹求解。保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移,偏小时c右移。c和d相遇时,表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环,当b循环结束后,a++,进入下一轮a循环。 即(a在最外层循环,里面嵌套b循环,再嵌套双指针c,d包夹求解)。因为要使用双指针的方法,排序是必须要做的。上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后, 对应的数字要发生改变才行哦。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution{
    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(),nums.end());
    vector<vector<int> > res;
    if(nums.size()<4)
    return res;
    int a,b,c,d,_size=nums.size();
    for(a=0;a<=_size-4;a++){
    if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了
    for(b=a+1;b<=_size-3;b++){
    if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了
    c=b+1,d=_size-1;
    while(c<d){
    if(nums[a]+nums[b]+nums[c]+nums[d]<target)
    c++;
    else if(nums[a]+nums[b]+nums[c]+nums[d]>target)
    d--;
    else{
    res.push_back({nums[a],nums[b],nums[c],nums[d]});
    while(c<d&&nums[c+1]==nums[c]) //确保nums[c] 改变了
    c++;
    while(c<d&&nums[d-1]==nums[d]) //确保nums[d] 改变了
    d--;
    c++;
    d--;
    }
    }
    }
    }
    return res;
    }
    };

题目19 删除链表的倒数第N个节点

  • 时间: 4月10日
  • 难度: 中等
  • 心得: 只用了15分钟,一次提交直接通过,执行用时超过83%,内存消耗超过54%,拿捏。思路是之前看过的(说明刷题确实是有用的),我们使用p1和p2指向滑动窗口的首和尾,p2是从p1开始经过N-1次向后移动得到的。之后我们就固定这个窗口大小不变,这个窗口就像一把尺子让p1和p2同步向后移动,当p2->next == nullptr时,p1就是需要删除的元素。需要注意的是还需要维护一个p1_pre指针,用来指向p1的前一个节点。

题目30 串联所有单词的子串

  • 时间: 4月11日

  • 难度: 困难

  • 心得: 这道题有两种思路,分别进行记录

    • 思路一

      首先,最直接的思路,判断每个子串是否符合,符合就把下标保存起来,最后返回即可。

      如上图,利用循环变量 i ,依次后移,判断每个子串是否符合即可。

      怎么判断子串是否符合?这也是这个题的难点了,由于子串包含的单词顺序并不需要固定,如果是两个单词 A,B,我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A,B,C 也还好,只需要判断子串是否是 ABC,或者 ACB,BAC,BCA,CAB,CBA 就可以了,但如果更多单词呢?那就崩溃了。

      用两个 HashMap 来解决。首先,我们把所有的单词存到 HashMap 里,key 直接存单词,value 存单词出现的个数(因为给出的单词可能会有重复的,所以可能是 1 或 2 或者其他)。然后扫描子串的单词,如果当前扫描的单词在之前的 HashMap 中,就把该单词存到新的 HashMap 中,并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ,如果大了,就代表该子串不是我们要找的,接着判断下一个子串就可以了。如果不大于,那么我们接着判断下一个单词的情况。子串扫描结束,如果子串中的单词个数和期望的单词个数相同,就意味着子串的全部单词都符合,那么该子串就是我们找的其中一个。

    • 思路二

      滑动窗口。下面的代码采用的就是这个思路。第17行的for循环的意思是,如果每个单词的长度是3,我们需要分别以0,1,2为起点来滑动窗口,举个例子就可以解释清楚。假如现在words = [“foo”, “bar”],那么对于字符串”foobarab”,只有当我们以0为起点时可以得到答案,而对于”afoobarb”,只用我们用1为起点时,才能得到答案,”abfoobar”同理。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    class Solution 
    {
    public:
    vector<int> findSubstring(string s, vector<string>& words)
    { //滑动窗口 + 哈希统计
    int n = s.size();
    if (n == 0 || words.size() == 0)
    return vector<int> {};
    int word_num = words.size(); //单词个数
    int one_w_len = words[0].size(); //一个单词的长度

    unordered_map<string, int> word_cnt; //统计每个单词出现的freq
    for (string & w: words)
    word_cnt[w] += 1;

    vector<int> res;
    for (int i = 0; i < one_w_len; i ++) //每次的起点
    {
    int cur_w_num = 0; //滑动窗口内单词的个数
    int L = i, R = i; //LR指针
    unordered_map<string, int> cur_w_cnt; //统计滑动窗口内 每个单词的freq
    while (R + one_w_len <= s.size()) //R的范围
    {
    string w = s.substr(R, one_w_len);
    R += one_w_len; //R右移
    if (word_cnt.count(w) == 0) //不是有效的单词。unordered_map的count函数的参数是key,如果这个key在哈希表中,就返回1,否则返回0。所以count函数可以用来判断某个key是否存在于哈希表中
    { //突然冒出一个傻子 前面就全废了
    L = R;
    cur_w_cnt.clear();
    cur_w_num = 0;
    }
    else
    {
    cur_w_cnt[w] += 1;
    cur_w_num += 1;
    while (cur_w_cnt[w] > word_cnt[w]) //处理的L标准模板
    {
    string L_w = s.substr(L, one_w_len);
    L += one_w_len;
    cur_w_cnt[L_w] --;
    cur_w_num --;
    }
    if (cur_w_num == word_num) //若单词个数对上了,就记录下来
    res.push_back(L);
    }
    }
    }
    return res;
    }
    };

题目42 接雨水

  • 时间: 4月12日

  • 难度: 困难

  • 心得: 困难题果然和中等题不是一个级别呀。这道题还是值得反复玩味的。

    • 解法一:暴力求解

      对于数组中的每个元素,我们找出下雨后水能达到的最高位置,等于两边最大高度的较小值减去当前高度的值。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      int trap(vector<int>& height)
      {
      int ans = 0;
      int size = height.size();
      for (int i = 1; i < size - 1; i++) {
      int max_left = 0, max_right = 0;
      for (int j = i; j >= 0; j--) { //Search the left part for max bar size
      max_left = max(max_left, height[j]);
      }
      for (int j = i; j < size; j++) { //Search the right part for max bar size
      max_right = max(max_right, height[j]);
      }
      ans += min(max_left, max_right) - height[i];
      }
      return ans;
      }
    • 解法二:动态规划

      在暴力方法中,我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此,可以通过动态规划解决。我们定义,从下标 i 到最左端最高的条形块高度为left_max,从下标 i 到最右端最高的条形块高度为right_max。我们从左向右扫描一遍height,就可以找到每个位置i所对应的left_max,从右向左扫描一遍就可以找到每个位置i对应的right_max。最后扫描数组并累加 min( max_left[i], max_right[i] ) - height[i] 到ans上。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      int trap(vector<int>& height)
      {
      if (height == null)
      return 0;
      int ans = 0;
      int size = height.size();
      vector<int> left_max(size), right_max(size);
      left_max[0] = height[0];
      for (int i = 1; i < size; i++) {
      left_max[i] = max(height[i], left_max[i - 1]);
      }
      right_max[size - 1] = height[size - 1];
      for (int i = size - 2; i >= 0; i--) {
      right_max[i] = max(height[i], right_max[i + 1]);
      }
      for (int i = 1; i < size - 1; i++) {
      ans += min(left_max[i], right_max[i]) - height[i];
      }
      return ans;
      }
    • 解法三:双指针

      我们先明确几个变量的意思:

      1
      2
      3
      4
      left_max:左边的最大值,它是从左往右遍历找到的
      right_max:右边的最大值,它是从右往左遍历找到的
      left:从左往右处理的当前下标
      right:从右往左处理的当前下标

      定理一:在某个位置i处,它能存的水,取决于它左右两边的最大值中较小的一个。

      定理二:当我们从左往右处理到left下标时,左边的最大值left_max对它而言是可信的,但right_max对它而言是不可信的。(见下图,由于中间状况未知,对于left下标而言,right_max未必就是它右边最大的值)

      定理三:当我们从右往左处理到right下标时,右边的最大值right_max对它而言是可信的,但left_max对它而言是不可信的。

      对于位置left而言,它左边最大值一定是left_max,右边最大值“大于等于”right_max,这时候,如果left_max<right_max成立,那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max,都不影响这个结果。 所以当left_max<right_max时,我们就希望去处理left下标,反之,我们希望去处理right下标。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      class Solution:
      def trap(self, height: List[int]) -> int:
      left=0
      right=len(height)-1
      left_max=right_max=0
      ans=0
      while left<=right:
      if left_max<right_max:
      ans+=max(0,left_max-height[left])
      left_max=max(left_max,height[left])
      left+=1
      else:
      ans+=max(0,right_max-height[right])
      right_max=max(right_max,height[right])
      right-=1
      return ans

题目26 删除有序数组中的重复项

  • 时间: 4月13日
  • 难度: 简单
  • 心得: 放松日。九分钟秒杀

题目27 移除元素

  • 时间: 4月13日
  • 难度: 简单
  • 心得: 放松日。八分钟秒杀

题目26 删除有序数组中的重复项

  • 时间: 4月13日
  • 难度: 简单
  • 心得: 放松日。十分钟秒杀

题目28 实现strStr()

  • 时间: 4月13日
  • 难度: 简单
  • 心得: 放松日。十分钟秒杀。这道题虽然不难,但是字符串匹配有很多东西值得学习。

题目80 删除有序数组中的重复项II

  • 时间: 4月14日
  • 难度: 中等
  • 心得: 很简单,十分钟搞定,懒得写心得。

题目76 最小覆盖子串

  • 时间: 4月14日

  • 难度: 困难

  • 心得:

    滑动窗口的思想

    用i,j表示滑动窗口的左边界和右边界,通过改变i,j来扩展和收缩滑动窗口,可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串T的所有元素,记录下这个滑动窗口的长度j-i+1,这些长度中的最小值就是要求的结果。

    • 步骤一

      不断增加j使滑动窗口增大,直到窗口包含了T的所有元素

    • 步骤二

      不断增加i使滑动窗口缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值

    • 步骤三

      让i再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从步骤一开始执行,寻找新的满足条件的滑动窗口,如此反复,直到j超出了字符串S范围。

    面临的问题

    如何判断滑动窗口包含了T的所有元素?
    我们用一个字典need来表示当前滑动窗口中需要的各元素的数量,一开始滑动窗口为空,用T中各元素来初始化这个need,当滑动窗口扩展或者收缩的时候,去维护这个need字典,例如当滑动窗口包含某个元素,我们就让need中这个元素的数量减1,代表所需元素减少了1个;当滑动窗口移除某个元素,就让need中这个元素的数量加1。
    记住一点:need始终记录着当前滑动窗口下,我们还需要的元素数量,我们在改变i,j时,需同步维护need。
    值得注意的是,只要某个元素包含在滑动窗口中,我们就会在need中存储这个元素的数量,如果某个元素存储的是负数代表这个元素是多余的。比如当need等于{‘A’:-2,’C’:1}时,表示当前滑动窗口中,我们有2个A是多余的,同时还需要1个C。这么做的目的就是为了步骤二中,排除不必要的元素,数量为负的就是不必要的元素,而数量为0表示刚刚好。
    回到问题中来,那么如何判断滑动窗口包含了T的所有元素?结论就是当need中所有元素的数量都小于等于0时,表示当前滑动窗口不再需要任何元素。
    优化
    如果每次判断滑动窗口是否包含了T的所有元素,都去遍历need看是否所有元素数量都小于等于0,这个会耗费O(k)的时间复杂度,k代表字典长度,最坏情况下,k可能等于len(S)。其实这个是可以避免的,我们可以维护一个额外的变量needCnt来记录所需元素的总数量,当我们碰到一个所需元素c,不仅need[c]的数量减少1,同时needCnt也要减少1,这样我们通过needCnt就可以知道是否满足条件,而无需遍历字典了。

    自己想的时候没想出来,双指针还是得练,之后只做困难题。

题目142 环形链表II

  • 时间: 4月16日

  • 难度: 中等

  • 心得:

    这道题的题解太妙了!

    算法流程:

    双指针第一次相遇: 设两指针 fast,slow 指向链表头部 head,fast 每轮走 2 步,slow 每轮走 1 步;
    第一种结果: fast 指针走过链表末端,说明链表无环,直接返回 null;
    TIPS: 若有环,两指针一定会相遇。因为每走 1 轮,fast 与 slow 的间距 +1,fast 终会追上 slow;
    第二种结果: 当fast == slow时, 两指针在环中第一次相遇 。

    下面分析此时fast 与 slow走过的 步数关系 :
    设链表共有 a+b 个节点,其中 链表头部到链表入口 有 a 个节点(不计链表入口节点), 链表环 有 b 个节点(这里需要注意,a 和 b 是未知数;设两指针分别走了 f,s 步,则有:fast 走的步数是slow步数的 2 倍,即 f=2s;(解析: fast 每轮走 2 步)fast 比 slow多走了 n 个环的长度,即 f=s+nb;( 解析: 双指针都走过 a 步,然后在环内绕圈直到重合,重合时 fast 比 slow 多走 环的长度整数倍 );
    以上两式相减得:f=2nb,s=nb,即fast和slow 指针分别走了 2n,n 个 环的周长 (注意: n 是未知数,不同链表的情况不同)。
    目前情况分析:
    如果让指针从链表头部一直向前走并统计步数k,那么所有 走到链表入口节点时的步数 是:k=a+nb(先走 a 步到入口节点,之后每绕 1 圈环( b 步)都会再次到入口节点)。而目前,slow 指针走过的步数为 nb 步。因此,我们只要想办法让 slow 再走 a 步停下来,就可以到环的入口。但是我们不知道 a 的值,该怎么办?依然是使用双指针法。我们构建一个指针,此指针需要有以下性质:此指针和slow 一起向前走 a 步后,两者在入口节点重合。那么从哪里走到入口节点需要 a 步?答案是链表头部head。
    双指针第二次相遇:
    slow指针 位置不变 ,将fast指针重新 指向链表头部节点 ;slow和fast同时每轮向前走 1 步;
    TIPS:此时 f=0,s=nb ;
    当 fast 指针走到f=a 步时,slow 指针走到步s=a+nb,此时 两指针重合,并同时指向链表环入口 。
    返回slow指针指向的节点。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    * int val;
    * ListNode *next;
    * ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
    return nullptr;
    }
    ListNode *fast = head->next->next, *slow = head->next;
    while (fast != slow) {
    slow = slow->next;
    if (fast->next == nullptr || fast->next->next == nullptr) {
    return nullptr;
    } else {
    fast = fast->next->next;
    }
    }
    //fast == slow
    int cycle_len = 0;
    do {
    slow = slow->next;
    cycle_len++;
    fast = fast->next->next;
    } while (fast != slow);
    fast = head;
    while (fast != slow) {
    fast = fast->next;
    slow = slow->next;
    }
    return fast;
    }
    };

题目209

  • 时间:4月16日
  • 难度: 中等
  • 心得: 简单的滑动窗口

题目 15 三数之和

  • 时间: 2021.9.28

  • 难度: 中等

  • 心得: 这道题的思路并不难,但是做了很多次总是出错,原因是这道题的边界条件比较多,如何优雅地处理这些边界条件就是代码能力的体现了。边界条件主要有:l < r,l和r要跳过重复元素,l和r不能越界。

    这道题的思路是,第一个指针i遍历数组,指针l和r从i+1的位置和数组最后一个位置开始,相向而行,直到三个指针的数字和为0

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
    public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int> > res;
    if (nums.size() < 3) return res;
    sort(nums.begin(), nums.end());
    int l, r;
    for (int i = 0; i < nums.size() && nums[i] <= 0; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    l = i + 1;
    r = nums.size() - 1;
    while (l < r) {
    if (nums[l] + nums[r] + nums[i] == 0) {
    vector<int> vec = {nums[i], nums[l], nums[r]};
    res.push_back(vec);
    while (l < r && nums[l + 1] == nums[l]) l++;
    while (l < r && nums[r - 1] == nums[r]) r--;
    l++;
    r--;
    } else if (nums[l] + nums[r] + nums[i] < 0) {
    l++;
    } else {
    r--;
    }
    }
    }
    return res;
    }
    };

二分查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法,前提是数据结构必须先排好序,可以在数据规模的对数时间复杂度内完成查找。但是,二分查找要求线性表具有有随机访问的特点(例如数组),也要求线性表能够根据中间元素的特点推测它两侧元素的性质,以达到缩减问题规模的效果。

题目29 两数相除

  • 时间: 4月20日

  • 难度: 中等

  • 心得: 这道题感觉完全是递归,没有二分。举个例子:11 除以 3 。
    首先11比3大,结果至少是1, 然后我让3翻倍,就是6,发现11比3翻倍后还要大,那么结果就至少是2了,那我让这个6再翻倍,得12,11不比12大,吓死我了,差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数,这个数是多少呢?我让11减去刚才最后一次的结果6,剩下5,我们计算5是3的几倍,也就是除法,看,递归出现了。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
    public:
    int divide(int dividend, int divisor) {
    if(dividend == 0) return 0;
    if(divisor == 1) return dividend;
    if(divisor == -1){
    if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数,都是直接返回相反数就好啦
    return INT_MAX;// 是最小的那个,那就返回最大的整数啦
    }
    long a = dividend;
    long b = divisor;
    int sign = 1;
    if((a>0&&b<0) || (a<0&&b>0)){
    sign = -1;
    }
    a = a>0?a:-a;
    b = b>0?b:-b;
    long res = div(a,b);
    if(sign>0)return res>INT_MAX?INT_MAX:res;
    return -res;
    }
    int div(long a, long b){ // 似乎精髓和难点就在于下面这几句
    if(a<b) return 0;
    long count = 1;
    long tb = b; // 在后面的代码中不更新b
    while((tb+tb)<=a){
    count = count + count; // 最小解翻倍
    tb = tb+tb; // 当前测试的值也翻倍
    }
    return count + div(a-tb,b);
    }
    };

题目34 在排序数组中查找元素的第一个和最后一个位置

  • 时间: 4月22日

  • 难度: 中等

  • 心得: 二分查找题感觉就是很注重细节,基本的框架都是一样的,不同的地方在于细节处的赋值以及大于还是大于等于。这道题的思路是,通过两次二分查找分别找到第一个等于target的位置以及第一个大于target的位置。在寻找后者时有一个细节,就是第14行的赋值,r = n而不是r = n - 1,这是因为如果nums中所有的值都等于target,例如nums为[-1]而target为-1时,r的初始值设置为最后一个下标的下一位。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
    vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res(2,-1);
    if(nums.empty()) return res;
    int n=nums.size(),l=0,r=n-1;
    while(l<r){
    int m=l+(r-l)/2;
    if(nums[m]>=target) r=m;
    else l=m+1;
    }
    if(nums[l]!=target) return res;
    res[0]=l;
    r=n;
    while(l<r){
    int m=l+(r-l)/2;
    if(nums[m]<=target) l=m+1;
    else r=m;
    }
    res[1]=l-1;
    return res;
    }
    };

题目35 搜索插入位置

  • 时间: 4月27日
  • 难度: 简单
  • 心得: 是最基本的二分查找问题,第一次提交没有通过是因为没有考虑nums中只有一个元素且恰好是target的情况。

题目50 Pow(x, n)

  • 时间: 4月28日

  • 难度: 中等

  • 心得:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
    double quickMul(double x, long long N) {
    if (N == 0) {
    return 1.0;
    }
    double y = quickMul(x, N / 2);
    return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
    long long N = n;
    return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
    double quickMul(double x, long long N) {
    double ans = 1.0;
    // 贡献的初始值为 x
    double x_contribute = x;
    // 在对 N 进行二进制拆分的同时计算答案
    while (N > 0) {
    if (N % 2 == 1) {
    // 如果 N 二进制表示的最低位为 1,那么需要计入贡献
    ans *= x_contribute;
    }
    // 将贡献不断地平方
    x_contribute *= x_contribute;
    // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可
    N /= 2;
    }
    return ans;
    }

    double myPow(double x, int n) {
    long long N = n;
    return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    };

题目69 x的平方根

  • 时间: 5月16日

  • 难度: 简单

  • 心得: 过去的半个月没有刷题,惭愧。之后继续坚持。一开始没想出来二分查找怎么写,还用了本方法结果超时了。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
    int mySqrt(int x) {
    int l = 0, r = x, ans = -1;
    while (l <= r) {
    int mid = l + (r - l) / 2;
    if ((long long)mid * mid <= x) {
    ans = mid;
    l = mid + 1;
    } else {
    r = mid - 1;
    }
    }
    return ans;
    }
    };

题目167 两数之和II - 输入有序数组

  • 时间: 5月17日
  • 难度: 简单
  • 心得: 这道题首先想到的是双指针,并且顺利AC了。如果采用二分查找方法,可以先固定第一个数,然在第一个数右侧二分查找第二个数,第二个数为目标值减去第一个数。

题目74 搜索二维矩阵

  • 时间: 5月18日
  • 难度: 中等

题目81 搜索旋转排序数组II

  • 时间: 5月19日

  • 难度: 中等

  • 心得: 没做出来。自己的思路是,数组的第一个元素是两个有序序列的分割点,设为n,然后依据nums[mid]与n与target之间的关系,分类讨论,每个情况都判断一下应该取左边还是右边。但是最后发现,有些情况是没有办法确定的,所以这种方法行不通。

    题解:本题是需要使用二分查找,怎么分是关键,举个例子:

    第一类
    10111和 11101 这种。此种情况下 nums[start] == nums[mid],分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。
    第二类
    2 3 4 5 6 7 1这种,也就是 nums[start] < nums[mid]。此例子中就是 2 < 5;
    这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。
    第三类
    6 7 1 2 3 4 5这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2;
    这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找,否则去前半部分找。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    public boolean search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
    return false;
    }
    int start = 0;
    int end = nums.length - 1;
    int mid;
    while (start <= end) {
    mid = start + (end - start) / 2;
    if (nums[mid] == target) {
    return true;
    }
    if (nums[start] == nums[mid]) {
    start++;
    continue;
    }
    //前半部分有序
    if (nums[start] < nums[mid]) {
    //target在前半部分
    if (nums[mid] > target && nums[start] <= target) {
    end = mid - 1;
    } else { //否则,去后半部分找
    start = mid + 1;
    }
    } else {
    //后半部分有序
    //target在后半部分
    if (nums[mid] < target && nums[end] >= target) {
    start = mid + 1;
    } else { //否则,去后半部分找
    end = mid - 1;

    }
    }
    }
    //一直没找到,返回false
    return false;

    }

题目153 寻找旋转排序数组中的最小值

  • 时间: 5月21日
  • 难度: 中等
  • 心得: 情况一:nums[left] < nums[mid],此时[left, mid]区间为升序,这个区间中的最小值为nums[left],与min比较,如果小于min则使用min进行记录。然后令left = mid + 1,去探索mid右侧有没有更小的值。
    情况二:nums[left] > nums[mid],此时[mid, right]区间为升序,这个区间的最小值为nums[mid],与min比较,如果小于min则使用min进行记录。然后令right = mid - 1,去探索mid左侧有没有更小的值。
    情况三:nums[left] = nums[mid],此时可能left到right的区间已经来到了最小值附近,nums[left]与min比较,如果小于min则使用min进行记录。既然已经对nums[left]进行了判断,nums[left]就没用了,令left = left + 1

题目162 寻找峰值

  • 时间: 5月22日

  • 难度: 中等

  • 心得: 二分查找并不仅仅适用于数组完全排序的情况,对于局部有序的数组,仍然可以借助变种的二分查找解决问题。不论如何,都是利用的有序性(全局有序或局部有序)。本题, nums 中找到中间的元素 mid。若该元素恰好位于降序序列或者一个局部下降坡度中(通过将 nums[mid] 与右侧比较判断),则说明峰值会在本元素的左边。于是,我们将搜索空间缩小为 mid 的左边(包括其本身),并在左侧子数组上重复上述过程。

    若该元素恰好位于升序序列或者一个局部上升坡度中(通过将nums[mid] 与右侧比较判断),则说明峰值会在本元素的右边。于是,我们将搜索空间缩小为 mid 的右边,并在右侧子数组上重复上述过程。

    就这样,我们不断地缩小搜索空间,直到搜索空间中只有一个元素,该元素即为峰值元素。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class Solution {
    public int findPeakElement(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1])
    return i;
    }
    return nums.length - 1;
    }
    }

题目222 完全二叉树的节点个数

  • 时间: 5月23日

  • 难度: 中等

  • 心得: 对于没有约束的二叉树而言,可以很简单地想到使用下面这个递归的解法:

    1
    2
    3
    4
    5
    6
    public int countNodes(TreeNode root) {
    if (root == null){
    return 0;
    }
    return countNodes(root.left) + countNodes(root.right) + 1;
    }

    但这是一个普适的解法,对于此题给的完全二叉树的特点没有利用起来,进一步考虑如何使用完全二叉树的特点更快解出此题。

    首先需要明确完全二叉树的定义:它是一棵空树或者它的叶子节点只出在最后两层,若最后一层不满则叶子节点只在最左侧。

    再来回顾一下满二叉的节点个数怎么计算,如果满二叉树的层数为h,则总节点数为:2^h - 1.
    那么我们来对 root 节点的左右子树进行高度统计,分别记为 left 和 right,有以下两种结果:

    left == right。这说明,左子树一定是满二叉树,因为节点已经填充到右子树了,左子树必定已经填满了。所以左子树的节点总数我们可以直接得到,是 2^left - 1,加上当前这个 root 节点,则正好是 2^left。再对右子树进行递归统计。
    left != right。说明此时最后一层不满,但倒数第二层已经满了,可以直接得到右子树的节点个数。同理,右子树节点 +root 节点,总数为 2^right。再对左子树进行递归查找。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    * int val;
    * TreeNode left;
    * TreeNode right;
    * TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
    public int countNodes(TreeNode root) {
    if(root == null){
    return 0;
    }
    int left = countLevel(root.left);
    int right = countLevel(root.right);
    if(left == right){
    return countNodes(root.right) + (1<<left);
    }else{
    return countNodes(root.left) + (1<<right);
    }
    }
    private int countLevel(TreeNode root){ //计算高度
    int level = 0;
    while(root != null){
    level++;
    root = root.left;
    }
    return level;
    }
    }

链表

题目24 两两交换链表中的节点

  • 时间: 5月25日

  • 难度: 中等

  • 心得: 链表变换的题目通常会在head节点前面加一个pre节点,从而保证头结点和后面的节点可以使用相同的操作。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public ListNode swapPairs(ListNode head) {
    ListNode pre = new ListNode(0);
    pre.next = head;
    ListNode temp = pre;
    while(temp.next != null && temp.next.next != null) {
    ListNode start = temp.next;
    ListNode end = temp.next.next;
    temp.next = end;
    start.next = end.next;
    end.next = start;
    temp = start;
    }
    return pre.next;
    }
    }

题目82 删除排序链表中的重复元素

  • 时间: 5月26日
  • 难度: 中等
  • 心得: 利用pre节点,最后一个节点的next是空指针,注意不要对空指针进行操作

题目92 反转链表II

  • 时间: 5月27日

  • 难度: 中等

  • 心得: 头插法

    1、我们定义两个指针,分别称之为 g(guard 守卫) 和 p(point)。
    我们首先根据方法的参数 left 确定 g 和 p 的位置。将 g 移动到第一个要反转的节点的前面,将 p 移动到第一个要反转的节点的位置上。我们以 m=2,n=4为例。
    2、将 p 后面的元素删除,然后添加到 g 的后面。也即头插法。
    3、重复right - left次步骤(2)
    4、返回 dummyHead.next

    链表变换的代码:

    1
    2
    3
    4
    5
    ListNode removed = p.next;
    p.next = p.next.next;

    removed.next = g.next;
    g.next = removed;
  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /**
    * Definition for singly-linked list.
    * type ListNode struct {
    * Val int
    * Next *ListNode
    * }
    */
    func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
    return nil
    }
    if head.Next == nil {
    return head
    }
    if left == right {
    return head
    }
    var preNode ListNode
    preNode.Next = head
    p := &preNode
    i := 1
    for i < left {
    i = i + 1
    p = p.Next
    }
    s := p.Next
    i = right - left
    var t *ListNode
    for i > 0 {
    i = i - 1
    t = s.Next
    s.Next = t.Next
    t.Next = p.Next
    p.Next = t
    }
    return preNode.Next
    }

题目109 有序链表转换二叉搜索树

  • 时间: 5月29日

  • 难度: 中等

  • 心得: 做和树相关的题目比较少,直接懵逼看了题解。似乎和树有关的题很多都是用递归的方式来做?

    这道题首先将链表转换成有序数组,然后将数组想象成一条绳,提起中点作为根节点,分出左右两部分,再提起各自的中点作为根节点……分治下去,这根绳就成了BST的模样

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    func sortedListToBST(head *ListNode) *TreeNode {
    arr := []int{}
    for head != nil {
    arr = append(arr, head.Val)
    head = head.Next
    }
    return buildBST(arr, 0, len(arr)-1)
    }
    func buildBST(arr []int, start, end int) *TreeNode {
    if start > end {
    return nil
    }
    mid := (start + end) >> 1
    root := &TreeNode{Val: arr[mid]}
    root.Left = buildBST(arr, start, mid-1)
    root.Right = buildBST(arr, mid+1, end)
    return root
    }

题目132 重排链表

  • 时间: 5月29日
  • 难度: 中等
  • 心得: 这道题把链表这里的三个技巧都包含了,分别是双指针、链表翻转和链表合并。这道题首先用快慢指针找到链表的中点,然后将链表一分为二。之后将后半段链表反向,再和前半段链表合并

题目237 删除链表中的节点

  • 时间: 5月30日

  • 难度: 简单

  • 心得: 删除链表中的节点是很简单的操作,但是这道题的方式十分新颖。直接看代码。函数的参数是要被删除的节点的指针。

  • 代码:

    1
    2
    3
    4
    func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
    }

题目445 两数相加II

  • 时间: 6月8日

  • 难度: 中等

  • 心得: 逆序处理应该首先想到栈

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
    public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    stack<int> s1, s2;
    while (l1) {
    s1.push(l1 -> val);
    l1 = l1 -> next;
    }
    while (l2) {
    s2.push(l2 -> val);
    l2 = l2 -> next;
    }
    int carry = 0;
    ListNode* ans = nullptr;
    while (!s1.empty() or !s2.empty() or carry != 0) {
    int a = s1.empty() ? 0 : s1.top();
    int b = s2.empty() ? 0 : s2.top();
    if (!s1.empty()) s1.pop();
    if (!s2.empty()) s2.pop();
    int cur = a + b + carry;
    carry = cur / 10;
    cur %= 10;
    auto curnode = new ListNode(cur);
    curnode -> next = ans;
    ans = curnode;
    }
    return ans;
    }
    };

    多线程

    题目 1114 按序打印

  • 时间: 8月2日

  • 难度: 简单

  • 心得: 熟悉一下互斥锁和条件变量。second和third使用的是同一个锁,我所理解的过程是这样的:由于second和third的第一行代码都是在上锁,所以一开始second和third会争夺这个锁,加入third争夺到了这个锁,那么second就先在19行等待,接着,third在29行处判断lambda表达式能否满足,发现不满足后,释放锁,并使得third阻塞在29行处。释放锁后,second将有机会获得这个锁,然后也检查lambda表达式能否满足条件,发现也不满足,然后释放锁,阻塞在20行处。second和third一直会重复“获得锁->发现lambda不满足->释放锁”的过程。直到first使得k = 1,second在发现lambda可以满足后,释放锁后不再阻塞,使得k = 2。然后third也发现lambda满足,进而也可以执行下面的代码。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    //方法一:条件变量
    class Foo {
    private:
    int k = 0;
    mutex mu;
    condition_variable cv;

    public:
    Foo() {
    }

    void first(function<void()> printFirst) {
    // printFirst() outputs "first". Do not change or remove this line.
    printFirst();
    k = 1;
    cv.notify_all();
    }

    void second(function<void()> printSecond) {
    unique_lock<mutex> lock(mu);
    cv.wait(lock, [this]()->int{return k == 1;});
    // printSecond() outputs "second". Do not change or remove this line.
    printSecond();
    k = 2;
    cv.notify_one();
    }

    void third(function<void()> printThird) {
    unique_lock<mutex> lock(mu);
    cv.wait(lock, [this]()->int{return k == 2;});
    // printThird() outputs "third". Do not change or remove this line.
    printThird();
    }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    // 方法二:信号量
    #include <semaphore.h>

    class Foo {
    private:
    sem_t sem_1, sem_2;

    public:
    Foo() {
    sem_init(&sem_1, 0, 0), sem_init(&sem_2, 0, 0);
    }

    void first(function<void()> printFirst) {
    printFirst();
    sem_post(&sem_1);
    }

    void second(function<void()> printSecond) {
    sem_wait(&sem_1);
    printSecond();
    sem_post(&sem_2);
    }

    void third(function<void()> printThird) {
    sem_wait(&sem_2);
    printThird();
    }
    };

位运算

题目 136 只出现一次的数字

  • 时间: 8月15日

  • 难度: 简单

  • 心得: 两个相同的数字异或就抵消了,所有数字异或一次即可。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
    int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int i = 0; i < nums.size(); i++) {
    res ^= nums[i];
    }
    return res;
    }
    };

题目 137 只出现一次的数字 II

  • 时间: 8月15日

  • 难度: 中等

  • 心得:

    位运算的题不一定都是借助异或运算。比如这道题,考虑数字的二进制形式,对于出现三次的数字,各 二进制位 出现的次数都是 3 的倍数。因此,统计所有数字的各二进制位中 1 的出现次数,并对 3 求余,结果则为只出现一次的数字。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public int singleNumber(int[] nums) {
    int[] counts = new int[32];
    for(int num : nums) {
    for(int j = 0; j < 32; j++) {
    counts[j] += num & 1;
    num >>>= 1; //三个>为逻辑右移,即高位直接补0
    }
    }
    int res = 0, m = 3;
    for(int i = 0; i < 32; i++) {
    res <<= 1; //两个<为算数左移
    res |= counts[31 - i] % m;
    }
    return res;
    }
    }

题目 645 错误的集合 【分组异或】

  • 时间: 8月15日

  • 难度: 简单

  • 心得: 与剑指offer 56采用了类似的方法。将nums中所有元素以及1~n全部异或在一起,就得到了重复数字与丢失数字的异或,记为xorr。找到xorr二进制中最低的为1的那一位,然后根据这一位是否为1,将nums中的所有元素以及1-n分为两组。这两组中的元素再分别进行异或,得到的两个数字即为所求

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
    vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int xorSum = 0;
    for (int num : nums) {
    xorSum ^= num;
    }
    for (int i = 1; i <= n; i++) {
    xorSum ^= i;
    }
    int lowbit = xorSum & (-xorSum);
    int num1 = 0, num2 = 0;
    for (int &num : nums) {
    if ((num & lowbit) == 0) {
    num1 ^= num;
    } else {
    num2 ^= num;
    }
    }
    for (int i = 1; i <= n; i++) {
    if ((i & lowbit) == 0) {
    num1 ^= i;
    } else {
    num2 ^= i;
    }
    }
    for (int num : nums) {
    if (num == num1) {
    return vector<int>{num1, num2};
    }
    }
    return vector<int>{num2, num1};
    }
    };

动态规划

题目 5 最长回文子串 +1

  • 时间: 9月5日

  • 难度: 中等

  • 心得:

    方法一:动态规划

    方法一的时间复杂度为O(n^2^),空间复杂度为O(n^2^)

    方法二:中心扩展法

    时间复杂度O(n^2^),空间复杂度O(1)

  • 代码:

    方法一:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    #include <iostream>
    #include <string>
    #include <vector>

    using namespace std;

    class Solution {
    public:
    string longestPalindrome(string s) {
    int n = s.size();
    if (n < 2) {
    return s;
    }

    int maxLen = 1;
    int begin = 0;
    // dp[i][j] 表示 s[i..j] 是否是回文串
    vector<vector<int>> dp(n, vector<int>(n));
    // 初始化:所有长度为 1 的子串都是回文串
    for (int i = 0; i < n; i++) {
    dp[i][i] = true;
    }
    // 递推开始
    // 先枚举子串长度
    for (int L = 2; L <= n; L++) {
    // 枚举左边界,左边界的上限设置可以宽松一些
    for (int i = 0; i < n; i++) {
    // 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
    int j = L + i - 1;
    // 如果右边界越界,就可以退出当前循环
    if (j >= n) {
    break;
    }

    if (s[i] != s[j]) {
    dp[i][j] = false;
    } else {
    if (j - i < 3) {
    dp[i][j] = true;
    } else {
    dp[i][j] = dp[i + 1][j - 1];
    }
    }

    // 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
    if (dp[i][j] && j - i + 1 > maxLen) {
    maxLen = j - i + 1;
    begin = i;
    }
    }
    }
    return s.substr(begin, maxLen);
    }
    };

    方法二:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
    --left;
    ++right;
    }
    return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); ++i) {
    auto [left1, right1] = expandAroundCenter(s, i, i);
    auto [left2, right2] = expandAroundCenter(s, i, i + 1);
    if (right1 - left1 > end - start) {
    start = left1;
    end = right1;
    }
    if (right2 - left2 > end - start) {
    start = left2;
    end = right2;
    }
    }
    return s.substr(start, end - start + 1);
    }
    };

剑指offer

题目 剑指Offer 07 重建二叉树 【树递归】+1

  • 时间: 6月29日

  • 难度: 中等

  • 心得: 利用前序遍历和中序遍历的特点构造递归函数。前序遍历的第一个节点一定是根节点,根据这个根节点在中序遍历中的位置,可以确定根节点的左子树和右子树各有多少个节点。recur函数的参数解释:root为根节点在前序遍历中的index,left为树在中序遍历中的左边界,right为树在中序遍历中的右边界

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    /**
    * Definition for a binary tree node.
    * type TreeNode struct {
    * Val int
    * Left *TreeNode
    * Right *TreeNode
    * }
    */
    var mp = make(map[int]int)
    var pre []int
    func buildTree(preorder []int, inorder []int) *TreeNode {
    pre = preorder
    for i,j := range inorder {
    mp[j] = i
    }
    return recur(0, 0, len(inorder) - 1)
    }
    func recur(root int, left int, right int) *TreeNode {
    if left > right {
    return nil
    }
    index := mp[pre[root]]
    ret := TreeNode{pre[root], recur(root + 1, left, index - 1), recur(root + 1 + index - left, index + 1, right)}
    return &ret
    }

题目 剑指offer 题目10 青蛙跳台阶 【递归 迭代】+1

  • 时间: 7月9日

  • 难度: 简单

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
    long long arr[101] = {0};
    long long numWays(long long n) {
    if (n == 0 || n == 1) {
    return 1;
    }
    if (arr[n] != 0)
    return arr[n];
    arr[n] = (numWays(n - 1) + numWays(n - 2)) % 1000000007;
    return arr[n];
    }
    };

    对于这中递归式比较简单的,还可以这样写

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public int numWays(int n) {
    int a = 1, b = 1, sum;
    for(int i = 0; i < n; i++){
    sum = (a + b) % 1000000007;
    a = b;
    b = sum;
    }
    return a;
    }
    }

    这样可以使得空间复杂度也降低。

题目 剑指offer 11 旋转数组的最小数字 【二分】+1

  • 时间: 7月11日

  • 难度: 简单

  • 心得: 这道题好像之前面试的时候遇到过,还没做出来。这次居然又没做出来。第一想法是用numbers[mid]与numbers[mid - 1], numbers[mid + 1]作比较,但是这样情况很多,比较麻烦。正确方法是用中间值与最右边的值比较。需要注意的是,当中间值和最右边的值相等时,无法判断最小值是在mid左边还是右边,所以就right–来缩小查找范围

    注意这种结束循环的方法:知道left>=rights时结束,然后返回left值

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
    int minArray(vector<int>& numbers) {
    int i = 0, j = numbers.size() - 1;
    while (i < j) {
    int m = (i + j) / 2;
    if (numbers[m] > numbers[j]) i = m + 1;
    else if (numbers[m] < numbers[j]) j = m;
    else j--;
    }
    return numbers[i];
    }
    };

题目 剑指offer 16 数值的整数次方 【快速幂 递归】+1

  • 时间: 7月15日

  • 难度:中等

  • 心得:本题使用的是快速幂算法,快速幂有递归和迭代两个版本,递归更好理解。迭代太难想了,算了。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    double myP(double x, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
    return myP(x * x, n / 2) * x;
    } else {
    return myP(x * x, n / 2);
    }
    }
    double myPow(double x, int n) {
    long long nn = n;
    if (n < 0) {
    nn = 0 - nn;
    x = 1 / x;
    return myP(x, nn);
    } else {
    return myP(x, nn);
    }
    }
    };

题目 剑指offer 20 表示数值的字符串 【有限状态机】+1

  • 时间: 7月17日

  • 难度: 中等

  • 心得: 一位一位地分析字符固然可以,但是会比较混乱,有限状态机会更加清晰。状态定义:

    按照字符串从左到右的顺序,定义以下 9 种状态。

    1. 开始的空格

    2. 幂符号前的正负号

    3. 小数点前的数字

    4. 小数点、小数点后的数字

    5. 当小数点前为空格时,小数点、小数点后的数字

    6. 幂符号

    7. 幂符号后的正负号

    8. 幂符号后的数字

    9. 结尾的空格

      结束状态:合法的结束状态有 2, 3, 7, 8 。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public boolean isNumber(String s) {
    Map[] states = {
    new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
    new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.
    new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
    new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
    new HashMap<>() {{ put('d', 3); }}, // 4.
    new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.
    new HashMap<>() {{ put('d', 7); }}, // 6.
    new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.
    new HashMap<>() {{ put(' ', 8); }} // 8.
    };
    int p = 0;
    char t;
    for(char c : s.toCharArray()) {
    if(c >= '0' && c <= '9') t = 'd';
    else if(c == '+' || c == '-') t = 's';
    else if(c == 'e' || c == 'E') t = 'e';
    else if(c == '.' || c == ' ') t = c;
    else t = '?';
    if(!states[p].containsKey(t)) return false;
    p = (int)states[p].get(t);
    }
    return p == 2 || p == 3 || p == 7 || p == 8;
    }
    }

题目 剑指offer 26 树的子结构 【树递归】+1

  • 时间: 7月19日

  • 难度: 中等

  • 心得:

    1. 与树有关的题目,大多数都通过递归来解决。
    2. 与树有关的题目,一定要时刻注意对空指针的判断
    3. 回到这道题本身,如果要查找树A中是否存在和树B一样的结构,可以分为两步,第一步是在树A中找到和树B的根节点值一样的节点R;第二步是判断树A中以节点R为根节点的子树是否包含和树B相同的结构。这两个步骤都是通过编写递归函数来解决。
  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * TreeNode *left;
    * TreeNode *right;
    * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    class Solution {
    public:
    bool isSubTree (TreeNode *root1, TreeNode *root2) {
    if (root2 == NULL) return true;
    if (root1 == NULL) return false;
    bool ret1, ret2;
    if (root1->val == root2->val) {
    ret1 = isSubTree(root1->left, root2->left);
    ret2 = isSubTree(root1->right, root2->right);
    } else return false;
    return (ret1 && ret2);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
    bool result = false;
    if (A != NULL && B != NULL) {
    if (A->val == B->val) {
    result = isSubTree(A, B);
    }
    if (result == false) {
    result = isSubStructure(A->left, B);
    }
    if (result == false) {
    result = isSubStructure(A->right, B);
    }
    }
    return result;
    }
    };

题目 剑指offer 28 对称的二叉树 【树递归】+1

  • 时间: 7月19日

  • 难度: 简单

  • 心得: 再次证明了树的题大多数都使用递归来解。编写递归函数要点:寻找问题的子结构,确定递归结束条件

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * TreeNode *left;
    * TreeNode *right;
    * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    class Solution {
    public:
    bool isSameVal (TreeNode *root1, TreeNode *root2) {
    if (root1 == NULL && root2 == NULL) return true;
    if (root1 == NULL || root2 == NULL) return false;
    bool ret = false;
    if (root1->val == root2->val) {
    ret = isSameVal(root1->left, root2->right) && isSameVal(root1->right, root2->left);
    } else return false;
    return ret;
    }
    bool isSymmetric(TreeNode* root) {
    if (root == NULL) return true;
    if (root->left == NULL && root->right == NULL) return true;
    if (root->left == NULL || root->right == NULL) return false;
    return isSameVal(root->left, root->right);
    }
    };

题目 剑指offer 30 包含min函数的栈 【辅助栈(单调栈)】+1

  • 时间: 7月19日

  • 难度: 简单

  • 心得: 这道题的解法挺新颖的。本题的难点在于,返回min的时候,时间复杂度要求是O(1)。如果只是单纯维护一个变量min保存最小值,每次有新的元素被Push进来时就对min进行更新,会存在一个问题,就是当pop出去的刚好是min对应的值时,pop之后就没办法在O(1)时间内再次确定min的值了。本题采用的方法是维护一个辅助栈,专门保存最小值,详见代码。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class MinStack {
    public:
    /** initialize your data structure here. */
    stack<int> s_data, s_min;
    MinStack() {

    }

    void push(int x) {
    s_data.push(x);
    if (s_min.empty()) s_min.push(x);
    else if (x <= s_min.top()) s_min.push(x);
    }

    void pop() {
    if (s_data.top() == s_min.top()) s_min.pop();
    s_data.pop();
    }

    int top() {
    return s_data.top();
    }

    int min() {
    return s_min.top();
    }
    };

    /**
    * Your MinStack object will be instantiated and called as such:
    * MinStack* obj = new MinStack();
    * obj->push(x);
    * obj->pop();
    * int param_3 = obj->top();
    * int param_4 = obj->min();
    */

题目 剑指offer35 复杂链表的复制 【哈希 链表 指针】+1

  • 时间: 7月26日

  • 难度: 中等

  • 心得:

    1. 方法一 哈希表

      利用哈希表的查询特点,考虑构建 原链表节点新链表对应节点 的键值对映射关系,再遍历构建新链表各节点的 nextrandom 引用指向即可。

    2. 方法二 拼接与拆分

      考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表,如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。

  • 代码:

    方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
    Node* copyRandomList(Node* head) {
    if(head == nullptr) return nullptr;
    Node* cur = head;
    unordered_map<Node*, Node*> map;
    // 3. 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
    while(cur != nullptr) {
    map[cur] = new Node(cur->val);
    cur = cur->next;
    }
    cur = head;
    // 4. 构建新链表的 next 和 random 指向
    while(cur != nullptr) {
    map[cur]->next = map[cur->next];
    map[cur]->random = map[cur->random];
    cur = cur->next;
    }
    // 5. 返回新链表的头节点
    return map[head];
    }
    };

    方法二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
    public:
    Node* copyRandomList(Node* head) {
    if(head == nullptr) return nullptr;
    Node* cur = head;
    // 1. 复制各节点,并构建拼接链表
    while(cur != nullptr) {
    Node* tmp = new Node(cur->val);
    tmp->next = cur->next;
    cur->next = tmp;
    cur = tmp->next;
    }
    // 2. 构建各新节点的 random 指向
    cur = head;
    while(cur != nullptr) {
    if(cur->random != nullptr)
    cur->next->random = cur->random->next;
    cur = cur->next->next;
    }
    // 3. 拆分两链表
    cur = head->next;
    Node* pre = head, *res = head->next;
    while(cur->next != nullptr) {
    pre->next = pre->next->next;
    cur->next = cur->next->next;
    pre = pre->next;
    cur = cur->next;
    }
    pre->next = nullptr; // 单独处理原链表尾节点
    return res; // 返回新链表头节点
    }
    };

题目 剑指offer 38 字符串的排列 【递归 避免重复元素】+1

  • 时间: 7月27日

  • 难度: 中等

  • 心得: 此题需要注意的是,字符串中可能存在重复的字符,而最后的输出结果中不能存在重复的字符串。如果初始字符串中没有重复字符,可以维护一个visited数组标志各个字符是否被访问过,然后dfs,很显然,如果初始字符串中存在重复字符的话,这种方法的输出中会存在相同的字符串。所以考虑将visited数组更换为一个哈希表,哈希表中维护的是目前还没有被使用过的各个字符的数量。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
    public:
    vector<string> vec;
    void func(unordered_map<char, int> char_left, string s, string str) {
    if (str.size() == s.size()) {
    vec.push_back(str);
    return;
    }
    unordered_map<char, int>::iterator it, itt;

    for (it = char_left.begin(); it != char_left.end(); it++) {
    if (it->second == 0) continue;
    char_left[it->first]--;
    str += it->first;
    func(char_left, s, str);
    char_left[it->first]++;
    str = str.substr(0, str.size() - 1);
    }
    }
    vector<string> permutation(string s) {
    int size = s.size();
    unordered_map<char, int> char_left;
    for (int i = 0; i < size; i++) {
    if (char_left.find(s[i]) == char_left.end()) {
    char_left[s[i]] = 1;
    } else char_left[s[i]]++;
    }
    string str = "";
    func(char_left, s, str);
    return vec;
    }
    };

题目 剑指offer 40 最小的K个数 【快排 多解 思维】+1

  • 时间: 7月27日

  • 难度: 简单

  • 心得: 这道题虽然简单,但是很有意思,而且寻找前K大/前K小的这类题目很经典,我们不妨来探索一下这道题目的多种解法。

    1. 方法一:偷懒sort法

      最朴实无华的解法,就是直接用sort函数对所有元素进行排序,然后取出前k个。这种方法耗时32ms,内存占用18.7M。时间复杂度nlogn,显然还有优化空间。

    2. 方法二:快排法

      在快速排序中,我们会使用第一个元素作为pivot,最后使得pivot元素前面的元素都比pivot小,后面的元素都比pivot大。我们将pivo元素的下标记为j,如果j刚好等于k,那么pivot前面的元素即为所求。如果j > k,我们就对[0, j - 1]的元素再次进行快排,如果j > k,就对j后面的元素进行快排。时间复杂度为N +N/2 + N/4 + N/N = O(N)。每次快排都会舍弃掉一半的无用元素,提高了时间复杂度,这种方法耗时1ms,内存占用39.4M。时间效率提升明显。

    3. 方法三:简单好用法

      直接看代码就能明白,这种方法虽然简单,但是运行耗时只有2ms,原本以为是空间换时间,但是内存占用同样为39.4M。

  • 代码:

    方法二:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0 || arr.length == 0) {
    return new int[0];
    }
    // 最后一个参数表示我们要找的是下标为k-1的数
    return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
    // 每快排切分1次,找到排序后下标为j的元素,如果j恰好等于k就返回j以及j左边所有的数;
    int j = partition(nums, lo, hi);
    if (j == k) {
    return Arrays.copyOf(nums, j + 1);
    }
    // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
    return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分,返回下标j,使得比nums[j]小的数都在j的左边,比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
    int v = nums[lo];
    int i = lo, j = hi + 1;
    while (true) {
    while (++i <= hi && nums[i] < v);
    while (--j >= lo && nums[j] > v);
    if (i >= j) {
    break;
    }
    int t = nums[j];
    nums[j] = nums[i];
    nums[i] = t;
    }
    nums[lo] = nums[j];
    nums[j] = v;
    return j;
    }
    }

    方法三:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0 || arr.length == 0) {
    return new int[0];
    }
    // 统计每个数字出现的次数
    int[] counter = new int[10001];
    for (int num: arr) {
    counter[num]++;
    }
    // 根据counter数组从头找出k个数作为返回结果
    int[] res = new int[k];
    int idx = 0;
    for (int num = 0; num < counter.length; num++) {
    while (counter[num]-- > 0 && idx < k) {
    res[idx++] = num;
    }
    if (idx == k) {
    break;
    }
    }
    return res;
    }
    }

题目 剑指offer 42 连续子数组的最大和 【动态规划】+1

  • 时间: 7月28日

  • 难度: 简单

  • 心得:

    这道题居然是简单题。。

    当一个窗口的两个边界都不太好确定时,不妨只去考虑其中一个 边界

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public int maxSubArray(int[] nums) {
    int res = nums[0];
    for(int i = 1; i < nums.length; i++) {
    nums[i] += Math.max(nums[i - 1], 0);
    res = Math.max(res, nums[i]);
    }
    return res;
    }
    }

题目 剑指offer 45 把数组排成最小的数 【排序】+1

  • 时间: 7月28日

  • 难度: 中等

  • 心得: 这道题其实是排序,我们只要定义好排序规则,其他的就交给sort函数来完成就可以了。需要注意的是,一开始我写的cmp函数没有加static,就收到报错reference to non-static member function must be called。看下手册可以知道其实我们写参数cmp时,是把函数名作为实参传递给了sort函数,而sort函数内部是用一个函数指针去调用这个cmp函数的,我们知道class普通类成员函数cmp需要通过对象名.cmp()来调用,而sort()函数早就定义好了,那个时候哪知道你定义的是什么对象,所以内部是直接cmp()的,那你不加static时,去让sort()直接用cmp()当然会报错

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
    static bool cmp(int a, int b) {
    string ab = to_string(a) + to_string(b);
    string ba = to_string(b) + to_string(a);
    return ab < ba;
    }

    string minNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end(), cmp);
    string str = "";
    for (int i = 0; i < nums.size(); i++) {
    str += to_string(nums[i]);
    }
    return str;
    }
    };

题目 剑指offer 46 把数字翻译成字符串 【动态规划】+1

  • 时间: 7月29日

  • 难度: 中等

  • 心得: 这道题做出来了感觉很有成就感,感觉到自己的水平有所提高了。做完后再思考,这道题其实就是有条件的青蛙跳格子问题。编写递归函数func(int index),其值为从数字的第index位(包含第index位)开始的后面的数字中,可能的翻译数量。递归过程中,总是把index定位在距离起点最近的那个可以组合成字母的数字的位置,即定位在第一个index位和index + 1位可以组合成字母的位置。当index后面不再有两个数字可以组合成字母时,返回1。递推式为func(index) = func(index + 1) + func(index + 2),index位和index + 1位可以组合成字母,我们暂且称之为复合字母,func(index + 1)表示不翻译复合字母的情况下,后续数字的翻译数,func(index + 2)表示翻译复合字母的情况下,后续数字的翻译数。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
    public:
    unordered_map<int, int> str_num;
    string str;

    int func(int index) {
    if (str_num.find(index) != str_num.end()) return str_num[index];
    stringstream ss;
    int temp;
    int no_num_flag = true;
    int i;
    for (i = index; i < str.size() - 1; i++) {
    ss << str.substr(i, 2);
    ss >> temp;
    ss.clear();
    if (temp <= 25 && str[i] != '0') {
    no_num_flag = false;
    break;
    }
    }
    if (no_num_flag) {
    str_num[index] = 1;
    return 1;
    }
    int res = func(i + 1) + func(i + 2);
    str_num[index] = res;
    return res;
    }

    int translateNum(int num) {
    str = to_string(num);
    return func(0);
    }
    };

题目 剑指offer 47 礼物的最大值 【二维动态规划】+1

  • 时间: 7月30日

  • 难度: 中等

  • 心得: 一开始用的递归,时间复杂度是2^(m + n),结果超时了。看了解析后正确解法是二维动态规划。image-20210730224455044

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public int maxValue(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for(int i = 0; i < m; i++) {
    for(int j = 0; j < n; j++) {
    if(i == 0 && j == 0) continue;
    if(i == 0) grid[i][j] += grid[i][j - 1] ;
    else if(j == 0) grid[i][j] += grid[i - 1][j];
    else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
    }
    }
    return grid[m - 1][n - 1];
    }
    }

题目 剑指offer 49 丑数 【动态规划】+1

  • 时间: 8月7日

  • 难度: 中等

  • 心得:

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
    int nthUglyNumber(int n) {
    int a = 0, b = 0, c = 0;
    int dp[n];
    dp[0] = 1;
    for(int i = 1; i < n; i++) {
    int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
    dp[i] = min(min(n2, n3), n5);
    if(dp[i] == n2) a++;
    if(dp[i] == n3) b++;
    if(dp[i] == n5) c++;
    }
    return dp[n - 1];
    }
    };

题目 剑指offer 55 二叉树的深度 【DFS】+1

  • 时间: 8月12日

  • 难度: 简单

  • 心得: 题解的解法简洁巧妙,就记录下来

  • 代码:

    我自己的方法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
    int g_depth = 0;
    void func(TreeNode* root, int depth) {
    g_depth = ++depth > g_depth ? depth : g_depth;
    if (root->left != NULL) func(root->left, depth);
    if (root->right != NULL) func(root->right, depth);
    }

    int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    func(root, 0);
    return g_depth;
    }
    };

    题解的方法:

    1
    2
    3
    4
    5
    6
    class Solution {
    public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
    }

题目 剑指offer 56 数组中数字出现的次数 【分组位运算】+1

  • 时间: 8月14日

  • 难度: 中等

  • 心得:

    注意:第八行的&要加括号,因为==优先级高于&

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
    vector<int> singleNumbers(vector<int>& nums) {
    int ret = 0;
    for (int n : nums)
    ret ^= n;
    int div = 1;
    while ((div & ret) == 0)
    div <<= 1;
    int a = 0, b = 0;
    for (int n : nums)
    if (div & n)
    a ^= n;
    else
    b ^= n;
    return vector<int>{a, b};
    }
    };

题目 剑指offer 59 队列的最大值 【辅助队列】+1

  • 时间: 8月18日

  • 难度: 中等

  • 心得: 本题与剑指offer第30题类似,30题是要构造一个minStack,方法是构造了一个辅助栈用于存放最小值。对于本题,我们只需记住当前最大值出队后,队列里的下一个最大值即可。

    具体方法是使用一个双端队列 deque,在每次入队时,如果 deque 队尾元素小于即将入队的元素 value,则将小于 value 的元素全部出队后,再将 value 入队;否则直接入队

题目 剑指offer 23 两个链表的第一个重合节点+1

  • 时间: 9月9日

  • 难度: 简单

  • 心得: 使用双指针,第一个指针指向第一个链表的头结点,第二个指针指向第二个链表的头结点。两个指针每次都只移动一位。

    • 链表存在交点的情况:如果两个链表的长度相同,那么两个指针会在移动过程中相遇,但是如果两个指针的长度不相同,则他们第一次遍历无法相遇,继续规定第一个指针遍历完第一个链表之后遍历第二个链表,第二个指针遍历完第二个链表之后遍历第一个链表,如此肯定能保证两个指针到达交点的路程相同,则他们会相遇

    • 链表无交点的情况:如果两个链表的长度相同,则两个指针遍历完聊表之后同时指向NULL,可以判断不存在交点。如果两个链表长度不相同则两个指针遍历完各自的链表遍历另一个链表,最后也会同时指向NULL,可以判断不存在交点。

      时间复杂度为O(N),空间复杂度为O(1)

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* p1 = headA;
    ListNode* p2 = headB;
    while (p1 != nullptr || p2 != nullptr) {
    if (p1 == p2) {
    return p1;
    }
    p1 = (p1 == nullptr) ? headB : p1->next;
    p2 = (p2 == nullptr) ? headA : p2->next;
    }
    return nullptr;
    }
    };

题目 剑指offer 59 滑动窗口的最大值 【单调双端队列】+1

  • 时间: 2021.9.15

  • 难度: 困难

  • 心得:

    构造一个deque,deque的首元素永远都是当前窗口中的最大值,并且deque中的元素从前向后是单调递减的(所以叫单调队列)。当此时滑出窗口的元素恰好是deque中的首元素,就将deque首元素出队。一个新元素a进入到滑动窗口后,我们将a不断地与deque末尾的元素进行比较,如果a大于deque末尾元素,就pop掉deque末尾元素,直到a不大于deque末尾元素或者deque为空后,将a从deque末尾push进去。上述核心想法就是,deque中的元素永远都是存在于当前窗口的元素,并且单调递减,当一个新元素进入滑动窗口,需要将deque中小于新元素的元素都出队。

    假如我们要求滑动窗口的最小值,其实思路完全相同,只需要将代码第10行和20行的大于号改成小于号。

    代码中第一个for循环是第一个滑动窗口在形成,第二个for循环是滑动窗口在滑动。ß

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    if (nums.size() == 0) {
    return res;
    }
    deque<int> deq;
    for (int i = 0; i < k; i++) {
    while (!(deq.empty()) && nums[i] > deq.back()) {
    deq.pop_back();
    }
    deq.push_back(nums[i]);
    }
    res.push_back(deq.front());
    for (int i = k; i < nums.size(); i++) {
    if (nums[i - k] == deq.front()) {
    deq.pop_front();
    }
    while (!(deq.empty()) && nums[i] > deq.back()) {
    deq.pop_back();
    }
    deq.push_back(nums[i]);
    res.push_back(deq.front());
    }
    return res;
    }
    };

单调栈

题目402 移掉K位数字

  • 时间: 2021.9.29

  • 难度: 中等

  • 心得:

    • 方法一:类似于下一个排列那道题的解法,我们需要确保删除掉某个元素之后,该元素后面的那个元素比我们删掉的这个元素更小,并且要使得我们删掉的元素尽可能处于高位。具体方法是从前向后遍历,找到相邻的两个元素num[i]和num[j],并且num[i] > num[j],然后将num[i]删除并让k减一。每删除一个元素,就要重新从头开始遍历。当整个数字字符串都不没办法找到符合要求的num[i]和num[j]时,如果k > 0,就将最后的k位删除。然后将剩余字符串的前导0删除。
      这个方法的时间复杂度为O(N^2)
    • 方法二:单调栈。这种方法类似于求滑动窗口最小值的那道题。我们对数字字符串的每一位从前向后入栈,当一个新元素a要入栈前,如果栈顶元素top大于a,就将top弹出,再将下一个top与a比较,直到top小于a后,将a入栈。下面的代码为方法二的代码。这种方法的时间复杂度为O(n)
  • 代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
    public:
    string removeKdigits(string num, int k) {
    if (k >= num.size()) return "0";
    if (num.size() == 1) {
    if (k == 0) return num;
    if (k >= 1) return "0";
    }
    stack<char> s;
    s.push(num[0]);
    int i = 1;
    while (i <= num.size() - 1 && k > 0 && (!s.empty())) {
    while ((!s.empty()) && num[i] < s.top() && k > 0) {
    s.pop();
    k--;
    }
    s.push(num[i++]);
    }
    num.erase(0, i);
    //接上
    while (!s.empty()) {
    char temp = s.top();
    s.pop();
    string ss(1, temp);
    num = ss + num;
    }
    //判断k > 0,删除后面k个
    if (k > 0) {
    num.erase(num.size() - k, k);
    }
    //删除前导0
    i = 0;
    while (num[i] == '0') {
    i++;
    }
    num = num.erase(0, i);
    if (num.size() == 0) return "0";
    return num;
    }
    };

贪心算法

题目 435 无重叠区间

  • 时间: 2021.10.2

  • 难度: 中等

  • 心得: 在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区 间。

    具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选 择的区间不重叠的区间。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.size() == 0) return 0;
    sort(intervals.begin(), intervals.end(), cmp);
    int count = 1; // 记录非交叉区间的个数
    int end = intervals[0][1]; // 记录区间分割点
    for (int i = 1; i < intervals.size(); i++) {
    if (end <= intervals[i][0]) {
    end = intervals[i][1];
    count++;
    }
    }
    return intervals.size() - count;
    }
    };

题目 763 划分字母区间

  • 时间: 2021.10.4

  • 难度: 中等

  • 心得: 贪心算法。我们遍历一遍字符串,然后用一个last[26]数组维护每个字母最后出现的位置。接着我们再次遍历一遍字符串,下面举例:

    上图中横线起始位置分别为某个字母第一次出现和最后一次出现的位置。一开始我们令index = 0,由于a最后一次出现在8位置,所以令end = 8。接着,index递增,当index没有大于end的时候,我们将index新指向的那个字母最后出现的位置与end比较,让end等于两者中更大的。当index等于end时,意味着一个划分结束了,开始一个新的划分。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
    vector<int> partitionLabels(string s) {
    int last[26] = {0};
    for (int i = 0; i < s.size(); i++) {
    last[s[i] - 'a'] = i;
    }
    int end = last[s[0] - 'a'], len = 0;
    vector<int> res;
    for (int i = 0; i < s.size(); i++, len++) {
    if (i <= end) {
    end = end > last[s[i] - 'a'] ? end : last[s[i] - 'a'];
    } else {
    res.push_back(len);
    len = 0;
    end = last[s[i] - 'a'];
    }
    }
    res.push_back(len);
    return res;
    }
    };