早起刷题（Day 10）
洪笳淏 Lv4
 2022-04-11 06:00:00      

LeetCode28. 实现 strStr()

#字符串

题目描述

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2

示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：
输入：haystack = "", needle = ""
输出：0
 

提示：
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

解题思路

直接一次遍历比对即可

时间复杂度

$O(M-N)$

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func strStr(haystack string, needle string) int {
	m, n := len(haystack), len(needle)
	if m < n {
		return -1
	}

	for i:=0; i<m-n+1; i++ {
		if haystack[i:i+n] == needle {
			return i
		}
	}
	
	return -1
}

LeetCode1442. 形成两个异或相等数组的三元组数目

#位运算 #前缀异或

题目描述

给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , 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
示例 1：
输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例 2：
输入：arr = [1,1,1,1,1]
输出：10

示例 3：
输入：arr = [2,3]
输出：0

示例 4：
输入：arr = [1,3,5,7,9]
输出：3

示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8
 

提示：
1 <= arr.length <= 300
1 <= arr[i] <= 10^8

解题思路

(1). 一开始很直观想到枚举全部三元组，然后再根据规则，从 i 遍历到 j-1，再从 j 遍历到 k 来判断是否是合法三元组，但是时间复杂度是 $O(N^4)$；
(2). 然后思考优化的思路，那么在哪里可以简化呢？其实可以从异或的过程入手，我们可能比较熟悉 前缀和 了，那么同样可以思考到 前缀异或：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
假设我们有数组 arr: [1, 2, 3, 4, 7, 9]; 
前零项的异或值为: 0 = 0
前一项的异或值为: 1 = 1
前二项的异或值为: 1 ⊕ 2 = 3
前三项的异或值为: 1 ⊕ 2 ⊕ 3 = 0
前四项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 = 4
前五项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 7 = 3
前六项的异或值为: 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 7 ⊕ 9 = 10

因此它的前缀异或数组为 preXOR: [0, 1, 3, 0, 4, 3, 10];

假设现在我们想求第 3 项到第 6 项的异或值， 此时我们不需要去暴力计算 "3 ⊕ 4 ⊕ 7 ⊕ 9"
我们知道 (3 ⊕ 4 ⊕ 7 ⊕ 9) = (1 ⊕ 2) ⊕ (1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 7 ⊕ 9) 
我们可以使用前缀异或的数组来计算第 3 项到第 6 项的异或值
(1 ⊕ 2) 为前 2 项的异或值为 “3”
(1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 7 ⊕ 9) 为前 6 项异或值为 “10”
因此第 3 项到第 6 项的异或值为：3 ⊕ 10 = 9
所有对于前缀异或我们同样也可以用O(1)的时间计算区间内的异或值

这样可以有效节省时间开销，此时时间复杂度是 $O(N^3)$；
(3). 再考虑进行优化，利用异或的性质 题目让我们找到满足 a == b 的坐标，那么当 a 等于 b 时满足什么性质? a ⊕ b = 0! 我们就可以得到 arr[i] ^...^ arr[j-1]^ arr[j] ^...^ arr[k] = 0。因此在 i 之前的前缀异或值到 k 时不会变。因为[i，k] 的区间异或值为0，可以得到： xor[i] == preXor[k+1]。其另一点重点在于在区间 [i, k]内 j 在哪并不重要， 因为无论 j 在哪，i 到 k 的异或值都等于 0，不影响结果。此时时间复杂度是 O(N^2)
(4). 对于下标 k，若下标 i=$i_1$,$i_2$,…,$i_m$ 时均满足 $xor_i$ = $xor_{k+1}$，根据之前方法，这些二元组 $(i_1,k),(i_2,k),…,(i_m,k)$对答案的贡献之和为:
$\left(k-i_{1}\right)+\left(k-i_{2}\right)+\cdots+\left(k-i_{m}\right)=m \cdot k-\left(i_{1}+i_{2}+\cdots+i_{m}\right)$
也就是说，当遍历下标 k 时，我们需要知道所有满足$xor_i$ = $xor_{k+1}$ 的

  • 下标 i 的出现次数 m
  • 下标 i 之和
    我们可以在计算异或前缀和的同时计算答案，从而做到仅遍历 arr 一次就计算出答案。此时时间复杂度可以压缩到 $O(N)$

解题代码

暴力：

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
42
func countTriplets(arr []int) int {  
  
   	var opration func(i, j, k int) bool  
 	opration = func(i, j, k int) bool {  
		a, b := 0, 0  
		for idx1 := i; idx1 <= j-1; idx1++ {  
			 a ^= arr[idx1]  
		}  
		for idx2 := j; idx2 <= k; idx2++ {  
			 b ^= arr[idx2]  
		}  

		return a == b  
   }  
  
   	count := 0  
 	path := []int{}  
   	var backTacking func(start int, k int)  
   	backTacking = func(start int, k int) {  
      	if k == 0 {  
         	if opration(path[0], path[1], path[2]) {  
            // fmt.Println(path)  
 				count++  
 			}  
       		return  
 		}  
  
      	for i := start; i < len(arr); i++ {  
         	path = append(path, i)  
         	if k == 3 {  
            	backTacking(i+1, k-1)  
         	} else {  
            	backTacking(i, k-1)  
         	}  
  
         	path = path[:len(path)-1]  
      	}  
   	}  
  
   	backTacking(0, 3)  
   	return count  
}

暴力+前缀和优化：

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
42
43
func countTriplets(arr []int) int {  
  
   	xor := make([]int, len(arr)+1)  
   	for i := 1; i <= len(arr); i++ {  
      	xor[i] = xor[i-1] ^ arr[i-1]  
   	}  
  
   	var opration func(i, j, k int) bool  
 	opration = func(i, j, k int) bool {  
      	a, b := 0, 0  
 		a = xor[j] ^ xor[i]  
      	b = xor[k+1] ^ xor[j]  
  
      	return a == b  
   }  
  
   	count := 0  
 	path := []int{}  
   	var backTacking func(start int, k int)  
   	backTacking = func(start int, k int) {  
      	if k == 0 {  
         	if opration(path[0], path[1], path[2]) {  
            // fmt.Println(path)  
 				count++  
 			}  
         	return  
 		}  
  
      	for i := start; i < len(arr); i++ {  
         	path = append(path, i)  
         	if k == 3 {  
            	backTacking(i+1, k-1)  
         	} else {  
            	backTacking(i, k-1)  
         	}  
  
         	path = path[:len(path)-1]  
      	}  
   	}  
  
   	backTacking(0, 3)  
   	return count  
}

利用异或性质两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func countTriplets(arr []int) int {

	xor := make([]int, len(arr)+1)
	for i:=1; i<=len(arr); i++ {
		xor[i] = xor[i-1]^arr[i-1]
	}

	count := 0
	for i:=0; i<len(arr)-1; i++ {
		for k:=i+1; k<len(arr); k++ {
			if xor[i] == xor[k+1] {
				count += k-i
			}
		}
	}

	return count
}

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func countTriplets(arr []int) (ans int) {

	cnt := map[int]int{}
	total := map[int]int{}
	s := 0

	for k, val := range arr {
		if m, has := cnt[s^val]; has {
			ans += m*k - total[s^val]
		}
		cnt[s]++
		total[s] += k
		s ^= val
	}

	return
}
  • Post title：早起刷题（Day 10）
  • Post author：洪笳淏
  • Create time：2022-04-11 06:00:00
  • Post link：https://jiahaohong1997.github.io/2022/04/11/早起刷题（Day 10）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments