周赛355 | 顾澜的技术小站

6921. 按分隔符拆分字符串

解题思路：

遍历 $words$ 的字字符串 $word$ ，定义变量 $begin$ 表示子字符串开始位置，当 $words[i] == separator$ 时表示 $word[begin:i]$ 是满足条件的子串，将子串加入结果集中，同时 $begin = i+1$ 表示为下一个字符串的开始位置。

注意：

当 $words[i] == separator$ 且 $begin = i$ 时会切割出空字符串，需要跳过
当 $word$ 遍历结束后， $begin < len(word)$ 时，需要将 $word[begin:]$ 加入结果集

func splitWordsBySeparator(words []string, separator byte) []string {
    var res []string
    for _, word := range words {
        begin := 0
        for i, w := range word {
            if w == int32(separator) {
                if i != begin {
                    res = append(res, word[begin:i])
                }
                begin = i + 1
            }
        }
        if begin < len(word) {
            res = append(res, word[begin:])
        }
    }
    return res
}

6915. 合并后数组中的最大元素

倒序相加：

遵循「正难则反」的原则，从后往前倒序遍历， $nums[i-1] <= nums[i]$ 时进行合并，使用 $res$ 记录最大值。

第一个数可能比后面累加起来都要大，所以 $res$ 初始值为 $nums[0]$ 。

func maxArrayValue(nums []int) int64 {
    res := nums[0]
    for i := len(nums) - 1; i > 0; {
        if nums[i] >= nums[i-1] {
            nums[i] += nums[i-1]
            if nums[i] > res {
                res = nums[i]
            }
            nums = append(nums[:i-1], nums[i:]...)
        }
        i--
    }
    return int64(res)
}

6955. 长度递增组的最大数目

解题思路：

首先将 $usageLimits$ 排序，假设排好序的数组为 $usageLimits = [1,2,3,4,5]$ ，我们可以组出如下数组（其中 $x$ 为占位符）：

0 1 2 3 4
x 1 2 3 4
x x 2 3 4
x x x x 4

一行即为一个数组，我们可以模拟一下生成上述数组的过程，首先是第一个子数组 $[0]$ ，然后在第一个子数组中加入 $1$ ，并添加一个新的子数组 $1$ ，数组就变成了 $[[0,1], [1]]$ ，以此类推 $[[0,1,2], [1,2], [2]] \rightarrow [[0,1,2,3],[1,2,3],[2,3],[3]] \rightarrow ...$ ，根据规律发现，没添加一个子数组，就需要下一位拥有前面数组个数 $+1$ 个数

当 $usageLimits[i] = i+1$ 时，就可以添加一位新的子数组

如果 $usageLimits[i] < i+1$ 时，仅靠 $usageLimits[i]$ 个不够，就需要将 $usageLimits[i]$ 与 $usageLimits[i+1]$ 的数字合并起来，只要这两个位置的数字能够满足 $i+1$ ，也可以添加新的数组（因为是排过序的，所以单个组内不会存在重复的数字），如果任然不能满足，则在加上 $usageLimits[i+2]$ 的个数。

距离说明： $usageLimits = [1,2,1,2]$

0 1 2
x 1 3
x x 3

其中 $usageLimits[2] < 3$ ，所以有 $usageLimits[2] + usageLimits[3] = 3$ 后进行处理

func maxIncreasingGroups(usageLimits []int) int {
    sort.Ints(usageLimits)
    curr, ans := 0, 0
    for _, n := range usageLimits {
        curr += n
        if curr>=ans+1 {
            ans += 1
            curr -= ans
        }
    }
    return ans
}

6942. 树中可以形成回文的路径数

位运算：

回文串等价于至多一个字母出现奇数次，其余字母出现偶数次（两个奇数次字符串无法满足对称性）。

用一个长为 26 的二进制数来压缩存储每个字母的奇偶性，一条边可以看成是 $1 << (s[i]-'a')$ 。

那么路径所对应的二进制数，就是路径上的所有边的异或和（因为异或就是摸 $2$ 剩余系中的加法，刚好可以表示奇偶性）。

只有 27 个二进制数符合要求：

$0$ 表示每个字母都出现偶数次
$2^0,2^1,...2^{25}$ ，表示第 $i$ 个字母出现奇数次，其余字母出现偶数次

设 $v$ 和 $w$ 的最近公共祖先为 $lca$ ，设从根到 $x$ 的路径异或和为 $XOR_v$ 。

$v$ 到 $w$ 的路径可以看出是 $v - lca - w$ ，其中 $lca$ 到 $v$ 的路径异或和，等于跟到 $v$ 的异或和，再加上跟到 $lca$ 的异或和。（从根到 $lca$ 的边异或了两次，等于 0 低效掉。）

所以 $v - lca - w$ 异或和为：

$(XOR_v \oplus XOR_{lca}) \oplus (XOR_w \oplus XOR_{lca})$

$XOR_{lca}$ 异或了两次，抵消掉，所以上式为

$XOR_v \oplus XOR_w$

所有 $XOR$ 求出来，就变成判断 $n-1$ 个数当中：

两数异或和是否为 $0$ ？这意味着路径上的每个字母都出现偶数次。
两数异或和是否为 $2$ 的幂？这意味着路径上恰好有个字母出现奇数次，其余字母为偶数次
特殊情况： $XOR_v = 0$ 或者 $XOR_v $ 为 $2$ 的幂，表示从根到 $v$ 的路径满足要求，我们可以异或上一条「空路径」对应的异或值( $0$ )，就转换为了上面两数异或和的情况。

这可以用类似两数之和的思路解决，用哈希表记录 $XOR_v$ 的个数，设当前算出的异或和为 $x$ ，去哈希表中找 $x$ 的出现次数以及 $x \oplus 2^i$ 的出现次数

func countPalindromePaths(parent []int, s string) int64 {
	n := len(parent)
	type pair struct{ to, wt int }
	g := make([][]pair, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		g[p] = append(g[p], pair{i, 1 << (s[i] - 'a')})
	}

	ans := 0
	cnt := map[int]int{0: 1} // 一条「空路径」
	var dfs func(int, int)
	dfs = func(v, xor int) {
		for _, e := range g[v] {
			x := xor ^ e.wt
			ans += cnt[x] // x ^ x = 0
			for i := 0; i < 26; i++ {
				ans += cnt[x^(1<<i)] // x ^ (x^(1<<i)) = 1<<i
			}
			cnt[x]++
			dfs(e.to, x)
		}
	}
	dfs(0, 0)
	return int64(ans)
}

作者：endlesscheng
链接：https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/solution/yong-wei-yun-suan-chu-li-by-endlesscheng-n9ws/
来源：力扣（LeetCode）