思路
前缀和后缀和相减的绝对值
注意后缀和下标问题
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> leftRigthDifference(vector<int>& nums) {
int n = nums.size();
vector<int> left(n + 10);
vector<int> right(n + 5);
for(int i = 0; i < n; i++)
left[i + 1] = left[i] + nums[i];
for(int i = n; i; i--)
right[i - 1] = right[i] + nums[i - 1];
vector<int> ret;
for(int i = 0; i < n; i++)
ret.push_back(abs(left[i] - right[i + 1]));
return ret;
}
};
|
思路
取模运算法则
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
int n = word.size();
vector<int> ret(n);
long long temp = 0;
for(int i = 0; i < n; i++)
{
temp *= 10;
temp += word[i] - '0';
temp %= m;
ret[i] = !temp;
}
return ret;
}
};
|
思路
解法1.二分
要匹配n对,
如果n能够匹配上,那么 n - 1, n -2, n -3 也能匹配上
如果n匹配补上, 那么 n + 1, n + 2, n + 3 也匹配不上
check函数
一定是最小的k个数和最大的k个数比较
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:
bool check(int k, vector<int> &nums)
{
if(2 * k > nums.size()) return false;
for(int i = 0; i < k; i++)
if(2 * nums[i] > nums[nums.size() - k + i]) return false;
return true;
}
int maxNumOfMarkedIndices(vector<int>& nums) {
sort(nums.begin(), nums.end());
int l = 0, r = nums.size() / 2;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid, nums)) l = mid;
else r = mid - 1;
}
return 2 * l;
}
};
|
解法2. 贪心+双指针
根据上面的二分思路, 我们发现最先的前k 个和 最大的k个数 能匹配上的个数就是最后的答案, 我们直接写代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
sort(nums.begin(), nums.end());
int l = 0, r = nums.size() + 1 >> 1;
int ans = 0;
while(r < nums.size())
{
while(r < nums.size() && 2 * nums[l] > nums[r]) r++;
if(r < nums.size() && 2 * nums[l] <= nums[r]) {
l++;
r++;
ans += 2;
}
}
return ans;
}
};
|
思路
Djikstra最短路问题
模板题
