# # Leetcode 第195场周赛题解

## # Problem A - 判断路径是否相交 (opens new window)

class Solution:
def isPathCrossing(self, path: str) -> bool:
s = set()
x = 0
y = 0
dx = {"N": 0, "S": 0, "E": 1, "W": -1};
dy = {"N": 1, "S": -1, "E": 0, "W": 0};
for c in path:
x += dx[c]
y += dy[c]
if (x, y) in s:
return True;
return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem B - 检查数组对是否可以被 k 整除 (opens new window)

class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
vector<int> cnt(k);
for (int i : arr)
cnt[(i % k + k) % k]++;
if (k & 1) {
for (int i = 1; i <= k / 2; ++i)
if (cnt[i] != cnt[k - i])
return false;
if (cnt[0] & 1)
return false;
return true;
} else {
for (int i = 1; i < k / 2; ++i)
if (cnt[i] != cnt[k - i])
return false;
if ((cnt[0] & 1) || (cnt[k / 2] & 1))
return false;
return true;
}
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

## # Problem C - 满足条件的子序列数目 (opens new window)

const int MOD = 1e9 + 7;

class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<int> two(n);
two[0] = 1;
for (int i = 1; i < n; ++i)
two[i] = (two[i - 1] << 1) % MOD;
int ans = 0, l = 0;
for (int r = n - 1; r >= 0; --r) {
if (l > r)
l = r;
if (nums[l] + nums[r] > target)
continue;
while (l < r && nums[l + 1] + nums[r] <= target)
l++;
if (l == r)
ans = (ans + two[r]) % MOD;
else
ans = (ans + two[r] - two[r - l - 1]) % MOD;
}
if (ans < 0)
ans += MOD;
return ans;
}
};

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

## # Problem D - 满足不等式的最大值 (opens new window)

class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
int n = points.size();
deque<pair<int, int>> plus, minus;
plus.push_back({points[0][1] + points[0][0], 0});
minus.push_back({points[0][1] - points[0][0], 0});
int ans = INT_MIN;
for (int i = 1; i < n; ++i) {
while (!plus.empty() && points[plus.front().second][0] < points[i][0] - k)
plus.pop_front();
while (!minus.empty() && points[minus.front().second][0] < points[i][0] - k)
minus.pop_front();
int cplus = points[i][1] + points[i][0], cminus = points[i][1] - points[i][0];
if (!plus.empty())
ans = max(ans, cminus + plus.front().first);
if (!minus.empty())
ans = max(ans, cplus + minus.front().first);
while (!plus.empty() && plus.back().first <= cplus)
plus.pop_back();
plus.push_back({cplus, i});
while (!minus.empty() && minus.back().first <= cminus)
minus.pop_back();
minus.push_back({cminus, i});
}
return ans;
}
};

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