力扣双周赛140

本文最后更新于 2024年9月29日 下午

T1:替换为数位和以后的最小元素

给你一个整数数组 nums 。

请你将 nums 中每一个元素都替换为它的各个数位之 和 。

请你返回替换所有元素以后 nums 中的 最小 元素。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minElement(self, nums: List[int]) -> int:
        ans = inf
        for x in nums:
            tmp = 0
            while x:
                tmp += x % 10
                x= x//10
            ans = min(ans, tmp)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minElement(int[] nums) {
        int ans = Integer.MAX_VALUE;
        for (int x : nums) {
            int tmp = 0;
            while (x > 0) {
                tmp += x % 10;
                x /= 10;
            }
            ans = Integer.min(ans, tmp);
        }
        return ans;
    }
}

T2:高度互不相同的最大塔高和

给你一个数组 maximumHeight ，其中 maximumHeight[i] 表示第 i 座塔可以达到的 最大 高度。

你的任务是给每一座塔分别设置一个高度，使得：

  1. 第 i 座塔的高度是一个正整数，且不超过 maximumHeight[i] 。
  2. 所有塔的高度互不相同。

请你返回设置完所有塔的高度后，可以达到的 最大 总高度。如果没有合法的设置，返回 -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
class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
        maximumHeight.sort(reverse = True)
        cnt = Counter(maximumHeight)
        ans = 0
        curr = inf
        for x, ct in cnt.items():
            if curr == inf:
                curr = x-ct
                for i in range(ct):
                    ans += x-i
                if curr < 0:
                    return -1
            else:
                if curr <= x:
                    for i in range(ct):
                        ans += curr - i 
                    curr = curr-ct
                else:
                    for i in range(ct):
                        ans += x - i 
                    curr = x-ct
                if curr < 0:
                    return -1
        return ans

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
import java.util.*;

class Solution {
    public long maximumTotalSum(int[] maximumHeight) {
        Arrays.sort(maximumHeight);
        int n = maximumHeight.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = maximumHeight[n-i-1];
        }
        maximumHeight = b;
        LinkedHashMap<Integer,Integer> cnt = new LinkedHashMap<>();
        for (int x : maximumHeight) {
            if (cnt.containsKey(x)) {
                cnt.put(x,cnt.get(x)+1);
            } else {
                cnt.put(x,1);
            }
        }
        int curr = Integer.MAX_VALUE;
        long ans = 0L;
        for (int x : cnt.keySet()) {
            if (x < curr) {
                for (int k = 0; k < cnt.get(x); k++) {
                    ans += x-k;
                }
                curr = x - cnt.get(x);
            } else {
                for (int k = 0; k < cnt.get(x); k++) {
                    ans += curr-k;
                }
                curr = curr - cnt.get(x);
            }
            if (curr < 0) {
                return -1;
            }
        }

        return ans;
    }
}

注:这里一定要用LinkedHashMap,以此保证哈希表的关键字集是有序的(根据插入顺序)

灵茶山艾府解法

1
2
3
4
5
6
7
8
9
class Solution:
    def maximunTotalSum(self, h:List[int])->int:
        h.sort(reverse=True)
        n = len(h)
        ans = h[0]
        for i in range(1,n):
            h[i] = min(h[i-1]-1, h[i])
            ans += h[i]
        return ans

T3:字典序最小的合法序列

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
class Solution {
    public int[] validSequence(String s, String T) {
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        int n = s.length;
        int m = t.length;
        
        int[] suf = new int[n+1];
        suf[n] = m;
        int j = m-1;
        for (int i = n-1; i >= 0; i--) {
            if (j >= 0 && s[i] == t[j]) {
                j--;
            }
            suf[i] = j+1;
        }
        
        int ans = new int[m];
        boolean changed = false;
        j = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == t[j] || !changed && suf[i+1] <= j+1) {
                if (s[i] != t[j]) {
                    changed = true;
                }
                ans[j++] = i;
                if (j == m) {
                    return ans;
                }
            }
        }
        return new int[]{};
    }
}

补充:最少得分子序列

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 int minimumScore(String s, String t) {
        int n = s.length();
        int m = t.length();
        int j = m-1;
        int[] suf = new int[n+1];
        Arrays.fill(suf, m);
        for (int i = n-1; i >= 0; i--) {
            if (j >= 0 && s.charAt(i) == t.charAt(j)) {
                j--;
            }
            if (j < 0){
                return 0;
            }
            suf[i] = j+1;
        }

        int ans = suf[0];
        j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t.charAt(j)) {
                j++;
                ans = Integer.min(ans, suf[i+1] - j);
            }
        }
        return ans;
    }
}

T4:第一个几乎相等子字符串的下标

利用Z算法，分别求出pattern与s的公共最长前缀数组和公共最长后缀数组，索引从小到大遍历，返回对应前缀+后缀\(\geq\)len(pattern)-1(即几乎相等)的下标.

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:
    def calc_z(self, s: str) -> list[int]:
        n = len(s)
        z = [0] * n
        box_l = box_r = 0  # z-box 左右边界
        for i in range(1, n):
            if i <= box_r:
                z[i] = min(z[i - box_l], box_r - i + 1)  # 改成手动 if 可以加快速度
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                box_l, box_r = i, i + z[i]
                z[i] += 1
        return z

    def minStartingIndex(self, s: str, pattern: str) -> int:
        pre_z = self.calc_z(pattern + s)
        suf_z = self.calc_z(pattern[::-1] + s[::-1])
        suf_z.reverse()  # 也可以不反转，下面写 suf_z[-i]
        m = len(pattern)
        for i in range(m, len(s) + 1):
            if pre_z[i] + suf_z[i - 1] >= m - 1:
                return i - m
        return -1

扩展:Z算法(Z Algorithm,扩展KMP)

定义

对于一个长度为n的字符串s,定义函数z[i]表示s和s[i,n-1]的最长公共前缀(LCP)的长度,则z称为s的Z函数,热别地,z[0]=0

朴素算法

时间复杂度:\(O(n^2)\)

1
2
3
4
5
6
7
def z_function_trivial(s):
    n = len(s)
    z = [0] * n
    for i in range(1,n):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
	return z

线性算法

思路

我们从1到n-1顺次计算z[i],在计算z[i]的过程中,我们会利用已经计算好的z[0],...z[i-1].

[i,i+z[i]-1]称为i的匹配段(Z-box)

算法过程中我们维护右端点最靠右的匹配段,记作[l,r],s[l,r]是s的前缀,在计算z[i]时保证l\(\leq\)i,初始时l=r=0

在计算z[i]的过程中:

  • 如果\(i\leq r\),则s[i,r]=s[i-l,r-l](字符串相同),因此\(z[i]\geq min(z[i-l],r-i+1)\)
    • 若\(z[i-l]<r-i+1\),则z[i]=z[i-l]
    • 否则\(z[i-l]\geq r-i+1\),这时z[i]=r-i+1,然后暴力枚举下一个字符扩展z[i]直到不能扩展为止
  • 如果\(i\geq r\),那么我们直接按照朴素算法,从s[i]开始比较,暴力求出z[i]
  • 在求出z[i]后,如果i+z[i]-1>r,更新[l,r],即令l=i,r=i+z[i]-1

动画

Z算法动画

时间复杂度

线性遍历，\(O(n)\)

#算法
力扣双周赛140
https://meteor041.git.io/2024/09/29/力扣双周赛140/
作者
meteor041
发布于
2024年9月29日
许可协议