71.简化路径(2022.01.06)
链接：https://leetcode-cn.com/problems/simplify-path/
思路：先以/作为分隔符将字符串切割，切割后存在以下四种情况：..，.，xx和空。
- 对于
..，我们使用栈用于弹出最后添加的目录 - 对于
.和空，我们不需处理 - 对于
xx，我们将其添加到栈中即可。
题解： 1
2
3
4
5
6
7
8
9
10
11
12# python
class Solution:
def simplifyPath(self, path: str) -> str:
names = path.split('/')
stack = []
for name in names:
if name =='..':
if stack:
stack.pop()
elif name and name != '.':
stack.append(name)
return '/'+'/'.join(stack)
1614.括号的最大深度(2022.01.07)
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses/
思路：建立一个栈，遍历字符串，遇到(便将其入栈；遇到)时，保存此时栈中的大小，再将栈顶(弹出以匹配)。栈中大小的最大值，即为嵌套深度。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// cpp
class Solution {
public:
int maxDepth(string s) {
int count = 0, size=0;
for(char ch : s){
if (ch == '('){
++size;
}else if(ch ==')'){
count = max(size, count);
--size;
}
}
return count;
}
};
89.格雷编码(2022.01.08)
链接：https://leetcode-cn.com/problems/gray-code/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//cpp
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ans;
ans.push_back(0);
for(int i = 1; i <= n; i++){
int len = ans.size();
for(int j = len-1; j >=0; j--){
ans.push_back(ans[j]|(1<<(i-1)));
}
}
return ans;
}
};
1629.按键持续时间最长的键(2022.01.09)
链接：https://leetcode-cn.com/problems/slowest-key/
思路：一次遍历keysPressed和releaseTimes，记录按键和按键的持续时间。
为避免越界问题，首先记录第0个按键，持续时间为releaseTimes[0]，按下的键为keysPressed[0]，将其记为按键持续的最长时间和对应的按键。然后遍历其余按键更新最大持续时间和对应的按键。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//cpp
class Solution {
public:
char slowestKey(vector<int>& releaseTimes, string keysPressed) {
int n = keysPressed.size();
char ans = keysPressed[0];
int maxTime = releaseTimes[0];
for(int i = 1; i < n; i++){
char key = keysPressed[i];
int time = releaseTimes[i] - releaseTimes[i-1];
if((time > maxTime)||(time == maxTime && key > ans)){
ans = key;
maxTime = time;
}
}
return ans;
}
};
306.累加数(2022.01.10)
链接：https://leetcode-cn.com/problems/additive-number/
思路：
题解： 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
54
55
56
57
58
59
60
61
62
63//cpp
class Solution {
public:
bool isAdditiveNumber(string num) {
int n = num.size();
for (int secondStart = 1; secondStart < n - 1; ++secondStart) {
if (num[0] == '0' && secondStart != 1) {
break;
}
for (int secondEnd = secondStart; secondEnd < n - 1; ++secondEnd) {
if (num[secondStart] == '0' && secondStart != secondEnd) {
break;
}
if (valid(secondStart, secondEnd, num)) {
return true;
}
}
}
return false;
}
bool valid(int secondStart, int secondEnd, string num) {
int n = num.size();
int firstStart = 0, firstEnd = secondStart - 1;
while (secondEnd <= n - 1) {
string third = stringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
int thirdStart = secondEnd + 1;
int thirdEnd = secondEnd + third.size();
if (thirdEnd >= n || !(num.substr(thirdStart, thirdEnd - thirdStart + 1) == third)) {
break;
}
if (thirdEnd == n - 1) {
return true;
}
firstStart = secondStart;
firstEnd = secondEnd;
secondStart = thirdStart;
secondEnd = thirdEnd;
}
return false;
}
string stringAdd(string s, int firstStart, int firstEnd, int secondStart, int secondEnd) {
string third;
int carry = 0, cur = 0;
while (firstEnd >= firstStart || secondEnd >= secondStart || carry != 0) {
cur = carry;
if (firstEnd >= firstStart) {
cur += s[firstEnd] - '0';
--firstEnd;
}
if (secondEnd >= secondStart) {
cur += s[secondEnd] - '0';
--secondEnd;
}
carry = cur / 10;
cur %= 10;
third.push_back(cur + '0');
}
reverse(third.begin(), third.end());
return third;
}
};
1036.逃离大迷宫(2022.01.11)
链接：https://leetcode-cn.com/problems/escape-a-large-maze/
思路：
题解： 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72// cpp
class Solution {
private:
// 在包围圈中
static constexpr int BLOCKED = -1;
// 不在包围圈中
static constexpr int VALID = 0;
// 无论在不在包围圈中，但在 n(n-1)/2 步搜索的过程中经过了 target
static constexpr int FOUND = 1;
static constexpr int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static constexpr int BOUNDARY = 1000000;
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
if (blocked.size() < 2) {
return true;
}
auto hash_fn = [fn = hash<long long>()](const pair<int, int>& o) -> size_t {
auto& [x, y] = o;
return fn((long long)x << 20 | y);
};
unordered_set<pair<int, int>, decltype(hash_fn)> hash_blocked(0, hash_fn);
for (const auto& pos: blocked) {
hash_blocked.emplace(pos[0], pos[1]);
}
auto check = [&](vector<int>& start, vector<int>& finish) -> int {
int sx = start[0], sy = start[1];
int fx = finish[0], fy = finish[1];
int countdown = blocked.size() * (blocked.size() - 1) / 2;
queue<pair<int, int>> q;
q.emplace(sx, sy);
unordered_set<pair<int, int>, decltype(hash_fn)> visited(0, hash_fn);
visited.emplace(sx, sy);
while (!q.empty() && countdown > 0) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if (nx >= 0 && nx < BOUNDARY && ny >= 0 && ny < BOUNDARY && !hash_blocked.count({nx, ny}) && !visited.count({nx, ny})) {
if (nx == fx && ny == fy) {
return FOUND;
}
--countdown;
q.emplace(nx, ny);
visited.emplace(nx, ny);
}
}
}
if (countdown > 0) {
return BLOCKED;
}
return VALID;
};
if (int result = check(source, target); result == FOUND) {
return true;
}
else if (result == BLOCKED) {
return false;
}
else {
result = check(target, source);
if (result == BLOCKED) {
return false;
}
return true;
}
}
};
334.递增的三元子序列(2022.01.12)
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence/
思路：从左到右遍历数组，维护两个变量 first 和 second，分别表示三元子序列的第一个，第二个数，且有 first < second。
初始时，first = num[0]，second = +∞。对于 1 <= i < n，当遍历到下标 i 时： 1. 如果 nums[i] > second，则找到了一个递增的三原子序列 2. 否则，如果 nums[i] > first，则令 second = nums[i] 3. 否则，first = nums[i]
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// cpp
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
if(n < 3) return false;
int first = nums[0];
int second = INT_MAX;
for(int i = 1; i < n; i++){
if(nums[i] > second) return true;
else if(nums[i] > first) second = nums[i];
else first = nums[i];
}
return false;
}
};
747.至少是其他数字两倍的最大数(2022.01.13)
链接：https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/
思路：遍历数组，找到数组中的最大值 max1 和次大值 max2。判断 max1 是否大于或等于 max2 的两倍。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// cpp
class Solution {
public:
int dominantIndex(vector<int>& nums) {
int n = nums.size();
int index;
int max1 = -1, max2 = -1;
for(int i = 0; i < n; i++){
if (nums[i] > max1){
max2 = max1;
max1 = nums[i];
index = i;
}
else if(nums[i] > max2) max2 = nums[i];
}
return max1 >= (max2*2) ? index : -1;
}
};
373.查找和最小的 K 对数字(2022.01.14)
链接：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
思路：构建堆，因为两个数组已经有序，故遍历两个数组，求和，将结果加入堆中。弹出前 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
26
27// cpp
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < min(k, m); i++) {
pq.emplace(i, 0);
}
while (k-- > 0 && !pq.empty()) {
auto [x, y] = pq.top();
pq.pop();
ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
if (y + 1 < n) {
pq.emplace(x, y + 1);
}
}
return ans;
}
};
1716.计算力扣银行存的钱(2022.01.15)
链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank/
思路：每周存的前是一个等差数列，故可以直接计算整数个周存的前，之后再计算最后不足一周存的钱，也可以通过等差数列计算。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// cpp
class Solution {
public:
int totalMoney(int n) {
// 所有完整的周存的钱
int weekNumber = n / 7;
int firstWeekMoney = (1 + 7) * 7 / 2;
int lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1);
int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber / 2;
// 剩下的不能构成一个完整的周的天数里存的钱
int dayNumber = n % 7;
int firstDayMoney = 1 + weekNumber;
int lastDayMoney = firstDayMoney + dayNumber - 1;
int dayMoney = (firstDayMoney + lastDayMoney) * dayNumber / 2;
return weekMoney + dayMoney;
}
};
382.链表随机节点(2022.01.16)
链接：https://leetcode-cn.com/problems/linked-list-random-node/
思路：使用数组存储链表的所有元素，直接通过下标返回随机索引值。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// cpp
class Solution {
vector<int> arr;
public:
Solution(ListNode *head) {
while (head) {
arr.emplace_back(head->val);
head = head->next;
}
}
int getRandom() {
return arr[rand() % arr.size()];
}
};
1220.统计元音字母序列的数目(2022.01.17)
链接：https://leetcode-cn.com/problems/count-vowels-permutation/
思路：使用动态规划的思想
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// cpp
class Solution {
public:
int countVowelPermutation(int n) {
long long mod = 1e9 + 7;
vector<long long> dp(5, 1);
vector<long long> ndp(5);
for (int i = 2; i <= n; ++i) {
/* a前面可以为e,u,i */
ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
/* e前面可以为a,i */
ndp[1] = (dp[0] + dp[2]) % mod;
/* i前面可以为e,o */
ndp[2] = (dp[1] + dp[3]) % mod;
/* o前面可以为i */
ndp[3] = dp[2];
/* u前面可以为i,o */
ndp[4] = (dp[2] + dp[3]) % mod;
dp = ndp;
}
return accumulate(dp.begin(), dp.end(), 0LL) % mod;
}
};
539.最小时间差(2022.01.18)
链接：https://leetcode-cn.com/problems/minimum-time-difference/
思路：将 timePoints 进行排序，然后遍历一遍数组记录最小的时间差。另外，根据题意，一共会有 24*60 = 1440 中不同的时间。因此如果 timePoints 长度超过了 1440，那么必然会有两个相同的时间，可以直接返回 0。
题解： 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// cpp
class Solution {
int getMinutes(string &t) {
return (int(t[0] - '0') * 10 + int(t[1] - '0')) * 60 + int(t[3] - '0') * 10 + int(t[4] - '0');
}
public:
int findMinDifference(vector<string> &timePoints) {
int n = timePoints.size();
if (n > 1440) {
return 0;
}
sort(timePoints.begin(), timePoints.end());
int ans = INT_MAX;
int t0Minutes = getMinutes(timePoints[0]);
int preMinutes = t0Minutes;
for (int i = 1; i < n; ++i) {
int minutes = getMinutes(timePoints[i]);
ans = min(ans, minutes - preMinutes); // 相邻时间的时间差
preMinutes = minutes;
}
ans = min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
return ans;
}
};
219.存在重复元素(2022.01.19)
链接：https://leetcode-cn.com/problems/contains-duplicate-ii/
思路：遍历 nums，使用哈希存储值和索引 i，每添加一个元素时，判断是否存在该元素以及判断 i-j <= k 是否成立，成立则返回 true。
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14// cpp
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> dictionary;
int n = nums.size();
for(int i = 0; i < n;i++){
int num = nums[i];
if(dictionary.count(num) && i - dictionary[num] <= k) return true;
dictionary[num] = i;
}
return false;
}
};
2029.石子游戏Ⅸ(2022.01.20)
链接：https://leetcode-cn.com/problems/stone-game-ix/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// cpp
class Solution {
public:
bool stoneGameIX(vector<int>& stones) {
int cnt0 = 0, cnt1 = 0, cnt2 = 0;
for (int val: stones) {
if (int type = val % 3; type == 0) {
++cnt0;
}
else if (type == 1) {
++cnt1;
}
else {
++cnt2;
}
}
if (cnt0 % 2 == 0) {
return cnt1 >= 1 && cnt2 >= 1;
}
return cnt1 - cnt2 > 2 || cnt2 - cnt1 > 2;
}
};
1332.删除回文子序列(2022.01.22)
链接：https://leetcode-cn.com/problems/remove-palindromic-subsequences/
思路：就两种情况：如果是字符串是回文串，则返回 1；否则返回 2；
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13// cpp
class Solution {
public:
int removePalindromeSub(string s) {
int n = s.size();
for (int i = 0; i < n / 2; ++i) {
if (s[i] != s[n - 1 - i]) {
return 2;
}
}
return 1;
}
};
2034.股票价格波动(2022.01.23)
链接：https://leetcode-cn.com/problems/stock-price-fluctuation/
思路：
题解： 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// cpp
class StockPrice {
public:
StockPrice() {
this->maxTimestamp = 0;
}
void update(int timestamp, int price) {
maxTimestamp = max(maxTimestamp, timestamp);
int prevPrice = timePriceMap.count(timestamp) ? timePriceMap[timestamp] : 0;
timePriceMap[timestamp] = price;
if (prevPrice > 0) {
auto it = prices.find(prevPrice);
if (it != prices.end()) {
prices.erase(it);
}
}
prices.emplace(price);
}
int current() {
return timePriceMap[maxTimestamp];
}
int maximum() {
return *prices.rbegin();
}
int minimum() {
return *prices.begin();
}
private:
int maxTimestamp;
unordered_map<int, int> timePriceMap;
multiset<int> prices;
};
2013.检测正方形(2022.01.26)
链接：https://leetcode-cn.com/problems/detect-squares/
思路：
题解： 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// cpp
class DetectSquares {
public:
unordered_map<int, unordered_map<int, int>> cnt;
DetectSquares() {
}
void add(vector<int> point) {
int x = point[0], y = point[1];
cnt[y][x]++;
}
int count(vector<int> point) {
int res = 0;
int x = point[0], y = point[1];
if (!cnt.count(y)) {
return 0;
}
unordered_map<int, int> & yCnt = cnt[y];
for (auto & [col, colCnt] : cnt) {
if (col != y) {
// 根据对称性，这里可以不用取绝对值
int d = col - y;
res += (colCnt.count(x) ? colCnt[x] : 0) * (yCnt.count(x + d) ? yCnt[x + d] : 0) *
(colCnt.count(x + d)? colCnt[x + d] : 0);
res += (colCnt.count(x) ? colCnt[x] : 0) * (yCnt.count(x - d) ? yCnt[x - d] : 0) *
(colCnt.count(x - d) ? colCnt[x - d] : 0);
}
}
return res;
}
};
2047.句子中的有效单词数(2022.01.27)
链接：https://leetcode-cn.com/problems/number-of-valid-words-in-a-sentence/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# python
class Solution:
def countValidWords(self, sentence: str) -> int:
def valid(s: str) -> bool:
hasHyphens = False
for i, ch in enumerate(s):
if ch.isdigit() or ch in "!.," and i < len(s) - 1:
return False
if ch == '-':
if hasHyphens or i == 0 or i == len(s) - 1 or not s[i - 1].islower() or not s[i + 1].islower():
return False
hasHyphens = True
return True
return sum(valid(s) for s in sentence.split())
176.地图中的最高点(2022.01.29)
链接：https://leetcode-cn.com/problems/map-of-highest-peak/
思路：
题解： 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// cpp
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> ans(m, vector<int>(n, -1)); // -1 表示该格子尚未被访问过
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (isWater[i][j]) {
ans[i][j] = 0;
q.emplace(i, j); // 将所有水域入队
}
}
}
while (!q.empty()) {
auto &p = q.front();
for (auto &dir : dirs) {
int x = p.first + dir[0], y = p.second + dir[1];
if (0 <= x && x < m && 0 <= y && y < n && ans[x][y] == -1) {
ans[x][y] = ans[p.first][p.second] + 1;
q.emplace(x, y);
}
}
q.pop();
}
return ans;
}
};
884.两句话中的不常见单词(2022.01.30)
链接：https://leetcode-cn.com/problems/uncommon-words-from-two-sentences/
思路：
题解： 1
2
3
4
5
6
7
8
9
10# python
class Solution:
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
freq = Counter(s1.split()) + Counter(s2.split())
ans = list()
for word, occ in freq.items():
if occ == 1:
ans.append(word)
return ans
1342.将数字变为 0 的操作次数(2022.01.31)
链接：https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14// cpp
class Solution {
public:
int numberOfSteps(int num) {
int step = 0;
while (num) {
if((num & 1) == 0) num >>= 1;
else --num;
++step;
}
return step;
}
};
540.有序数组中的单一元素(2022.02.14)
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (nums[mid] == nums[mid ^ 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return nums[low];
}
};
717. 1比特于2比特字符(2022.2.20)
链接：https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/
思路：
题解： 1
2
3
4
5
6
7
8
9class Solution {
public:
bool isOneBitCharacter(vector<int> &bits) {
int n = bits.size();
for(int i = 0; i < n; i += bits[i] + 1)
if (i == n-1) return true;
return false;
}
};
917. 反转字母(2022.2.23)
链接：https://leetcode-cn.com/problems/reverse-only-letters/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
string reverseOnlyLetters(string s) {
int n = s.size();
int left = 0, right = n-1;
while(left < right){
while(left < right && !isalpha(s[left])) left++;
while(right > left && !isalpha(s[right])) right--;
swap(s[left], s[right]);
left++;
right--;
}
return s;
}
};
1291. 顺次数(2022.2.23)
链接：https://leetcode-cn.com/problems/sequential-digits/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
for(int i = 1; i <= 9; i++){
int num = i;
for(int j = i+1; j <= 9; j++){
num = num * 10 + j;
if(num >= low && num <= high) ans.push_back(num);
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
2016. 增量元素之间的最大差值(2022.2.26)
链接：https://leetcode-cn.com/problems/maximum-difference-between-increasing-elements/
思路：
题解： 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int maximumDifference(vector<int>& nums) {
int pre_min = nums[0];
int ans = -1;
int n = nums.size();
for (int i = 1; i < n; i++){
if (nums[i] > pre_min) ans = max(ans, nums[i] - pre_min);
else pre_min =min(pre_min, nums[i]);
}
return ans;
}
};