Go学习笔记

Go学习笔记

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

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
}

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

/**
 * 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。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

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 。

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，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

func lastSubstring(s string) string {
	maxs := ""
	for i := 0; i < len(s); i ++ {
		if s[i:] > maxs {
			maxs = s[i:]
		}
	}

	return maxs
}

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

/**
 * 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 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

/**
 * 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 个元素，请找出移除后数组中不同整数的最少数目。

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

}