用 Rand7() 实现 Rand10()

解题思路

已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数，即实现了rand_XY()


rand_N() % Y +1 ==> 只要N是Y的倍数，就可以实现利用rand_N()实现rand_Y()

要实现rand10()，就需要实现rand_N()，并且保证N大于10且是10的倍数。这样就可以通过rand_N() % 10 + 1得到[1, 10]范围内的随机数了。

(rand7()-1) × 7 + rand7() ==> rand49()，但是49不是10的倍数。这里就涉及到了“拒绝采样”的知识了，也就是说，如果某个采样结果不在要求的范围内，则丢弃它。

解题代码

func rand10() int {
    for {
        num := (rand7()-1) * 7 + rand7()    // rand49()
        if num <= 40 {  // 拒绝采样
            return num % 10 + 1
        }
    }
}

优化

func rand10() int {
    for {
        a := rand7()
        b := rand7()
        num := (a-1) * 7 + b    // rand49
        if num <= 40 {  // 拒绝采样
            return num % 10 + 1
        }

        a = num - 40    // rand9
        b = rand7()
        num = (a-1) * 7 + b      // rand63
        if num <= 60 {
            return num % 10 + 1
        }

        a = num - 60    // rand3
        b = rand7()
        num = (a-1) * 7 + b      // rand21
        if num <= 20 {
            return num % 10 + 1
        }
    }
}

和为K的子数组

解题思路

前缀和：preSum[i]为数组第0项到第i项的和。数组第i项到第j项的和：nums[i] + ... + nums[j] = preSum[j] - preSum[i-1]，令preSum[-1]=0，使i=0时成立。

使用一个哈希表记录前缀和出现的次数，从前到后遍历数组，若当前的前缀和为preSum，那么若前缀和为preSum-k，则可以构成两个前缀和之差为k。

解题代码

func subarraySum(nums []int, k int) int {
    hashMap := map[int]int{}    // 记录前缀和出现的次数
    hashMap[0] = 1  // 前缀和为0出现了0次，即preSum[-1]=0对应的
    preSum := 0     // 记录到nums[i]的前缀和
    count := 0

    for _, num := range nums {
        preSum += num   // 计算preSum[i]
        if hashMap[preSum-k] > 0 {
            // 有前缀和为preSum[i]-k
            count += hashMap[preSum-k]
        }
        hashMap[preSum]++
    }

    return count
}

课程表

解题思路

利用拓扑排序的思路，将选课过程看成是一次拓扑排序。某个课程的入度即为先修课程数，用一个栈记录没有先修课的课程。则拓扑排序的过程如下：

计算初始时的入度/先修课程数
将没有先修课的课程推入栈中
当栈中不空时循环，弹出栈中的课程，选择该课程。删除所有该课程的出边，若在删除出边后，某个课程的入度为0，则将这个课程送入栈中。

解题代码

func canFinish(numCourses int, prerequisites [][]int) bool {
    inDegrees := make([]int, numCourses)     // 记录入度，即先修课程数
    stack := make([]int, numCourses)         // 记录没有先修课的栈
    top := -1                                // 栈顶指针
    count := 0                               // 选课数
    // 计算初始时的入度/先修课程数
    for _, prerequisite := range prerequisites {
        inDegrees[prerequisite[0]]++
    }
    // 将没有先修课的课程推入栈中
    for course, inDegree := range inDegrees {
        if inDegree == 0 {
            top++
            stack[top] = course
        }
    }

    // 栈为空时结束循环
    for top >= 0 {
        // 将该课程弹出栈
        course := stack[top]
        top--
        // 选择该课程
        count++
        // 删除所有该课程的出边
        for _, prerequisite := range prerequisites {
            if prerequisite[1] == course {
                inDegrees[prerequisite[0]]--
                if inDegrees[prerequisite[0]] == 0 {
                    // 入度为0，送入栈中
                    top++
                    stack[top] = prerequisite[0]
                }
            }
        }
    }
    
    return count == numCourses
}

每日温度

解题思路

利用单调栈，从栈底到栈顶的温度递减，栈中记录的是温度下标。从前向后遍历温度列表：

若栈为空或者符合单调栈的单调递减特性，则入栈
否则弹出栈中所有小于当前温度的元素，弹出元素的同时更新answer

解题代码

func dailyTemperatures(temperatures []int) []int {
    answer := make([]int, len(temperatures))
    stack := make([]int, len(temperatures))     // 单调栈，从栈底到栈顶温度递减，栈中记录的是下标
    top := -1                                   // 栈顶指针

    // 遍历第i天的温度temperature
    for i, temperature := range temperatures {
        if top < 0 || temperature <= temperatures[stack[top]] {
            // 若栈为空，或者第i天的温度低于栈顶所对应的温度，直接进栈
            top++
            stack[top] = i
        } else {
            // 弹出栈中所有小于当前温度的元素
            for top >= 0 && temperature > temperatures[stack[top]] {
                // 更新answer
                answer[stack[top]] = i-stack[top]
                // 出栈
                top--
            }
            // 当前温度进栈
            top++
            stack[top] = i
        }
    }

    return answer
}

Dawn's Blogs

算法刷题笔记 (26) 用Rand7()实现Rand10() 和为K的子数组课程表每日温度

用 Rand7() 实现 Rand10()

解题思路

解题代码

和为K的子数组

解题思路

解题代码

课程表

解题思路

解题代码

每日温度

解题思路

解题代码