Leetcode 11-20
11. 盛最多水的容器
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15func maxArea(height []int) int {
s:=0
for i:=0 ;i<len(height)-1;i++{
for j:=i+1;j<len(height);j++{
a:=height[j]*(j-i)
if height[j]> height[i]{
a = height[i]*(j-i)
}
if a > s{
s = a
}
}
}
return s
}
2.双指针法
-
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19func maxArea(height []int) int {
l := len(height)
s := 0
i,j := 0,l-1
for i<j {
var s1 int
if height[i]<height[j]{
s1 = height[i]*(j-i)
i++
}else{
s1 = height[j]*(j-i)
j--
}
if s1 > s{
s = s1
}
}
return s
}
12. 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
-
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15func intToRoman(num int) string {
var base = []int{1000,900, 500,400, 100,90, 50,40, 10,9,5,4,1}
var strs = []string{"M","CM", "D","CD","C","XC","L","XL","X", "IX","V","IV","I"}
ret := ""
for i,b:=range base{
x := num/b
num = num%b
if x!=0{
for j:=0;j<x;j++{
ret +=strs[i]
}
}
}
return ret
}
13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
-
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15func romanToInt(s string) int {
var base = []int{1000,900, 500,400, 100,90, 50,40, 10,9,5,4,1}
var strs = []string{"M","CM", "D","CD","C","XC","L","XL","X", "IX","V","IV","I"}
ret:=0
for i:=0;i< len(strs);{
if strings.HasPrefix(s,strs[i]){
ret+=base[i]
s = s[len(strs[i]):]
}else{
i++
}
}
return ret
}
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
-
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15func longestCommonPrefix(strs []string) string {
if len(strs)==0{ // 如果空，返回“”
return ""
}
base:=strs[0] // 选取第一个字符串作为对比基串
for i:=0;i<len(base);i++{
b:=base[i]
for j:=1;j<len(strs);j++{ // 按索引对比
if i>=len(strs[j]) || strs[j][i]!=b{
return base[:i] // 不想等就返回
}
}
}
return base
}
15. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解: 1.分层循环
-
code
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
64func threeSum(nums []int) [][]int {
sort.Ints(nums)
ret := [][]int{}
l:=len(nums)
for i:=0;i< l-2; i++{
if nums[i] > 0 {
break
}
if i>0 && nums[i] == nums[i-1]{
continue
}
ts := twoSum(nums[i+1:], -nums[i])
for _,s:=range ts{
ret = append(ret, []int{nums[i], s[0], s[1]})
}
}
return ret
}
func twoSum(nums []int, n int)[][]int{
ret := [][]int{}
for i:=0; i<len(nums)-1;i++{
if nums[i]>n/2{
break
}
if i>0 && nums[i] == nums[i-1]{
continue
}
o,has := one(nums[i+1:], n-nums[i])
if has{
ret = append(ret, []int{nums[i], o})
}
}
return ret
}
func one(nums []int,n int) (int,bool) {
end:=len(nums)-1
start:=0
if nums[start] == n{
return nums[start],true
}
if nums[end] == n{
return nums[end],true
}
for start<end {
mid := (start+end)/2
if mid > start{
if nums[mid] == n{
return nums[mid],true
}
if nums[mid]>n {
end = mid
}else{
start = mid
}
}else{
break
}
}
return 0,false
}
2.三指针法
-
code
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
31func threeSum(nums []int) [][]int {
ret := [][]int{}
sort.Ints(nums)
for i:=0; i<len(nums)-2; i++{
if nums[i] > 0{
break
}
if i > 0 && nums[i] == nums[i-1]{
continue
}
j, k := i+1, len(nums)-1
for j<k {
if j > i+1 && nums[j] == nums[j-1]{
j++
continue
}
if nums[i] + nums[j] + nums[k] == 0{
ret = append(ret, []int{nums[i], nums[j], nums[k]})
j++
k--
}else if nums[i] + nums[j] + nums[k] > 0{
k--
}else{
j++
}
}
}
return ret
}
16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
解: 三指针
- code
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
41func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
det:=0
for i:=0; i<len(nums)-2; i++{
if i == 0{
det = nums[0] + nums[1] + nums[len(nums)-1] - target
}else if nums[i] == nums[i-1]{
continue
}
j, k := i+1, len(nums)-1
for j<k {
if j > i+1 && nums[j] == nums[j-1]{
j++
continue
}
temp := nums[i] + nums[j] + nums[k] - target
if temp == 0{
return target
}else {
if abs(temp)< abs(det) {
det = temp
}
if temp < 0{
j++
}else{
k--
}
}
}
}
return det + target
}
func abs(n int)int{
if n < 0{
return -n
}
return n
}
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
-
code
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// 当然可以做复用
func letterCombinations(digits string) []string {
numMap := map[byte][]string{
'2': []string{"a", "b", "c"},
'3': []string{"d", "e", "f"},
'4': []string{"g", "h", "i"},
'5': []string{"j", "k", "l"},
'6': []string{"m", "n", "o"},
'7': []string{"p", "q", "r", "s"},
'8': []string{"t", "u", "v"},
'9': []string{"w", "x", "y", "z"},
}
if len(digits) == 0{
return nil
}
fm := numMap[digits[0]]
if len(digits) == 1{
return fm
}
em := letterCombinations(digits[1:])
ret := []string{}
for _,f := range fm{
for _,e:=range em{
ret = append(ret , f+e)
}
}
return ret
}
18. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解:有一句mmp，不知当讲不当讲
-
code
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
48func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
return kSum(nums, 4, target)
}
// k>=2
func kSum(nums []int, k, target int)[][]int{
ret := [][]int{}
if k == 2{
i, j := 0, len(nums)-1
for i < j{
if nums[i] > target/2{
break
}
if i > 0 && nums[i] == nums[i-1]{
i++
continue
}
if nums[i] + nums[j] == target{
ret = append(ret, []int{nums[i], nums[j]})
i++
j--
}else if nums[i] + nums[j] < target{
i++
}else{
j--
}
}
}else{
for i:=0; i<len(nums) - k + 1; i++{
if nums[i] > target/k {
break
}
if i > 0 && nums[i] == nums[i-1]{
continue
}
ts := kSum(nums[i+1:], k-1, target-nums[i])
for j:=range ts{
r := make([]int, k)
r[0] = nums[i]
copy(r[1:], ts[j])
ret = append(ret,r)
}
}
}
return ret
}
19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
解: 从头节点与第n个节点同时移动，后一个节点移动至末尾，头节点将移动至倒数第n个节点
-
code
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/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
first := head
for i := 1; i < n; i++ {
first = first.Next
}
var npNode *ListNode
second := head
for first.Next != nil {
first = first.Next
npNode = second
second = second.Next
}
if npNode == nil {
return second.Next
}
npNode.Next = second.Next
return head
}
20. 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
解: 经典栈
- code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20func isValid(s string) bool {
var match = map[byte]byte{
')':'(',
']':'[',
'}':'{',
}
stack := []byte{}
for _,b:= range []byte(s){
switch b{
case '(','{','[':
stack = append(stack, b)
case ')','}',']':
if len(stack) == 0 || stack[len(stack)-1] != match[b]{
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}