细语呢喃

技术改变生活

0%

leetcode contest 52 solution

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括：

    1. Repeated String Match
    1. Longest Univalue Path
    1. Knight Probability in Chessboard
    1. Maximum Sum of 3 Non-Overlapping Subarrays

686. Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note: The length of A and B will be between 1 and 10000.

题目地址：leetcode Repeated String Match

题意：

给定字符串A和字符串B，问B是A重复几次的字串。（这里的字串是连续的，比如abcd中的ad就不是字串）

思路：

方法一

引用solution的写的很清楚：

Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:] starts with B, as S is long enough to contain B, and S has period at most len(A).

Now, suppose q is the least number for which len(B) <= len(A * q). We only need to check whether B is a substring of A * q or A * (q+1). If we try k < q, then B has larger length than A * q and therefore can't be a substring. When k = q+1, A * k is already big enough to try all positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

翻译过来就是:

B如果是S=AAAA的字串，那么必然有B的长度不大于S。

len(B) <= len(Aq)，只需要查看B是否为 A q 或者A * (q+1)的字串。因为如果尝试的k<q，那么不够长。当k=q+1的时候，A*k已经足够长来包括所有的B了， A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        repeat = (len(B) - 1) // len(A) + 1
        if B in A * repeat: return repeat
        if B in A * (repeat + 1): return repeat + 1
        return -1

方法二

KMP，对B求失配函数，然后匹配A。如果每次A遍历完一次而出现了重复的B中的下标，说明无解。

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(object):
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """

        def get_fail(s):
            f = [0] * (len(s) + 1)
            for i in range(1, len(s)):
                j = f[i]
                while j and s[i] != s[j]: j = f[j]
                if s[i] == s[j]: j += 1
                f[i + 1] = j
            return f

        # kmp
        f = get_fail(B)
        j = 0
        vis = {0}
        cnt = 1
        while True:
            for i in range(len(A)):
                while j and A[i] != B[j]: j = f[j]
                if A[i] == B[j]: j += 1
                if j == len(B):
                    return cnt
            if j in vis: return -1 # 说明循环
            vis.add(j)
            cnt += 1
        return -1

 

方法三

Rolling Hash

见： https://leetcode.com/articles/repeated-string-match/

687. Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

1
2
3
4
5
    5
   / \
  4   5
 / \   \
1   1   5

Output:

1
2

Example 2:

Input:

1
2
3
4
5
 1
/ \
  4   5
 / \   \
4   4   5

Output:

1
2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

题目地址：leetcode Longest Univalue Path

题意：给定一颗二叉树，求相同元素组成的最大路径长度。注意最大路径长度为路径上边的个数。

思路：

写个递归，返回左or右的最大路径即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def dfs(root):
            if not root: return 0
            left = dfs(root.left)
            right = dfs(root.right)
            left_path = right_path = 0
            if root.left and root.left.val == root.val:
                left_path = left + 1
            if root.right and root.right.val == root.val:
                right_path = right + 1
            self.ans = max(self.ans, left_path + right_path)
            return max(left_path, right_path)

        self.ans = 0
        dfs(root)
        return self.ans

 

688. Knight Probability in Chessboard

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly Kmoves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

Example:

1
2
3
4
5
Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Note:

  • N will be between 1 and 25.
  • K will be between 0 and 100.
  • The knight always initially starts on the board.

题目地址：leetcode Knight Probability in Chessboard

题意：给定一个N*N的国际象棋棋盘，初始的时候在r,c这个位置。骑士每步可以如上图那样走动。问经过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
class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """

        def dfs(x, y, k, dp):
            if dp[x][y][k] != -1:
                return dp[x][y][k]
            
            if k == 0:
                cur = 1
            else:
                cur = 0
                for i in range(8):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < N and 0 <= ny < N:
                        cur += 0.125 * dfs(nx, ny, k - 1, dp)
            dp[x][y][k] = cur
            return cur

        dx = [-2, -1, 1, 2, -2, -1, 1, 2]
        dy = [-1, -2, -2, -1, 1, 2, 2, 1]
        dp = [[[-1] * (K + 1) for _ in range(N)] for _ in range(N)]
        dfs(r, c, K, dp)
        return dp[r][c][K]

 

写成迭代貌似速度还慢了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dx = [-2, -1, 1, 2, -2, -1, 1, 2]
        dy = [-1, -2, -2, -1, 1, 2, 2, 1]
        dp = [[0] * N for _ in range(N)]
        dp[r][c] = 1
        for _ in range(K):
            ndp = [[0] * N for _ in range(N)]
            for x in range(N):
                for y in range(N):
                    for i in range(8):
                        nx, ny = x + dx[i], y + dy[i]
                        if 0 <= nx < N and 0 <= ny < N:
                            ndp[x][y] += 0.125 * dp[nx][ny]
            dp = ndp
        return sum(map(sum, dp))

 

689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

1
2
3
4
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

  • nums.length will be between 1 and 20000.
  • nums[i] will be between 1 and 65535.
  • k will be between 1 and floor(nums.length / 3).

题目地址：leetcode Maximum Sum of 3 Non-Overlapping Subarrays

题意：给定一个数组nums和数字k，求数组中三个长度为k的不重叠子数组，它们的和最大。返回这三个数组的起始坐标即可。

思路：

方法一

朴素的方法：

1
2
3
4
5
6
----------------
          ------
     -----
-----
        
a    b    i

枚举ab、bi、i之后的三段O(n^3)，不用看也知道TLE

如何加速?

为了方便描述，下面将ab、bi、i之后三段称为a、b、i

如果我们枚举i，对于当前的这个i，那么我们要是知道a、b两段的和的最大值就好了。

换句话说，假设已知a、b两段的和的最大值，那么我们只需要枚举i即可。

因此我们可以用dp[k][i]来表示前i个数字分为k-1段的最大和。

则显然有dp[k][i] = max(dp[k – 1][i – k] + sum[i -k + 1…i], dp[k][i – 1])

最后回溯恢复下标即可。

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
class Solution {
public:
	vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
		if (nums.empty()) return vector<int>{};
		vector<int> sum(nums.size(), 0);
		sum[0] = nums[0];
		for (int i = 1; i < nums.size(); ++i)
			sum[i] += nums[i] + sum[i - 1];

		vector<vector<int>> dp(3, vector<int>(nums.size(), 0));
		dp[0][k - 1] = sum[k - 1];
		for (int i = k; i < nums.size(); ++i) {
			dp[0][i] = max(sum[i] - sum[i - k], dp[0][i - 1]);
			if (i >= k) {
				dp[1][i] = max(dp[0][i - k] + sum[i] - sum[i - k], dp[1][i - 1]);
				if(i >= 2*k)
					dp[2][i] = max(dp[1][i - k] + sum[i] - sum[i - k], dp[2][i - 1]);
			}
		}
		vector<int> ans(3, 0);
		ans[2] = max_element(dp[2].begin(), dp[2].end()) - dp[2].begin();
		for (int i = 1; i >= 0; --i)
			ans[i] = find(dp[i].begin(), dp[i].end(), dp[i + 1][ans[i + 1]] - (sum[ans[i + 1]] - sum[ans[i + 1] - k])) - dp[i].begin();
		for (int i = 0; i < 3; ++i)
			ans[i] -= k - 1;
		return ans;
	}
};

 

以前写的：

那么如何只枚举i的时候更新前面两段最大值?

注意到i每次向右滑动一个（就是i+1）的时候，

b段不重复的就可以多了一个元素，即[i-k-1,i-1]，而这个元素要能在最大的a、b段中，必然加上之前的最大值。

于是维护max_interval为a段、a、b两段、a、b、i三段的最大值，对应的下标为max_index，初始值max_index = [[0], [0, k], [0, k, k << 1]]

然后枚举i，范围为：[(k << 1) + 1, len(nums) - k + 1)

分别计算现在新增的三段：pre_sum为累计和

  • three = pre_sum[i + k - 1] - pre_sum[i - 1]
  • two = pre_sum[i - 1] - pre_sum[i - 1 - k]
  • one = pre_sum[i - 1 - k] - pre_sum[i - 1 - (k << 1)]

然后更新各段维护的最大值和其下标即可。

第一次写的时候下标max_index更新错了。因为可能第一段更新而第二段没有更新，第三段更新这种，然后max_index[0]和max_index[1]的区间是重叠的。改了就对了。

Python 72ms

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
class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        pre_sum = [0] * len(nums)
        pre_sum[0] = nums[0]
        for i in range(1, len(nums)):
            pre_sum[i] = nums[i] + pre_sum[i - 1]

        max_index = [[0], [0, k], [0, k, k << 1]]
        max_interval = [pre_sum[k - 1], pre_sum[(k << 1) - 1] - pre_sum[k - 1],
                        pre_sum[3 * k - 1] - pre_sum[(k << 1) - 1]]

        max_interval[1] = max_interval[0] + max_interval[1]
        max_interval[2] = max_interval[1] + max_interval[2]

        for i in range((k << 1) + 1, len(nums) - k + 1, 1):
            three = pre_sum[i + k - 1] - pre_sum[i - 1]
            two = pre_sum[i - 1] - pre_sum[i - 1 - k]
            one = pre_sum[i - 1 - k] - pre_sum[i - 1 - (k << 1)]
            if one > max_interval[0]:
                max_interval[0] = one
                max_index[0][0] = i - (k << 1)
            if two + max_interval[0] > max_interval[1]:
                max_interval[1] = two + max_interval[0]
                max_index[1] = [max_index[0][0], i - k]
            if max_interval[1] + three > max_interval[2]:
                max_interval[2] = max_interval[1] + three
                max_index[2] = [max_index[1][0], max_index[1][1], i]
        return max_index[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
33
34
35
36
class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        k_sub = []
        cur = 0
        for i, num in enumerate(nums):
            cur += num
            if i >= k: cur -= nums[i - k]
            if i >= k - 1: k_sub.append(cur)

        max_left, max_right = 0, len(k_sub) - 1
        max_left_index = [0] * len(k_sub)
        max_right_index = [0] * len(k_sub)

        for i in range(len(k_sub)):
            if k_sub[i] > k_sub[max_left]:
                max_left = i
            max_left_index[i] = max_left

            if k_sub[len(k_sub) - 1 - i] >= k_sub[max_right]:
                max_right = len(k_sub) - 1 - i
            max_right_index[len(k_sub) - 1 - i] = max_right

        ans = [0, 0, 0]
        max_sum = 0
        for i in range(k << 1, len(k_sub)):
            b = i - k
            a = b - k
            if k_sub[max_left_index[a]] + k_sub[max_right_index[i]] + k_sub[b] > max_sum:
                max_sum = k_sub[max_left_index[a]] + k_sub[max_right_index[i]] + k_sub[b]
                ans = [max_left_index[a], b, max_right_index[i]]
        return ans

 

本次是 leetcode 如下的题解

    1. Repeated String Match
    1. Longest Univalue Path
    1. Knight Probability in Chessboard
    1. Maximum Sum of 3 Non-Overlapping Subarrays

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~