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日
  • 难度: 中等
  • 心得: 简单的滑动窗口

二分查找

二分查找也称折半查找(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);
    }
    };