Go学习笔记

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

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
func nextGreaterElements(nums []int) []int {
if len(nums) == 1 {
return []int{-1}
}
    if len(nums) == 0 {
return []int{}
}
res := make([]int, len(nums))

copy(res, nums)
sort.Ints(res)
max := res[len(nums)-1]

for idx, num := range nums {
if num == max {
res[idx] = -1
}
flag := true
for _, m := range nums[idx+1:] {
if m > num {
res[idx] = m
flag = false
break
}
}
if flag {
for _, m := range nums[:idx] {
if m > num {
res[idx] = m
break
}
}
}
}

return res
}

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
if head == nil {return head}
num1, num2 := make([]int, 0), make([]int, 0)
n := 1
for head != nil {
if n % 2 != 0 {
num1 = append(num1, head.Val)
} else {
num2 = append(num2, head.Val)
}
n ++
head = head.Next
}

// fmt.Println("num1:", num1, ", num2:", num2)

num := append(num1, num2...)
// fmt.Println("num:", num)

head = &ListNode{}
res := head
for _, v := range num {
res.Next = &ListNode{Val: v}
res = res.Next
}

return head.Next

}

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func searchMatrix(matrix [][]int, target int) bool {
for i := 0; i < len(matrix); i ++ {
for j := 0; j < len(matrix[i]); j ++ {
if matrix[i][j] == target {
return true
}
if matrix[i][j] > target {
break
}
}
}

return false
}

在显示着数字的坏计算器上，我们可以执行以下两种操作：

  • 双倍（Double）：将显示屏上的数字乘 2；
  • 递减（Decrement）：将显示屏上的数字减 1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func brokenCalc(X int, Y int) int {
cnt := 0

if X >= Y {return X - Y}

for Y > X {
if Y % 2 == 1 {cnt++}
t := (Y + 1) / 2
if t == X {
cnt++
} else if t < X {
cnt += (X - t + 1)
} else {
Y = t
cnt++
continue
}
break
}

return cnt
}

给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

1
2
3
4
5
6
7
8
9
10
func lastSubstring(s string) string {
maxs := ""
for i := 0; i < len(s); i ++ {
if s[i:] > maxs {
maxs = s[i:]
}
}

return maxs
}

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
headL, res := make([]int, 0), &ListNode{}
for head != nil {
headL = append(headL, head.Val)
head = head.Next
}

sort.Ints(headL)
cp := res

for i := 0; i < len(headL); i ++ {
t := &ListNode{Val: headL[i]}
cp.Next = t
cp = cp.Next
}

return res.Next
}

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
res := &ListNode{Val: 0, Next: nil}
nums1, nums2 := make([]int, 0), make([]int, 0)
for {
if head != nil {
if head.Val >= x {
nums2 = append([]int{head.Val}, nums2...)
} else {
nums1 = append([]int{head.Val}, nums1...)
}
head = head.Next
} else {
break
}
}

result := res

nums := append(nums1, nums2...)
for i := 0; i < len(nums); i++ {
result.Next = &ListNode{Val: nums[i]}
result = result.Next
}

return res.Next
}

给你一个整数数组 arr 和一个整数 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
24
25
26
27
28
29
30
func findLeastNumOfUniqueInts(arr []int, k int) int {
// Map用来统计数字出现的频率
// Arr为数字出现频率数组
arrMap, arrNum := make(map[int]int), make([]int, 0)
for i := 0; i < len(arr); i ++ {
arrMap[arr[i]] ++
}

for _, num := range arrMap {
arrNum = append(arrNum, num)
}
// 排序
sort.Ints(arrNum)

cnt := 0
for i, v := range arrNum{
if k > v {// 若当前k大于该频率,则直接减
k -= v
} else if k == v {//若等于,则最少数目为接下来数组的长度
cnt = len(arrNum) - i - 1
break
} else { //若小于,则最少数目为当前数之后数组的长度
cnt = len(arrNum) - i
break
}
}

return cnt

}