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# 将slice编程器数组，在进行求解
func twoSum(nums []int, target int) []int {
// turn slice to map
numsMap := make(map[int][]int)
for index, value := range nums {
if numsMap[value] == nil {
numsMap[value] = []int{}
}
numsMap[value] = append(numsMap[value], index)
}
for value, indexArr1 := range numsMap {
indexArr2, isExist := numsMap[target-value]
if isExist {
if target == value*2 && len(indexArr1)>=2 {
return []int{indexArr1[0], indexArr1[1]}
} else if target == value*2 && len(indexArr1)<2 {
return nil
}
return []int{indexArr1[0], indexArr2[0]}
}
}
return nil
}
无重复字符的最长子串
- 题目
- 滑动窗口详解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# 使用滑动窗口
func lengthOfLongestSubstring(s string) int {
var i, j, max int
for j < len(s) {
if strings.Contains(s[i:j], string(s[j])) {
// 遇到重复的
if max < j-i {
max = j-i
}
i++
continue
}
j++
}
if max < j-i {
return j-i
}
return max
}
最长回文子串
- 题目
- 中心扩展法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# 使用滑动窗口
func longestPalindrome(s string) string {
s = strings.Replace(s, "", "|", -1)
retStr := ""
length := len(s)
for i:=0; i<length; i++ {
left := i
right := i
for left-1>=0 && right+1<length {
if s[left-1] != s[right+1] {
break
}
left--
right++
}
if len(retStr) < (right-left+1) {
retStr = s[left:right+1]
}
}
return strings.Replace(retStr, "|", "", -1)
}
整数反转
- 题目
1
2
3
4
5
6
7
8
9
10
11
12# 这一题其实不难，主要为下一题作准备
func reverse(x int) ( num int) {
for x != 0 {
num = num*10 + x%10
x = x / 10
}
// 使用 math 包中定义好的最大最小值
if num > math.MaxInt32 || num < math.MinInt32 {
return 0
}
return
}
回文数
- 题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24# 判断一个数是不是回文数，可以先将其反转，然后在判断与原来的数是否相等
func isPalindrome(x int) bool {
if x < 0 {
return false
}
reverseX := reverse(x)
if reverseX == x {
return true
}
return false
}
func reverse(x int) ( num int) {
for x != 0 {
num = num*10 + x%10
x = x / 10
}
// 使用 math 包中定义好的最大最小值
if num > math.MaxInt32 || num < math.MinInt32 {
return 0
}
return
}
三数之和
- [题目](https://leetcode-cn.com/problems/3sum/）
- 思路（双指针法思路）
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
78
79
80
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
int size = nums.size();
if (size < 3) {
return ret;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size()-2; ++i) {
int r1 = i+1;
int r2 = size-1;
// 最小的数大于0
if (nums[i] > 0) {
continue;
}
if ( i != 0 && nums[i]==nums[i-1]) {
continue;
}
while(r1 < r2) {
int sum = nums[i] + nums[r1] + nums[r2];
if (sum>0) {
r2 = moveR2(nums, r2);
} else if (sum<0) {
r1 = moveR1(nums, r1);
} else {
ret.push_back(vector<int>{nums[i], nums[r1], nums[r2]});
r1 = moveR1(nums, r1);
r2 = moveR2(nums, r2);
}
}
}
return ret;
}
int moveR1(vector<int>& nums, int r1){
int temp = nums[r1];
r1++;
while (r1 < nums.size()) {
if (nums[r1] != temp) {
break;
}
r1++;
}
return r1;
}
int moveR2(vector<int>& nums, int r2){
int temp = nums[r2];
r2--;
while (r2 >= 0) {
if (nums[r2] != temp) {
break;
}
r2--;
}
return r2;
}
};
int main() {
vector<int> test = {-2,0,0,2,2};
Solution s;
auto result = s.threeSum(test);
for (auto i : result){
cout<< i[0] << i[1] << i[2] << endl;
}
}
最接近的三数之和
- [题目](https://leetcode-cn.com/problems/3sum-closest/）
- 思路（双指针法思路）
- 这个题目和上个题目类似，都是先固定一个参数，再通过两个指针收尾移动的方法来确定
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
46class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int size = nums.size();
if (size < 3) {
return 0;
}
int nearest = nums[0] + nums[1] + nums[size-1];
int difference = abs(nums[0] + nums[1] + nums[size-1] - target);
for (int i = 0; i < size-2; ++i) {
int r1 = i+1;
int r2 = size-1;
int roundNearest = nums[i] + nums[r1] + nums[r2];
int roundDifference = abs(nums[i] + nums[r1] + nums[r2] - target);
while(r1 < r2) {
int sum = nums[i] + nums[r1] + nums[r2];
if (abs(sum-target) < roundDifference) {
roundDifference = abs(sum-target);
roundNearest = sum;
}
if (sum < target) {
r1++;
} else if (sum > target){
r2--;
} else {
return target;
}
}
if (difference > roundDifference) {
nearest = roundNearest;
difference = roundDifference;
}
}
return nearest;
}
};
- 这个题目和上个题目类似，都是先固定一个参数，再通过两个指针收尾移动的方法来确定
矩形重叠
- 题目
- 思路：
- 将其映射到x，y轴上，如果相交的话，则x，y上也必定都相交
1 | func isRectangleOverlap(rec1 []int, rec2 []int) bool { |
