Leetcode-数组的经典题目

一、二分法

1.相关题目

• 704.二分查找
• 35.搜索插入位置
• 34.在排序数组中查找元素的第一个和最后一个位置
• 69.x 的平方根
• 367.有效的完全平方数

(1)704.二分查找

class Solution {
  public int search(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
}

总结

二分法前提：数组为有序数组，无重复元素。
循环不变量规则：
区间是左闭右开时，while(left < right)，if (nums[middle] > target) right 更新为 middle
区间是左闭右闭时，while (left <= right) ，if (nums[middle] > target) right 要赋值为 middle - 1

(2)35.搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0,r=nums.length-1,m=(l+r)/2;
        while(l<=r){
            m=(l+r)/2;
            if(nums[m]>target){
                r=m-1;
            }else if(nums[m]<target){
                l=m+1;
            }else{
                return m;
            }
        }
        return l;
    }
}

总结

经典二分法

(3)34.在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int n = nums.length;
        if (n == 0) return ans;

        int l = 0, r = n - 1;
        while (l < r) { 
            int mid =( l + r ) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return ans;
        } else {
            ans[0] = l;
            l = 0; r = n - 1;
            while (l < r) {
                int mid =( l + r + 1 ) / 2;
                if (nums[mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            } 
            ans[1] = l;
            return ans;
        }
    }
}

总结

看了题解后发现还是用的二分法，但是思路挺巧妙的。由于二分是从中间开始找起的，所以找的必然是条件区间中靠近中心的的边界值。

(4)69.x 的平方根

class Solution {
    public int mySqrt(int x) {
       // double t=Math.sqrt(x);
       // return (int)t;
       //二分法
       int l=0,r=x;
       int ans=0;//记录平方根的值
       while(l<=r){
           int mid=l+(r-l)/2;
           if((long)mid*mid<=x){
               ans=mid;
               l=mid+1;
           }else{
               r=mid-1;
           }
       }
       return ans;
    }
}

总结

刚开始用了sqrt,但是这个题目是想让大家自己实现，有多种方法，二分法有一个注意点，(long)mid*mid<=x,l=mid+1,是小于号，搜索出来的值是较小的左值，相当于取整后。

(5)367.有效的完全平方数

class Solution {
    public boolean isPerfectSquare(int num) {
        int l=0,r=num;
        int ans=0;//记录平方根的值
        while(l<=r){
            int mid=l+(r-l)/2;
            if((long)mid*mid<=num){
               ans=mid;
               l=mid+1;
            }else{
               r=mid-1;
            }
        }
        if(ans*ans==num) return true;
        else return false;
    }
}

总结

和上个题一样，稍微修改下返回值即可。

二、双指针法

1.相关题目

• 27.移除元素
• 26.删除排序数组中的重复项
• 283.移动零
• 844.比较含退格的字符串
• 977.有序数组的平方

(1)27.移除元素

class Solution {
    public int removeElement(int[] nums, int val) {
        int index=0;
    for(int i=0;i<nums.length;i++){
         if(nums[i]!=val){
             nums[index++]=nums[i];
         }
        }
        return index;
    }
}

总结

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
与26. 删除排序数组中的重复项类似，如果当前元素 x 与移除元素 val 相同，那么跳过该元素。如果当前元素 x 与移除元素 val 不同，那么我们将其放到下标 index 的位置，并让 index 自增右移。最终得到的 index 即是答案。
暴力：两层for循环，第二层for循环时，遇到相同数值，则将此元素之后的数前移一位。

(2)26.删除排序数组中的重复项

//暴力
class Solution {
    public int removeDuplicates(int[] nums) {
        int s=nums.length;
        for(int i=0;i<s;i++){
            for(int j=i+1;j<s;j++){
                if(nums[i]==nums[j]){
                    for(int t=j+1;t<s;t++){
                        nums[t-1]=nums[t];
                    }
                    j=j-1;
                    s--;    
                }
            }
        }
        return s;
    }
}

//双指针法
class Solution {
    public int removeDuplicates(int[] nums) {
        int s=nums.length;
        int slow=0;
        for(int fast=0;fast<s-1;fast++){
            if(nums[fast]!=nums[fast+1]){
                nums[++slow]=nums[fast+1];
            }
        }
        return slow+1;
    }
}

总结

假设数组nums的长度为s。将快指针fast 依次遍历从0到s-1的每个位置，对于每个位置，如果nums[fast]!=nums[fast+1]，说明fast和之后的元素都不同，因此将nums[fast+1]的值复制到 nums[slow]，然后将 slow 的值加 1，即指向下一个位置。

(3)283.移动零

(4)844.比较含退格的字符串

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;//指向末尾
        int skipS = 0, skipT = 0;//记录#个数

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

总结

key:#只会消除左边元素，对右边是没有影响的。所以从数组末尾开始判断。
题解

(5)977.有序数组的平方

class Solution {
    public int[] sortedSquares(int[] nums) {
        //双指针，比较谁大，把较大的数逆序放入位置pos
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
}

总结

双指针，比较谁大，把较大的数逆序放入位置pos

三、滑动窗口

1.相关题目

• 209.长度最小的子数组
• 904.水果成篮
• 76.最小覆盖子串

(1)209.长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //利用滑动窗口思想
        int sum=0;
        int index=0;//相当于是慢指针
        int result=999999;
        for(int j=0;j<nums.length;j++){//快指针
            sum+=nums[j];
            while(sum>=target){//注意是while
                int l=j-index+1;
                result=result<=l?result:l;
                sum-=nums[index++];//key
            }
        }
        if(result==999999) result=0;
        return result;
    }
}

总结

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

(2)904.水果成篮

class Solution {
    public int totalFruit(int[] tree) {
        if (tree == null || tree.length == 0) return 0;
        int n = tree.length;

        Map<Integer, Integer> map = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int i = 0; i < n; i++) {
            map.put(tree[i], map.getOrDefault(tree[i], 0) + 1);  // 右边界
            while (map.size() > 2) {  // 不符合条件：水果种类大于2
                map.put(tree[left], map.get(tree[left]) - 1);
                if (map.get(tree[left]) == 0) map.remove(tree[left]); 
                left++;  // 左边界
            }
            maxLen = Math.max(maxLen, i - left + 1); // 更新结果
        }
        return maxLen;
    }
}

总结

用HashMap，Map<水果种类，出现频次>，延伸右边界时，增加频次。缩进左边界时，减少频次。频次为0时，从map删除。
getOrDefault(Object key, V defaultValue)，当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue。

(3)76.最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
    int[] map = new int[128];
    //记录字符串t中每个字符的数量
    for (char ch : t.toCharArray())
        map[ch]++;
    //字符串t的数量
    int count = t.length();
    int left = 0;//窗口的左边界
    int right = 0;//窗口的右边界
    //覆盖t的最小长度
    int windowLength = Integer.MAX_VALUE;
    //覆盖字符串t开始的位置
    int strStart = 0;
    while (right < s.length()) {
        if (map[s.charAt(right++)]-- > 0)
            count--;
        //如果全部覆盖
        while (count == 0) {
            //如果有更小的窗口就记录更小的窗口
            if (right - left < windowLength) {
                windowLength = right - left;
                strStart = left;
            }
            if (map[s.charAt(left++)]++ == 0)
                count++;
        }
    }
    //如果找到合适的窗口就截取，否则就返回空
    if (windowLength != Integer.MAX_VALUE)
        return s.substring(strStart, strStart + windowLength);
    return "";
    }
}

总结

这道题目注意，在目标字符串中字母是可以重复的，最后结果是唯一的。

四、模拟行为

1.相关题目

• 59.螺旋矩阵II
• 54.螺旋矩阵
• 剑指Offer 29.顺时针打印矩阵

(1)59.螺旋矩阵II

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums=new int[n][n];
        int left=0,right=n-1,top=0,down=n-1;
        int begin=1,end=n*n;
        while(begin<=end){
            for(int i=left;i<=right;i++){
                nums[top][i]=begin++;
            }
            top++;
            for(int i=top;i<=down;i++){
                nums[i][right]=begin++;
            }
            right--;
            for(int i=right;i>=left;i--){
                nums[down][i]=begin++;
            }
            down--;
            for(int i=down;i>=top;i--){
                nums[i][left]=begin++;
            }
            left++;
        }     
        return nums;
    }
}

总结

(2)54.螺旋矩阵

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0)
    		return list;
        int m = matrix.length;//行数
        int n = matrix[0].length;//列数
        int i = 0; 

        //统计矩阵从外向内的层数，如果矩阵非空，那么它的层数至少为1层
        int count = (Math.min(m, n)+1)/2;
        //从外部向内部遍历，逐层打印数据
        while(i < count) {
        	for (int j = i; j < n-i; j++) {//从左到右
				list.add(matrix[i][j]);
			}
        	for (int j = i+1; j < m-i; j++) {//从上到下
				list.add(matrix[j][(n-1)-i]);
			}
        	
        	for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--) {//从右到左
				list.add(matrix[(m-1)-i][j]);
			}
        	for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {//从下到上
				list.add(matrix[j][i]);
			}
        	i++;
        }    
        return list;
    }


}

总结

将矩阵从外部向内部逐层遍历打印矩阵，最外面一圈打印完，里面仍然是一个矩阵。
m - 1 - i 是指随着层数增加时，层数的边界所在行（即最上行和最下行的所处的行数），如果出现最上行和最下行是同一行的情况（比如：3行5列的矩阵中，第二层是1行3列的矩阵），此时按顺序打印完第二层第一行后，第一列为空，不打印，折返后如果没有（m - 1 - i != i）这个限制，会重新打印第二层的第一行，造成结果的值变多。同理可得，n - 1 - i != i。

(3)29.顺时针打印矩阵

class Solution {
    public int divide(int dividend, int divisor) {
        long x = dividend, y = divisor;
        boolean isNeg = false;
        if ((x > 0 && y < 0) || (x < 0 && y > 0)) isNeg = true;
        if (x < 0) x = -x;
        if (y < 0) y = -y;
        long l = 0, r = x;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (mul(mid, y) <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        long idx = isNeg ? -l : l;
        if (idx > Integer.MAX_VALUE || idx < Integer.MIN_VALUE) return Integer.MAX_VALUE;
        return (int)idx;
    }
    long mul(long a, long k) {
        long ans = 0;
        while (k > 0) {
            if ((k & 1) == 1) ans += a;
            k >>= 1;
            a += a;
        }
        return ans;
    }
}

总结

二分法+快速乘法模板
快速乘法使用二进制将乘法转化为加法，既加快可以加快运算速度，又可以防止直接相乘之后溢出