LC 828 + offerII 101

统计子串中的唯一字符

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。例如：s = “LEETCODE” ，则其中 “L”, “T”,“C”,“O”,“D” 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

输入: s = “ABC”
输出: 10
解释: 所有可能的子串为：“A”,“B”,“C”,“AB”,“BC” 和 “ABC”。其中，每一个子串都由独特字符构成。所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

分析：

对于一个字符c，如果它在某个子字符串中仅出现了一次，则它对这个子字符串的唯一字符个数是有贡献的。所以只需要计算对每一个字符，有多少子字符串包含它一次即可。如果c这次出现的位置是i，上一次是j，下一次是k，则这样的子字符串一共有$(i-j)\times (k-i)$ 种。故要先处理字符串s，统计每种字符出现的位置到数组中去，然后进行计算。

class Solution {
    public int uniqueLetterString(String s) {
        HashMap<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), new ArrayList<>());
                map.get(s.charAt(i)).add(-1);
            }
            map.get(s.charAt(i)).add(i);
        }
        int ans = 0;
        for (Map.Entry<Character, List<Integer>> entry : map.entrySet()){
            List<Integer> index = entry.getValue();
            index.add(s.length());
            for (int i = 1; i < index.size()-1; i++) {
                ans += (index.get(i)-index.get(i-1))*(index.get(i+1)-index.get(i));
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

分析：

dp中的0-1背包问题。该问题的本质就是，能否从数组中选出若个数字，使它们的和等于 target = sum / 2，那么所有数字之和 sum 必须为偶数，若 sum 不为偶数则等和子集肯定不存在。设dp[i][j]表示前i个数字(下标0~i-1)能否满足target=j的分割，如果选择第i个数字，那么dp[i][j]与dp[i-1][j-nums[i-1]]一致，如果不选择第i个数字，dp[i][j]与dp[i-1][j]保持一致。初始化时当 j 等于 0 时，即target为空，只要不选择数字就可以，所以dp[i][0] 为 true。当 i 等于 0 时，即数字数量为 0，那么除了target=0都无法满足，所以当 j 大于 0 时，dp[0][j]为 fasle。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum%2!=0) return false;
        int target = sum/2;
        boolean[][] dp = new boolean[n+1][target+1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (!dp[i][j] && j >= nums[i-1]) dp[i][j] = dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20