Xu an's Web
0%

算法学习记录

发表于 更新于 分类于 Valine：
算法练习记录

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路一、暴力求解

输入所给数组，将其遍历求和，判断其值是否等于目标值，若等于则输出两个数的数组下标。

求解代码如下 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		int n = nums.size();
		for(int i = 0; i < n; ++i){
			for(int j = i + 1; j < n; ++j){
				if(nums[i] + nums[j] == target){
					return {i , j};
				}
			}
		}
	return {};
	}
}

回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

思路：反转一半数字

既然数字为回文数，则可以将其反转一半来判断。

首先考虑一些临界情况。一定不是回文数的有负数及个位数，故首先排除。

再来考虑如何反转后半部分的数字。为得到后半数字，可以进行%10计算，在循环内重组后半数字的顺序。例如对于1221这个数字，先通过/10移除最后一个数字得到122，再求出1221%10得到1。122%10则可以得到倒数第二位数字。如果我们把倒数第一位数字*10再加上倒数第二位数字，则得到了反转后的数字，以此类推。

关键在于如何知道我们已经反转了一半的数字。由于我们不断地将原始数字/10，然后给反转的数字*10，故当原始数字小于等于反转后的数字时，我们就已经处理了一半的数字了。

回文数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
public:
	bool isPalindrome(int x){
		if(x < 0 || (x/10 == 0 && x != 0)){
		return false;
		}
		
		int revertedNumber = 0;
		while (x > revertedNumber){
			revertedNumber = revertedNumber * 10 + x%10;
			x /= 10;
		}
		
		return x == revertedNumber || x == revertedNumber/10
		//若x有奇数个数字，则中间一位并不影响回文数的性质，去掉中间一位即可
	}
}

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

思路：摩尔投票法

核心理念为票数正负抵消。

在本题中，假设数组长度为n，数组的众数为x。

  • 推论一：若记众数的票数为+1，非众数的票数为-1，则所有数字的和一定>0。
  • 推论二：若数组前a个数票数和为0，则剩余（n-a）个数字的众数仍为x。

根据以上推论，当发生票数和=0的时候，剩余数组的众数一定不变，因为：

  • 若 \(n_1\) = x，则已经遍历过的数组中有一半是众数。

  • 若 \(n_1\) != x，则所有抵消过的数字中众数的个数最小是0个，最大是一半。

即按照以上推论，每次出现票数和为零都可以缩小搜索范围，直到遍历完成，最后一个假定的数字即为众数。

多数元素 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;//当票数和为零的时候假设当前数字为众数
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};

区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

思路：归并排序

设前缀和数组为Prenum ，则等价于对所有下标 (i,j)，满足 \[Prenum[j]-Prenum[i]\in(lower,upper)\]

我们先考虑两个升序排列的数组\(n_1\),\(n_2\),试找出所有下标对 (i,j),满足

\[n_1[j]-n_2[i]\in(lower,upper)\]

在已知两个数组为升序排列的情况下，是相对简单的。我们维护两个指针l,r。起初，他们都指向\(n_2\)的起点。

随后，我们首先考察\(n_1\)的第一个元素。首先，不断将指针l向右移动，直到\(n_2[l]-n_1[0]\ge lower\)为止，则此时l右侧的所有元素都满足\(n_2[i]-n_1[0]\ge lower\)；然后，向右移动r，直到\(n_2[r]-n_1[0]\ge upper\)为止，此时r左侧的所有元素都满足\(n_2[r]-n_1[0]\leq upper\)。故l,r区间内的所有元素都满足

\[n_1[j]-n_2[i]\in(lower,upper)\]

至此，由于数组是升序排列的，所以l,r都只需要向右移动，依此来遍历\(n_1\)中的所有元素，每次都统计下标 (l,r) 的大小，我们就得到了区间和的数量。

因此最后需要考虑的就是得到两个升序数组，则使用归并排序对原数组处理得到两个升序数组用于计算。

区间和的个数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int countRangeSumRecursive(vector<long>& sum, int lower, int upper, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
            int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int l = mid + 1;
            int r = mid + 1;
            while (i <= mid) {
                while (l <= right && sum[l] - sum[i] < lower) l++;
                while (r <= right && sum[r] - sum[i] <= upper) r++;
                ret += (r - l);
                i++;
            }

            // 随后合并两个排序数组
            vector<long> sorted(right - left + 1);
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = sum[p2++];
                } else if (p2 > right) {
                    sorted[p++] = sum[p1++];
                } else {
                    if (sum[p1] < sum[p2]) {
                        sorted[p++] = sum[p1++];
                    } else {
                        sorted[p++] = sum[p2++];
                    }
                }
            }
            for (int i = 0; i < sorted.size(); i++) {
                sum[left + i] = sorted[i];
            }
            return ret;
        }
    }

    int countRangeSum(vector<int>& nums, int lower, int upper) {
        long s = 0;
        vector<long> sum{0};
        for(auto& v: nums) {
            s += v;
            sum.push_back(s);
        }
        return countRangeSumRecursive(sum, lower, upper, 0, sum.size() - 1);
    }
};

最大装水

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路：双指针

水箱的面积大小由左右两侧最短板的长度决定，故可以得到以下计算公式：

\[S = min(height[i],height[j]) \times (j -i)\]

设置两个指针分别指向水箱的两个端点，当指针对撞的时候结束计算。

每一次移动指针向内收窄，都会导致底板长度-1，这时面积的变化会有两种可能：

1、将指向较长板的指针向内收窄：由于底的长度一定会减小，而板的最小值的长度一定会减小或者不变，故得到的面积\(S\leq S_{min}\)

2、将指向较短板的指针向内收窄：由于板的最小值只可能变大（下一个最短板的长度大于当前最短板）或不变（即当前最短板的长度等于下一组最短板的长度）。

由此，得到解题算法：比较前后指针所指向的板长，每次将指向较短板的指针向内移动，保存最大面积值，直到指针相撞比较结束，返回最大面积。

最大装水 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

数组中的第k大的元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：快速选择

设N为数组长度，根据快速排序原理，如果某次哨兵划分后，基准数的索引恰好为\(N-k\),则意味着它就是第k大的数字，可以直接返回。

对于包含大量重复数字的数组，每轮的哨兵划分都有可能划分为长度为1，和n-1两个部分，时间复杂度会退化至\(O(n^2)\)。

有一种解决办法是使用三路划分，即每次都把数组划分为大于、小于、等于基准数的三部分。

数组中第k大的元素 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, k);
    }
    
private:
    int quickSelect(vector<int>& nums, int k) {
        // 随机选择基准数
        int pivot = nums[rand() % nums.size()];
        // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        vector<int> big, equal, small;
        for (int num : nums) {
            if (num > pivot)
                big.push_back(num);
            else if (num < pivot)
                small.push_back(num);
            else
                equal.push_back(num);
        }
        // 第 k 大元素在 big 中，递归划分
        if (k <= big.size())
            return quickSelect(big, k);
        // 第 k 大元素在 small 中，递归划分
        if (nums.size() - small.size() < k)
            return quickSelect(small, k - nums.size() + small.size());
        // 第 k 大元素在 equal 中，直接返回 pivot
        return pivot;
    }
};

股票

有一支股票，你只有一股，已知过去N天的股价，只能进行一次买卖，请问你能获得最大利润是多少

（给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。）

思路：找到已经过去的每一天的最小值

在买卖股票的时候，为了获得最高的利润，肯定希望在最低价买入，在最高价卖出。由此，我们可以遍历数组一边，每次记录已遍历的部分的最小值，然后用于计算和数组后面数字的差的最大值。

买卖股票的时机 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

判断一个链表中是否存在一个环

给出一个链表A->B->C->D->E->F->G->D，如何判断是否存在环。

思路：快慢指针

有序三元数组的最大值

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

思路：类似股票问题

和上述买卖股票问题相似，可以先存储（nums[i] - nums[j]）的最大值，然后枚举k得到三元数组的最大值。

有序三元数组的最大值 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long maximumTripletValue(vector<int> &nums) {
        long long ans = 0;
        int max_diff = 0, pre_max = 0;
        for (int x : nums) {
            ans = max(ans, (long long) max_diff * x);
            max_diff = max(max_diff, pre_max - x);
            pre_max = max(pre_max, x);
        }
        return ans;
    }
};

滑动窗口的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

思路：单调队列

通过移动窗口，可以看到每移动一次，队尾向右增加一个数字，队首减少一个数字。每次出队的元素都有可能是最大值，即小于新入队的元素。故想到每次出队入队都将原窗口内的数字和即将入队的数字比较，将最大值存入窗口，将小于最大值的所有元素移出窗口，保证窗口中的第一个元素为当前窗口内的最大值，则整个判断过程只需要遍历一次，时间复杂度为O(1)。

单调队列 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0 || k == 0) return {};
        deque<int> deque;
        vector<int> res(nums.size() - k + 1);
        for(int j = 0, i = 1 - k; j < nums.size(); i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.front() == nums[i - 1])
                deque.pop_front();
            // 保持 deque 递减
            while(!deque.empty() && deque.back() < nums[j])
                deque.pop_back();
            deque.push_back(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.front();
        }
        return res;
    }
    }
};

存在重复元素

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

思路：滑动窗口

由于只需要判断在k范围内是否存在重复元素，故可以使用滑动窗口限制比较的元素的数量。

滑动窗口 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (i > k) {
                s.erase(nums[i - k - 1]);
            }
            if (s.count(nums[i])) {//计算出现的次数
                return true;
            }
            s.emplace(nums[i]);//将元素添加到队列末尾
        }
        return false;
    }
};

序列化分

给定一个正整数序列，将该序列化分为m个连续的子序列，每个子序列至少包含一个元素，要求使得子序列的和的最大值最小。

思路：二分查找

对于整数数列，他的子序列和的最大值的范围为：最小值：序列中单个元素的最大值(即将单个元素划分为子列)；最大值：序列中所有元素的和(即将整个序列划分为子列)，故二分查找的区间为[min,max]。

二分查找是为了更快的实现在子序列的个数已经限定的条件下，找到子序列和的最大值最小的情况。

具体算法： 1、先选取查找区间中点元素作为最大值，判断在该最大值的情况下，序列是否可以划分为要求的m个子序列。若划分个数 n<m ，则说明最大值过大，若 n>m ，则说明最大值取得过小，依此找到题目要求的最大值的最小值。

二分查找 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n, m;
int a[maxn];
int check(int x) {
	int cut = 1;
	int s = a[1];
	for (int i = 2; i <= n; i++) {
		if (s + a[i] <= x) s += a[i];
		else { s = a[i]; cut++; }
	}
	return cut;
}
int bin_search(int l, int r) {
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (check(mid) <= m) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}
int main() {
	int t;
	ll mx, sum;
	cin >> t;
	while (t--) {
		mx = 0, sum = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum += a[i];
			if (mx < a[i])
				mx = a[i];
		}
		int ans = bin_search(mx, sum);

		cout << ans;
	}
	return 0;
}

分裂数组（一）

给定一个整数集合,将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,元素之和分别是S1和S2.设计一个算法满足|n1-n2|最小且|S1-S2|最小.

思路：动态规划

要将一个整数集合划分为两个不相交的子集，使得两个子集的元素个数之差 ∣n1−n2∣ 和元素之和之差 ∣S1−S2∣ 都尽可能小，我们可以利用动态规划的方法来解决这个问题。

具体来说，我们可以使用一个二维动态规划数组 dp[i][j] 来表示：当前集合的前 i 个元素能否被划分为两个子集，使得其中一个子集的和为 j。然后，我们可以进一步记录划分方案，以找到最佳的划分方式。

以下是算法的具体步骤：

初始化动态规划数组：

dp[i][j] 表示前 i 个元素能否划分出和为 j 的子集。

初始化 dp[0][0] = True，表示空集合可以划分出和为 0 的子集。 填充动态规划数组：

遍历集合中的每个元素 num 和每个可能的和 j。

如果 dp[i-1][j] 为 True，那么 dp[i][j+num] 也为 True，表示可以将 num 加入到和为 j 的子集中。 记录划分方案：

使用一个额外的数组来记录每个 j 对应的划分方案中是否包含当前元素 num。 寻找最佳划分：

遍历所有可能的和 j，找到最接近集合总和一半的和，从而确保 ∣S1−S2∣ 最小。 在找到的和附近，寻找元素个数之差 ∣n1−n2∣ 最小的划分。

动态规划 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def min_difference_partition(nums):  
    total_sum = sum(nums)  
    n = len(nums)  
    half_total = total_sum // 2  
      
    # Initialize dp array  
    dp = [[False] * (half_total + 1) for _ in range(n + 1)]  
    dp[0][0] = True  
      
    # Include/Exclude array to keep track of partition  
    include = [[False] * (half_total + 1) for _ in range(n + 1)]  
      
    # Fill dp array  
    for i in range(1, n + 1):  
        for j in range(half_total + 1):  
            if j >= nums[i-1]:  
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]  
                include[i][j] = include[i-1][j] if dp[i-1][j] else include[i-1][j-nums[i-1]]  
            else:  
                dp[i][j] = dp[i-1][j]  
                include[i][j] = include[i-1][j]  
      
    # Find the maximum sum that can be achieved up to half_total  
    max_sum = 0  
    for j in range(half_total, -1, -1):  
        if dp[n][j]:  
            max_sum = j  
            break  
      
    # Trace back to find the partition  
    partition1 = []  
    partition2 = nums[:]  
    current_sum = max_sum  
      
    for i in range(n, 0, -1):  
        if include[i][current_sum]:  
            partition1.append(nums[i-1])  
            current_sum -= nums[i-1]  
        else:  
            partition2.remove(nums[i-1])  
      
    # Calculate results  
    n1, n2 = len(partition1), len(partition2)  
    S1, S2 = sum(partition1), sum(partition2)  
      
    # Optionally, further adjust to balance n1 and n2 if needed  
    # This is an NP-hard problem in general, but here we can do some greedy adjustments  
    # if possible to minimize |n1 - n2| while keeping |S1 - S2| small.  
      
    # However, since we already balanced S1 and S2 optimally, we focus on the best we found.  
      
    return partition1, partition2, n1, n2, S1, S2

N皇后问题

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路：排列型回溯

N皇后问题 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        queens = [0] * n  # 皇后放在 (r,queens[r])
        col = [False] * n
        diag1 = [False] * (n * 2 - 1)
        diag2 = [False] * (n * 2 - 1)
        def dfs(r: int) -> None:
            if r == n:
                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
                return
            # 在 (r,c) 放皇后
            for c, ok in enumerate(col):
                if not ok and not diag1[r + c] and not diag2[r - c]:  # 判断能否放皇后
                    queens[r] = c  # 直接覆盖，无需恢复现场
                    col[c] = diag1[r + c] = diag2[r - c] = True  # 皇后占用了 c 列和两条斜线
                    dfs(r + 1)
                    col[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场
        dfs(0)
        return ans

单词接龙

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk： 每一对相邻的单词只差一个字母。 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。 sk == endWord 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

思路：广度优先搜索

本题要求的是最短转换序列，首先想到的就是广度优先搜索。广度优先搜索自然而然就可以想到图，但题中并没有给出图，所有首先构造一个图。我们把每一个单词都抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边。因此我们只需要把满足转换条件的点相连，就形成了一张图。 基于该图，我们以beginWord为图的起点，以endWord为终点进行广度优先搜索，寻找beginWord到endWord的最短路径。

由于根据给定的字典构造的图可能会很大，而加入每个结点的分支数量相同，搜索空间会随着层数的增长指数级的增加。则考虑使用两个同时进行的广度搜索，这样可以减少搜索空间。一边从beginWord开始，一边从endWord开始，当发现某一时刻两边都访问过同一顶点时就停止搜索。

算法

首先为了方便表示，我们先给每一个单词标号，即给每一个单词分配一个id，创建一个由单词word到id对应的映射wordId,并将beginWord与wordList中所有的单词都加入这个映射中，之后检查endWord是否在该映射内，若不存在则输入无解。

单词接龙 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>> edge;
    int nodeNum = 0;

    void addWord(string& word) {
        if (!wordId.count(word)) {
            wordId[word] = nodeNum++;
            edge.emplace_back();
        }
    }

    void addEdge(string& word) {
        addWord(word);
        int id1 = wordId[word];
        for (char& it : word) {
            char tmp = it;
            it = '*';
            addWord(word);
            int id2 = wordId[word];
            edge[id1].push_back(id2);
            edge[id2].push_back(id1);
            it = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.count(endWord)) {
            return 0;
        }
        vector<int> dis(nodeNum, INT_MAX);
        int beginId = wordId[beginWord], endId = wordId[endWord];
        dis[beginId] = 0;

        queue<int> que;
        que.push(beginId);
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int& it : edge[x]) {
                if (dis[it] == INT_MAX) {
                    dis[it] = dis[x] + 1;
                    que.push(it);
                }
            }
        }
        return 0;
    }
};

平面最近点对

https://oi-wiki.org/geometry/nearest-points/

用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小弓箭数 。

思路：贪心算法

解释题意，就是把这些区间画在数轴上，在数轴上最少要放置多少个点使得每个区间都包含至少一个点。

把区间按照右端点从小到大排序，这样第一个点就放在第一个区间的右端点处。去掉包含第一个点的区间后，第二个点就放在剩余区间的第一个区间的右端点处，以此类推。

引爆气球 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda p: p[1])  # 按照右端点从小到大排序
        ans = 0
        pre = -inf
        for start, end in points:
            if start > pre:  # 上一个点在区间左边
                ans += 1
                pre = end  # 在区间的最右边放一个点
        return ans

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

思路：分类讨论

柠檬水找零 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for b in bills:
            if b == 5:  # 无需找零
                five += 1
            elif b == 10:  # 返还 5
                five -= 1
                ten += 1
            elif ten:  # 此时 b=20，返还 10+5
                five -= 1
                ten -= 1
            else:  # 此时 b=20，返还 5+5+5
                five -= 3
            if five < 0:  # 无法正确找零
                return False
        return True