今天早上复盘一下昨天晚上的双周赛
#位运算
题目描述
一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。
比方说，x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101 ，或者翻转右边起第五位（这一位是前导 0 ）得到 10111 等等。
给你两个整数 start 和 goal ，请你返回将 start 转变成 goal 的 最少位翻转 次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 示例 1：
输入：start = 10, goal = 7
输出：3
解释：10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：
- 翻转右边起第一位得到：1010 -> 1011 。
- 翻转右边起第三位：1011 -> 1111 。
- 翻转右边起第四位：1111 -> 0111 。
我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。
示例 2：
输入：start = 3, goal = 4
输出：3
解释：3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：
- 翻转右边起第一位：011 -> 010 。
- 翻转右边起第二位：010 -> 000 。
- 翻转右边起第三位：000 -> 100 。
我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。
提示：
0 <= start, goal <= 109
|
解题思路
(1). 本质上是判断两个数有多少个比特位值是不一样的（包含前导零）；
(2). 那就从最后一个比特位开始往前比较就好了。
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func minBitFlips(start int, goal int) int {
count := 0
var judgeLastBit func(int) bool
judgeLastBit = func(x int) bool {
if x == 0 || x^(x-1) != 1 {
return false
}
return true
}
for start > 0 || goal > 0 {
x1 := judgeLastBit(start)
x2 := judgeLastBit(goal)
if (x1 && !x2) || (!x1 && x2) {
count++
}
start >>= 1
goal >>= 1
}
return count
}
|
#模拟题
题目描述
给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。
nums 的 三角和 是执行以下操作以后最后剩下元素的值：
1.nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2.对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3.将 newNums 替换 数组 nums 。
4.从步骤 1 开始 重复 整个过程。
5.请你返回 nums 的三角和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。
示例 2：
输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 9
|
解题思路
(1). 太简单了。。没啥好说的
时间复杂度
O(N)
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func triangularSum(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
for len(nums) > 1 {
for i:=0; i<len(nums)-1; i++ {
nums[i] += nums[i+1]
nums[i] %= 10
}
nums = nums[:len(nums)-1]
}
return nums[0]
}
|
#动态规划
题目描述
给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：
s[i] = ‘0’ 表示第 i 栋建筑是一栋办公楼，
s[i] = ‘1’ 表示第 i 栋建筑是一间餐厅。
作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。
比方说，给你 s = “001101” ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 “011” ，有相邻两栋建筑是同一类型，所以 不合 题意。
请你返回可以选择 3 栋建筑的 有效方案数 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 示例 1：
输入：s = "001101"
输出：6
解释：
以下下标集合是合法的：
- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"
没有别的合法选择，所以总共有 6 种方法。
示例 2：
输入：s = "11100"
输出：0
解释：没有任何符合题意的选择。
提示：
3 <= s.length <= 105
s[i] 要么是 '0' ，要么是 '1' 。
|
解题思路
方法一：暴力递归搜索（超时）
(1). 类似组合数这种类型的题目，不过要判断一下是否符合最终合法的约定；
(2). 当字符串剩下的长度不足以满足要求，剪枝。（实际上这个优化并没什么用，因为剪枝的长度最大也就 3，根本不影响最终的复杂度）
方法二：统计前缀数量（O(N)）
分别定义 5 个变量，n1 代表前缀为 1 的子序列数量，n0 代表前缀为 0 的子序列数量，n01 代表前缀为 01 的子序列数量,n10 代表前缀为 10 的子序列数量，count则是统计合法的子序列数量（010 + 101）
解题代码
方法一：
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
| func numberOfWays(s string) int64 {
var count int64
path := []byte{}
var backTracking func(start int, rest int)
backTracking = func(start int ,rest int) {
if rest == 0 {
count++
return
}
for i:=start; i<len(s); i++ {
if rest > len(s[start:]) {
return
}
if len(path) == 0 {
path = append(path, s[i])
backTracking(i+1, rest-1)
} else if s[i] != path[len(path)-1] {
path = append(path, s[i])
backTracking(i+1, rest-1)
} else {
continue
}
if len(path) > 0 {
path = path[:len(path)-1]
}
}
}
backTracking(0, 3)
return count
}
|
方法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func numberOfWays(s string) int64 {
var count int64
var n0, n1, n01, n10 int64
for i:=0; i<len(s); i++ {
if s[i] == '1' {
n01 += n0
n1++
count += n10
} else {
n10 += n1
n0++
count += n01
}
}
return count
}
|
