Leetcode 每日一题练习

648. 单词替换

题解

读懂题是第一步, 本题要将句子中所有的单词替换为在词典中对应的它的前缀形式(如果字典中存在这个单词的前缀的话), 最直接的思路就是遍历句子中的所有单词, 将每个单词依次和词典中的所有单词比较, 看词典中是否存在它的前缀, 但这种方法无疑效率极低, 这个场景和我们日常查词典有些相似, 想想我们日常在词典中查一个单词是如何快速定位的, 当然是按照字母顺序在词典中先定位第一个字母的范围, 再定位第二个字母的范围…,最后找到需要的单词. 现在只要把这种方法表示出来就可以大大加快寻找前缀的速度. 这样就可以构造一棵词典树, 树的边表示不同的字母, 节点可以用来标定是否是一个可行单词. 再去查找某个单词的前缀的时候, 只需要去树中执行bfs找到最短的可行前缀即可.

代码

type TreeNodes struct{
    node [26]*TreeNodes
    over bool
}

func construct(dic []string) *TreeNodes{
    root := TreeNodes{}
    var point *TreeNodes
    for _, str := range dic{
        point = &root
        for i,_ := range str{
            if point.node[str[i]-'a']==nil{
                newnode := &TreeNodes{}
                point.node[str[i]-'a'] = newnode
                point = newnode
            }else{
                point = point.node[str[i]-'a']
            }
        }
        point.over = true
    }
    return &root
}

func findWord(root *TreeNodes, word string)(bool, string){
    var point *TreeNodes
    point = root
    prefix := []byte{}
    for i,_ := range word{
        if point.node[word[i]-'a'] == nil{
            return false,""
        }else{
            prefix = append(prefix, word[i])
            point = point.node[word[i]-'a']
            if point.over{
                return true, string(prefix)
            }
        }
    }
    return false,""
}

func replaceWords(dictionary []string, sentence string) string {
    root := construct(dictionary)
    sentenceArray := strings.Split(sentence, " ")
    exist, str := false, ""
    for i, word := range sentenceArray{
        exist, str = findWord(root, word)
        if exist{
            sentenceArray[i] = str
        }else{
            sentenceArray[i] = word
        }
    }
    return strings.Join(sentenceArray, " ")
}


总结

注意直接使用"+“在go中进行字符串连接是非常耗时的, 因此可以将原句子分割后得到字符串数组, 查询是否存在单词的可行前缀并直接替换对应数组中的字符串, 最后再调用strings.Join将数组中的所有字符串使用空格连接, 可以自行测试如果对数组中每个字符串在查找其可行前缀后都使用”+"连接到结果字符串上耗时远远大于这种方案.

523. 连续的子数组和

题解

本题要求连续子数组和为k的倍数, 则实际有影响的为各个位置上的元素对k取模后的余数, 这种求连续子数组和满足某种条件的问题, 常常可以使用前缀和求解. 在这个问题中使用前缀和保存从数组开头到当前位置元素的所有数字对k取模后求和再对k取模的值, 并将对应的值和当前的下标保存到长度为k的数组中, 数组下标表示前缀和(因为最终要对k取模,因此取值范围一定在k以内), 对应的数组位置的值为这个前缀和对应nums数组中的下标. 这种用数组保存的方式比用map来保存要快得多.

代码

func checkSubarraySum(nums []int, k int) bool {
    prefixsum := map[int]int{}
    prefixsum[0] = -1
    sum := 0
    exist := false
    val := 0
    for i,value := range nums{
        sum = (sum + value) % k
        val, exist = prefixsum[sum]
        if !exist{
            prefixsum[sum] = i
        }else if i - val > 1{
                return true
        }
    }
    return false
}

总结

没有注意到k的取值范围, 因为k的取值范围非常大, 使用数组来保存前缀和对应的下标需要开始k大小的数组, 在实践中会导致超出leetcode的内存限制. 因此这里还是要用map来保存前缀和和对应的下标, 但思路仍然是相同的.

974. 和可被 K 整除的子数组

题解

本题和昨天的题目类似, 通过前缀和相同来得到能被k整除的连续子数组, 注意本题中k的范围为 10^4, 因此可以用数组来保存前缀和对k取模后得到某个余数对应的下标位置个数. 后续遇到相同余数在结果中加上之前相同余数的位置个数, 并更新该余数对应的位置个数.

代码

func subarraysDivByK(nums []int, k int) int {
    remain := make([]int, k)
    remain[0] = 1
    sum  := 0
    result := 0
    for _, value := range nums{
        sum = ((sum + value)%k + k) % k
        result += remain[sum]
        remain[sum]++
    }
    return result
}

总结

注意对负数取模的处理, 在这里为了将相同余数的位置个数保存到数组中, 要将负数取模后的数转换为正数(如对5取模得-4转换为1, 在求和过程中这二者的效果相同), 先取模再加一个k再取模(如果是正数通过再取模将加上的k消掉)即可

1051. 高度检查器

题解

本题思路上很简单, 只需将数组复制一份并排序, 再与原数组比较即可. 这里主要意图应该是让你练习一下排序算法, 因此我们手动实现一下归并排序这种比较经典的排序算法. 归并算法是经典的分治法思想, 分治法分为"分"和"治"两部分, 分即将数组一分为二, 治即对于每个子数组进行排序, 最后将排好序的两个子数组合并(归并的"并"). 对于某一类分治法, 其时间复杂度可以使用主定理进行计算(感兴趣可自行了解).

代码

func heightChecker(heights []int) int {
    length := len(heights)
    sorted := mergeSort(heights, length)
    result := 0
    for i,value := range sorted{
        if value != heights[i]{
            result++
        }
    }
    return result
}

func mergeSort(input []int, length int) []int{
    if length == 1{
        return input
    }else{
        mid := length / 2
        left := mergeSort(input[0:mid],mid)
        right := mergeSort(input[mid:length],length-mid)
        result := []int{}
        j := 0
        for _,value := range right{
            for j<mid && left[j]<value{
                result = append(result, left[j])
                j++
            }
            result = append(result, value)
        }
        for j<mid{
                result = append(result, left[j])
                j++
        }
        return result
    }
}

1122. 数组的相对排序

题解

考虑数组中数字的大小范围在1000以内, 因此直接对数组排序可以使用计数排序算法. 本题中要求将数组1中的数字按照数组2中数字的顺序排序, 这部分也可以使用计数排序的思想, 即统计数组1中各个数的出现次数, 并保存在一个计数数组中, 这个数组中下标i处的值为数字i对应的数组1中出现的次数. 这种用下标指示值, 用元素指示个数的思路在前面的题中也多次出现. 得到计数数组后, 先将数组中包含在arr2的数按照arr2中的顺序放置, 并将对应位置次数归零, 再从头遍历数组, 按升序将其余数字放在末尾即可.

代码

func relativeSortArray(arr1 []int, arr2 []int) []int {
    count := make([]int, 1001)
    for _,value := range arr1{
        count[value]++
    }
    result := []int{}
    for _,value := range arr2{
        for count[value]>0{
            result = append(result, value)
            count[value]--
        }
    }
    for index,value := range count{
        for value > 0{
            result = append(result, index)
            value--
        }
    }
    return result
}

75. 颜色分类

题解

本题只有0,1,2三个数, 对只包含这三个数的数组进行排序, 直接在原数组上修改, 充分考虑题目条件, 没有必要使用排序算法来排序, 当题目中只有两个数的时候, 对整个数组排序相当于通过两变量交换将小的数都交换到前面, 大的都交换到后面. 现在有三个数, 则通过只需通过交换位置将所有的2都放到数组末尾, 将所有的0放到数组开头, 1自然就位于中间位置. 交换的思路也很简单, 通过两个变量分别标记被移到数组开头的0的个数和移到数组末尾的2的个数, 遇到0就将其移到之前的0的后面并将开头0的个数加一, 对2同理.

代码

func sortColors(nums []int)  {
    zeros := 0
    twos := len(nums) - 1
    Loop:
    for i, value := range nums{
        if value == 0{
            nums[i],nums[zeros] = nums[zeros],nums[i]
            zeros++
        }else if value == 2{
            for twos >= 0 && nums[i] == 2{
                if i >= twos{
                    break Loop
                }
                fmt.Println()
                nums[i],nums[twos] = nums[twos],nums[i]
                twos--
            }
            if nums[i] == 0{
            nums[i],nums[zeros] = nums[zeros],nums[i]
            zeros++
            }
        }
    }
    return
}

总结

思路是正确的, 但在实现时有一些细节要注意, 如遇到2将其交换到末尾时, 如果被交换过来的数也是2则要继续将其移到末尾, 直到交换过来的数不是2或者已经将当前下标后面的所有数都交换为2为止.

1 Like

2037. 使每位学生都有座位的最少移动次数

题解

本题总体思路比较直观, 因为找最小的移动次数让每个同学都坐在某个位置的椅子上, 因此只要找到同学位置和椅子位置最小的差值和就可以得到答案. 首先将椅子位置和同学位置均排序, 再从头遍历数组将二者差加和即得最终结果, 是一种贪心算法, 这里分析一下为什么排序后将椅子和同学的位置依次做差就能得到正确答案. 考虑数组中的任意两个位置, 假设椅子对应的位置为i和i+k, 同学对应的位置为j和j+m, 若则无论j,j+m和i的大小关系如何, 这两个同学挪到两个椅子的最小值均为|j-i|+|j+m-i-k|(可以自行考虑i,i+k,j,j+m这四个数的全部不同位置关系, 一一列举即可得出结论). 由两个位置的情况可推得一般情况, 即两个数组长度相同且均从小到大排序的情况下, 两个数组各个元素的差值的最小和就是各个位置元素差的和(还可以思考无论哪个同学坐到哪个位置上, 总要有另一个同学坐在另一个位置上从而将这两个同学的距离补上, 因此按照顺序一一就坐就是最优的).

代码

func minMovesToSeat(seats []int, students []int) int {
    sort.Ints(seats)
    sort.Ints(students)
    result := 0
    for i,value := range seats{
        if value > students[i]{
            result += value - students[i]
        }else{
            result += students[i] - value
        }
    }
    return result
}

945. 使数组唯一的最小增量

题解

本题思路上和昨天的题目基本一致, 先排序再从头遍历排好序的数组, 将重复的数字增加到最小不重复为止(如2,2,2,3, 将第二个2增加到3,将第三个2增加到4, 将3增加到5). 使用一个变量记录当前已经遍历过的数字修改后不重复数字中的最大值. 对遍历的每个数字, 判断其与当前最大值的关系, 若相等则将最大值加一并将结果加一, 小于最大值将最大值加一并将结果加上当前数字与最大值的差值, 大于最大值将最大值更新为当前数字.
考虑排序在这里的作用, 排序给每一个数字都提供了隐含的信息, 即前面的数字都比当前数字小, 后面的数字都比当前数字大, 这一信息使得我们可以做出更好的决策. 在未排序前, 对数组中的数我们无法知道是应该保持原样还是增加到某个数字可以满足题目条件, 但在排序后, 只需要增加到最小不重复的数即可, 考虑两个数字2,4, 假如当前不重复需要数字4,5(注意题目中只允许增加, 不允许减小). 无论是将2增加到4,4增加到5. 还是4不变,2增加到5, 增加的差值均为3. 这是因为任何比4大的值, 2都需要先增加到4, 再增加到这个值. 这一过程无论是在同一个数字上完成还是拆分为在两个数字上完成, 过程中需要改变的差值都是一样的.

代码

func minIncrementForUnique(nums []int) int {
    sort.Ints(nums)
    current := -1
    result := 0
    for _,value := range nums{
        if value == current{
            value++
            current++
            result++
        }else if value < current{
            current++
            result += current - value
        }else {
            current = value
        }
    }
    return result
}

502. IPO

题解

本题是一道难题, 思路总体还是比较清晰的, 本题目标是取k个不同的project, 使得最后能得到的利润最大. 每一个project都有对应的利润和成本. 要使最后的整体利润最大, 无疑只要在当前可以选择(即成本在当前已获得的资金范围内)的所有project中选择利润最大的, 再更新可选择的project, 再次选择利润最大的. 如此反复直到选择完全部的k个project即可. 有了这个思路, 我们要解决两个问题. 1. 如何高效的选择利润最大的project, 最大堆显然是一个不错的选择. 2. 如何更新可选择的project的范围, 我们将project的成本排序, 每次获得了更多的本金后就将小于当前本金的所有project的利润加入最大堆, 为了每次只放入新增加的project, 可以对project的成本数组排序, 用一个标记变量标记之前已经选择过的project位置. 获得更多本金后从标记位置开始继续遍历数组, 并将成本小于本金的项的利润放入最大堆中. 代码实现以上解题思路即可.

代码

type ProHeap []int

func (h ProHeap) Len()int {
        return len(h)
    }

func (h ProHeap) Less(i,j int)bool {
        return h[i] > h[j]
    }

func (h *ProHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *ProHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *ProHeap) Pop() interface{}{
	res := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return res
}

type Project struct {
	capital int
	profit  int
}

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
    n := len(profits)
	projects := make([]Project, n)

	for i := 0; i < n; i++ {
		projects[i] = Project{capital: capital[i], profit: profits[i]}
	}

    sort.Slice(projects, func(i, j int) bool {
		return projects[i].capital < projects[j].capital
	})



    proheap := make(ProHeap, 0)
    heap.Init(&proheap)

    mark := 0
    for k>0{
        for _,value := range projects[mark:n]{
            if value.capital > w{
                break
            }else{
                heap.Push(&proheap, projects[mark].profit)
                mark++
            }
        }
        if proheap.Len() == 0{
            return w
        }
        w += heap.Pop(&proheap).(int)
        k--
    }
    return w
}

总结

go中最大堆可以使用容器类heap来实现, 只要实现了heap接口的所有方法, 就可以直接使用这个堆了.

330. 按要求补齐数组

题解

本题是一道难题, 难点在于根据题目题意, 如何确定某个数组中数的和能够覆盖的数字范围. 按照我们一贯使用的思考方式, 先考虑一下简单情况, 若只有一个数字1, 则能覆盖的数字只有1, 添加上一个数字2, 则能覆盖的数字有1,2,1+2. 如果在1,2基础上再添加一个数字3, 则能覆盖的数字有1,2,1+2,3,1+3,2+3,1+2+3. 则由这几个简单例子可以发现, 如果之前能够覆盖的数字为集合{x}, 则加上一个数字r后能覆盖的数字为集合 x \cup (x + r) . 若之前能够覆盖的为一个连续的区间[x,x+k],则加上数字r后能够覆盖的区间为 [x,x+k] \cup [x+r, x+k+r]. 则此时想到可以用贪心算法, 如果已经覆盖了[x, x+k], 则只需要让x+r = x+k+1, 即新增加的数恰好可以使得新覆盖区间的开头为已经覆盖区间的末尾. 就能得到[x,x+k+r]的新覆盖区间. 如果r比这种情况小, 那么新覆盖的区间没有我们当前得到的区间大. 如果比这种情况大, 则x+r和x+k之间会有几个数字没有覆盖上, 还需要再用一个新的数覆盖一次, 显然很难使得添加数字的个数最小.

将这个思路在代码中实现, 初始化一个数字表示当前覆盖的区间最大值sum, 遍历数组, 设x为nums[i], 判断当前sum是否大于nums[i](即已经覆盖的区间是否包含当前这个数组中的数字). 如果小于, 则添加一个数字sum+1 前面分析中的x+k+1 (因为题目只要求添加的数字的最小个数,因此不需要真的添加到数组中, 只需扩大可行区间的范围即可), 将区间最大值扩展为sum+sum+1 前面分析中的x+k+r, 并将添加数字的个数加一. 再次判断与x的关系. 如此反复直到覆盖的区间包含x为止, 继续向下遍历. 遍历完成后, 判断当前区间是否已经可以覆盖n, 如果不能, 则按照之前的方法继续扩展区间直到能覆盖n为止.

代码

func minPatches(nums []int, n int) int {
    midsum := 0
    result := 0
    for _,value := range nums{
        for midsum < value-1 && midsum < n{
            result++
            midsum += midsum + 1
        }
        midsum += value
    }
    for midsum < n{
        result++
        midsum += midsum + 1
    }
    return result
}