算法-rand10&链表插入排序

一、用 Rand7() 实现 Rand10()

难度：中等

题目

给定方法rand7可生成 [1,7] 范围内的均匀随机整数，试写一个方法rand10生成 [1,10] 范围内的均匀随机整数。

你只能调用rand7()且不能调用其他方法。请不要使用系统的Math.random()方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:
    输入: 1
    输出: [2]
示例 2:
    输入: 2
    输出: [2,8]
示例 3:
    输入: 3
    输出: [3,8,10]

提示：

1 <= n <= 10^5

思路

核心在于构建[1-10]的结果集，每个结果出现的概率概率和不一定为1，但是单个结果出现的概率须相等。

方法一：

rand10需要输出[1-10]，那么构建一个二维数组，单维长度为7。内置元素为[1-10],为保证概率均衡，每个元素在数组中的出现次数须一致。

即配置4组[1-10],每个元素被选中的概率都是1/10。多余的位置补0，随机算法逢0跳过。可以是3组，但是0会变多，导致跳过操作变多，所以0的最优个数必须小于10。

这种方法需要额外存储样本数据，扩展性不好。

方法二：

扩充随机算法的取值，有方法：randn()*n + randn().接下来用rand7做证明。 rand7的取值为：{1,2,3,4,5,6,7},则randn()*n的取值为：{7,14,21,28,36,42,49}。

那么randn()*n + randn()中：8出现的概率为1/49，9出现的概率为1/49，56出现的概率为1/49。以此归类，取值[8-56]的随机概率均衡。

当扩展的rand10时，截取取值集合[8-56]中40个数字，如[8-47]。每个元素随机概率依旧不变，每个出现概率为1/49。

每个数字对10取余数+1，则1出现的概率就是4/40 = 1/10，其他类推，满足rand10概率均衡要求。

代码

方法一

var arr = [][]int{
	{1, 2, 3, 4, 5, 6, 7},
	{8, 9, 10, 1, 2, 3, 4},
	{5, 6, 7, 8, 9, 10, 1},
	{2, 3, 4, 5, 6, 7, 8},
	{9, 10, 1, 2, 3, 4, 5},
	{6, 7, 8, 9, 10, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
}

func rand10() int {
	result := 0
	for result == 0 {
		result = arr[rand7()-1][rand7()-1]
	}
	return result
}

方法二：

func rand10() int {
    result := 1
	for result >= 48 || result < 8 {
		result = rand7()*7 + rand7()
	}
	return result % 10 + 1
}

性能

来自Leetcode, 0表示小于1个单位。

方法一：

执行用时: 8 ms

内存消耗: 5.5 MB

方法二：

执行用时: 4 ms

内存消耗: 5.5 MB

二、对链表进行插入排序

难度：中等

题目传送门：对链表进行插入排序

题目

给定单个链表的头head，使用插入排序对链表进行排序，并返回排序后链表的头。

插入排序算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。

部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

示例 1:
    输入: head = [4,2,1,3]
    输出: [1,2,3,4]
示例 2:
    输入: head = [-1,5,3,4,0]
    输出: [-1,0,3,4,5]

提示：

列表中的节点数在 [1, 5000]范围内
-5000 <= Node.val <= 5000

思路

由于是链表，所以需要记录表头，后续每一个需要插入的元素都需要从表头开始比对。其次插入条件，比前一位大，比后一位小于或者等于。

链表插入后，需要更新前一个节点的Next指针，还要连接后续没有排序的节点。

代码

编码之前，先写好测试：

func Test_insertionSortList(t *testing.T) {
	head1 := &ListNode{}
	head1.Val = 4
	next := &ListNode{Val: 2}
	head1.Next = next
	next.Next = &ListNode{Val: 1}
	next = next.Next
	next.Next = &ListNode{Val: 3}
	next = next.Next

	rHead1 := &ListNode{}
	rHead1.Val = 1
	next = &ListNode{Val: 2}
	rHead1.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next

	head2 := &ListNode{}
	head2.Val = -1
	next = &ListNode{Val: 5}
	head2.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next
	next.Next = &ListNode{Val: 0}
	next = next.Next

	rHead2 := &ListNode{}
	rHead2.Val = -1
	next = &ListNode{Val: 0}
	rHead2.Next = next
	next.Next = &ListNode{Val: 3}
	next = next.Next
	next.Next = &ListNode{Val: 4}
	next = next.Next
	next.Next = &ListNode{Val: 5}
	next = next.Next

	inputs := []*ListNode{head1, head2}
	expects := []*ListNode{rHead1, rHead2}

	for i := 0; i < len(inputs); i++ {
		got := insertionSortList(inputs[i])
		expected := expects[i]
		if !ListNodeEqual(got, expected) {
			t.Logf("[%d] want ", i+1)
			expected.print()
			t.Logf(",got ")
			got.print()
			t.Fatal()
		}
	}
}

func ListNodeEqual(head1, head2 *ListNode) bool {
	if head1.Val != head2.Val {
		return false
	}
	if !(head1.Next != nil && head2.Next != nil) {
		return true
	}
	return ListNodeEqual(head1.Next, head2.Next)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func (head *ListNode) print() {
	fmt.Print(head.Val)
	next := head.Next
	for next != nil {
		fmt.Printf(" ,%d", next.Val)
		next = next.Next
	}
	fmt.Println()
}

方法实现

func insertionSortList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	rHead := &ListNode{Val: 0, Next: head}
	end := head
	current := head.Next
	for current != nil {
		if current.Val >= end.Val {
			//直接下一个
			end = end.Next
			current = current.Next
			continue
		}

		// 插入之前，保存短点
		end.Next = current.Next

		insertNode := rHead
		for insertNode.Next.Val < current.Val {
			insertNode = insertNode.Next
		}

		//插入到insertNode后面
		current.Next = insertNode.Next
		insertNode.Next = current
		current = end.Next

	}
	return rHead.Next
}

性能

来自Leetcode, 0表示小于1个单位。

执行用时: 4 ms

内存消耗: 3.1 MB