Posted Updated 算法a few seconds read (About 3 words)

线段树

线段树

Posted Updated 算法3 minutes read (About 461 words)

leetcode727

最小窗口子序列

题目描述

给定字符串 s1 和 s2，找出 s1 中最短的连续 子串，使得 s2 是该子串的 子序列 。

如果 s1 中没有窗口可以包含 s2 中的所有字符，返回空字符串 ""。如果有不止一个最短长度的窗口，返回 开始位置最靠左 的那个。

示例 1

1
2
3
4
5
6
输入：
s1 = "abcdebdde", s2 = "bde"
输出："bcde"
解释：
"bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。
"deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。

示例 2

1
2
输入：s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
输出：""

解题思路

用滑动窗口去做，遍历 s1 串，如果 s2 到了末尾（p2 == l2），进行回溯寻找起点。

代码实现

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
class Solution {
    public String minWindow(String s1, String s2) {
        int l1 = s1.length(), l2 = s2.length();
        int p1 = 0, p2 = 0;
        int min = l1 + 1;
        String res = "";
        while (p1 < l1) {
            if (s1.charAt(p1) == s2.charAt(p2)) {
                p2++;
            }
            if (p2 == l2) {
                int r = p1;
                while (p2 > 0) {
                    if (s1.charAt(p1) == s2.charAt(p2 - 1)) {
                        p2--;
                    }
                    p1--;
                }
                p1++;
                if (r - p1 + 1 < min) {
                    min = r - p1 + 1;
                    res = s1.substring(p1, r + 1);
                }
            }
            p1++;
        }
        return res;
    }
}

注意点

  1. 因为先做 p2++，所以末尾的判断条件是 p2 == l2，而不是 p2 == l2 - 1，此时 p1 还没加 1，还在最后一个字符位置。
  2. 进行回溯后，p1 指向的位置是第一个字符的前一个位置，所以要加 1。
  3. 要维护一个 min 变量，判断这个长度是不是最小的，如果是，就动态更新 res 的值。
  4. 因为 p1 的坐标进行了回溯，最后又加 1 了，所以下一次遍历是从 s1 的下一个字符开始的。s1 确实需要进行遍历，因为要找到最小的子串。
Posted Updated 算法4 minutes read (About 540 words)

leetcode134

加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

解题思路

这是一道贪心问题，用图的思路去解决，重点是利用数组前缀和，让亏损最严重的点最后走。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int minIndex = 0;
        int minValue = Integer.MAX_VALUE;
        int spare = 0;
        for (int i = 0; i < len; i++) {
            spare += gas[i] - cost[i];
            if (spare < minValue) {
                minValue = spare;
                minIndex = i;
            }
        }
        return spare < 0 ? -1 : (minIndex + 1) % len;
    }
}
Posted Updated 算法2 minutes read (About 298 words)

leetcode673

最长递增子序列问题

题目描述

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1

1
2
3
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2

1
2
3
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

代码实现

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
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        int[] gp = new int[len];
        Arrays.fill(dp, 1);
        Arrays.fill(gp, 1);
        int max = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        gp[i] = gp[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        gp[i] += gp[j];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (dp[i] == max) {
                ans += gp[i];
            }
        }
        return ans;
    }
}

总结

正常的求最长递增子序列是两层 for 循环、一个 dp 数组，求个数需要一个额外的 gp 数组，记录当下以 i 为结尾的最长子序列的个数，同时还要维护递增子序列最大值，最后遍历 gp 数组求和。

Categories

Recents

Archives

×