算法汇总

介绍常用的算法

二分查找

有三个关键量，right、left、middle；middle = (right - left)>>1，其中>>为右移运算符，将right - left结果的二进制位向右移一位，>>n右移n位，举个例子

  • 8 - 4 = 4，4的二进制位为0100，右移一位变为0010，代表十进制2。
  • 7 - 2 = 5，5的二进制位为0101，右移一位变为0010，代表十进制2。
    可以看出，右移运算符的作用是将两数相减并向下取整得到结果
    为什么要用右移运算符而不用/2？
  • 右移运算 >> 通常比除法 / 更快，因为位运算是底层硬件直接支持的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (right >= left)
        {
            int middle = left + ((right - left)>>1); //left每一次加上新的中间值
			if (nums[middle]>target){
                right = middle - 1;
            }
            else if (nums[middle]<target){
                left = middle + 1;
            }
            else return middle;
        }
        return -1;
    }

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
采用二分法，注意停止条件，当left>right就停止了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        while (right>=left)
        {
            int middle = left + ((right-left)>>1);
            double p = 1.0*middle*middle;
            if (p==x) return middle;
            if (p<x){
                left = middle+1;
            }
            else right = middle-1;
        }
        return right;
    }
};

滑动窗口法

滑动窗口类似于双指针，用于去求最短子序列

j是终止位置，很像毛毛虫往前拱，吃到了，然后尾巴再上来。
LeetCode 209

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minSubArrayLen(int target, vector<int>& nums) {
        int x = INT32_MAX;
        int i = 0;
        int subLength = 0;
        int sum = 0;
        for (int j = 0;j<nums.size();j++){
            sum+=nums[j];
            while (sum>=target){
                subLength = j - i + 1;
                x = x > subLength ? subLength : x;
                sum-=nums[i++];
            }
        }
        return x == INT32_MAX? 0 : x;
    }

滑动窗口例题2
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence({-2, 1, -3, 4, -1, 2, 1, -5, 4});
//should be 6: {4, -1, 2, 1}
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>
#include <algorithm>

int maxSequence(const std::vector<int>& arr) {
    int left = 0, sum = 0, maxSum = 0;  // 初始化最大和为 0（符合题目要求）
    
    for (int right = 0; right < arr.size(); ++right) {
        sum += arr[right];  // 扩展窗口
        
        maxSum = std::max(maxSum, sum);  // 更新最大子数组和
        
        // 如果当前窗口的和变成负数，移动左指针
        while (sum < 0) {
            sum -= arr[left++];
        }
    }

    return maxSum;
}

关键的一步在while(sum<0),会把之前为负数的窗口给舍弃掉，1 + -3 = -2，-2 -1 = -3，left左移动一位，-3 -（-3） = 0，left左移一位，所以left变成了3；从3又继续开始遍历。

贪心算法

说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
LeetCode455分饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if (g.size()==0||s.size()==0) return 0;
        sort (s.begin(),s.end());
        sort (g.begin(),g.end());
        int i = 0,j = 0;
        while (i<g.size()&&j<s.size()){
            if (g[i]<=s[j]){
                i++;
            }
            j++;
        }
        return i;
    }
};