LeetCode 刷题记录，以 array专题开刷。
AC
LeetCode 977. Squares of a Sorted Array
归并思想，然后0（如果有）分成左右两边，右边是平方的正序，左边是平方的倒序。时间复杂度是$O(n)$, 空间是$O(n)，$$n$ 是数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
l, r =0, len(A)-1
res =[]
while l<=r:
if A[r] **2 >=A[l] **2:
res.append(A[r] **2)
r -=1
else:
res.append(A[l] **2)
l +=1
return res[::-1]
|
1304. Find N Unique Integers Sum up to Zero
题目要求只需要找到一组，那么可以构造一组解。如果是奇数，那么最后一个放0，其他的位置放上相反数。时间复杂度是$O(n)$， 空间是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
vector<int> sumZero(int n) {
vector<int> res(n);
if(n &1) res[n-1] =0;
for(int i =0; i< n /2; i++)
{
res[i] =i +1;
res[i +n/2] =-i -1;
}
return res;
}
};
|
LeetCode 1295. Find Numbers with Even Number of Digits
数的性质，对一个数字 $\log 10$并且进行下取整，如果结果是奇数，那么说明是偶数位数。所以这个是可以在$O(n)$，假设log 运算是常数的话。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
int findNumbers(vector<int>& nums) {
int counts =0;
for(int num : nums)
{
if(int(double(log10(num))) &1) counts +=1;
}
return counts ;
}
};
|
1266. Minimum Time Visiting All Points
模拟题，最少的步数是 max(x-point[i][0], y-point[i][1])，因为不管是横着走还是竖着走，还是斜着走，长度都是1。所示时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int ans =0;
int x =points[0][0], y =points[0][1];
int n =points.size();
for(int i =1; i< n; i++)
{
ans += max(abs(x -points[i][0]), abs(y -points[i][1]));
x =points[i][0];
y =points[i][1];
}
return ans;
}
};
|
NAC
581. Shortest Unsorted Continuous Subarray
有两种思路。一种是先排序，然后排序前后进行比较，去掉首尾相同的，剩下的长度就是结果，时间复杂度是$O(nlogn)$。第二种思路是将数字划分成三个部分：起始单调递增，中间乱序和 尾部单调递增，时间复杂度是$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
43
|
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n =nums.size();
int st =n;
for(int i =0; i< n -1; i++) // 前半部分的逆序的index
if(nums[i] > nums[i+1])
{
st= i+1;
break;
}
int ed =-1;
for(int i =n -1; i>=1; i--) // 后半部分的逆序的index
if(nums[i -1] > nums[i])
{
ed =i -1;
break;
}
int max_num =INT_MIN, min_num =INT_MAX;
for(int i =0; i<= ed; i++) // 前中 部分的最大值
max_num =max(max_num, nums[i]);
for(int i =st; i<n; i++) //中后 部分的最小值
min_num =min(min_num, nums[i]);
for(int i =0; i< st; i++)
if(min_num < nums[i])
{
st =i;
break;
}
for(int i =n -1; i> ed; i--)
if(max_num > nums[i])
{
ed =i;
break;
}
return max(0, ed -st +1);
}
};
|
1089. Duplicate Zeros
重复一次 0，随后的数字是依次往后推延。双指针问题， i 表示慢指针, j 表示快指针， 当快指针走到头的时候，开始向回走，时间复杂度是$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
|
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int n =arr.size();
int i, j;
i =j =0;
while(j <n)
{
if(arr[i] ==0)
j ++;
i ++;
j ++;
}
i --;
j --;
while(i >=0)
{
if(j <n)
arr[j] =arr[i];
if(arr[i] ==0)
arr[--j] =0;
i --;
j --;
}
}
};
|
1260. Shift 2D Grid
时间复杂度，总的时间复杂度是$O(mn)$；求解最大公约数是 $O(\log (mn))$
空间复杂度：in-place 算法
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
|
class Solution {
public:
int gcd(int x, int y) {
while (y) {
int t = x % y;
x = y;
y = t;
}
return x;
}
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int n = grid.size(), m = grid[0].size();
int g = gcd(k, n * m);
for (int s = 0; s < g; s++) {
int x = s / m, y = s % m;
int tmp = grid[x][y];
while (1) {
int nx = x, ny = y - k;
while (ny < 0) {
nx = (nx - 1 + n) % n;
ny += m;
}
grid[x][y] = grid[nx][ny];
if (nx == s / m && ny == s % m) {
grid[x][y] = tmp;
break;
}
x = nx; y = ny;
}
}
return grid;
}
};
|
1252. Cells with Odd Values in a Matrix
cnt_r, cnt_c 表示多少行经过了奇数次更新， 表示多少列经过了奇数次更新，如果最后单元格变成奇数，那么奇数行经过偶次更新。时间复杂度是$O(n)$, 需要申请一个字典，所以空间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int oddCells(int n, int m, vector<vector<int>>& indices) {
unordered_map<int, int> r, c;
int cnt_r =0, cnt_c =0;
for(auto &v : indices)
{
int &vr =r[v[0]], &vc =c[v[1]];
vr ^= 1; vc ^= 1;
cnt_r += (vr &1) ? 1: -1;
cnt_c += (vc &1) ? 1: -1;
}
return cnt_r * (m -cnt_c) + cnt_c *(n -cnt_r);
}
};
|
1266. Minimum Time Visiting All Points
模拟题，最少的步数是 max(x-point[i][0], y-point[i][1])，因为不管是横着走还是竖着走，还是斜着走，长度都是1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int counts =0;
int x =points[0][0], y =points[0][1];
int n =points.size();
for(int i =1; i< n; i++)
{
counts += max(abs(points[i][0]- x), abs(points[i][1] -y));
x =points[i][0];
y =points[i][1];
}
return counts;
}
};
|
1217. Play with Chips
思路比较重要：最终的位置只分为奇数和偶数两种.对于奇数位置，所有偶数位置的代价为1；对于偶数位置，所有奇数位置的代价为1。时间复杂度$O(n)$
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int n =chips.size();
int x =0;
for(int i =0; i< n; i++)
x += chips[i] %2;
return min(x, n -x);
}
};
|
1200. Minimum Absolute Difference
读懂题意之后还是比较好写的，首先是要找出最小的绝对差值，然后根据差值然后再去选择 满足条件的对数。时间复杂度是$nlogn$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
int n =arr.size();
sort(arr.begin(), arr.end());
int min_diff =arr[1] -arr[0];
for(int i =1; i< n; i++)
{
min_diff=min(min_diff, arr[i]- arr[i-1]);
}
vector<vector<int>> res;
for(int i =1; i< n; i++)
{
if(arr[i] -arr[i-1] ==min_diff)
res.push_back({arr[i-1], arr[i]}); # 这里补不能直接使用 emplace_back()，因为该函数是以现有的 vector<> 进行后面添加的，所以不能使用构造函数的写法 {}
}
return res;
}
};
|
1185. Day of the Week
想说的这样逻辑的计算是令人佩服，从1970 开始，当2100 ，不超过 5000天，所以这个是可以枚举的，枚举的。是可以在 1s 内运算出结果的
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
44
45
46
47
48
49
50
51
52
53
|
class Solution {
public:
string dayOfTheWeek(int day, int month, int year) {
vector<string> days(8);
days[1] ="Monday";
days[2] ="Tuesday";
days[3] ="Wednesday";
days[4] ="Thursday";
days[5] ="Friday";
days[6] ="Saturday";
days[7] ="Sunday";
vector<int> md={0,
31, 28, 31, 30,
31, 30, 31, 31,
30, 31, 30, 31};
int cur_days =5;
int y =1971, m =1, d =1;
while( !(y ==year && m ==month && d ==day))
{
d ++;
cur_days ++;
if(cur_days > 7)
cur_days =1;
bool t =false;
if(y %4 ==0 && y%100 !=0 || y%400 ==0)
t =true;
// 是不是闰年的问题
if(t && m ==2)
{
if(d >29)
{
m ++;
d =1;
}
}
else{
if(d >md[m])
{
m ++;
d =1;
}
}
if (m > 12)
{
m =1;
y ++;
}
}
return days[cur_days];
}
};
|
1184. Distance Between Bus Stops
这个是环形公路，给定起点和终点， 返回最短路径，其实路径只有两条，一条是顺时针，一条是逆时针。所以 while 循环就可以搞定，如果不是终点，那么就一直循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
int n =distance.size();
int tot =0;
for(int i =0; i< n; i++)
tot += distance[i];
int ans =0;
while(start != destination)
{
ans += distance[start];
start ++;
if(start ==n)
start =0;
}
return min(ans, tot -ans);
}
};
|
905. Sort Array By Parity
是按照快排split() 进行解题。时间复杂度最优是$O(n)$，空间复杂度是$O(1)$, in-place 的做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
if( A.empty()) return A;
int n = A.size();
int l=0, r =n-1;
// 有点类似快排的思路， 偶数在前面；奇数在后面
while(l <r)
{
while (l<r && (A[r] & 1) ==1) r -=1;
while(l <r &&(A[l] &1 )==0 ) l ++;
if(l<r)
{
swap(A[l], A[r]);
l ++;
r --;
}
}
return A;
}
};
|
922. Sort Array By Parity II
在上一道题的基础上，进行交换操作。时间复杂度是$O(n)$，空间是 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int n =A.size();
int l =0, r =n -1;
while(l<r)
{
while(l <r && (A[r] &1) ==1) r -=1; // 注意 & 或者 && 的优先级是小于 == 运算符的
while(l< r && (A[l] & 1) ==0) l ++;
if(l<r)
{
swap(A[l], A[r]);
l ++;
r --;
}
}
for(int i =1, j=n -2; i< j; i +=2, j -=2)
swap(A[i], A[j]);
return A;
}
};
|
941. Valid Mountain Array
所谓的山峰就是前面是严格递增， 后面是是严格递减；第一个循环找出分界点、
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:
bool validMountainArray(vector<int>& A) {
int n =A.size();
if(n <3) return false;
int pivot =-1;
for(int i =1; i< n; i++)
{
if(A[i-1] ==A[i])
return false;
else if(A[i-1] > A[i])
{
if(i ==1) return false;
pivot =i -1;
break;
}
}
if(pivot ==-1)
return false;
for(int i =pivot +1; i<n; i++)
if(A[i-1] <= A[i]) return false;
return true;
}
};
|
1122. Relative Sort Array
题解：按照 arr2的顺序对 arr1 进行排序，结果是 arr1 相对于 arr2 的顺序。时间复杂度是$O(nlogn)$，实现了自定义的排序方式。如果出现过那么按照index 排序，如果没有出现过，那么按照value 排序。 自定义排序很精髓呀。
1
2
3
4
5
6
7
8
9
10
|
class Solution(object):
def relativeSortArray(self, arr1, arr2):
def custom_sort(val):
try:
index = arr2.index(val)
return (0, index)
except ValueError:
return (1, val)
return sorted(arr1, key = custom_sort)
|
1287. Element Appearing More Than 25% In Sorted Array
该题思路 和统计出现次数超过一半的数字 是一个思路，时间复杂度是 $O(n)$，空间复杂度是$O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
int n =arr.size();
int cnt =1, num =arr[0];
for(int i =1; i< n; i++)
{
if(arr[i] == arr[i-1])
{
cnt ++;
}
else{
if(cnt *4 > n) return num;
else
{
cnt =1;
num =arr[i];
}
}
}
return num;
}
};
|
1299. Replace Elements with Greatest Element on Right Side
好多类似的题目了，求解右边最大的元素。模拟题。倒序遍历，查找最大的元素。时间复杂度是$O(n)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
vector<int> replaceElements(vector<int>& arr) {
int n =arr.size() , m =-1;
for(int i =n -1; i>=0; i--)
{
int t =arr[i];
arr[i] =m;
m =max(m , t);
}
return arr;
}
};
|
1002. Find Common Characters
实现的时候注意 Counter() 和可以进行集合操(&)， 但是 dicitonary 是不能的。时间复杂度分析，$O(mn)$，其中 $m$ 是list 的长度， $n$ 是单个字符串的平均长度。也可以理解为所有的字母，因为每个单词的每个字母都是需要遍历一遍的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
def commonChars(self, A):
"""
:type A: List[str]
:rtype: List[str]
"""
if len(A) ==1:
return list(A[0])
c =collections.Counter(A[0])
for i in range(1, len(A)):
t =collections.Counter(A[i])
c =c & t
ans =[]
for i in c:
ans += i *c[i]
return ans
|
1013. Partition Array Into Three Parts With Equal Sum
题目： 如果能够把array 进行三等分，那么return true；否则的话return false。时间复杂度是$O(n)$，当正向找到了 $sum /3$，这个时候从反向查找，如果能够找到那么就返回true，佛则返回 false。
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
|
class Solution {
public:
bool canThreePartsEqualSum(vector<int>& A) {
int n = A.size(), sum =0;
for(int i =0; i< n; i++)
sum += A[i];
if(sum %3 != 0) return false;
int s =sum /3;
sum =0;
for(int i =0; i< n; i++)
{
sum += A[i];
if(sum ==s)
{
sum =0;
for(int j =n -1; j> i+1; j --)
{
sum += A[j];
if(sum ==s)
return true;
}
return false;
}
}
return false;
}
};
|
1018. Binary Prefix Divisible By 5
这个思路还是比较简单的， 因为是二进制的数字，所以返回成 整数之后，然后维护一个 % 5的结果，时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
vector<bool> prefixesDivBy5(vector<int>& A) {
int n =A.size(), tot =0;
vector<bool> ans;
for(int i =0; i< n; i++)
{
tot = tot*2 + A[i];
tot %=5;
ans.push_back(tot ==0);
}
return ans;
}
};
|
1160. Find Words That Can Be Formed by Characters
首先说的是这种逻辑结构是非常清楚的，需要对每个单词进行单独的处理，得到的是部分的结果，然后将全部的结果相加。时间复杂度分析$O(nL +m)$，其中 $n$表示 words 的长度，$L$ 表示单词的平均长度， $m$表示chars 的长度。空间复杂度 $O(1)$， 因为这里保存了26 个字母， 是不随着题目中的变量而变化的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int countCharacters(vector<string>& words, string chars) {
int ans =0;
vector<int> seen(26, 0);
for(char & ch : chars)
seee[ch -'a'] ++;
for(auto & word : words)
{
vector<int> cur(26, 0);
for(char & ch : word)
cur[ch -'a'] ++;
bool flag =true;
for(int i =0; i< 26; i++)
if(cur[i] > seen[i])
flag =false;
if(flag)
ans += word.length();
}
return ans;
}
};
|
1051. Height Checker
思路超级简单， 排序之后，统计不在正确位置的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int heightChecker(vector<int>& heights) {
int n =heights.size();
vector<int> h(heights);
sort(h.begin(), h.end());
int tot =0;
for(int i =0; i< n; i++)
if(heights[i] != h[i])
tot ++;
return tot;
}
};
|
665. Non-decreasing Array
时间复杂度是$O(n)$，一次遍历就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n =nums.size();
bool chance =true;
for(int i =1; i< n; i++)
{
if(nums[i] < nums[i-1])
{
if(!chance ) return false; // 如果是第二次，那么 return false
// 题目要求最多 改变一个元素的情况下，变成一个非递减，所以
if(i >1 && i < n -1 && nums[i-2] > nums[i] && nums[i-1] > nums[i+1])
return false;
chance =false;
}
}
return true;
}
};
|
不能说先排序，然后比较index 上的值，因为 4 2 3 是一个bad case。
605. Can Place Flowers
贪心的思想（如果能够插入花，那么就直接插入），时间复杂度是$O(n)$， if( (i ==0 || flowerbed[i-1] ==0) && (i ==flowerbed.size()-1 || flowerbed[i+1] ==0)) 这个判断非常的巧妙，将首尾边界情况和数组中间普通的情况一块考虑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for(int i =0; i< flowerbed.size(); i++)
{
if(flowerbed[i] ==0)
{
if( (i ==0 || flowerbed[i-1] ==0) && (i ==flowerbed.size()-1 || flowerbed[i+1] ==0))
{
flowerbed[i] =1;
n --;
}
}
}
return n <=0;
}
};
|
989. Add to Array-Form of Integer
时间复杂度是$O(n)$， 其中的 reverse() 操作是非常的nice：处理了从小到大的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
vector<int> addToArrayForm(vector<int>& A, int K) {
int n =A.size();
reverse(A.begin(), A.end());
A[0] +=K;
int i =0;
while(A[i] >=10)
{
if(i >=n -1)
A.push_back(0); // 如果超过了位数，那么就补一位
A[i+1] += A[i] /10;
A[i] %= 10;
i ++;
}
reverse(A.begin(), A.end());
return A;
}
};
|
628. Maximum Product of Three Numbers
这个定理用得好：三个数的最大乘积， 必然是是哪个最大的数的乘积或者两个最小的数字（负数）和最大的数字的乘积，所以算法复杂度是 $O(n)$ 或者 $O(nlogn)$。$O(n) $就是写多个for 循环，找出上述的三个数字。$O(nlogn) $排序之后直接进行判断。
1
2
3
4
5
6
7
8
9
|
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n =nums.size();
return max(nums[n-1] * nums[n-2] *nums[n-3], nums[0] *nums[1] * nums[n-1]);
}
};
|
566. Reshape the Matrix
实习的是 reshape 函数，时间复杂度是$O(mn)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int n =nums.size(), m =nums[0].size();
if(n *m != r *c) return nums;
vector<vector<int>> res(r, vector<int>(c));
int a =0, b =0;
for(int i =0; i< n; i++)
for(int j =0; j< m ; j++)
{
res[a][b] =nums[i][j];
b ++;
// 这种代码是非常的简洁
if(b == c)
{
a ++;
b =0;
}
}
return res;
}
};
|
832. Flipping an Image
水平旋转是对称交换位置，从 0到1或者从1 到0的转换，使用异或操作^ 就可以完成。时间复杂度是$O(mn)$， 需要遍历每个元素；空间复杂度是$O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
int n =A[0].size();
for(int i =0; i< A.size(); i++)
for(int j =0; j< (n+1) /2; j ++)
{
int tmp = A[i][j] ^1;
A[i][j] = A[i][n -1-j] ^1;
A[i][n -1-j] =tmp;
}
return A;
}
};
|
840. Magic Squares In Grid
合法的矩阵每行每列的和一定是15。枚举所有可行的枚举点，然后以该点为左上角构建矩阵，判断矩阵是否为可行解。判断单个矩阵用常数时间，总共的时间复杂度是 $O(mn)$。
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
44
45
46
|
class Solution {
public:
bool check(int x, int y, const vector<vector<int>> & grid)
{
vector<int> vis(10, false);
int row =0, col =0;
// 每一行的
for(int i = x; i< x+3; i++)
{
int tmp =0;
for(int j =y; j< y+3; j++){
if(grid[i][j] >= 10 || vis[grid[i][j]])
return false;
tmp += grid[i][j];
vis[grid[i][j]] =true;
}
if(tmp != 15) return false;
}
//每一列的
for(int j =y; j< y +3; j++)
{
int tmp =0;
for(int i =x; i< x+3; i++)
tmp += grid[i][j];
if(tmp != 15)
return false;
}
//两个对角线的
if(grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2] != 15)
return false;
if(grid[x][y+2] +grid[x+1][y+1] + grid[x+2][y] != 15)
return false;
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int n =grid.size(), m =grid[0].size();
int ans =0;
for(int i =0; i<= n -3; i++)
for(int j =0; j<= m -3; j ++)
if(check(i, j, grid))
ans ++;
return ans;
}
};
|
849. Maximize Distance to Closest Person
时间复杂度是$O(n)$，暴力枚举。last 保存是上一个1的位置，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 并没有说求出所在的位置，实际上是求解连续0的个数长度
int maxDistToClosest(vector<int>& seats) {
int n =seats.size();
int last =-1, ans =-1;
for(int i =0; i<n; i++)
{
if(seats[i] ==1)
{
if(ans ==-1)
ans =i;
else
ans=max(ans, (i-last) /2);
last =i;
}
}
ans =max(ans, n -1- last); # 主要是为了处理这样的bad case [1,0,0,0]
return ans;
}
};
|
867. Transpose Matrix
Transpose（转置）是行数据和列数据互换。这个从理论上也是非常简单的 [i,j] 转化成[j, i]。所以时间和空间复杂度是 $O(mn)$。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
vector<vector<int>> transpose(vector<vector<int>>& A) {
int n =A.size(), m =A[0].size();
vector<vector<int>> B(m, vector<int>(n));
for(int i =0; i< n; i++)
for (int j =0; j< m; j++)
B[j][i] =A[i][j];
return B;
}
};
|
LeetCode 888. Fair Candy Swap
hash表的用途是提高了查找速度，从之前的查找速度转化成$O(1)$的查找速度。交换两个数字$a$和 $b$，那么两者数组之间的差值会变化 $2|a-b|$，所以如果某个值能变化$|a-b|$，那么是其中的一个解。时间复杂度是$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
|
class Solution {
public:
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
int n =A.size(), m =B.size();
unordered_set<int> set_a(A.begin(), A.end());
// 这个使用的是构造方法，还可以这样写
int sum1 =0, sum2 =0;
for(int & t : A)
sum1 +=t;
for(int & t : B)
sum2 += t;
int delta =(sum1 -sum2) /2;
for(int i =0; i< m; i++)
{
int t =B[i] + delta;
if(set_a.count(t))
{
return vector<int>{t, B[i]};
}
}
return vector<int>{};
}
};
|
896. Monotonic Array
时间复杂度是$O(n)$，判断是否是单调数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool isMonotonic(vector<int>& A) {
int n =A.size();
bool inc =true, dec =true;
for(int i =1; i<n; i++)
{
if(A[i-1] < A[i])
dec =false;
else if(A[i-1] > A[i])
inc =false;
if(!inc && !dec)
return false;
}
return true;
}
};
|
661. Image Smoother
定义两个偏移数组来简化代码，是按照逆时针遍历。这个就是暴力枚举，每个格子都是遍历常数次，时间复杂度是$O(mn)$。
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
|
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
int n=M.size(), m =M[0].size();
vector<vector<int>> ans(M);
int dx[9] ={-1, -1, -1, 0, 1, 1,1, 0, 0}; // 逆时针的顺序
int dy[9] ={-1, 0, 1, 1, 1, 0, -1 , -1, 0};
for(int i =0; i< n; i++)
for(int j =0; j<m; j++)
{
int tot =0, cnt =0;
for(int k =0; k <9; k++)
{
int x =i +dx[k], y = j +dy[k];
if(x >=0 && x <n && y>=0 && y<m)
{
tot += M[x][y];
cnt ++;
}
}
ans[i][j] =tot/ cnt;
}
return ans;
}
};
|
LeetCode 376. Wiggle Subsequence
从数学表达上还是非常好理解的。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//c++经典的去重的操作
nums.erase(unique(nums.begin(), nums.end()), nums.end());
if(nums.size() <= 2) return nums.size();
int res =2;
for(int i =1; i+1 < nums.size() ; i++)
if(nums[i-1] < nums[i] && nums[i] > nums[i+1] || nums[i-1] > nums[i] && nums[i] < nums[i+1])
res ++;
return res;
}
};
|
674. Longest Continuous Increasing Subsequence
线性扫描数组，当发现（不合法） $nums[i] <= nums[i -1] $的时候， 则使用 $i-st$ 更新长度，其中 $st$ 表示上一个合法的位置的起点， $i$ 表示当前的位置。时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n =nums.size(), st =0, maxl =0;
for(int i =1; i<n; i++)
{
if(nums[i] <= nums[i-1])// 不是递增的时候才会发生变化
{
maxl =max(maxl , i -st);
st =i;
}
}
//return maxl;
return max(maxl, n -st);
}
};
|
643. Maximum Average Subarray I
这种固定了长度的子数组是比较巧妙的， 开始的时候是无脑加入，当长度为 $k$ 的时候，这个是后开始判断子数组长度的问题，最后返回平均值。时间复杂度是 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n =nums.size(), ans =INT_MIN, tmp =0;
for(int i =0; i<n; i++)
{
tmp += nums[i];
if(i >= k-1)
{
ans =max(ans, tmp);
tmp -= nums[i -k +1];
}
}
return 1.0* ans / k;
}
};
|
LeetCode 561. Array Partition I
贪心的做法：两个比较小的放在一起比 一个大一个小的数字 放在一起最后的结果要大, 一旦排序，那么时间复杂度是 O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n =nums.size();
int ans =0;
for(int i =0; i< n; i+= 2)
ans += nums[i];
return ans;
}
};
|
485. Max Consecutive Ones
（上面有类似的题目）last 存储上一个符合条件序列的头， i 表示当前遍历的index。时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int n =nums.size();
int last =0, ans =0;
for(int i =0; i< n; i++)
if(nums[i] != 1)
{
ans = max(ans, i -last);
last = i +1;
}
ans =max(ans, n -last);
return ans;
}
};
|
217. Contains Duplicate
简单题目，时间复杂度和空间复杂度都是$ O(n)$。注意 unordered_set 的操作， inset() 用于添加元素， find() 用于查找元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
int n =nums.size();
for(int i =0; i< n; i++)
{
if(hash.find(nums[i]) != hash.end())
return true;
hash.insert(nums[i]);
}
return false;
}
};
|
219. Contains Duplicate II
对于hash 的维护，并不需要一开始就是将所有的nums 放到hash 映射，在访问判断的过程中可以慢慢放。使用hash 表，其中key 是值，val 是index。所以时间和空间复杂度都是 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for(int i =0; i< nums.size() ; i++)
{
if(hash.find(nums[i]) != hash.end())
if(i -hash[nums[i]] <= k)
return true;
hash[nums[i]] =i;
}
return false;
}
};
|
需要使用两种语言实现，python 中的multiset 是如何实现的？
LeetCode 220. Contains Duplicate III
set（multiset） 是基于平衡树实现的，所以查找的时间效率是$O(logn)$。如果能把 $nums[i] -t <= x$的数字构建成一棵平衡树，找到其中最小的数字 $x$，如果该 $x <= t +nums[i]$，那么就是答案。总共的时间复杂度是$nlogk$， $n$表示结点的个数， $k$是multiset 的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#define LL long long
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
multiset<LL> hash;
multiset<LL>::iterator it;
for (int i = 0; i < nums.size(); i++) {
it = hash.lower_bound((LL)(nums[i]) - t);
if (it != hash.end() && *it <= (LL)(nums[i]) + t)
return true;
hash.insert(nums[i]);
if (i >= k)
hash.erase(hash.find(nums[i - k]));
}
return false;
}
};
|