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

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

2441. 与对应负数同时存在的最大正整数-简单

题目描述：
给你一个不包含任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。
返回正整数 k ，如果不存在这样的整数，返回 -1 。

题解：
哈希表存储负数，再遍历nums对每一个正数去哈希表中查找是否存在对应的负数。存在就更新返回值

代码（Go）：

func findMaxK(nums []int) int {
    dict := map[int]int{}
    for _,v := range nums{
        if v < 0{
            dict[v] = 1
        }
    }
    temp := -1
    for _,v := range nums{
        if v > 0 && dict[-v] == 1{
            if v > temp{
                temp = v
            }
        }
    }
    return temp
}

1464. 数组中两元素的最大乘积-简单

题目描述：
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。

题解：
一次遍历，维护最大值和最小值

代码（Go）：

func maxProduct(nums []int) int {
    first,second := 0,0
    for _,v := range nums{
        if v > first {
            second = first
            first = v
        }else if v > second{
            second = v
        }
    }
    return (first - 1) * (second - 1)
}

1646. 获取生成数组中的最大值-简单

题目描述：
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
返回生成数组 nums 中的最大值。

题解：
直接模拟，创建数组的过程中记录最大值即可

代码（Go）：

func getMaximumGenerated(n int) int {
    nums := make([]int,n + 1)
    temp := 0
    for i := 0;i <= n;i++{
        if i == 0{
            nums[i] = 0
        }else if i == 1{
            nums[1] = 1
        }
        if i%2 == 0{
            nums[i] = nums[i/2]
        }else{
            nums[i] = nums[i/2] + nums[i/2 + 1]
        }
        if nums[i] > temp{
            temp = nums[i]
        }
    }
    return temp
}

93. 复原 IP 地址-中等

题目描述:
有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

题解：
回溯常规步骤，终止条件是已经插入三个点，如果分割成的第四部分字符串对应的数值在0-255之间且没有前导0就加入结果集，for循环需要一个start变量标记起点，加入新数字的判断与终止条件判断相同，如果可以加入就用一个新字符串存储插入点后的字符串并用于递归传递，循环次数不能超过3次并且起始位置必须小于len(s)-3+point，这是为了给后续的插入留出空间；递归调用时需要让point加一，因为插入了一个点，所以i需要额外再加一即i加二

代码（Go）：

func restoreIpAddresses(s string) []string {
    re := []string{}
    var backtrack func(s string,point int,start int)
    backtrack = func(s string,point int,start int){
        if point == 3{
            temp := strings.Split(s,".")
            tempnum,_ := strconv.Atoi(temp[3])
            if tempnum >=0 && tempnum <= 255{
                if temp[3][0] == '0' && len(temp[3]) != 1{
                    return
                }
                re = append(re,s)
                return
            }
            return
        }
        var temp string
        for i := start;i < start + 3 && i < len(s) - 3 + point;i++{
            temp += string(s[i])
            tempnum,_ := strconv.Atoi(temp)
            if tempnum >= 0 && tempnum <= 255{
                if temp[0] == '0' && len(temp) != 1{
                    break
                }
                temps := s[:i + 1] + "." + s[i + 1:]
                backtrack(temps,point + 1,i + 2)
            }

        }
    }
    backtrack(s,0,0)
    return re
}