LeetCode num016

Problem

3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution

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
class Solution {
public:
int threeSumClosest(vector<int> &num, int target)
{

sort(num.begin(), num.end());
int i = 0, min, temp, first;
min = num[0] + num[1] + num[2] - target;
while (num.size() >= 3)
{
first = num[0];
num.erase(num.begin());
temp = twoSumClosest(num, target - first);
if (abs(temp + first - target) < abs(min))
{
min = temp + first - target;
}
}
return min + target;
}
int twoSumClosest(vector<int> num, int target)
{

int i, j, minBig, minSmall, markBig = 0, markSmall = 0;
for (i = 0, j = num.size() - 1; i < j;)
{
if (num[i] + num[j] == target)
{
return target;
}
else if (num[i] + num[j] > target)
{
if (markBig == 0)
{
minBig = num[i] + num[j];
markBig = 1;
}
else
{
minBig = minBig < (num[i] + num[j]) ? minBig : (num[i] + num[j]);
}
j--;
}
else
{
if (markSmall == 0)
{
minSmall = num[i] + num[j];
markSmall = 1;
}
else
{
minSmall = minSmall > (num[i] + num[j]) ? minSmall : (num[i] + num[j]);
}
i++;
}
}
if (markSmall == 0)
{
return minBig;
}
else if (markBig == 0)
{
return minSmall;
}
else
{
return (target - minSmall) < (minBig - target) ? minSmall : minBig;
}
}
};

Comment

  1. 写代码要细致;
  2. 不要迁就代码,尽量不要黏贴别的代码进行改;
  3. 要有勇气放弃代码,从头写;
  4. 本题时间复杂度为O(n^2)。

LeetCode num015

Problem

3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

1
2
3
4
5
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

Solution

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
73
74
75
76
77
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int>> result, get;
vector<int> fine;
int target;
int i, j, k, mark;
for (i = 0; num.size() >= 3; i++)
{
target = 0 - num[0];
if (i >= 1 && target == mark)
{
num.erase(num.begin());
continue;
}
mark = target;
num.erase(num.begin());
get = twoSum(num, target);
for (k = 0; k < get.size(); k++)
{
fine = get[k];
result.push_back(fine);
}
}
return result;
}
vector<vector<int> > twoSum(vector<int> &num, int target)
{
vector<int> fine;
vector<vector<int> > result;
int sum, count1 = 0, count2 = 0, mark1, mark2;
vector<int>::iterator it1 = num.begin(), it2 = num.end() - 1;
for (it1 = num.begin(), it2 = num.end() - 1; it1 < it2;)
{
if (count1 >= 1 && *it1 == mark1)
{
it1++;
continue;
}
else if (count2 >= 1 && *it2 == mark2)
{
it2--;
continue;
}
sum = *it1 + *it2;
if (sum == target)
{
fine.push_back(0 - target);
fine.push_back(*it1);
fine.push_back(*it2);
result.push_back(fine);
fine.clear();
mark1 = *it1;
mark2 = *it2;
it1++;
it2--;
count1++;
count2++;
}
else if (sum < target)
{
mark1 = *it1;
it1++;
count1++;
}
else
{
mark2 = *it2;
it2--;
count2++;
}

}
return result;
}
};

Comment

  1. 代码不够简洁;
  2. 类似两个数的和;
  3. 复杂度能够到O(n^2)。

LeetCode num088

Problem

Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Solution

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:
void merge(int A[], int m, int B[], int n) {
int i, j = m - 1, k = n - 1;
for (i = m + n - 1; i >= 0; i--)
{
if (A[j] > B[k] & j >= 0)
{
A[i] = A[j];
j--;
}
else
{
A[i] = B[k];
k--;
if (k < 0)
{
break;
}
}
}
}
};

Comment

  1. 题比较简单。

LeetCode num080

Problem

Remove Duplicates from Sorted Array II
Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Solution

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:
int removeDuplicates(int A[], int n) {
int gap = 0, count = 0, i;
for (i = 1; i < n; i++)
{
if (A[i] == A[i - 1])
{
count++;
if (count >= 2)
{
gap++;
}
}
else
{
count = 0;
}
if (gap > 0)
{
A[i - gap] = A[i];
}
}
return n - gap;
}
};

Comment

  1. 与去重类似;
  2. 多加一个标识位。

LeetCode num078

Problem

Subsets
Given a set of distinct integers, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Solution

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
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S)
{
vector<vector<int> > result = subsetsWithoutSort (S);
for (int i = 0; i < result.size(); i++)
{
sort(result[i].begin(), result[i].end());
}
return result;
}
vector<vector<int> > subsetsWithoutSort(vector<int> &S)
{
int i, j, k;
vector<int> love, leave, empty;
vector<vector<int> > family, result;
if (S.size() == 1)
{
love.push_back(S[0]);
result.push_back(love);
result.push_back(empty);
return result;
}
for (j = 1; j < S.size(); j++)
{
leave.push_back(S[j]);
}
family = subsets(leave);
for (k = 0; k < family.size(); k++)
{
result.push_back(family[k]);
family[k].push_back(S[0]);
result.push_back(family[k]);
}
return result;
}
};

Comment

  1. 全排列;
  2. 动态规划;
  3. 类似背包。

LeetCode num077

Problem

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Solution

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
class Solution {
public:
vector<vector<int> > combine(int n, int k)
{
vector<int> input;
vector<vector<int> > result;
if (n == 0 || k == 0 || n < k)
{
return result;
}
for (int i = 1; i <= n; i++)
{
input.push_back(i);
}
result = love(input, k);
for (int i = 0; i < result.size(); i++)
{
sort(result[i].begin(), result[i].end());
}
return result;
}
vector<vector<int> > love (vector<int> input, int k)
{
vector<vector<int> > result, leave, all;
vector<int> process;
int i, dispute = input[0];
if (k == 1)
{
for (i = 0; i < input.size(); i++)
{
process.push_back(input[i]);
result.push_back(process);
process.clear();
}
return result;
}
else if (input.size() == k)
{
result.push_back(input);
return result;
}
input.erase(input.begin());
leave = love(input, k - 1);
for (i = 0; i < leave.size(); i++)
{
leave[i].push_back(dispute);
result.push_back(leave[i]);
}
all = love(input, k);
for (i = 0; i < all.size(); i++)
{
result.push_back(all[i]);
}
return result;
}
};

Comment

  1. 递归。