LeetCode

关于老年退役 OIer 竟然忘光光所有的算法和数据结构，然后从所有 OIer 和 ACMer 都看不起的 LeetCode 开始学习算法和数据结构的故事。

二分

算法模板

为什么不是具体分析而是二分模板呢，因为具体分析太乱了，left right 的范围，while 循环结束的条件，每一次 mid 判断之后，left 和 right 变化的过程。每一道题目都不一样，所以二分还是要这样写：

1
2
3
4
5
6
7
8
while(left+1<right) { //推出循环条件就是 left+1==right
    mid=left+(right-left)/2;
    if(nums[mid]>target) right=mid;
    else left=mid;
}
//退出循环之后，需要的答案就在 left 或者 right 里面，只需要对他们两个进行判断就好了
if(XXX) XXX; // 单独判断 left
if(XXX) XXX; // 单独判断 right

算法题目

都很简单就不搞了。

双指针

算法模板

没有模板。

旋转数组

题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

  • 输入: nums = [1,2,3,4,5,6,7], k = 3
  • 输出: [5,6,7,1,2,3,4]

要求使用空间复杂度为 O(1) 的算法。

题解一

我们观察 [1,2,3,4,5,6,7] 变为 [5,6,7,1,2,3,4] 的过程，是将原来的顺序的数组拆分成了两个部分 [5,6,7] 和 [1,2,3,4] 两个部分。我们将这个两个部分进行反转，变成 [7,6,5] 和 [4,3,2,1] 。结合在一起就变成了原数组的反转。

所以我们可以利用这个过程的逆过程来求数组右移的结果，也就是三次反转：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class P0189 {
    public static void rotate(int[] nums,int k) {
        k=k%nums.length;
        trunOver(nums, 0, nums.length-1); //整体翻转
        trunOver(nums, 0, k-1); //前一块翻转
        trunOver(nums, k, nums.length-1); //后一块翻转
    }
    public static void trunOver(int[] nums,int start,int end) {
        int temp;
        for(int i=0;i<(end-start+1)/2;i++) {
            temp=nums[start+i];
            nums[start+i]=nums[end-i];
            nums[end-i]=temp;
        }
    }
}

题解二

这里是一个一个元素置换实现的，至于为什么需要 GCD(n,k) 轮置换才能全部结束，我根本看不懂它是怎么证明的，所以我选择另外一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Method2 {
    public static void rotate(int[] nums,int k) {
        int times=GCD(nums.length, k);
        for(int i=0;i<times;i++) {
            int temp,pre=nums[i],next=i;
            do {
                next=(next+k)%nums.length;
                temp=nums[next];
                nums[next]=pre;
                pre=temp;
            }while(next!=i);
        }
    }
    public static int GCD(int x,int y) {
        return y>0?GCD(y, x%y):x;
    }
}

那就是不计算置换多少轮，而是如果换位置的元素数量小于，则继续置换直到换位置元素数量等于 n 就好了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Method3 {
    public static void rotate(int[] nums,int k) {
        int count=0;
        for(int i=0;count<nums.length;i++) {
            int temp,pre=nums[i],next=i;
            do {
                count++; //使用 count 计数
                next=(next+k)%nums.length;
                temp=nums[next];
                nums[next]=pre;
                pre=temp;
            } while(next!=i);
        }
    }
}