leetcode入门之数组系列


前言

之前看到刷leetcode的技巧相关文章的时候,看到一个大神建议说,在一开始可以先按数组、字符串、链表、树的tag来刷,同时切记一开始先刷easy的。这样可以很大程度上将基础巩固,因为在后面的中等题以上都是会用到这些基础知识,如果有了牢固基础,相信在学习其他复杂的知识点就可以很快解决。下面是记录一些解题的技巧和好的题目。

题目

#leetcode-learn环节

下面的例题是在英文版本的leetcode中的explore环节的学习。

1、找出连续1的数组长度

image-20200603100321399

2、位数为偶数位的个数

image-20200603102137902

image-20200603102106796

3、数组的平方

image-20200603103439065

做法一

image-20200603103553978

做法二

image-20200603104524713

4、复制零并且移动数组

image-20200603221149084

image-20200603224454937

5、合并数组

image-20200604095218172

image-20200604095321571

6、删除数组中的重复数字

image-20200604164428972

image-20200604163548016

7、在升序的数组删除重复的数字。6的变式

image-20200610212514429

O(1)空间复杂度的数组复制

image-20200610213506246

#66-加一操作

image-20200523141838014

答案示例,这里的思路和清晰,这个题看似简单,但是里面的数组进位操作处理有点意思。

image-20200523142054241

#88 合并两个有序数组

image-20200524105015152

这里需要注意的是,这道题是直接在数组一上操作,不是开辟个新数组,这道题可以从后往前做,这样可以节省空间,更加高效,代码也很简洁。代码在下面

image-20200524105113799

#287-寻找重复数

题目如下,方框中是所需要注意的点

image-20200526085409344

采用快慢指针的方法,这是一个环的入口问题

#974 子数组被K整除的个数

image-20200527234100861

使用前缀和的方法-简单的讲是记录数组的前n项

有 N 个的正整数放到数组 A 里,现在要求一个新的数组 B,新数组的第 i 个数 B[i]是原数组 A 第 0 到第 i 个数的和。

#1464 数组中最大的两个数

image-20200611085650281

暴力法

image-20200611085928108

城市轨道交通与其它交通方式衔接的研究2017052397-颜华艺

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;