LeetCode

LeetCode-方法论-数组相关-一

与数组相关的问题是最常出现的问题。
这篇笔记记录问题编号：
283, 167, 209, 75, 11, 125, 3

敲黑板
常用技术：

  • 计数排序，当元素种类较小时使用
  • 对撞指针，当数据元素有序时使用
  • 滑动串口，注意此窗口大小不一定固定
  • 图示简化实现，有些情况下，画好了中间过程的图示，实现起来就像看图说话
  • 循环不变量，保证程序正确性，并且使图示简化实现成为可能
  • 更新记录，更新循环中的每一步结果
  • 跳过，
  • 频数记录，技巧 记录频数
  • 大条件先满足，在if语句中，大小条件一定要在小条件之前

实现时的注意：

  • 对边界的正确处理，明确循环不变量的定义且需要始终维护。
  • 使用小数据集调试，先保证算法的正确性。
  • 应尽量减少代码量，合并可以合并的，删掉无用的。经验上讲，同一个算法，代码量越多越容易出错。
  • 先由算法过程，后实现，不要上来就实现。

#283 Move Zeros

  • 描述：给出一个序列，将所有0元素移动到序列尾部，并且其他元素相对位置不变。

    1
    2
    Input: [0,1,0,3,12]
    Output: [1,3,12,0,0]

  • 思路一：

    如图，整个过程保持[0,..,k)中元素非零。遍历结束后，将k及其以后的元素值设为0。就得到最后值。

    时间复杂度：O(N)
    空间复杂度：O(1)

  • 思路二：

    将思路一中，当nums[i]!=0时，的执行改为 swap(nums[i], nums[k++])。如此不需要思路一的最后一步。

    时间复杂度：O(N)
    空间复杂度：O(1)

  • 实现见这里，的对应文件。

关键：协调两指针

#167 Two Sum II 对撞指针

  • 问题描述：

    1
    2
    Input: numbers = [2,7,11,15], target = 9
    Output: [1,2]

    当数组有序时使用对撞指针。
    number[0+1] + number[1+1] = target.

  • 思路：

    一个指针`i`从左端向右，另一个指针`j`从右端向左。
如果`number[i] + mumber[j] = target` 时，返回对应的`i+1, j+1`。
如果`number[i] + number[j] < target`, 说明`number[i]`小，所以`i++`；
如果`number[i] + number[j] > taregt`, 说明`number[j]`大，所以`j--`；

  • 实现见这里，的对应文件。

  • 同类问题：
    345

#209 Minimum Size Subarray Sum 滑动窗口

  • 问题描述：

    1
    2
    3
    Input: s = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: the subarray [4,3] has the minimal length under the problem constraint.

  • 思路

    设置窗口左右端，并且初始化：

    1
    2
    3
    int  l=0, r=-1  //始终保证nums[l,...,r]为滑动窗口，初始化为空
    int sum = 0;
    int res = nums.size()-1  // 结果设置为可能的最大值

    然后窗口向右移动，移动过程中要判断两次：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(l < nums.size()){
        // 第一次判断
        if (r+1 < nums.size() && sum < s)
            sum += nums[++r];
        else
            sum -= nums[l++];

        // 第二次判断
        if (sum>s)
            res = min(res, r-l+1);  // 更新结果
    }

    循环中:

    第一次判断:
    如果r没有到头，且sum小于s：则r右移，sum加上此时的nums[r]。
    如果r到最右边，或sum大于等于s：则Sum减去nums[l]，且l右移。
第二次判断:
    如果sum大于等于s，
    结果res取这次res和上次res的最小值。

最后一步，判断，如果res扔等于初始值，即没有发生变化，则表示sum中所有元素和都小于s。返回0.

    第一次判断的两种情况：

关键：图示简化实现，循环不变量，更新记录，滑动窗口，大条件先满足

#75 Sort Colors 三路快排

  • 问题描述：

    1
    一个数组由n个元素，元素只有0,1,2三种数值，为这个数组排序

  • 思路

    1. 思路一： 计数排序

      先统计每个数值出现过多少次，之后从小到大将对应的值放入元素组，放入多少个呢，放入对应数值出现的次数个。实现：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      void sortColor(vector<int>& nums){
          int count[3] = {0,0,0};   
          if (nums.size() == 0)
              return;

          // 记录每个数值出现的频数
          for (int i=0; i<nums.size(); i++){
              count[nums[i]]++;
          }

          // 挨个儿放入元素组
          int index = 0;
          for (int i=0; i<count[0]; i++)
              nums[index++] = 0;
          for (int i=0; i<count[1]; i++)
              nums[index++] = 1;
          for (int i=0;i<count[2]; i++)
              nums[index++] = 2;
      }

      很容易理解。

    2. 思路二： 三路快排

      初始化函数操作，

      1
      2
      3
      void sortColors(vector<int>& nums){
          int zero = -1;         // 定义[0,...,zero] 的元素为0
          int two = nums.size();   // 定义[two,...,n-1] 的元素为 3

      明确循环不变量的定义 zero：数组中元素为0的最后一个index，two：数组中元素为2的第一个index。

      之后执行如下图的操作：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
          for (int i=0; i<two; ){
              if(nums[i] == 1)
                  i++;
              else if(nums[i] == 2)
                  swap(nums[--two], nums[i] );
              else {
                  assert( nums[i] == 0 );
                  swap(nums[++zero], nums[i++]);
              }
          }
      }

关键：图示简化实现，循环不变量

#11 Container With Most Water 对撞指针

  • 问题描述：

    1
    2
    3
    4
    The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. 

    Input: [1,8,6,2,5,4,8,3,7]
    Output: 49

  • 思路(无序数组求最值)：

    两指针分别从数组首位处开始，两个指针向中间移动，两指针的距离为宽，两指针对应的数值的较小值为高度，要最大化宽度x高度。注意两指针相互靠近，所以宽度是单调减小的，所以，要想记录最大值，就要跳过高度减小的值，即i++和j++。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int maxArea(vector<int>& height){
        // 初始化时，宽度是最大的
        int maxWater = 0;
        int i=0;
        int j=height.size()-1;

        // 开始对撞
        while(i<j){
            int h = min(height[i], height[j]);
            maxWater = max(maxWater, h*(j-i));  // 每次循环，更新最大值
            while(height[i]<=h && i<j) i++;   // h减小了，所以跳过
            while(height[j]<=h && i<j) j--;   // 跳过
        }
        return maxWater;
    }

    关键：两指针对撞，跳过，更新记录

#125 PalineDrome 判断是否是回文

  • 问题描述：

    1
    2
    3
    Input: "A man, a plan, a canal: Panama"
    Output: true
    Note: For the purpose of this problem, we define empty string as valid palindrome.

  • 实现：

    1
    2
    3
    4
    5
    6
    7
    8
    bool isPalindrome(string s) {
        for(int l = 0,r=s.length()-1;l<r; l++,r-- ){
            while(isalnum(s[l])==false && l<r) l++;  //跳过 non alnum
            while(isalnum(s[r])==false && l<r) r--;  //跳过 non alnum
            if(tolower(s[l]) != tolower(s[r])) return false;
        }
        return true;
    }

关键：两指针对撞，跳过，常用字符串函数

#3 Longest Substring Without Repeating Charactors 最长无重复子串

  • 描述

    1
    2
    3
    4
    Input: "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3. 
                Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

  • 思路见图示：

  • 看图说话：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};   // 记录频数

        int l = 0;    // 滑动窗口保证s[l,...,r]始终无重复字符，初始化为空 
        int r = -1;
        int res = 0;  

        while (l < s.size()){

            if (r+1<s.size() && freq[s[r+1]] == 0){
                r++;
                freq[s[r]] ++;
            }
            else {   // r is out of bound || freq[r+1] == 1
                freq[s[l]] --;
                l++;
            }

            res = max(res, r-l+1);   // 更新结果
        }
        return res;
    }

关键：图示简化实现，循环不变量，更新记录，记录频数，滑动窗口，大条件先满足

敲黑板想要思维升级，就需要见足够多的问题类型，每种类型见过并解决不止一遍。只见过一遍就像完全掌握，是不实际的。见得多了，自然大脑就接受了，思维就升级了。另外一点，“回头看”会把之前不明白或者不能接受的问题“回锅”，可以增强大脑对这个问题的接纳程度。