leetcode-二进制

leetcode经典二进制运算题目

寻找只出现一次的两个数

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,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
class Solution {
public int[] singleNumbers(int[] nums) {
//用到了异或运算和与运算
int res = 0;
//遍历所有,最后的异或运算的结果就是这两个不同数的结果
for(int a : nums){
res ^= a;
}

//算出一个mask,二进制中的1的最低位
int flag = res & (-res);
int result[] = new int[2];
for(int a: nums){
//与运算等于0的分到一组,另一个分到另一组去
if((a&flag )== 0){
result[0] ^= a;
}else{
result[1] ^= a;
}
}
return result;

}
}

50. Pow(x, n) (快速幂,二进制)

用到

  • 向下整除 n // 2 等价于 右移一位 n >> 1 ;

  • 取余数 n % 2 等价于 判断二进制最右位 n & 1

题目:实现函数求幂

image-20200511110535592

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}

这里需要注意的是int转为long,java中int类型的范围n∈[−2147483648,2147483647],如果n=−2147483648,执行-n就会出现越界,所以转为long来操作就安全了。一开始的报错。

image-20200511112239300

这道题最核心的部分在于下面这三行,从二进制来看,比如2的9次幂。

1
2
3
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;

那么上面的b就是9,我们需要转化为二进制为1001,又因为2的9次幂等于2的一次乘于2的八次;且由&运算可知,在1001中,也就是第一位1和第四位1会在if语句中生效,所以res就可以取得2^1*2^3=2^9;

leetcode-滑动窗口算法

leetcode刷题——总结字符串滑动窗口思想解法

做了一些字符串题目后,查看题解的时候看到了滑动窗口思想,之前都没有去了解过,看一些文章也比较模糊,想自己总结弄懂,然后能够讲接地气给你们看。

是什么

【滑动窗口算法】(sliding window algorithm)–想必大家都有在平常生活中遇到过滑动窗口的场景,这个算法浅白来讲就是这样的感觉,滑动窗口(满足了连续的位置),改变长度或者位置,去获得不同要求的结果,很明显的是这个窗口滑动距离满足不超过这个窗户整体长度,所以在处理一些字符/数组的子部分的问题时候,可能就派上用场了。

简单的数组滑动实例:

leetcode3-求无重复字符的最长子串长度

1
2
3
4
5
6
7
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串

image-20200523132319424

滑动窗口问题的解决一般都得设置好双指针

leetcode76-最小覆盖子串

image-20200523101638056

答案解析如下

image-20200523110555077

模板

在leetcode上有一位大佬总结出来了模板,可以参考下

大致逻辑如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0, right = 0;

while (right < s.size()) {`
// 增大窗口
window.add(s[right]);
right++;

while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
//对应上面的例题,中间的while条件需要自己去修改,原理是一样的,遇到不符合的条件,就调整窗口大小
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
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
int left = 0 , right = 0;
char[] needs = new char[128]; //相当于hashMap,用于记录每个字符的个数
char[] windows = new char[128];
for (int i = 0; i < p.length(); i++) {
needs[p.charAt(i)]++;
}
//统计符合要求字符个数
int count =0;
while(right < s.length()){

char ch = s.charAt(right);
windows[ch]++;
if (needs[ch] > 0 && needs[ch] >= windows[ch]){
count++;
}
//长度满足条件
while( count == p.length()){
//加入符合要求的结果
if (right + 1 - left == p.length()){
list.add(left);
}
//经过一轮的条件满足,要向下继续寻找,不符合下面要求,则滑动窗口,往右走
char ch1 = s.charAt(left);
//这一步是有点难理解的,一开始我是结合例子,步步过才掌握了。很巧妙
if (needs[ch1] > 0){
//这里是通过剔除已经满足的窗边位置,这样才可以往下走,重新往右搜索
windows[ch1]--;
if ( windows[ch1] < needs[ch1]){
count--;
}
}
left++;
}
right++;
}
return list;
}

作用

  • 滑动窗口算法可以解决字符串或者数组的一些子部分问题,比如一些要求连续的子部分
  • 同时可以提高效率,减低时间复杂度,将嵌套问题优化。
  • 在有些字符串情况下,比kmp算法还要高效