从零开始的力扣刷题记录-第六十二天-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零开始的力扣刷题记录-第六十二天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2357. 使数组中所有元素都等于零-简单

题目描述：
给你一个非负整数数组 nums 。在一步操作中，你必须：
选出一个正整数 x ，x 需要小于或等于 nums 中最小的非零元素。
nums 中的每个正整数都减去 x。
返回使 nums 中所有元素都等于 0 需要的最少操作数。

题解：
由于每次都要减去一个最小的非零元素，可以想到的是两个不同的值不可能同时减为0，所以最小操作数实际上就等于数组中非零元素有多少种，直接哈希表统计即可

代码（Go）：

func minimumOperations(nums []int) int {
    arr := [101]int{}
    for _,v := range nums{
        arr[v]++
    }
    re := 0
    for i,v := range arr{
        if i != 0 && v != 0{
            re++
        }
    }
    return re
}

1984. 学生分数的最小差值-简单

题目描述：
给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间最高分和最低分的差值达到最小化。
返回可能的最小差值。

题解：
排序之后比较数组中两个间隔下标间隔k-1的数的差值，取最小值返回即可

代码（Go）：

func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    re := 100000
    for i,v := range nums[:len(nums) - k + 1] {
        re = min(re, nums[i + k - 1] - v)
    }
    return re
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

122. 买卖股票的最佳时机 II-中等

题目描述：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润。

题解：
贪心，只要第二天的价格比前一天高就在前一天买入第二天卖出，由于同时只能持有一只股票，可以想到这样做就可以得到最大利润，具体的证明可以去看官方题解

代码（Go）：

func maxProfit(prices []int) int {
    re := 0
    if len(prices) == 1{
        return re
    }
    for i := 1;i < len(prices);i++{
        if prices[i] - prices[i - 1] > 0{
            re += prices[i] - prices[i - 1]
        }
    }
    return re
}

213. 打家劫舍 II-中等

题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

题解：
实际上就是两次动态规划，一次包括开头，一次包括结尾，返回二者之间的最大值。我代码写的太繁琐了，两次动态规划合并在一起写的，需要判断一堆条件，所以这里就放一下官方的题解

代码（Go）：

func _rob(nums []int) int {
    first, second := nums[0], max(nums[0], nums[1])
    for _, v := range nums[2:] {
        first, second = second, max(first+v, second)
    }
    return second
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }
    return max(_rob(nums[:n-1]), _rob(nums[1:]))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}