LeetCode题目总结
LeetCode 合并两个排序的数组
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
| void merge(vector<int>& A, int m, vector<int>& B, int n) {
vector<int> res;
int i = m - 1;
int j = n - 1;
int cur = m+n-1;
if(m == 0)
{
for(int i = 0; i < n; i++)
{
A[i] = B[i];
}
return;
}
else if(n == 0)
{
return;
}
while(i != -1 && j != -1 )
{
if(A[i] < B[j])
{
A[cur] = B[j];
j--;
cur--;
}
else
{
A[cur] = A[i];思路：
i--;
cur--;
}
}
if(j != -1)
{
for(int k = j; k > -1; k--)
{
A[k] = B[k];
}
}
}
|
和为s的连续正数序列
滑动窗口
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
思路：
选取一个点i，让j一直走，直到j>target，若都没有找到和为target的连续序列，则证明前面选的i之后没有满足条件的连续数，因此i向下一位移动。循环往复，直到i的上界（i <= target/2）时。
用sum记录累加的和，如果sum<target，j还能往右走，sum不断累加。直到sum>target，都没有找到连续的数和为target，则证明以i开头没有连续的数，则sum-i，i继续下一位，i++。
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
| vector<vector<int>> findContinuousSequence(int target) {
int i = 1;
int j = 1;
int sum = 0;
vector<vector<int>>ans;
while(i <= target/2){
if(sum < target){
sum += j;
j++;
}
else if(sum > target){
sum -= i;
i++;
}
else{
vector<int>vec;
for(int k = i; k < j; k++){
vec.push_back(k);
}
ans.push_back(vec);
sum -= i;
i++;
}
}
return ans;
}
|
**LeetCode调整数组顺序，使得奇数在前，偶数在后 **
双指针+位运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void Swap(int &a, int &b){
a^=b;
b^=a;
a^=b;
}
vector<int> exchange(vector<int>& nums) {
int i = 0;
int j = nums.size() - 1;
while(i < j){
if((nums[i] & 1)){
i++;
continue;
}
else if(!(nums[j] & 1)){
j--;
continue;
}
Swap(nums[i],nums[j]);
}
return nums;
|
三数之和
找出所有集合中三数之和为0的三元组，且答案不能重复
思路:设置三个指针，由i遍历整个集合，left和right指针根据条件左右移动。
首先给集合排序。在有序集合中，在每一次循环中，若三数之和<0，则证明可以继续往大的右方向走；若>0则证明得向左走才有机会加到0。
注意剪枝：例如集合的元素数量小于3（说明要三元组嘛），则直接返回空；第一个数时0的话，直接可以判断接下来没有数相加可以时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
26
27
| vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int> > ans;
int N = nums.size();
for(int i = 0; i < N - 2; ++i){
if(nums[i] > 0)
break;
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = N - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0){
--right;
}
else if(sum < 0){
++left;
}
else{
ans.push_back({nums[i],nums[left],nums[right]});
while(left < right && nums[left] == nums[++left]);
while(left < right && nums[right] == nums[--right]);
}
}
}
return ans;
}
|
LeetCode 找出链表的中间结点
若有两个结点，返回第二个
1
2
3
4
5
6
7
8
9
| ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
|
