一些算法题套路

最近刷leetcode上瘾，准备刷完一个tag就总结一下基本的写法，长期更新。。。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 前提是数组有序 O(logn)
// 例子:在数组中查找一个数
int binary_search(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    while(left<=right) {
        int mid = left + (right - left) / 2; //防止溢出
        if(nums[mid] == target) { 
            return mid;
        } else if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1; //没找到
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
// 快慢指针：主要对于链表操作，判断是否有环、寻找链表中点，思路比较简单，就不写代码了。
// 左右指针：需要数组有序，从两边到中间，O(n)
// 例子: 反转数组
void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}
## 滑动窗口

1
2
3
4
// 双指针的高阶用法，将嵌套的循环问题，转换为单循环问题，降低时间复杂度。
// 解决各种子串(子数组)问题.
// 核心思想是将满足要求的子串作为窗口在整个数组间移动，一次循环得到结果，O(n)
//