day 1 2024-02-27
543 Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
题解
读题, 题目要求寻找二叉树中任意两节点之间的最大距离. 这时这个二叉树更像是一个图的性质而不是树, 即寻找图中任意两节点之间的最大距离. 考虑任意一点到另一点的距离等于其到另一点的父节点的距离减一, 则使用一个二维数组保存每个节点的两个属性:
- 以该节点为根节点且经过该节点的最大直径
- 以该节点为根节点的子树中叶子节点到该节点的最大距离
属性1可以通过将该节点的两个子节点的属性2加和并加1来计算. 属性2取两个子节点属性2的最大值并加1来计算. 最后遍历数组求得数组中属性1的最大值即可. 有一点动态规划的思想.
题目中并没有提供二叉树的节点总数, 则可以使用动态创建的方法, 在遍历过程中每遇到新节点就在二维数组中增加一项. 这里使用递归来对树进行后序遍历, 对空节点, 设置其属性2的值为-1, 这样保证叶子节点的属性2的值为0.
解题时遇到一个小bug, 使用了一个全局切片(数组)来保存变量时, 第一个测试用例的数据会保留到测试第二个测试用例的过程中, 这大概是因为leetcode的测试是对每个用例直接调用给出的解题入口函数, 因此需要在解题函数中将使用的全局变量初始化一下, 将数组设置为空后问题得到解决.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var length [][]int
func diameterOfBinaryTree(root *TreeNode) int {
length = nil
_ = postorder(root)
max := -1
for _, value := range length{
if value[0] > max{
max = value[0]
}
}
return max
}
func postorder(father *TreeNode) int {
if father != nil{
len1 := postorder(father.Left)
len2 := postorder(father.Right)
len := make([]int,2)
// find the max diameter pass through current node from the tree rooted current node
len[0] = len1 + len2 + 2
len[1] = max(len1, len2) + 1
length = append(length, len)
return len[1]
} else {
return -1
}
}
|
day2 2024-02-28
513. Find Bottom Left Tree Value
Given the root of a binary tree, return the leftmost value in the last row of the tree.
题解
找到二叉树最底层最左边的节点值, 用层序遍历遍历到最后一层找到最后一层最左边节点的值即可. 实现层序遍历可以使用一个队列, 将当前层节点的所有子节点入队后将当前层节点出队. 在go中可以使用切片实现一个队列. 使用一个标记变量记录当前层所有节点是否有子节点, 若无子节点则当前层为最低层, 返回当前层最左侧节点的值(此时队列中第一个节点的值).
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
queue := []*TreeNode{root}
lowest := false
key := -1
var father *TreeNode
for !lowest{
queue = queue[key+1:]
lowest = true
for key, father = range queue{
if(father.Left != nil || father.Right != nil){
lowest = false
if(father.Left != nil){
queue = append(queue, father.Left)
}
if(father.Right != nil){
queue = append(queue, father.Right)
}
}
}
}
return queue[0].Val
}
|
总结
在题解中看到了一个使用深度优先搜索的方法, 记录当前搜索到的层级, 始终保存最大层级的第一个被搜索到的值, 因为使用的是后序遍历, 则每次遇到的当前层大于保存的最大层级时, 该节点就为新的最大层级的第一个节点, 即题目中要求的最左值(leftmost). 算法时间复杂度为O(n)——只遍历一次所有节点.
day3 2024-02-29
1609. Even Odd Tree
A binary tree is named Even-Odd if it meets the following conditions:
The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).
Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.
题解
对二叉树的奇数层, 其节点从左到右是严格递减的(意味着有两个节点的值相同是不允许的), 偶数层是严格递增的. 仍然可以使用昨天题目的层序遍历的方法, 增加一个level变量记录当前层数, 对该层内的节点值进行判断是否符合奇数层和偶数层对应的条件即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isEvenOddTree(root *TreeNode) bool {
level := 0
index := -1
var value *TreeNode
queue := []*TreeNode{root}
saved := 0
for len(queue) != 0{
// remove visited nodes
queue = queue[index+1:]
index = 0
if(level%2 == 0){
for index, value = range queue{
if(index == 0){
saved = value.Val
if(saved %2 != 1){return false}
} else{
if(value.Val <= saved || (value.Val%2) != 1){
return false
} else{
saved = value.Val
}
}
if(value.Left != nil){queue = append(queue, value.Left)}
if(value.Right != nil){queue = append(queue, value.Right)}
}
level++
} else{
for index, value = range queue{
if(index == 0){
saved = value.Val
if(saved %2 != 0){return false}
} else{
if(value.Val >= saved || value.Val %2 != 0){
return false
} else{
saved = value.Val
}
}
if(value.Left != nil){queue = append(queue, value.Left)}
if(value.Right != nil){queue = append(queue, value.Right)}
}
level++
}
}
return true
}
|
总结
go语言中的for range循环, 如果使用类似for key, value := range list 的形式, 那么key, value这两个变量都会在当前作用域下新建, 意味着即使在前面定义了key, key的值在循环结束后也不会被修改. 若想修改之前定义的key值, 需要将value也提前定义好并使用=而不是:=.
go语言中的for range循环时如果使用:=会新建两个变量, 然后将slice中的值复制给value变量, 将对应的index值赋值给key变量, 这意味着value变量不会指向数组中对应位置的地址, 而是一个不变的单独地址.
day4 2024-03-01
2864. Maximum Odd Binary number
You are given a binary string s that contains at least one ‘1’.
You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.
Return a string representing the maximum odd binary number that can be created from the given combination.
Note that the resulting string can have leading zeros.
Example 1:
Input: s = “010”
Output: “001”
Explanation: Because there is just one ‘1’, it must be in the last position. So the answer is “001”.
Example 2:
Input: s = “0101”
Output: “1001”
Explanation: One of the ‘1’s must be in the last position. The maximum number that can be made with the remaining digits is “100”. So the answer is “1001”.
题解
题目中说明了给出的字符串中至少有一个1, 因此可以复制一个字符串, 然后遍历原字符串, 遇到第一个1放在最后一位, 0永远插入到倒数第二位, 不是第一个1放在字符串最前面. 由此除保证字符串是奇数的最后一个1以外, 其余的1都在字符串最前面, 其余的0都插入在最前面的一串1和最后的1之间. 保证了字符串是最大的奇数字符串.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func maximumOddBinaryNumber(s string) string {
s_copy := ""
flag := 0
for _, value := range s{
if value == '1'{
if flag != 0{
s_copy = "1" + s_copy
} else{
s_copy = s_copy + "1"
flag = 1
}
} else{
if(len(s_copy) >=2){
s_copy = string(s_copy[:len(s_copy)-1]) + "0" + string(s_copy[len(s_copy)-1])
} else {
s_copy = "0" + s_copy
}
}
}
return s_copy
}
|
总结
在处理字符串的时候像中间某个位置插入字符也要使用双引号, 如插入字符0要用+"0"而不是+'0', 此外在截取切片的时候go的切片是左闭右开的. 如[0:3]截取的是0,1,2三个数
day5 2024-03-02
977. Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
题解
考虑原数组已经按照非递减排序的情况下, 找到数组中正负交界处元素, 即数组中第一个正数, 以该位置作为起始位置, 使用双指针法, 分别向前和向后遍历数组, 遍历时不断比较两个指针指向的数字的绝对值大小, 将绝对值小的数字平方后追加到结果数组的尾部, 遍历完成即可完成平方值排序. 这样只需要遍历一遍数组即可完成排序.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| func sortedSquares(nums []int) []int {
index := 0
value := nums[0]
var result []int
for index, value = range nums{
if(value >= 0){
break
}
}
backward := index - 1
forward := index
if index != 0{
for _,_ = range nums{
if backward<0{
result = append(result, nums[forward]*nums[forward])
forward++
} else if forward>= len(nums){
result = append(result, nums[backward] * nums[backward])
backward--
} else{
if(abs(nums[forward]) < abs(nums[backward])){
result = append(result, nums[forward]*nums[forward])
forward++
} else{
result = append(result, nums[backward] * nums[backward])
backward--
}
}
}
}else{
for _,_ = range nums{
result = append(result, nums[forward]*nums[forward])
forward++
}
}
return result
}
func abs(val int) int {
if(val < 0){
return -val
}else{
return val
}
}
|
总结
注意一个go的语法问题, 如果在for range循环中两个变量都使用匿名变量, 则应该使用赋值运算符而不是创建并赋值运算符, 即for _,_ = range slice 而不是for _,_ := range slice. 这很可能是因为匿名变量默认为已经创建好的变量, 不需要再创建匿名变量本身了.
day6 2024-03-03
19. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
题解
给出了链表头, 要求移除从后到前的第n个节点. 如果想一遍遍历就完成这个任务. 就使用空间换时间, 使用一个数组保存所有的Next指针的值. 然后让倒数第n+1个元素的Next指针指向n个元素的Next指针即可, 注意处理链表只有一个元素的特殊情况.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
var ptr []*ListNode
current := head
for current.Next != nil{
ptr = append(ptr, current)
current = current.Next
}
ptr = append(ptr, current)
if(len(ptr) == 1){
return nil
}else if len(ptr) == n{
return ptr[1]
}else{
ptr[len(ptr)-n-1].Next = ptr[len(ptr)-n].Next
return head
}
}
|
总结
在题解中看到大部分使用的是快慢指针的解法, 快慢指针应该是本题想要的解法, 下面贴一个快慢指针的解法示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummyHead := &ListNode{-1, head}
cur, prevOfRemoval := dummyHead, dummyHead
for cur.Next != nil{
// n step delay for prevOfRemoval
if n <= 0 {
prevOfRemoval = prevOfRemoval.Next
}
cur = cur.Next
n -= 1
}
// Remove the N-th node from end of list
nthNode := prevOfRemoval.Next
prevOfRemoval.Next = nthNode.Next
return dummyHead.Next
}
|
day7 2024-03-04
948. Bag of Tokens
You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] donates the value of tokeni.
Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):
Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.
Return the maximum possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).
Example 2:
Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.
There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.
Example 3:
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
The maximum score achievable is 2.
题解
本题的目的是最大化score. 一个基本的策略就是通过小的power换取score, 通过score换取大的power, 利用换到的大power赚取中间水平的token的score. 关键在于, 如何找到最大能换取的score. 首先考虑每次进行一次Face-up和Face-down, score没有变化, 只有power增大了, 那么每次都将score置0, 并判断当前能获得的最大score即可.
通过前面的分析可以得出, 算法分为以下几步
- 将tokens数组排序
- 判断power是否大于tokens[0], 即最小的token, 若大于, 则计算当前能获得的最大score
- 将power的值增加目前tokens数组中最大值和最小值(即排好序后的最后一项和第一项)的差值, 同时将tokens数组中第一项和最后一项移除. 重复2, 3步直到power小于tokens[0]或tokens数组长度为0中止.
- 返回最大的score
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func bagOfTokensScore(tokens []int, power int) int {
sort.Ints(tokens)
var powernormal []int
remain := power
score := 0
powernormal = append(powernormal, score)
for len(tokens) != 0 && power > tokens[0]{
remain = power
for _, value := range tokens{
if power >= value{
score++
power -= value
} else{
break
}
}
powernormal = append(powernormal, score)
score = 0
remain += tokens[len(tokens)-1] - tokens[0]
if len(tokens) <= 1{
break
}
tokens = tokens[1:len(tokens)-1]
power = remain
}
sort.Ints(powernormal)
return powernormal[len(powernormal)-1]
}
|
总结
在实现过程中, 起初使用一个数组来保存每次的score值, 这样空间复杂度略大, 后来查看他人代码, 发现只需要一个max变量来保存当前最大的score值, 并在每次循环计算当前轮次的score值时与当前的最大值比较并根据二者大小更新max变量的值即可, 这样只需要O(1)的空间复杂度.
day8 2024-03-05
1750. Minimum Length of String After Deleting Similar Ends
Given a string s consisting only of characters ‘a’, ‘b’, and ‘c’. You are asked to apply the following algorithm on the string any number of times:
- Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
- Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
- The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- Delete both the prefix and the suffix.
Return the minimum length of s after performing the above operation any number of times (possibly zero times).
题解
本题的题目略显复杂, 读起来乍一看让人不明所以, 实际上题目的目标即为从字符串的前后同时删除相同的字符, 删除时只要是相同的就全部删除, 如最前面有一个a最后面有3个a则同时将这四个a删除. 删除的字符串下标不能相交. 思路比较简单, 判断字符串的前后字符是否相同, 然后删除前后的连续相同字符即可, 注意下标不要重叠. 同时注意边界情况, 字符串只有一个字符的情况单独处理一下(直接返回1).
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func minimumLength(s string) int {
forward := 0
backward := 0
for s[0] == s[len(s)-1]{
if len(s) == 1{
return 1
} else {
forward = 0
backward = len(s)-1
for forward<backward && s[forward+1] == s[forward] {
forward++
}
for backward>forward && s[backward-1] == s[backward] {
backward--
}
if forward == backward{
return 0
}
s = s[forward+1:backward]
}
}
return len(s)
}
|
总结
本题值得注意的地方在于for循环中条件的设置, 可能会忽略与运算符两侧条件表达式的前后顺序, 但由于短路机制的存在, 与运算符两侧表达式的前后顺序有时非常重要, 例如在本题中, 如果将forward<backward条件设置在前面, 则当forward到达数组的边界时会直接退出循环, 但若将相等判断放在前面, 会因为当forward到达数组边界时forward+1下标越界而出错.
day9 2024-03-06
141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
题解
本题最简单的思路就是使用并查集, 因为go语言中的map类型在获取数据时会返回该键值在map中是否存在, 因此可以将map类型直接当作一个简单的并查集使用.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
if head==nil{
return false
}
ptrs := make(map[*ListNode]int)
var exist bool
ptrs[head] = 1
for head.Next != nil{
_, exist = ptrs[head.Next]
if !exist{
ptrs[head.Next] = 1
head = head.Next
} else{
return true
}
}
return false
}
|
总结
题目中给出提示本题可以使用O(1)的空间复杂度解决, 即使用常数空间复杂度, 研究他人题解发现本题同样可以使用快慢指针,核心思想类似于加速度, 快指针的加速度比慢指针要快, 即快指针每次移动的步长比慢指针移动的步长多1. 这样若链表中有环则快指针最终总能比慢指针快整整一个环的长度从而追上慢指针. 若没有环则快指针永远不可能追上慢指针. 类似于跑步时如果一直跑, 跑得快的同学最终总能套跑得慢的同学一圈. 快慢指针在很多情景下都有很巧妙的应用. 后续可以在遇到多个相关题目后加以总结. 给出快慢指针解决本题的代码示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
slow := head
fast := head
for slow != nil && fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
|
day10 2024-03-07
876. Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
题解
本题寻找链表中间位置的元素, 是一个经典快慢指针的题目. 只需要让快指针前进的速度为2, 慢指针为1, 则快指针到达链表末尾时慢指针正好指向中间位置. 要注意链表元素个数为奇数和偶数时的处理方法的不同.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode(head *ListNode) *ListNode {
fast := head
slow := head
for fast.Next != nil && fast.Next.Next != nil{
fast = fast.Next.Next
slow = slow.Next
}
// consider list number is even
if fast.Next != nil{
slow = slow.Next
}
return slow
}
|
总结
本题是一道经典的快慢指针的简单题目, 进一步深化了快慢指针的应用.
day11 2024-03-08
3005. Count Elements With Maximum Frequency
You are given an array nums consisting of positive integers.
Return the total frequencies of elements in nums such that those elements all have the maximum frequency.
The frequency of an element is the number of occurrences of that element in the array.
Example 1:
Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.
题解
因为题目给出了正整数的范围为1-100, 因此本题可以用简单的数组来解决, 数组下标表示对应的整数, 0不做任何表示. 然后遍历数组将频率最多的元素相加即可. 可以设置一个max标志位来表示当前的最大频率, 相等则增加和, 比max大则将和重置并设max为新的最大值.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func maxFrequencyElements(nums []int) int {
frequency := make([]int, 101)
for _,value := range nums{
frequency[value]++
}
max := 0
sum := 0
for _,value := range frequency{
if value > max{
max = value
sum = max
} else if value == max{
sum += value
}else{
continue
}
}
return sum
}
|
总结
本题注意考查数据范围, 在数据范围有限的情况下直接使用数组要比哈希表快得多.
day12 2024-03-09
2540. Minimum Common Value
Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.
Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.
Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest element common to both arrays is 2, so we return 2.
Example 2:
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.
题解
本题使用两个指针分别指向两个数组, 然后依次移动两个指针比较大小即可, 位于数值更小的位置的数组指针向前移动直到相等或者到数组末尾为止.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| func getCommon(nums1 []int, nums2 []int) int {
index1, index2 := 0 , 0
for index1<len(nums1) && index2 < len(nums2){
if nums1[index1] < nums2[index2]{
index1++
}else if nums2[index2] < nums1[index1]{
index2++
} else{
return nums1[index1]
}
}
return -1
}
|
总结
这是一道典型的双指针问题, 思路清晰就可以很快解决.
day13 2024-03-10
349. Intersection of Two arrays
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.
题解
因为数组是无序数组, 寻找二者的相同元素比较困难, 故可先对两数组排序, 然后双指针遍历两个数组找到数组中的相同值. 将值作为key, key对应的value为true放入map中. 这里不需要多余判断map中是否已经存在这个key了, 因为再次给相同的key赋值不会增加新的条目, 而只是覆盖之前的key的值, 我们只需要key来判断map中是否有相同值.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func intersection(nums1 []int, nums2 []int) []int {
intersection := make(map[int]bool)
sort.Ints(nums1)
sort.Ints(nums2)
index1, index2 := 0,0
for index1 < len(nums1) && index2 < len(nums2){
if nums1[index1] < nums2[index2]{
index1++
}else if nums1[index1] > nums2[index2]{
index2++
}else{
_, ok := intersection[nums1[index1]]
if !ok{
intersection[nums1[index1]] = true
}
index1++
index2++
}
}
var result []int
for key, _ := range intersection{
result = append(result, key)
}
return result
}
|
总结
在查看他人题解过程中, 发现排序其实是没有必要的, 可以直接将一个数组中的值全部作为key, 对应的value为true放入map中. 然后遍历另外一个数组, 同时判断当前遍历的元素在不在map中, 若存在则将其放入结果数组中, 同时将map中key对应的value置为false, 表示该key已经被访问过, 这样可以避免在结果数组中添加重复元素.
一个示例代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func intersection(nums1 []int, nums2 []int) []int {
res := make([]int, 0)
m := make(map[int]bool, len(nums1))
for _, v := range nums1 {
if _, exists := m[v]; exists {
continue
}
m[v] = false
}
for _, v := range nums2 {
used, exists := m[v]
if exists && !used {
res = append(res, v)
m[v] = true
}
}
return res
}
|
day14 2024-03-11
791. Custom Sort String
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
题解
本题初始想先扫描s字符串, 使用一个map记录字符串中各个字符的数量, 再遍历order依次将字符按数量附加到末尾即可. 但考虑到字符只有26个小写英文字母, 使用一个长度为26的数组来保存对应位置的英文字母的数量. 再遍历要比map速度快.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func customSortString(order string, s string) string {
a := 'a'
result := ""
numbers := make([]int, 26)
for _, character := range s{
numbers[character-a]++
}
for _,c := range order{
temp := numbers[c-a]
for i:=0;i<temp;i++{
numbers[c-a]--
result += string(c)
}
}
for key,c := range numbers{
if c!=0{
for i:=0;i<c;i++{
result += string(rune(int(a)+key))
}
}
}
return result
}
|
总结
注意题中条件, 遍历的类型有限的情况下直接使用数组保存, 遍历起来速度要快得多.
day15 2024-03-12
1171. Remove Zero Sum Consecutive Nodes from Linked List
Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.
After doing so, return the head of the final linked list. You may return any such answer.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
题解
本题有一定难度, 寻找连续的和为0的连续序列要使用前缀和, 若某两个元素的前缀和相同, 则位于二者之间的序列和即为0. 删除这部分序列. 先遍历链表, 找到所有前缀和相同的元素, 然后将其中间的部分全部删除即可.
使用一个map来保存前缀和对应的Node的指针, 当找到一个前缀和相同的Node时, 从map保存的指针开始删除到该Node的所有节点, 同时删除以中间部分节点的前缀和为key的map中对应的项防止后面有和中间部分项相同的前缀和的节点存在.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| v/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
current := head
sum := 0
summap := map[int](*ListNode){}
for current != nil{
sum += current.Val
if sum == 0{
for head != current.Next{
sum += head.Val
delete(summap, sum)
head = head.Next
}
}
ptr, exist := summap[sum]
if !exist{
summap[sum] = current
}else{
back := ptr
ptr = ptr.Next
for ptr != current{
sum += ptr.Val
delete(summap, sum)
ptr = ptr.Next
}
sum += ptr.Val
back.Next = current.Next
}
current = current.Next
}
return head
}
|
总结
删除中间部分节点的前缀和对应的key的项时, 考虑到中间部分的和一定为0, 因此用sum去累加中间部分节点的值并依次删除, 最后得到的sum就和删除节点开始前的sum相同. 本题一是要清楚通过前缀和来寻找连续的和为0的序列, 另一方面则是时刻记住这个序列的和为0的特性. 其实本题有一种代表元的抽象思想. 可以将一组和为0的序列看为一个, 其在加和过程中与不存在的节点具有等价性. 不影响和的变化.
day16 2024-03-13
2485. Find the Pivot Integer
Given a positive integer n, find the pivot integer x such that:
The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.
Example 1:
Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
Example 2:
Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.
Example 3:
Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.
题解
本题使用数学方法进行计算
根据公式直接求出x的值即可, 注意考虑到精度问题, 要对最终得到的运算结果与取整后的数字的差的绝对值进行判断, 小于一定限度即可认为是整数值.
代码
1
2
3
4
5
6
7
8
9
| func pivotInteger(n int) int {
n_float := float64(n)
x := n_float*math.Sqrt(n_float+1)/math.Sqrt(2*n_float)
if math.Abs(x-float64(int(x))) < 0.0000001{
return int(x)
}else {
return -1
}
}
|
总结
查看他人解法发现本题其实也可以使用前缀和进行求解, 将每个下标位置处的前缀和求出并保存, 倒序遍历数组, 将后面的数的和与当前位置的前缀和比较即可, 示例代码
day17 2024-03-14
930. Binary Subarrays With Sum
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.
A subarray is a contiguous part of the array.
Example 1:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
Example 2:
Input: nums = [0,0,0,0,0], goal = 0
Output: 15
题解
本题可以用前缀和求解, 类似这种求数组中连续和的问题都可以用前缀和求解, 首先计算出所有位置上的前缀和, 使用滑动窗口遍历前缀和数组, 根据goal的值调整窗口的左右边界, 注意0需要特殊处理, 0是否存在不影响整个序列的和, 0所在的位置处的前缀和和前面的元素相同.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| func numSubarraysWithSum(nums []int, goal int) int {
sum := 0
prefixsum := []int{0}
for _,value := range nums{
sum += value
prefixsum = append(prefixsum, sum)
}
front := 1
back := 0
flag := 0
result := 0
for front < len(prefixsum){
if prefixsum[front] - prefixsum[back]<goal{
front++
}else if prefixsum[front] - prefixsum[back]>goal{
if front-1 == back{
front++
}
back++
}else{
if (front-1 == back){
result++
front++
back = flag
}else if prefixsum[back] == prefixsum[back+1]{
result++
back++
}else if (front<len(prefixsum)-1) && prefixsum[front] == prefixsum[front+1]{
result++
front++
back = flag
}else{
result++
back++
flag=back
}
}
}
return result
}
|
总结
本题使用滑动窗口时间复杂度上比较高, 考虑在滑动窗口的过程中, 连续的0的部分被重复遍历, 大大增加了总体的运行时间. 其实本题只需要用当前的前缀和减去goal, 并寻找前面的前缀和中是否有符合差值的前缀和存在, 存在则从该前缀和位置到当前前缀和位置直接的序列满足和为goal的条件. 已经求出了前缀和就没必要再去一个个遍历并且滑动了, 如果使用滑动窗口则没必要计算前缀和. 我的解法实际上是对前缀和理解不深刻导致的. 巧用前缀和加哈希表(存储某个前缀和出现的次数)可以快速的解决这个问题. 示例代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func numSubarraysWithSum(nums []int, goal int) int {
hash := map[int]int{}
sum := 0
count := 0
hash[0] = 1
for i:=0; i < len(nums); i++ {
sum = sum + nums[i]
count = count + hash[sum - goal]
val, ok := hash[sum]
if(ok) {
hash[sum] = val + 1
} else {
hash[sum] = 1
}
}
return count
}
|
还有一种极其巧妙的解法, 分别求得和小于等于goal的连续子序列的数量, 再减去和小于等于goal-1的连续子序列的数量即为最终结果. 本题中求子序列等于goal是比较困难的, 要考虑很多条件, 但是求小于等于goal的子序列却是比较简单的问题. 这种方法将一个困难问题转化为两个简单的子问题求解, 得到了更高效的方法. 充分利用整体性可使问题更简单. 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| func numSubarraysWithSum(nums []int, goal int) int {
return counting(nums, goal) - counting(nums, goal-1)
}
func counting(nums []int, goal int) int {
if goal < 0 {
return 0
}
left, right, sum, ans := 0, 0, 0, 0
for ; right < len(nums); right++ {
sum += nums[right]
for left <= right && sum > goal {
sum -= nums[left]
left++
}
ans += right - left + 1
}
return ans
}
|
day18 2024-03-15
238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
题解
题目中明确要求本题不能使用分治法, 且算法复杂度在O(n). 本题要求的为数组中每个元素对应的除该元素之外的其他元素的乘积. 根据给出的例子可以发现当存在0的时候是一种特殊情况. 当存在0时除0以外的其他元素对应的结果均为0. 一般情况下可以使用先求出全部元素的乘积, 再遍历数据使用总乘积除以当前元素即可求得对应位置的结果. 因为这样只需要固定遍历两次数据, 故时间复杂度为O(n), 又只需要一个变量来保存总乘积, 一个变量指示是否存在0元素, 故空间复杂度为O(1). 因为题目中明确说明了乘积保证为整数, 故在使用除法的过程中不用考虑结果为小数的问题.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| func productExceptSelf(nums []int) []int {
sum := 1
flag := 0
for _, value := range nums{
if value == 0{
flag++
}else{
sum *= value
}
}
if flag > 1{
return make([]int, len(nums))
}
if flag == 1{
result := []int{}
for _, value := range nums{
if value == 0{
result = append(result, sum)
}else{
result = append(result, 0)
}
}
return result
}
result := []int{}
if flag == 0{
for _, value := range nums{
result = append(result, sum/value)
}
}
return result
}
|
总结
查看更快的解法, 发现都使用了前缀积和后缀积, 即从前向后遍历, 计算出当前位置元素的前缀积, 然后反向遍历, 在计算出后缀积的同时就得到了最终的结果. 一个示例代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func productExceptSelf(nums []int) []int {
res := make([]int, len(nums))
prefix := 1
for i, n := range nums {
res[i] = prefix
prefix *= n
}
postfix := 1
for i := len(nums) - 1; i >= 0; i-- {
res[i] *= postfix
postfix *= nums[i]
}
return res
}
|
其实无论是前缀和还是前缀积, 都是一个对以往的计算状态的保留, 保存了更多的信息, 避免了重复的运算, 这种思想是值得细细品味的.
day19 525. Contiguous Array
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
题解
考虑本题若想找到到某一个位置处的0和1数量相同的最长子数组长度, 只需要根据到该下标处的0和1数量的差值, 找出符合这个差值的最小下标, 用当前下标减去这个差值下标, 得到的即为0和1数量相同的子数组的长度. 关键在于想要让0和1数量相同, 需要找出能消除当前0和1数量差值的位置. 0和1数量对于寻找相同数量子数组用处不大, 二者数量的差值对于构造一个数量相同的子数组至关重要. 通过加上或减去二者的数量差即可构造出二者数量相同的子数组. 考虑清楚这一点, 思路就很清晰了.
- 遍历数组, 保存到当前位置0和1的数量
- 计算二者的差值, 在一个哈希表中寻找以这个差值为key的项是否存在, 不存在则将差值为key, 当前下标作为该key对应的值插入哈希表. 若存在则用当前下标减去哈希表中以差值作为key的对应的下标值, 即得到到当前位置0和1数量相同的最长子数组的长度. 比较这个长度和保存的最长子数组长度, 更新最长子数组长度.
关键在与将差值作为key下标作为value插入哈希表后, 后续有相同的差值作为key时不在更新哈希表, 这样保存的就是符合这个差值的位置的最小值, 也就能构造出最长的0和1数量相同的子数组.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func findMaxLength(nums []int) int {
map0 := map[int]int{}
map1 := map[int]int{}
sum0 := 0
sum1 := 0
maxarray := 0
for index,value := range nums{
if value == 1{
sum1++
}else{
sum0++
}
if sum1>sum0{
i, ok := map1[sum1-sum0]
if !ok{
map1[sum1-sum0] = index
}else{
maxarray = max(maxarray, index-i)
}
}else if sum1<sum0{
i, ok := map0[sum1-sum0]
if !ok{
map0[sum1-sum0] = index
}else{
maxarray = max(maxarray, index-i)
}
}else{
maxarray = max(maxarray, index+1)
}
}
return maxarray
}
|
总结
本题和前几天的题目在思想上有异曲同工之妙, 也是前缀和的一种应用, 如果把0和1的数量差作为前缀和, 那么本题解题思路可简单概括为找到前缀和相等的位置的最远距离.
day20 2024-03-17
57. Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don’t need to modify intervals in-place. You can make a new array and return it.
题解
遍历intervals, 将interval复制到结果数组中. 判断要插入的interval的start和end是否在当前interval中
- 在范围内则将新interval的start设置为当前interval的start. 使用相同的方式判断end的范围.
- 若start或end不在当前interval范围内且小于下一个interval的start, 则将start或者end设置为新interval的start或end. 此时新interval构造完成, 将后面的interval原样复制到result中即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| func insert(intervals [][]int, newInterval []int) [][]int {
result := [][]int{}
start := newInterval[0]
end := newInterval[1]
insertInterval := []int{}
flag := 0
for _, value := range intervals{
if flag == 2{
result = append(result, value)
}else if flag == 0{
if start < value[0]{
insertInterval = append(insertInterval, start)
flag++
if end < value[0]{
insertInterval = append(insertInterval, end)
flag++
result = append(result, insertInterval)
result = append(result, value)
}else if end >= value[0] && end <= value[1]{
insertInterval = append(insertInterval, value[1])
flag++
result = append(result, insertInterval)
}
}else if start >= value[0] && start <= value[1]{
insertInterval = append(insertInterval, value[0])
flag++
if end >= value[0] && end <= value[1]{
insertInterval = append(insertInterval, value[1])
flag++
result = append(result, insertInterval)
}
}else{
result = append(result, value)
}
}else{
if end < value[0]{
insertInterval = append(insertInterval, end)
flag++
result = append(result, insertInterval)
result = append(result, value)
}else if end >= value[0] && end <= value[1]{
insertInterval = append(insertInterval, value[1])
flag++
result = append(result, insertInterval)
}
}
}
if flag == 0{
result = append(result, []int{start, end})
}else if flag == 1{
insertInterval = append(insertInterval, end)
result = append(result, insertInterval)
}
return result
}
|
总结
这种题思路上并没有特别之处, 但是判断逻辑比较繁琐, 需要耐心思考边界情况, 查看他人题解, 发现用原始数组与需要插入的interval做比较要比使用interval和原始数组的start和end做比较思路简单清晰得多, 这里还是对判断条件的变与不变理解的不够透彻, 需要插入的interval的start和end是不变的, 不断遍历原始数组与不变的start和end做比较要比使用不变的start和end去和不断变化的interval的start和end做比较判断起来容易得多. 找到不变的条件对于思路清楚的解决问题至关重要. 给出示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func insert(intervals [][]int, newInterval []int) [][]int {
res := make([][]int, 0)
i := 0
for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
res = append(res, intervals[i])
}
for ; i < len(intervals) && intervals[i][0] <= newInterval[1]; i++ {
newInterval[0] = min(intervals[i][0], newInterval[0])
newInterval[1] = max(intervals[i][1], newInterval[1])
}
res = append(res, newInterval)
for i < len(intervals) {
res = append(res, intervals[i])
i++
}
return res
}
|
day21 2024-03-18
452. Minimum Number of Arrows to Burst Balloons
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
题解
本题描述的很复杂, 其实是寻找相互交错的数组有几组, 如果将数组的范围看作集合, 范围重叠的数组可以看作一个大集合, 那么就是寻找这样的集合的数目. 本题可用贪心算法, 先将这些数组按照x_start的大小从小到大排序, 然后遍历并寻找x_start在当前重合范围内的数组,并且将重合范围设置为当前重合范围和当前遍历的数组的x_end中的较小值以缩小重合范围. 直到当前数组不满足条件, 即可认为之前的数组需要一个arrow. 继续遍历, 重复该操作, 即可找到所有需要的arrow.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func findMinArrowShots(points [][]int) int {
sort.Slice(points, func (i, j int)bool{
if points[i][0]<points[j][0]{
return true
}else{
return false
}
})
arrow := 0
current := []int{points[0][0],points[0][1]}
for _, value := range points{
if value[0] <= current[1]{
if value[1] < current[1]{
current[1] = value[1]
}
current[0] = value[0]
}else{
arrow++
current[0] = value[0]
current[1] = value[1]
}
}
arrow++
return arrow
}
|
总结
本题的题目说明上有一些含糊, 根据题目说明, arrow只在竖直方向上移动, 也就是说, 必须要有重合的区间的数组才能用一个箭头, 假如有一个数组区间很大, 其和两个小区间重合但这两个小区间不重合, 按理来说应该使用两个arrow才能扎爆这三个气球, 但是看他人提交的代码中有如下一种代码, 似乎说明用一个arrow就可以. 究竟这种对不对有待进一步的思考. 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
| func findMinArrowShots(points [][]int) int {
sort.Slice(points, func(i,j int) bool {
return points[i][1] < points[j][1]
})
res := 1
arrow := points[0][1]
for i := 0; i < len(points); i++ {
if arrow >= points[i][0] {continue}
res++
arrow = points[i][1]
}
return res
}
|
day22 2024-03-19
621. Task Scheduler
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there’s a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
题解
拿到本题, 最直接的想法就是将每种任务的数量统计出来, 从大到小排序, 然后按照冷却时间轮流按序执行不同的任务, 不能执行任务的时间片留空. 某种任务全部执行完后, 该任务占据的时间片也留空. 知道全部任务都执行完需要的时间就是最少时间. 这是一种贪心的思想, 简单思考其正确性, 因为即使调换顺序, 在执行到某个时间时也不会比这种贪心算法执行的任务更多.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| func leastInterval(tasks []byte, n int) int {
tasknumber := map[byte]int{}
for _, task := range tasks{
_, exist := tasknumber[task]
if !exist{
tasknumber[task] = 1
}else{
tasknumber[task]++
}
}
tasknumber_slice := []int{}
for _, value := range tasknumber{
tasknumber_slice = append(tasknumber_slice, value)
}
sort.Ints(tasknumber_slice)
length := 0
result := 0
for {
length = len(tasknumber_slice)
for i:=1;i<=n+1;i++{
if i<=length{
if(tasknumber_slice[length-i] == 1){
if i==1{
tasknumber_slice = tasknumber_slice[:length-1]
}else{
tasknumber_slice = append(tasknumber_slice[:length-i],tasknumber_slice[length-i+1:]...)
}
}else{
tasknumber_slice[length-i]--
}
}
result++
if len(tasknumber_slice)==0{
goto Loop
}
}
sort.Ints(tasknumber_slice)
}
Loop:
return result
}
|
总结
看了0ms的解法, 十分惊艳, 与其将任务一个一个的安放到插槽中, 不如直接按照频率最大的任务算出必须存在的空插槽的个数, 再用剩余的任务去填这些空插槽, 最后只需要将任务总数和剩余的空插槽个数相加即可得到最终的时长. 到这里我想到, 其实频率最高的任务留出的空插槽数目是固定的, 只要将除频率最高之外的任务总数和空插槽数目相比, 若小于空插槽数目, 则最后时长就是频率最高任务完成需要的时长. 这里需要将和频率最高的任务频率相同的任务数目先减一计算算到任务总数中, 最后再加到最终的时间总数上. 若大于空插槽数目, 最终结果就是任务数目.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func leastInterval(tasks []byte, n int) int {
freq := make([]int, 26)
for _, task := range tasks {
freq[task-'A']++
}
sort.Ints(freq)
maxFreq := freq[25]
idleSlots := (maxFreq - 1) * n
for i := 24; i >= 0 && freq[i] > 0; i-- {
idleSlots -= min(maxFreq-1, freq[i])
}
idleSlots = max(0, idleSlots)
return len(tasks) + idleSlots
}
|
day23 2024-03-20
1669. Merge In Between Linked Lists
You are given two linked lists: list1 and list2 of sizes n and m respectively.
Remove list1’s nodes from the ath node to the bth node, and put list2 in their place.
The blue edges and nodes in the following figure indicate the result:
Build the result list and return its head.
题解
本题为将链表中某段替换为指定的链表, 只需要遍历链表, 保存需要替换部分首尾两个节点的指针即可, 需要注意边界情况的处理, 即替换开头某段或者结尾某段链表时要处理空指针.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
count := 0
var before *ListNode
var after *ListNode
current := list1
head := list1
for count <= b {
if count == a-1 {
before = current
}
count++
current = current.Next
}
after = current
if before == nil {
head = list2
} else {
before.Next = list2
}
current = list2
for current.Next != nil {
current = current.Next
}
current.Next = after
return head
}
|
总结
本题保存了首尾两个指针的地址, 是典型的用空间换时间的思路, 不过实际应用过程中可能还要根据语言注意被动态分配出去的空间回收的问题.
day24 2024-03-21
206. Reverse Linked
Given the head of a singly linked list, reverse the list, and return the reversed list.
题解
本题相当基础, 是一道简单题, 只需要将链表整个反转过来即可. 用一个变量保存当前访问的节点的前一个节点的指针, 将当前节点的next修改为指向前一个节点的指针, 遍历整个链表即可. 注意处理边界情况(头指针为0).
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var before *ListNode
current := head
for current!=nil && current.Next!=nil {
temp := current.Next
current.Next = before
before = current
current = temp
}
if head!=nil{
current.Next = before
}
return current
}
|
总结
这两天都是链表相关的题目, 本题是一道基础题, 在查看他人解答的过程中发现本题也可以将链表数据全部复制出来, 再遍历链表逆序赋值即可. 示例代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
arr := []int{}
node := head
for node != nil {
arr = append(arr, node.Val)
node = node.Next
}
node = head
for i := len(arr); i > 0; i-- {
node.Val = arr[i-1]
node = node.Next
}
return head
}
|
day25 2024-03-22
234. Palindrome Linked
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
题解
本题也是一道基础题, 使用快慢指针的方法遍历到链表的中间, 在遍历的同时将链表的前半部分的值保存到数组中, 再从中间继续向后遍历, 遍历的同时反向遍历数组, 比较遍历的节点和遍历到的数组中元素的值. 若不同则不是回文, 直到全部遍历完成为止.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
back := head
before:= head
if head.Next != nil{
before = head.Next
}else{
return true
}
values := []int{head.Val}
for before!= nil && before.Next != nil{
back = back.Next
values = append(values, back.Val)
before = before.Next.Next
}
if before == nil{
for i:=len(values)-2;i>=0;i--{
back = back.Next
if back.Val != values[i]{
return false
}
}
return true
}else{
for i:= len(values)-1;i>=0;i--{
back =back.Next
if back.Val != values[i]{
return false
}
}
return true
}
}
|
总结
查看用时较短的题解, 使用了快慢指针, 找到中间位置后将后半截链表反转, 然后从原始链表头部和反转的后半截链表头部开始依次遍历并比较即可. 这种方法时间复杂度为O(n), 空间复杂度为O(1), 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
slow:=head
fast:=head.Next
for fast!=nil && fast.Next!=nil{
slow=slow.Next
fast=fast.Next.Next
}
second:=slow.Next
slow.Next=nil
second=reverse(second)
for second!=nil && head!=nil{
if second.Val!=head.Val{
return false
}
second=second.Next
head=head.Next
}
return true
}
func reverse(head *ListNode) *ListNode{
var prev *ListNode
var futr *ListNode
for head!=nil{
futr=head.Next
head.Next=prev
prev=head
head=futr
}
return prev
}
|
day26 2024-03-23
143. Reorder
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
题解
拿到本题, 首先想到的是将链表中的全部数据保存到数组中, 然后通过同时从前后遍历数组并且给原来的链表赋值的方式, 即可快速解决本题, 如果不使用额外的空间, 可以使用快慢指针, 找到链表的中间节点, 从中间节点开始将链表的后半部分反向, 用两个指针分别从前半部分的开始和后半部分的末尾开始遍历, 并构造新链表即可. 也可以构造一个栈, 将链表的后半部分放入栈中, 然后从顶端一边出栈一边构造新链表即可. 题目中要求不能直接修改节点的值, 因此采用第三种思路.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
slow := head
fast := head
if head.Next != nil{
fast = head.Next
}
stack := []*ListNode{}
for fast != nil && fast.Next != nil{
fast = fast.Next.Next
slow = slow.Next
}
odd := false
if fast == nil{
odd = true
}
// construct pointer stack
slow = slow.Next
for slow != nil{
stack = append(stack, slow)
slow = slow.Next
}
slow = head
temp := head.Next
temp2 := head
flag := 1
for i:=len(stack)-1;i>=0;i--{
if flag == 1{
stack[i].Next = nil
slow.Next = stack[i]
slow = slow.Next
flag = 0
}else{
temp2 = temp.Next
temp.Next = nil
slow.Next = temp
slow = slow.Next
flag = 1
i++
temp = temp2
}
}
if odd{
temp.Next = nil
slow.Next = temp
}
return
}
|
总结
查看最快速度代码, 使用了一个数组先将链表的全部节点指针留一个间隔存放在数组中, 然后再逆序遍历数组将后半节点的指针逆序插入前面留出的空格中, 最后从头遍历数组, 连接整个链表即可. 这样写得出的代码比较简洁.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
list := []*ListNode{}
for node := head; node != nil; node = node.Next {
list = append(list, node)
list = append(list, nil)
}
for i := 1; i < len(list) - i - 1; i += 2 {
list[i] = list[len(list) - i - 1]
}
for i := 0; list[i] != nil; i++ {
list[i].Next = list[i + 1]
}
}
|
day27 2024-03-24
287. Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
题解
根据鸽笼原理, 显然必有一个数字有一个重复数字. 最简单的思路就是用每个数和数组其余数字比较, 直到找到相同的数为止, 显然这个方法的时间复杂度比较高, 要O(n^2). 最终并没有想出题目中要求的时间复杂度为O(n), 空间复杂度为O(1)的解法, 看题解得知使用的是Floyd 循环检测算法, 这个算法一般用于检测链表中是否存在环, 即使用快慢指针, 同时遍历链表, 如果存在环, 快指针最终会追上慢指针. 如果链表没有环, 则遍历链表最终会到达空指针自然停止, 这里的快慢指针是给了未知长度的链表一个停止条件, 可以避免若链表有环无限循环遍历下去. 这里将数组堪称链表是非常精妙的思路, 将数组中的值看作下一个节点在数组中的下标, 这样如果有两个节点相同, 则最终快指针和慢指针指向的下标会相同, 再从头遍历一次数组, 找到值为这个下标的数据, 即为重复的数.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func findDuplicate(nums []int) int {
// Step 1: Find the intersection point of the two pointers
slow := nums[0]
fast := nums[0]
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
// Step 2: Find the entrance to the cycle (duplicate number)
slow = nums[0]
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
|
day28 2024-03-25
442. Find All Duplicates in an Array
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
题解
本题若想在O(n)时间复杂度内求解, 必须在遍历数组的时候充分利用遍历过的数据提供的信息, 在后续充分利用已有信息, 在本题中, 遍历过程中的每个位置处的数本身就是信息. 若使用O(n)的空间复杂度, 可以创建一个和目标数组长度相同的空数组, 将遍历到的元素的数作为下标, 设定对应空数组中下标所在位置的值作为标记. 这样后续遍历时看到标记则知道这个数是重复的. 若想空间复杂度为O(1), 因为本题并没有要求不修改数组, 可以修改数组中以这个数为下标处的数据, 这里可以将其取相反数来表明这个下标已经出现过. 这也是因为体重明确说明数组中的数的范围在1-数组长度之间, 因此可以采用这种方法来标记数据是否已经出现, 如果有数大小超过数组长度, 这种方案就不适用了, 则必须使用O(n)的空间.
代码
1
2
3
4
5
6
7
8
9
10
| func findDuplicates(nums []int) []int {
result := []int{}
for _, values := range nums{
if nums[int(math.Abs(float64(values)))-1] < 0{
result = append(result, int(math.Abs(float64(values))))
}
nums[int(math.Abs(float64(values)))-1] = -nums[int(math.Abs(float64(values)))-1]
}
return result
}
|
day28 2024-03-26
41. First Missing Positive
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
题解
本题要求O(n)的时间复杂度和O(1)的空间复杂度, 解题思路上与昨天的题目相似, 考虑到数组长度为n, 即使是从1开始的连续正整数, 最大填充到n. 故用数组中的数作为下标修改对应位置的值来标记某个数是否存在是可行的. 但要注意, 当前数组中可能出负数和超过n的数字, 如果想使用将数作为下标将对应位置数设为负数的方式来提供信息, 则要先对负数和超过n的数字进行处理, 为了区分被标记的数和本身为负的数, 将负数和超过n的数修改为0. 再遍历数组按照昨天的思路将数作为下标, 将相应位置数设为负数标记已经访问. 这里可以将数全部设为-1. 最后再遍历一遍数组, 找到第一个数字大于等于0的数的下标, 即为丢失的最小正整数. 这样需要固定遍历三遍数组, 且空间复杂度为O(1).
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| func firstMissingPositive(nums []int) int {
for index, value := range nums {
if value < 0 || value > len(nums) {
nums[index] = 0
}
}
flag := 0
for _, value := range nums {
if abs(value) > 1 || value == -1{
if nums[abs(value)-1] == 1 {
flag = 1
nums[abs(value)-1] = -1
} else if nums[abs(value)-1] == 0 {
nums[abs(value)-1] = -1
} else if nums[abs(value)-1] > 1 {
nums[abs(value)-1] = -nums[abs(value)-1]
}
}else if value == 1{
flag = 1
if nums[0] == 0{
nums[0] = -1
}else if nums[0] > 1{
nums[0] = -nums[0]
}
}
}
for index, value := range nums {
if flag == 1 && index == 0 {
continue
} else if index == 0 && flag == 0 {
return 1
}
if value >= 0 {
return index + 1
}
}
return len(nums)+1
}
func abs(num int) int {
if num < 0 {
return -num
} else {
return num
}
}
|
总结
查看最快速代码, 其将负数直接修改为整数类型最大值, 对于超过数组长度的数直接忽略, 不作处理, 其余的当作下标取对应位置的相反数. 这样处理起来思路比较清晰.
day29 2024-03-27
713. Subarray Product Less Than K
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.
题解
本题要求返回的是连续的相邻子数组, 第一个想到的就是滑动窗口, 设置窗口的前后指针, 当窗口内的积<k时, 扩大窗口, 并增加计数, 当窗口内的积≥k时, 缩小窗口, 直到重新满足<k的条件为止. 这里增加计数的地方需要仔细考量, 并不是扩大窗口且积<k时, 就将计数加一, 因为该题是求积, 所以当两个数的积<k时, 其实已经包含了每个数都小于k在其中, 同理, 当三个数积<k时, 包含了任意两个的组合积都<k, 而本题只要求连续相邻的子序列. 故每次窗口扩大且符合条件时增加的计数应该为当前窗口的长度. (可以自己考虑一下从2个数扩大到3个数时默认新增了几种符合要求的子序列, 应该是包含新增加的数本身, 加上相邻一个数, 加上相邻两个数三种情况, 前面两个数的情况在之前已经计数过了)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func numSubarrayProductLessThanK(nums []int, k int) int {
front := 0
back := 0
sum := 1
result := 0
for front < len(nums){
sum *= nums[front]
if sum < k{
front++
result += front - back
}else{
if front == back{
front++
back++
sum = 1
continue
}
sum /= nums[back]
sum /= nums[front]
back++
}
}
return result
}
|
总结
在查看速度更快的题解代码时, 发现可以通过内层循环一直缩小窗口到<k时, 才继续向下滑动窗口, 这样外层只需要不断向下遍历来扩大窗口即可. 这样写循环思路更清晰, 代码更简洁 如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func numSubarrayProductLessThanK(nums []int, k int) int {
if k <= 1 {
return 0
}
res := 0
p := 1
j := 0
for i := 0; i < len(nums); i++ {
p *= nums[i]
for p >= k {
p /= nums[j]
j++
}
res += i -j + 1
}
return res
}
|
想到这, 忽然明白, 其实核心在于只需要考虑以某个位置为结尾的向前连续符合要求的数组长度作为该位置处应该增加的计数数目即可. 这样就把整个问题拆分成了独立不关联的小问题. 将每个位置应该增加的计数数目累积, 就是最终的结果.
day30 2024-03-28
2958. Length of Longest Subarray With at Most K Frequency
You are given an integer array nums and an integer k.
The frequency of an element x is the number of times it occurs in an array.
An array is called good if the frequency of each element in this array is less than or equal to k.
Return the length of the longest good subarray of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
题解
拿到本题, 直接思路就是使用滑动窗口, 使用一个哈希表来存储每个数字对应的个数, 在滑动的过程中, 扩大窗口时增加窗口新增数字的计数并不断更新最大长度, 直到当前数字的计数达到上限k开始缩小窗口, 缩小至当前数字计数小于k(缩小过程中的数都在哈希表中对应减掉频率)即可继续扩大窗口. 如此直到遍历完整个数组. 其实从解题思路上与昨天的题内核是十分相似的.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func maxSubarrayLength(nums []int, k int) int {
count := map[int]int{}
end := 0
maxlength := 0
for front:=0;front < len(nums);front++{
_,exist := count[nums[front]]
if !exist{
count[nums[front]] = 1
}else{
count[nums[front]]++
}
if count[nums[front]] <= k{
maxlength = max(maxlength,front-end+1)
}else{
for nums[end] != nums[front]{
count[nums[end]]--
end++
}
// 将达到上限的数本身减掉
count[nums[end]]--
end++
}
}
return maxlength
}
|
总结
查看前面10%更快的代码, 发现判断缩小窗口的结束可以用当前窗口前端达到上限的数在哈希表中对应的计数值来判断, 缩小窗口直到达到上限的数的计数值小于k即可结束, 这样整体代码更清晰, 更简洁, 如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func maxSubarrayLength(nums []int, k int) int {
m := make(map[int]int)
res := 0
for l, r := 0, 0; r < len(nums); r++ {
m[nums[r]]++
for m[nums[r]] > k {
m[nums[l]]--
l++
}
if r-l+1 > res {
res = r-l+1
}
}
return res
}
|
day31 2024-03-29
2962. Count Subarrays Where Max Element Appears at Least K Times
You are given an integer array nums and a positive integer k.
Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
题解
本题感觉就是昨天那道题的姊妹+升级版, 现在要求找到数组中包含的最大值, 其在这个子数组中的出现次数至少为k次. 这里明确题目中需要解决的两个问题. 1. 找到数组中的最大值 2. 对这个值在子序列中出现的次数进行计数. 无疑, 仍然可以使用滑动窗口来解决, 思路和昨天的题类似, 这里在扩大窗口时, 一直扩大到最大值数目为k, 继续向后遍历时要每次增加从头开始到包含k个最大值的窗口的最左端的元素个数. 核心思路在于让滑动窗口中只保留k个最大值, 这样所有包含前面数据的子数组和包含后面不为最大值的子数组的所有子数组都符合条件.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func countSubarrays(nums []int, k int) int64 {
max := slices.Max(nums)
var result int64
left := 0
nextleft := 0
beforeadded := 0
frequency := 0
for _, value := range nums{
if value == max{
frequency++
if frequency >= k{
for nums[nextleft] != max{
nextleft++
}
beforeadded += nextleft - left + 1
result += int64(beforeadded)
left = nextleft+1
nextleft = left
}
}else if frequency >= k{
result += int64(beforeadded)
}
}
return result
}
|
总结
查看他人的题解发现, 可以在保持窗口内最大值个数为k的思路下优化解题过程, 重复的加前面的元素是不必要的, 先将所有最大值的下标放入数组, 然后确定包含k个最大值的窗口的两端的下标, 将该窗口左侧前面的元素个数和窗口右侧后面的元素个数相乘即为该窗口对应的符合条件的解的个数, 切换到下一个包含k个最大值的窗口, 继续此操作, 直到窗口中最大值数目不足k为止.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func countSubarrays(nums []int, k int) int64 {
var m int
for _, n := range nums {
m = max(m, n)
}
var idxs []int
for i := range nums {
if nums[i] == m {
idxs = append(idxs, i)
}
}
start := 0
count := int64(0)
for i := range idxs {
if i+k > len(idxs) {
break
}
last := len(nums)
if i+k < len(idxs) {
last = idxs[i+k]
}
count += int64(idxs[i]-start+1) * int64(last-idxs[i+k-1])
}
return count
}
|
day32 2024-03-30
992. Subarrays with K Different Integers
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A good array is an array where the number of different integers in that array is exactly k.
For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous part of an array.
题解
本题仍然使用滑动窗口, 这几天连续做滑动窗口的题, 总结了滑动窗口的"三要素": 1. 什么时候扩大窗口 2. 双么时候缩小窗口 3. 缩小和扩大窗口时执行哪些操作
对于本题, 题目中要求计数正好包含k个不同数的子数组的个数, 求精确包含k个这种问题往往比较困难, 可以转化为求解包含≤k个和≤k-1个不同数的子数组个数的差. 这种思路求解起来非常方便. 对于求解包含≤k个不同数的子数组的个数, 当数组中包含不同数个数不足k时, 扩大窗口同时将计数增加当前窗口的长度, 若为k+1, 则缩小窗口至正好完全去除了一个数(若某个数只出现了1次, 去掉后窗口内不同数个数就是k, 若不止一次, 则去掉了不同数个数也没有变化, 故要继续向下遍历). 最后求≤k和≤k-1情况的计数值做差即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| func subarraysWithKDistinct(nums []int, k int) int {
return countk(nums, k) - countk(nums, k-1)
}
func countk(nums []int, k int) int {
count := map[int]int{}
different := 0
left := 0
result := 0
for index, value := range nums {
_, exist := count[value]
if !exist {
different++
count[value] = 1
} else {
count[value]++
}
if different <= k {
result += index - left + 1
}
if different == k+1 {
for count[nums[left]] > 1 {
count[nums[left]]--
left++
}
delete(count, nums[left])
left++
different--
result += index - left + 1
}
}
return result
}
|
总结
解题时没有注意题目限制, 后来查看最快解法发现忽略了题目中的数的范围, 题目中的数组中的数的大小不超过数组的长度, 数的范围已知, 因此可以使用数组代替哈希表来计数这样可以大大加快解题速度.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func subarraysWithKDistinct(nums []int, k int) (ans int) {
f := func(k int) []int {
n := len(nums)
pos := make([]int, n)
cnt := make([]int, n+1)
s, j := 0, 0
for i, x := range nums {
cnt[x]++
if cnt[x] == 1 {
s++
}
for ; s > k; j++ {
cnt[nums[j]]--
if cnt[nums[j]] == 0 {
s--
}
}
pos[i] = j
}
return pos
}
left, right := f(k), f(k-1)
for i := range left {
ans += right[i] - left[i]
}
return
}
|
day33 2024-03-31
2444. Count Subarrays With Fixed Bounds
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
The minimum value in the subarray is equal to minK.
The maximum value in the subarray is equal to maxK.
Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
题解
本题先求出数组中包含上下界的所有可行子区域, 可行子区域指所有连续的符合上下界要求的最长区域. 将这些区域的头尾下标保存到一个二维数组中. 对于每个可行区域, 使用该区域包含的全部子数组的个数减去不满足上下界要求的子数组个数, 不满足上下界要求的子数组个数求解使用滑动窗口是比较容易的, 从头开始滑动, 窗口内只能包含上界或者下届或者都不包含. 若直接求解该区域中包含的满足上下界的子数组个数则比较困难. 用子数组总个数和不满足上下界要求的子数组个数做差即可得到想求的满足上下界的子数组个数. 对于每个子区域都执行这样的操作, 并将求得的满足条件的子数组个数加和即可得到最终的结果, 注意处理上下界都是同一个数的边界情况.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| func countSubarrays(nums []int, minK int, maxK int) int64 {
begin := 0
borders := [][]int{}
mincurrent := -1
maxcurrent := -1
var result int64
// 找到所有可行区间
for index, value := range nums{
border := []int{}
if value == minK {
mincurrent = 1
}
if value == maxK {
maxcurrent = 1
}
if value > maxK || value < minK || index == len(nums)-1{
if maxcurrent == -1 || mincurrent == -1{
mincurrent = -1
maxcurrent = -1
begin = index + 1
}else{
if value <= maxK && value >= minK && index == len(nums) - 1 {
index += 1
}
border = append(border, begin)
border = append(border, index)
borders = append(borders, border)
border = border[:0]
mincurrent = -1
maxcurrent = -1
begin = index + 1
}
}
}
// 求每个可行区间中解的数目并加和 求解可行区间已经保证区间内必有上下限存在
for _, region := range borders{
left := region[0]
right := region[1]
ismin := false
ismax := false
last := 0
allarray := (right - left + 1) * (right - left) / 2
left = 0
outrange := 0
for index, value := range nums[region[0]:right]{
if value != minK && value != maxK{
outrange += index - left + 1
}else if value == minK{
if value == maxK{
left = index + 1
continue
}
if ismax{
left = last + 1
ismax = false
ismin = true
}else if !ismin{
ismin = true
}
last = index
outrange += index - left + 1
}else{
if ismin{
left = last + 1
ismin = false
ismax = true
}else if !ismax{
ismax = true
}
last = index
outrange += index - left + 1
}
}
result += int64(allarray - outrange)
}
return result
}
|
总结
本次解题代码的运行速度超过了100%的提交, 因此不再看他人的题解了, 同时庆祝一下自己拿到了3月份的奖章, 证明这个月每天都在坚持. 下个月希望能继续坚持下去.
day34 2024-04-01
58. Length of Last Word
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal substring consisting of non-space characters only.
题解
本题是一道简单题, 直接从头开始遍历, 遇到空格结束当前单词计数, 再遇到新字符时重新计数, 直到遍历完整个字符串即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func lengthOfLastWord(s string) int {
length := 0
flag := false
for _, value := range s{
if value == ' ' {
flag = true
}
if value != ' ' {
if flag{
length = 1
flag = false
}else{
length++
}
}
}
return length
}
|
总结
前面的题解大多用了go strings库中的函数来按空格分割字符串, 再返回最后一个分割出来的字符串长度. 一般实际应用中, 使用官方库是第一选择, 因为官方库大多对这些操作做了大量优化, 效率会高得多.
day35 2024-04-02
205. Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
题解
本题是一道简单题, 要求判定s和t是不是同构的, 即类似常说的ABB型这种结构. 本题使用一个哈希表记录字符与字符的映射即可, 如果出现了不同的映射则是不同构的.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func isIsomorphic(s string, t string) bool {
table1 := map[rune]byte{}
table2 := map[byte]rune{}
for index, value := range s{
mapping1, exist := table1[value]
mapping2, exist2 := table2[t[index]]
if !exist{
table1[value] = t[index]
}else{
if !(mapping1 == t[index]){
return false
}
}
if !exist2{
table2[t[index]] = value
}else{
if mapping2 == value{
continue
}else{
return false
}
}
}
return true
}
|
总结
查看前面的题解, 发现了果然0ms用时的思路还是不同凡响, 用字符本身作为下标维护两个数组, 在遍历两个字符串的时候将两个字符串当前的字符作为下标, 将当前遍历的字符串的下标作为值放入两个数组中, 这样就记录了同时出现的两个字符最后的出现的下标, 如果这两个字符一直同时出现则二者下标一直是相同的, 若没有同时出现说明字符映射改变了, 没有继续之前的映射. 则两个字符串就是不同构的. 字符的本质是数, 那么字符可以表示更多的信息, 而不是字符本身, 将其作为数组下标就既使用了字符本身这个信息, 还使用了数组对应位置的元素这个信息, 能使用更多的信息就意味着更高的效率.
1
2
3
4
5
6
7
8
9
10
11
| func isIsomorphic(s string, t string) bool {
s2t := [128]byte{}
t2s := [128]byte{}
for i, end := 0, len(s); i < end; i++ {
if s2t[s[i]] != t2s[t[i]] {
return false
}
s2t[s[i]], t2s[t[i]] = byte(i+1), byte(i+1)
}
return true
}
|
day36 2024-04-03
79. Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
题解
本题可使用递归求解, 设置一个标记数组和board大小相同, 来标记已经访问过的元素, 遍历board数组, 找到目标字符串的起始字符, 对其调用explore函数求解, 若为true则直接返回true. 最后全部遍历完则返回false.
explore函数中, 传入了当前字符的行下标和列下标, 先判断可行的探索方向, 再在可行的探索方向上逐个判断其是否为目标字符串中的下一个字符以及是否已经被访问过, 若可以访问且为目标字符, 则对这个可行方向的字符调用explore函数继续后面的探索, 知道探索到目标字符串结尾则直接返回true. 若调用explore函数返回为true说明后面的字符串符合目标字符串且有可行路径, 则返回true. 若没有可探索方向或者所有可探索方向都不满足条件, 返回false.
使用递归要考虑的是在当前递归状态中应该完成什么任务以及递归的结束条件, 递归本质上是一种将全局问题化解为小的局部问题, 通过求解每个小的局部问题最终解决全局问题的解决问题的思路.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
func exist(board [][]byte, word string) bool {
for index, value := range board{
for index1, value2 := range value{
if value2 == byte(word[0]){
var flag [][]int
for _,_ = range board{
a := make([]int, len(board[0]))
flag = append(flag, a)
}
if (explore(board, index, index1, 0, flag, word)){
return true
}
}
}
}
return false
}
func explore(board [][]byte, row int, column int, target int, flag [][]int, word string)bool{
if target == len(word)-1 && byte(word[target]) == board[row][column]{
return true
}
up, down, left, right := !(row == 0),!(row == len(board)-1),!(column == 0), !(column == len(board[0])-1)
ok := false
if up && board[row-1][column] == byte(word[target+1])&&(flag[row-1][column] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok = ok || explore(board, row-1, column, target+1, flag,word)
flag[row][column] = 0
}
if down && board[row+1][column] == byte(word[target+1]) &&(flag[row+1][column] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok =ok || explore(board, row+1, column, target+1, flag, word)
flag[row][column] = 0
}
if left && board[row][column-1] == byte(word[target+1]) &&(flag[row][column-1] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok =ok || explore(board, row, column-1, target+1, flag, word)
flag[row][column] = 0
}
if right && board[row][column+1] == byte(word[target+1]) &&(flag[row][column+1] == 0){
if target+1 == len(word) - 1{
return true
}
flag[row][column] = 1
ok = ok || explore(board, row, column+1, target+1, flag, word)
flag[row][column] = 0
}
return ok
}
|
day37 2024-04-04
1614. Maximum Nesting Depth of the Parentheses
A string is a valid parentheses string (denoted VPS) if it meets one of the following:
It is an empty string “”, or a single character not equal to “(” or “)”,
It can be written as AB (A concatenated with B), where A and B are VPS’s, or
It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:
depth("") = 0
depth(C) = 0, where C is a string with a single character not equal to “(” or “)”.
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s.
depth("(" + A + “)”) = 1 + depth(A), where A is a VPS.
For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(” and “(()” are not VPS’s.
Given a VPS represented as string s, return the nesting depth of s.
题解
本题是简单题, 因为题目说明了给定的括号一定是匹配的, 因此不用考虑括号匹配的问题. 只需设计一个值来保存当前还未匹配的左括号的个数, 这也是到当前这个字符的括号深度, 因此若出现了新的左括号, 就更新最大深度为当前的左括号个数和之前的最大深度中的较大值, 出现右括号则将未匹配的左括号个数减一, 最后返回最大深度即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func maxDepth(s string) int {
depth := 0
left := 0
for _,value := range s{
if value == '('{
left++
depth = max(depth, left)
}
if value == ')'{
left--
}
}
return depth
}
|
day38 2024-04-05
1544. Make The String Great
Given a string s of lower and upper case English letters.
A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
题解
本题可以使用类似简单回溯的方法, 遍历字符串并判断当前字符和下一个字符是否互为大小写, 若是则删掉两个字符同时将循环下标回退到当前字符的前一个, 继续遍历字符串, 如此反复直到到达字符串结尾即可, 注意处理字符位于字符串结尾和开始的边界情况.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func makeGood(s string) string {
index := 0
length := len(s)
for index=0;index<length-1;index++{
if s[index]!=s[index+1]&&(s[index] == s[index+1]+32 || s[index] == s[index+1]-32){
if index == length-2{
s = s[0:index]
length = len(s)
break
}else{
s = s[0:index]+s[index+2:]
length = len(s)
}
if index == 0{
index--
continue
}else{
index = index - 2
}
}
}
return s
}
|
总结
看到题解中有人使用栈, 通过额外的空间获得了更快的速度, 将前面的字符都入栈, 将栈顶和当前字符比较, 互为大小写则将栈顶出栈, 继续向下遍历并比较, 不互为大小写则将当前字符入栈. 这样不用回退下标, 可以充分利用go 中对for range循环优化带来的效率.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func makeGood(s string) string {
sb := []rune(s)
stack := make([]byte, 0)
if len(sb) > 1 {
for i, _ := range s {
n := len(stack)
if n > 0 && ((s[i]-stack[n-1] == 32) || (stack[n-1]-s[i] == 32)) {
stack = stack[:n-1]
} else {
stack = append(stack, s[i])
}
}
return string(stack)
} else {
return s
}
}
|
day39 2024-04-06
1249. Minimum Remove to Make Valid parentheses
Given a string s of ‘(’ , ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(’ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
题解
本题实际上还是一个括号匹配的问题, 使用一个栈就可以解决问题, 与前一天题不同的是, 本题中的左括号不一定能完全被匹配, 所以栈中可以保存左括号的下标, 遍历到字符串末尾后, 将栈中仍然存在的未匹配的左括号全部删去即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| func minRemoveToMakeValid(s string) string {
stack := []int{}
number := 0
index := 0
for index < len(s){
if s[index] == ')' {
if number == 0{
if index == len(s) - 1{
s = s[0:index]
return s
}else{
s = s[0:index] + s[index+1:]
}
}else{
number--
stack = stack[0:len(stack)-1]
index++
}
}else if s[index] == '('{
number++
stack = append(stack, index)
index++
}else{
index++
}
}
if len(stack) != 0{
for index,value := range stack{
if value - index != len(s) - 1{
s = s[0:value-index]+s[value+1-index:]
}else{
s = s[0:value-index]
return s
}
}
}
return s
}
|
day40 2024-04-07
678. Valid Parenthesis String
Given a string s containing only three types of characters: ‘(’, ‘)’ and ‘*’, return true if s is valid.
The following rules define a valid string:
Any left parenthesis ‘(’ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(’.
Left parenthesis ‘(’ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string “”.
题解
本题仍然是括号匹配问题, 只是这次加了一个万能字符’*’,相当于赖子,既可以当’(‘用也可以当’)‘用. 作为一个判定问题, 只需要判断字符串是否匹配即可. 因此使用一个变量记录当前未匹配的左括号个数和可以被匹配的星号个数, 当遇到未匹配的右括号时如果没有未匹配的左括号则使用星号匹配. 若遍历结束左括号没有剩余则匹配成功. 若星号个数比左括号少则直接匹配失败. 若左括号和星号仍有剩余, 且星号个数大于左括号时, 说明剩余的星号可能能完全匹配左括号,这时反向遍历,把’)‘作为之前的左括号看待,用同样的方法尝试匹配所有’(’. 最后只要’(‘能匹配成功即成功. p.s: 这里考虑的是正向遍历时若’)‘都匹配成功了, 那么只需要测试’(‘能否匹配就够了, 因为剩余的’)‘在正向遍历时已经确认可以通过多余的’*‘来完全匹配, 因此不用再考虑’)‘的匹配问题.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| func checkValidString(s string) bool {
leftstack := 0
star := 0
for _, value := range s {
if value == '*'{
star++
}else if value == '('{
leftstack++
}else{
if leftstack > 0{
leftstack--
}else if star > 0{
star--
}else{
return false
}
}
}
if leftstack == 0{
return true
}else if star < leftstack{
return false
}else{
leftstack = 0
star = 0
for index:= len(s)-1;index>=0;index--{
if s[index] == ')'{
leftstack++
}else if s[index] == '*'{
star++
}else{
if leftstack > 0{
leftstack--
}else if star > 0{
star--
}else{
return false
}
}
}
}
return true
}
|
day41 2024-04-08
1700. Number of Students Unable to Eat Lunch
The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.
The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue’s end.
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.
题解
本题是一道简单题, 题干看似很长, 分析下来会发现, 若当前栈顶的三明治当前学生不喜欢, 就会向下轮换, 直到轮换到喜欢的学生, 因此栈顶三明治是否会被拿走取决于队伍中是否还有喜欢这种三明治的学生, 只要有这个学生总会被轮换到队伍的最前面. 则遍历学生数组, 统计两种三明治的喜欢的学生的数量. 遍历三明治数组, 遍历过程中减掉被拿走的三明治的类型喜欢的学生的数量, 直到三明治数组的当前元素没有学生喜欢, 则剩余的三明治就无法被拿到, 也就是无法吃到三明治的学生个数.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func countStudents(students []int, sandwiches []int) int {
love1 := 0
love0 := 0
length := len(sandwiches)
for _,value := range students{
if value == 1{
love1++
}else{
love0++
}
}
for index,value := range sandwiches{
if value == 1{
if love1 <= 0{
return length - index
}
love1--
}else{
if love0 <= 0{
return length - index
}
love0--
}
}
return 0
}
|
day42 2024-04-09
2073. Time Needed to Buy Tickets
There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.
You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].
Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.
Return the time taken for the person at position k (0-indexed) to finish buying tickets.
题解
本题是一道简单题,并不需要去考虑模拟队列一轮一轮买票的过程, 而考虑队伍中的每个人在目标k买完票之前买了多少次票并将每个人中买的次数加和即可. 这里要将k之前和k之后的分开考虑, k之前的如果比k的需求大则在k买完之前都要买k需求的票的数量, 比k小则将自己的需求数量买完即可. 在k之后不同在于需求数大于等于k的人只会买k-1张票, 在k买完自己需要的票的时候这些人还在k的后面故当k买完时这些人最多买了k-1张. 遍历一遍数组按照这个规则将每个人的买票数加和即可得到最终结果.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func timeRequiredToBuy(tickets []int, k int) int {
target := tickets[k]
time := 0
for _,value := range tickets[0:k]{
if value >= target{
time += target
}else{
time += value
}
}
for _,value := range tickets[k:]{
if value >= target - 1{
time += target - 1
}else{
time += value
}
}
// add itself once
time++
return time
}
|
day43 2024-04-10
950. Reveal Cards In Increasing Order
You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the ith card is deck[i].
You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.
You will do the following steps repeatedly until all cards are revealed:
Take the top card of the deck, reveal it, and take it out of the deck.
If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
If there are still unrevealed cards, go back to step 1. Otherwise, stop.
Return an ordering of the deck that would reveal the cards in increasing order.
Note that the first entry in the answer is considered to be the top of the deck.
题解
本题为中等难度, 题目中的不变的为牌的数量, 目标即为将牌按照合适的顺序插入这个牌堆, 首先排序, 然后模拟取牌顺序将牌插入. 用一个数组保存当前牌堆中的可用位置. 设置可用位置为一个队列, 对于需要跳过的位置(即翻一张牌后下一张牌需要放到底部, 相当于跳过了这张牌)将其从队列头放到队列尾, 取出队列下一个位置并将当前牌插入, 再跳过一个位置, 插入一张牌, 如此重复直到清空队列.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func deckRevealedIncreasing(deck []int) []int {
position := []int{}
sort.Ints(deck)
now := 0
result := make([]int,len(deck))
for index,_ := range deck{
position = append(position, index)
}
for len(position) > 1{
result[position[0]] = deck[now]
position = append(position,position[1])
position = position[2:]
now++
}
result[position[0]] = deck[now]
return result
}
|
总结
这样虽然写起来方便, 但实际上在不断append的过程中position会占用更多的空间, 使用循环队列可以避免空间的浪费.
day44 2024-04-11
402. Remove K Digits
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
题解
本题考虑数字中的某一位数字能产生的影响, 对应这个数字相邻的左右两个数字, 如果删掉了相邻的数字没有删掉当前这一位的数字, 在删除后的字符串中相当于用当前这一位数字代替了被删掉的相邻数字, 如果删掉了当前的数字没删掉相邻的数字, 同样相当于在这一位上用相邻的数字代替了被删掉的数字. 即在删除后的字符串中的这一位上用当前这一位的数字和相邻数字二选一, 前后的其余字符串不用考虑不影响这个局部变化. 仅考虑这个局部变化的过程, 最优解为在删除完毕的字符串中的当前位置应该放入较小的数字, 即相邻数字中较大的数应该被删去, 考虑左右相邻的对称性, 则可以得出, 删掉比左右相邻数字都大的数可以在删掉一个数后得到局部最优解, 删掉这个数后要回溯一位判断删除后之前的数是否符合条件. 重复此过程遍历数组, 删掉k个数后返回最终的字符串.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| func removeKdigits(num string, k int) string {
if len(num) == k{
return "0"
}
index := 0
delete := 0
for index < len(num) && delete < k{
if delete == 554{
fmt.Println(num)
}
if index == 0{
if len(num) == 1{
break
}
if num[index] == '0'{
num = num[1:]
index--
}else if num[index] > num[index+1]{
delete++
num = num[1:]
index--
}
index++
}else if index == len(num) - 1{
if num[index] >= num[index-1]{
num = num[0:len(num)-1]
index--
delete++
}
}else{
if num[index] > num[index-1]&&num[index] >= num[index+1] || num[index] > num[index+1] && num[index] >= num[index-1]{
num = num[0:index] + num[index+1:]
index--
delete++
}else{
index++
}
}
}
if delete < k{
return "0"
}
for index = 0;num[index] == '0'&&index < len(num)-1;index++{}
return num[index:]
}
|
总结
本题自己想出的解法效率实在不太行, 思路上也不够简洁优美, 看了前面的题解, 发现从原来的思考的基础上应该进一步思考, 对于一串数字字符串来说, 可以删除的数字数量是有限的, 则要首先让数字的高位部分尽可能小, 删除的时候不能改变未删除的数字的相对位置, 根据之前的局部最优解的思考, 如果当前位置的数字比后一位大, 则应将这一位删掉, 让后一位占据当前位置, 这样保证了当前的数字一定比后一位数字小, 这样就做到了尽可能让小的数字位于前面, 使得每一步操作结束后的子数组具有单调性. 这也意味着之前考虑前后两个相邻数字的大小是多余的, 考虑后一位即可, 只需要使用一个单调栈来保证栈末尾的数比要入栈的数字小即可. 注意处理前导0和遍历一次字符串后没有删够元素的情况即可. 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func removeKdigits(num string, k int) string {
result := []rune{}
for _, c := range num {
for len(result) > 0 && result[len(result) - 1] > c && k > 0 {
result = result[:len(result) - 1]
k--
}
if len(result) > 0 || c != '0' {
result = append(result, c)
}
}
for len(result) > 0 && k > 0 {
result = result[:len(result) - 1]
k--
}
if len(result) <= 0 {
return "0"
}
return string(result)
}
|
day45 2024-04-12
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
题解
本题是leetcode中一道经典难题, 思路上和昨天的题目有一些相似, 仍然思考局部的情况, 对于任一位置而言, 其在竖直方向上能接到的水的单位数与其自身的高度和其两侧的最高的"墙"的高度有关. 因此关键在于求出任一位置的两侧高度最高的"墙"的高度有多高. 可以使用两个数组来保存某一位置前面的最高的墙的高度和后面的最高墙的高度. 求最高墙的高度的过程可以通过动态规划解决, 用一个数记录当前位置左侧的最高墙高度是多少, 与自身比较, 如果该位置更高, 则更新最高高度, 否则将当前位置的左侧最高墙高度设置为之前的最高墙高度. 对于右侧同理.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func trap(height []int) int {
highest := 0
left_high := []int{}
right_high := make([]int,len(height))
for _,value := range height{
if value > highest{
highest = value
}
left_high = append(left_high, highest)
}
highest = 0
for i:=len(height)-1;i>=0;i--{
if height[i] > highest{
highest = height[i]
}
right_high[i] = highest
}
result := 0
for index,value := range height{
result += min(left_high[index],right_high[index]) - value
}
return result
}
|
总结
看题解时发现一种更巧妙高效的思路, 之前提到对每一个位置能接的雨水仅与其左右的最高墙高度有关, 那么可以把同时需要知道两个方向的信息固定为只需要考虑一个方向的信息即可. 如果当前位置右侧有墙比当前位置左侧所有墙都高, 那么只需要考虑当前位置左侧最高的墙有多高就可以计算出能接的雨水, 直到出现了墙比右侧的最高的墙还高, 此时就移动尾部的指向右侧最高墙的指针, 向左移动, 此时已知左侧的最高墙比目前尾部指针右侧的所有墙都高, 因此同样只需考虑右侧最高的墙有多高即可, 直到出现墙比左侧的最高墙高, 则再次交换主导权, 移动头部方向的指针. 如此轮换移动指针, 将需要同时比较两个方向的问题简化成了只需要比较一个方向的问题, 保留了更多的信息, 只需要遍历一遍数组即可求得结果.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func trap(height []int) int {
left, right := 0, len(height) - 1
leftWall, rightWall := 0,0
ans:=0
for left < right {
if height[left] < height[right] {
leftWall = max(height[left], leftWall)
ans += leftWall - height[left]
left++
} else {
rightWall = max(height[right], rightWall)
ans += rightWall - height[right]
right--
}
}
return ans
}
|
day46 2024-04-13
85. Maximal Rectangle
Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
题解
本题可以在一层层遍历矩阵的过程中, 将每一行中每个位置的元素按照如下规则进行操作加入到当前的列状态数组中. 若值为1且之前的列状态值大于0, 则增加对应的列状态值. 若值为0则用0替换对应的列状态值, 这样相当于在列状态中保存了从以该行为底该列中向上连续为1的值的个数. 根据当前的列状态即可求得到当前行为止以当前行为底的全为1的矩形区域中1的数量(仅包含1的矩形区域的面积). 如此不断遍历每一行并执行操作, 计算以该行为底的区域面积, 并更新面积最大值. 最后返回结果即可.
要解决的第二个问题就是如何求得以该行为底的最大矩形区域面积, 可以使用单调栈来保存之前的列的值, 如果遇到了比栈顶值小的列, 则将之前的最大列占据的面积求出来, 直到当前列值比栈顶大为止. 这里关键在于若后面的列值比前面某一个都大, 则前面的那一列的值可以一直扩展到后面, 在求面积时即用前面某一列的值乘以所有大于等于其值的连续的列的数量(即矩形的宽度)即可得到该列对应的得到的矩形面积. 而遇到更小的列时说明前面的某些列不能继续扩展了, 就要求出之前得到的面积是多少. 这里想起来有一些复杂, 可以细细思考一下.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| func maximalRectangle(matrix [][]byte) int {
now := make([]int, len(matrix[0]))
maxarea := 0
for _, row := range matrix{
for index, number := range row{
if number == '1'{
now[index] += 1
}else{
now[index] = 0
}
}
stack := []int{0}
maxarea = max(maxarea,now[0])
for index, value := range now[1:]{
for len(stack)>0 && now[stack[len(stack)-1]] > value{
length := len(stack)
prev := now[stack[length-1]]
stack = stack[:len(stack)-1]
width := index + 1
if len(stack) > 0{
width = index - stack[length-2]
}
maxarea = max(maxarea, width*prev)
}
if len(stack) > 0 && value == now[stack[len(stack)-1]]{
stack[len(stack)-1] = index+1
continue
}else{
stack = append(stack, index+1)
}
}
length := len(now)
for len(stack) > 0 && now[stack[len(stack)-1]] != 0{
width := length
prev := now[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) > 0{
width = length - stack[len(stack)-1] - 1
}
maxarea = max(maxarea,width*prev)
}
}
return maxarea
}
|
day47 2024-04-14
404. Sum of Left Leaves
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
题解
本题是一道简单题, 使用深度优先搜索, 尾序遍历. 遍历的实现可以使用简单的递归函数, 注意对左右两个节点的处理方式不同, 对左节点如果其没有子节点则将值加到结果中, 对右节点则直接继续遍历即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumOfLeftLeaves(root *TreeNode) int {
result := leftfirst(root)
return result
}
func leftfirst(root *TreeNode)int{
sum := 0
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil{
sum += root.Left.Val
}else if root.Left != nil{
sum += leftfirst(root.Left)
}
if root.Right != nil{
sum += leftfirst(root.Right)
}
return sum
}
|
day48 2024-04-15
129. Sum Root to Leaf Numbers
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
题解
仍然使用递归求解, 对树执行后序遍历, 在对子节点调用递归函数时将当前路径到该子节点的父节点组成的数字作为递归函数的参数, 子节点将该参数乘10后传给子节点的子节点, 并将子节点的两个子节点的返回值加和作为路径和返回给父节点. 若该子节点为叶子节点, 则加上叶子节点的值并返回. 最终在根节点将左右两子节点的返回值加和即可得到最终解.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumNumbers(root *TreeNode) int {
result := lastnode(root, 0)
return result
}
func lastnode(root *TreeNode, value int) int{
sum := 0
if root.Left != nil{
sum += lastnode(root.Left, value*10+root.Val)
}
if root.Right != nil{
sum += lastnode(root.Right, value*10+root.Val)
}
if root.Left == nil && root.Right == nil{
return value*10+root.Val
}
return sum
}
|
总结
运行时间2ms本以为算法效率不够高, 结果看了看运行时间0ms的代码, 代码逻辑和我一模一样, 可能被优化的点在于递归函数中可以先判断是否为叶子节点, 再去创建sum变量. 其实这种将属性传递给子节点的方法在编译原理中的语义分析阶段很常用, 也就是属性文法, 可以看作一种继承属性, 更加详细的内容可以查阅编译原理相关的书籍.
day49 2024-04-16
623. Add One Row to Tree
Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.
Note that the root node is at depth 1.
The adding rule is:
Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur’s left subtree root and right subtree root.
cur’s original left subtree should be the left subtree of the new left subtree root.
cur’s original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root’s left subtree.
题解
本题使用层序遍历, 遍历到对应深度减一的节点时按规则插入节点, 注意处理只有一个节点的特殊情况即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
newnode := &TreeNode{val, nil, nil}
if depth == 1{
newnode.Left = root
return newnode
}
queue := []*TreeNode{root}
depths := 1
for len(queue) != 0{
if depths == depth-1{
for _,value := range queue{
dunode := &TreeNode{val,nil,nil}
dunode.Left = value.Left
value.Left = dunode
dunoderight := &TreeNode{val,nil,nil}
dunoderight.Right = value.Right
value.Right = dunoderight
}
return root
}
for _,value := range queue{
if value.Left != nil{
queue = append(queue, value.Left)
}
if value.Right != nil{
queue = append(queue, value.Right)
}
queue = queue[1:]
}
depths++
}
return root
}
|
总结
本题也可使用dfs结合变量记录当前深度来解决.
day50 2024-04-17
988. Smallest String Starting From Leaf
You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters ‘a’ to ‘z’.
Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
As a reminder, any shorter prefix of a string is lexicographically smaller.
For example, “ab” is lexicographically smaller than “aba”.
A leaf of a node is a node that has no children.
题解
使用递归实现dfs, 在dfs的过程中将路径上经过的节点数组作为参数传递给子节点, 对子节点执行dfs. dfs中将父路径的数组和左右两个子树返回的数组分别拼接, 对拼接后的数组进行比较, 将较小的作为返回值返回. 最终在根节点即可返回全局最小字典序字符串.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) string {
result := dfs(root,[]int{})
var output []byte
for _, value := range result {
newbyte := []byte{byte('a' + value)}
output = append(newbyte, output...)
}
return string(output)
}
func dfs(root *TreeNode, parent []int) ([]int) {
localminstring := []int{root.Val}
parentstring := append(parent, root.Val)
if root.Left == nil && root.Right == nil {
return localminstring
} else if root.Left == nil && root.Right != nil {
localminstring = append(localminstring, dfs(root.Right, parentstring)...)
return localminstring
} else if root.Left != nil && root.Right == nil {
localminstring = append(localminstring, dfs(root.Left, parentstring)...)
return localminstring
} else {
leftstring := dfs(root.Left, parentstring)
rightstring := dfs(root.Right, parentstring)
v1 := make([]int,1)
v1 = append(v1, parentstring...)
v2 := make([]int,0)
v2 = append(v2, parentstring...)
v1 = append(v1,leftstring...)
v2 = append(v2,rightstring...)
length1 := len(v1) - 1
length2 := len(v2) - 1
for length1 >= 0 && length2 >= 0 {
if v1[length1] < v2[length2] {
return append(localminstring, leftstring...)
} else if v1[length1] > v2[length2] {
return append(localminstring, rightstring...)
}
length1--
length2--
}
if length1 > length2 {
return append(localminstring, rightstring...)
} else {
return append(localminstring, leftstring...)
}
}
}
|
总结
本题看似简单, 实则有一些陷阱, 如果只考虑子树的字典序大小, 只比较子树的字典序大小并返回, 在比较过程中不考虑经过的父路径的话, 对于下面这种情况就会产生错误.
感兴趣的可以自行尝试只考虑子树的字典序, 对于这个例子会产生问题.
另外一方面, 看0ms的解答代码, 其不在dfs过程中比较, 而是直接通过dfs将这棵树能产生的全部字符串保存起来, 最后再对所有的字符串进行排序, 使用了go内置的sort排序, 返回排好序后的第一个字符串即最小的字符串. 这种方法减少了递归过程中的处理逻辑, 运行起来开销小得多, 所以速度比较快.
day51 2024-04-18
463. Island Perimeter
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn’t have “lakes”, meaning the water inside isn’t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
题解
本题直接遍历二维数组, 当遇到值为1即陆地时对四个方向进行判断并对与水面相邻的陆地的边界进行累加即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func islandPerimeter(grid [][]int) int {
result := 0
for rowindex, row := range grid{
for columnindex, value := range row{
if value == 1{
if rowindex == 0 || grid[rowindex-1][columnindex] == 0{
result++
}
if rowindex == len(grid)-1 || grid[rowindex+1][columnindex] == 0{
result++
}
if columnindex == 0 || grid[rowindex][columnindex-1] == 0{
result++
}
if columnindex == len(grid[0]) - 1 || grid[rowindex][columnindex+1] == 0{
result++
}
}
}
}
return result
}
|
总结
在查看题解的过程中, 发现尽管算法思路相同, 但实现起来有一种比较巧妙的方法, 如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func islandPerimeter(grid [][]int) int {
DIRS := [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
sides := 0
for row, ROWS := 0, len(grid); row < ROWS; row++ {
for col, COLS := 0, len(grid[0]); col < COLS; col++ {
if grid[row][col] == 1 {
for _, dir := range DIRS {
r, c := row+dir[0], col+dir[1]
// Check to see if the neighbour is an edge tile or water.
if r < 0 || r >= ROWS || c < 0 || c >= COLS || grid[r][c] == 0 {
sides++
}
}
}
}
}
return sides
}
|
day52 2024-04-19
200. Number of Islands
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
题解
本题遍历矩阵, 遇到1时对该元素执行bfs, 并将搜索过程中遇到的所有1置为0. 搜索结束后将最终结果加一. 继续遍历, 重复此过程即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| func numIslands(grid [][]byte) int {
rowlength := len(grid)
columnlength := len(grid[0])
result := 0
for rowindex, row := range grid{
for columnindex, _ := range row{
if grid[rowindex][columnindex] == '1'{
queue := [][]int{{rowindex, columnindex}}
grid[rowindex][columnindex] = '0'
for len(queue) != 0{
for _, index := range queue{
queue = queue[1:]
if index[0] != 0 && grid[index[0]-1][index[1]] == '1'{
grid[index[0]-1][index[1]] = '0'
queue = append(queue,[]int{index[0]-1,index[1]})
}
if index[0] != rowlength-1 && grid[index[0]+1][index[1]] == '1'{
grid[index[0]+1][index[1]] = '0'
queue = append(queue,[]int{index[0]+1, index[1]})
}
if index[1] != 0 && grid[index[0]][index[1]-1] == '1'{
grid[index[0]][index[1]-1] = '0'
queue = append(queue, []int{index[0],index[1]-1})
}
if index[1] != columnlength-1 && grid[index[0]][index[1]+1] == '1'{
grid[index[0]][index[1]+1] = '0'
queue = append(queue, []int{index[0],index[1]+1})
}
}
}
result++
}
}
}
return result
}
|
总结
本题我的解法中使用队列来执行bfs, 使用数组来模拟队列的过程中出队入队都会消耗资源, 增加执行时间. 实际上本题无需额外空间, 因为数组是可以修改的, 只需要找到1并将与该1连接的岛屿的所有1置为0即可, 这个过程可以使用dfs来实现，在dfs的过程中目标仅为将所有相连岛屿的1置为0, 因此返回值并不重要. 这种方法省去了队列操作的开销, 下面这种总体比较简洁, 值得学习.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func numIslands(grid [][]byte) int {
if grid == nil {
return 0
}
var res int
for i:=0; i<len(grid); i++ {
for j:=0; j < len(grid[0]);j++ {
res += findIsl(i, j, grid)
}
}
return res
}
func findIsl(i, j int, m [][]byte) int {
if (i == -1 || j == -1 || i == len(m) || j == len(m[0])) {
return 0
}
if m[i][j] == '1' {
m[i][j] = '0'
findIsl(i-1, j, m)
findIsl(i+1, j, m)
findIsl(i, j+1, m)
findIsl(i, j-1, m)
return 1
}
return 0
}
|
day53 2024-04-20
1992. Find All Groups of Farmland
You are given a 0-indexed m x n binary matrix land where a 0 represents a hectare of forested land and a 1 represents a hectare of farmland.
To keep the land organized, there are designated rectangular areas of hectares that consist entirely of farmland. These rectangular areas are called groups. No two groups are adjacent, meaning farmland in one group is not four-directionally adjacent to another farmland in a different group.
land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].
Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.
题解
本题限定了农田只会是一个矩形, 因此遍历数组,遇到1时向右向下遍历, 即可知道这个矩形的长和宽. 将左上和右下坐标插入矩形坐标数组中, 并将该片矩形全部置零. 如此反复即可. 在全部置零后将右下角坐标插入矩形坐标数组中, 并将坐标数组放入结果数组.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func findFarmland(land [][]int) [][]int {
rowlen := len(land)
collen := len(land[0])
result := [][]int{}
nextrow := 0
nextcol := 0
for rowindex,row := range land{
for colindex,_ := range row{
if land[rowindex][colindex] == 1{
farmland := []int{rowindex, colindex}
nextrow = rowindex
nextcol = colindex
for nextrow < rowlen{
if land[nextrow][colindex] == 0{
break
}
nextcol = colindex
for nextcol < collen && land[nextrow][nextcol] == 1{
land[nextrow][nextcol] = 0
nextcol++
}
nextrow++
}
farmland = append(farmland, nextrow-1)
farmland = append(farmland, nextcol-1)
result = append(result, farmland)
}
}
}
return result
}
|
day54 2024-04-21
1971. Find if Path Exists in Graph
There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex source to vertex destination.
Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.
题解
本题使用并查集即可快速解决, 因为若两个节点连通, 两个节点必定位于同一个连通图中, 而每个连通图可以通过并查集使用一个节点的值来表示, 因此遍历所有边并构造并查集, 最终比较源点和目标点所在的并查集的代表元(即用来代表一个连通图的节点的值)是否相同即可确定是否有通路.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| func validPath(n int, edges [][]int, source int, destination int) bool {
querymap := map[int]int{}
querymap[source] = source
querymap[destination] = destination
for _,edge := range edges{
value,exist := querymap[edge[0]]
value2,exist2 := querymap[edge[1]]
if !exist && !exist2{
querymap[edge[0]] = edge[0]
querymap[edge[1]] = edge[0]
}else if exist && !exist2{
querymap[edge[1]] = value
}else if !exist && exist2{
querymap[edge[0]] = value2
}else{
for querymap[value] != value{
value = querymap[value]
}
for querymap[value2] != value2{
value2 = querymap[value2]
}
if value != value2{
querymap[value2] = value
}
}
}
for querymap[source] != source{
source = querymap[source]
}
for querymap[destination] != destination{
destination = querymap[destination]
}
if source != destination{
return false
}else{
return true
}
}
|
总结
最快的解法同样使用了并查集, 不过将并查集的操作都单独写成了对应的函数. 同时使用了数组来保存集合中某个元素的父元素是什么, 数组下标表示某个节点, 对应的值表示其父节点的值. 这样查询速度更快, 不过浪费了一些空间.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| type DisjointSet struct {
roots []int
ranks []int
}
func (ds *DisjointSet) Find(x int) int {
if ds.roots[x] == x {
return x
}
ds.roots[x] = ds.Find(ds.roots[x])
return ds.roots[x]
}
func (ds *DisjointSet) Union(x, y int) {
rootX := ds.Find(x)
rootY := ds.Find(y)
if rootX == rootY {
return
}
rankX := ds.ranks[rootX]
rankY := ds.ranks[rootY]
if rankX > rankY {
ds.roots[rootY] = rootX
return
}
if rankX < rankY {
ds.roots[rootX] = rootY
return
}
ds.roots[rootX] = rootY
ds.ranks[rootY] += 1
}
func (ds *DisjointSet) IsConnected(x, y int) bool {
return ds.Find(x) == ds.Find(y)
}
func newDisjointSet(n int) *DisjointSet {
roots := make([]int, n)
ranks := make([]int, n)
for i := range n {
roots[i] = i
ranks[i] = 1
}
newDisjointSet := DisjointSet{roots, ranks}
return &newDisjointSet
}
func validPath(n int, edges [][]int, source int, destination int) bool {
ds := newDisjointSet(n)
for _, edge := range edges {
ds.Union(edge[0], edge[1])
}
return ds.IsConnected(source, destination)
}
|
day55 2024-04-22
752. Open the Lock
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.
The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
题解
本题题面非常有意思, 关键是怎么转化这道题. 首先思考如果只有两个转盘, 那么问题可以转化成在一个二维平面上从点(0,0)走到目标点的有障碍物最短路问题, 即在二维数组中, 从(0,0)走到目标点,每次只能向相邻方向移动一位, 同时有一些坐标是不能走得(可以理解为有障碍物). 对于这个问题, 无疑首先想到的就可以通过BFS求解. 将这个问题从二维扩展到四维, 因为每个转盘只有0-9 共10个数字, 所以每一维只需要10个数表示即可, 这样问题就变成了在一个10*10*10*10的四维数组中, 从(0,0,0,0)走到目标点的最短路问题, 其中数组中有些位置是不可达的. 同样使用和二维数组中类似的BFS求解即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| func openLock(deadends []string, target string) int {
deadends_number := map[int]int{}
targetnumber,_ := strconv.Atoi(target)
for _, value := range deadends {
number,_ := strconv.Atoi(value)
if number == 0{
return -1
}
deadends_number[number] = 1
}
pathmap := [][][][]int{}
for z := 0; z < 11; z++ {
second := [][][]int{}
for i := 0; i < 11; i++ {
three := [][]int{}
for j := 0; j < 11; j++ {
four := []int{}
for k := 0; k < 11; k++ {
_, exist := deadends_number[z*1000+i*100+j*10+k]
if exist {
four = append(four, 0)
} else {
four = append(four, 1)
}
}
three = append(three, four)
}
second = append(second, three)
}
pathmap = append(pathmap, second)
}
queue := [][]int{{0, 0, 0, 0}}
pathmap[0][0][0][0] = 0
depth := -1
for len(queue) != 0 {
for _, way := range queue {
if way[0]*1000+way[1]*100+way[2]*10+way[3] == targetnumber{
return depth+1
}
for i := 0; i < 4; i++ { // 遍历四个维度
original := way[i] // 保存原始值
// 尝试向两个方向移动
for _, diff := range []int{-1, 1} {
newIdx := original + diff
// 处理边界情况
if newIdx < 0 {
newIdx = 9
} else if newIdx > 9 {
newIdx = 0
}
way[i] = newIdx // 更新当前维度
// 检查新位置是否可行
if pathmap[way[0]][way[1]][way[2]][way[3]] == 1 {
queue = append(queue, []int{way[0], way[1], way[2], way[3]})
pathmap[way[0]][way[1]][way[2]][way[3]] = 0
}
way[i] = original // 恢复原始值以便下一次循环使用
}
}
queue = queue[1:]
}
depth++
}
return -1
}
|
总结
遇到题面看上去复杂的题目需要将题目的核心问题抽离出来. 若题目本身解决起来比较困难, 可以先尝试思考解决题目的一个子问题, 如降低维度, 减少数量, 再尝试推广到题目本身. 另外在数学中往往从一维到二维有很多不同点, 可能需要全新的工具和解决方式. 但从二维到更高维往往只是简单推广, 这也是为什么很多数学问题只证明二维的情况即可代表全部高维情况的原因.
day56 2024-04-23
310. Minimum Height Trees
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs’ root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
题解
本题乍一看让人摸不着头脑, 细细想想最远的距离肯定是从一个叶子节点到另一个叶子节点, 那么最小高度的子树就是位于这个最远路径上中间位置的一个或者两个节点(取决于路径的长度是奇数还是偶数). 则本题的关键在于求出该无向图中的最长路径, 求出无向图中最长路径可以选择任一叶子节点, 对其进行dfs, 再将得到的当前最长路径的终点作为起点, 进行dfs即可得到全图的最长路径.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1{
return []int{0}
}
numbers := map[int]int{}
graph := map[int][]int{}
exist := false
for _,value := range edges{
for index,vertex := range value{
_, exist = numbers[vertex]
if !exist{
numbers[vertex] = 1
graph[vertex] = []int{value[1-index]}
}else{
numbers[vertex]++
graph[vertex] = append(graph[vertex], value[1-index])
}
}
}
start := 0
for node, count := range numbers{
if count == 1{
start = node
break
}
}
path := []int{start}
depth := 1
path = append(path, dfs(graph[start][0], start, depth+1, graph)...)
length := len(path)
start = path[length-1]
depth = 1
newtest := []int{start}
newtest = append(newtest, dfs(graph[start][0], start, depth+1,graph)...)
if len(newtest) > length{
path = newtest
length = len(newtest)
}
if length % 2 == 1{
return []int{path[length/2]}
}else{
return []int{path[length/2-1],path[length/2]}
}
}
func dfs(node int, parent int, depth int, graph map[int][]int)[]int{
max := depth
return_path := []int{node}
for _,value := range graph[node]{
if value != parent{
temppath := dfs(value, node, depth+1, graph)
if len(temppath) + depth > max{
max = len(temppath) + depth
return_path = append(return_path[0:1], temppath...)
}
}
}
return return_path
}
|
总结
显然, 这种解法是相当慢的, 执行两次dfs也有大量的重复计算. 这里解决本题可以使用对无向图的拓扑排序. 排序操作为设定一个队列, 找到当前图中所有度为1的点, 将其删去(从队列中弹出)并删去其邻接的边, 将与其相邻的点中度为1 的点放入队列. 如此重复, 直到队列中只有一个或者两个点, 即为整个图中的最长路径的中间点. 这里要理解拓扑排序其实是对图的从边缘到中心的一种刻画. 也就是对依赖关系的刻画. 越靠近"中心"的点依赖越多. 排序过程中越靠前的点离图的"中心"越远. 依赖越少. 代码如下, 很简洁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{ 0 }
}
//graph := make(map[int][]int)
neibors := make([][]int, n) //neibors[i] -- all nodes node i can connect to
degree := make([]int, n) //degree[i] -- connections from node i
for _, e := range edges {
na, nb := e[0], e[1]
neibors[na] = append(neibors[na], nb)
neibors[nb] = append(neibors[nb], na)
degree[na]++
degree[nb]++
}
queue := []int{}
for i, d := range degree {
if d == 1 {
queue = append(queue, i)
}
}
// topological sort
for n > 2 {
size := len(queue)
n -= size
for i:=0;i<size;i++{
cur:=queue[i]
for _, next:=range neibors[cur]{
degree[next]--
if degree[next]==1{
queue=append(queue, next)
}
}
}
queue=queue[size:]
}
return queue
}
|
day57 2024-04-24
1137. N-th Tribonacci Number
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
题解
一个简单的动态规划即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func tribonacci(n int) int {
if n == 0{
return 0
}else if n == 1{
return 1
}else if n == 2{
return 1
}else{
arrays := []int32{0,1,1}
var result int32
for i:=3;i<=n;i++{
result = arrays[i-1]+arrays[i-2]+arrays[i-3]
arrays = append(arrays, result)
}
return int(result)
}
}
|
今天题目有些过于简单了,遂再补一道题
2385. Amount of Time for Binary Tree to Be Infected
You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.
Each minute, a node becomes infected if:
The node is currently uninfected.
The node is adjacent to an infected node.
Return the number of minutes needed for the entire tree to be infected.
题解
这道题第一眼看上去就像在一个图中给定一个节点,寻找这个图中与这个节点距离最远的节点的距离.然而题面条件是二叉树,因此最直观的方法就是将二叉树转换为无向图, 再使用BFS找到最远的距离, 这样需要将所有节点遍历两遍.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func amountOfTime(root *TreeNode, start int) int {
undirected_map := map[int][]int{}
undirected_map[root.Val] = []int{}
queue := []*TreeNode{root}
for len(queue) != 0{
for _, node := range queue{
if node.Left != nil{
undirected_map[node.Val] = append(undirected_map[node.Val],node.Left.Val)
undirected_map[node.Left.Val] = []int{node.Val}
queue = append(queue, node.Left)
}
if node.Right != nil{
undirected_map[node.Val] = append(undirected_map[node.Val],node.Right.Val)
undirected_map[node.Right.Val] = []int{node.Val}
queue = append(queue, node.Right)
}
queue = queue[1:]
}
}
visited := make([]int,100001)
neibor := []int{start}
visited[start] = 1
time := 0
for len(neibor) != 0{
for _,node := range neibor{
for _,value := range undirected_map[node]{
if visited[value] != 1{
neibor = append(neibor, value)
visited[value] = 1
}
}
neibor = neibor[1:]
}
time++
}
return time-1
}
|
总结
显然这种方法略慢, 要是可以在一次遍历的时候保存一定的信息, 减少重复的节点访问就好了, 思考这棵二叉树, 如果我们知道了从根节点到开始节点的距离, 并且保存了从根节点到开始节点的路径, 那么最远距离分为两种情况, 要么是以开始节点为根节点的子树足够深, 要么是开始节点的祖先节点的另外一棵子树足够深, 二者哪个更大就取哪个的最远距离. 尽管思路如此, 但当时我的想法是这样在寻找从根节点到开始节点时也要使用DFS, 这样在最差情况也要访问整棵树, 但实际上平均情况下会少访问大概以开始节点为根节点的子树的节点. 这样当节点数很多的时候也有一定的复杂度优势. 但是事实证明, 我想的还是不够全面, 实际上我们在递归调用的时候可以通过返回更多信息(一个布尔值)来标记该节点的某个子树上含有开始节点, 同时返回当前节点距离开始节点的距离. 这样通过一个非常巧妙的信息流动, 在开始节点处判断了以开始节点为根节点的子树的最大深度, 从开始节点处递归返回时向祖先节点传递该子树包含开始节点和距离开始节点的距离信息. 这样充分利用了在递归遍历过程中的全部信息. 只需要一次遍历即可解决. 充分的利用和整合信息是提高算法效率的关键, 示例代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| func amountOfTime(root *TreeNode, start int) int {
if root == nil {
return 0
}
r := 0
//
// returns true if start is a child of p.
// and the distance from this node to start.
// false if the start is not child of p.
// and the longest distance to a leave in this subtree.
//
var dfs func(p * TreeNode) (bool, int)
dfs = func(p * TreeNode) (bool, int) {
ll, rr, lh, rh := 0, 0, false, false
if p.Left != nil {
lh, ll = dfs(p.Left)
ll++
}
if p.Right != nil {
rh, rr = dfs(p.Right)
rr++
}
if p.Val == start {
if r < ll {
r = ll
}
if r < rr {
r = rr
}
return true, 0 // 0 to get the dist to parent
}
if lh {
if ll + rr > r {
r = ll + rr
}
return true, ll
}
if rh {
if ll + rr > r {
r = ll + rr
}
return true, rr
}
if ll < rr {
ll = rr
}
return false, ll
}
dfs(root)
return r
}
|
day58 2024-04-25
2370. Longest Ideal Subsequence
You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied:
t is a subsequence of the string s.
The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.
Return the length of the longest ideal string.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of ‘a’ and ‘z’ is 25, not 1.
题解
字符串子序列问题是一类很经典的递推计数问题. 一般可以用动态规划来解决. 问题的关键在于如何找到问题的子问题. 对于本题, 思考通过贪心等方式直接找到最长的子序列显然是不可行的, 因为一个字符在当前串中作为结尾可以使该串长度增大, 但后续可能有更长的串与没有这个字符的串可以连接, 但加上这个字符使得这个更长的串不能连接了. 显然考虑的不够周全. 那么现在还是要紧紧围绕我们在解题时多次提到过的思想: 能更有效的利用更多的信息, 算法的效率就越高. 对于一个字符来说, 哪些信息是有用的, 与之相差k个距离以内的字符是有用的, 因为这些字符可以与当前字符连接. 用贪心难以解决的原因在于, 只考虑了和当前字符相邻的k以内这一群邻居中的一个, 自然不能高效求解. 那么我们只要一直保存着所有以字符结尾的子序列的长度, 在遇到新字符时只需要对k个距离内的字符子序列进行比较, 找出最长的并将其加1作为当前字符的最长子序列长度. 这样充分利用了以前遍历过的可行字符组合的信息. 并将所有邻居都考虑进来, 最终就能得到可行解.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func longestIdealString(s string, k int) int {
lengths := make([]int32, 26)
var left int32
var right int32
var temp_max int32
k32 := int32(k)
for _,value := range s{
temp_max = 0
left = value - 'a' - k32
right = value - 'a' + k32
if value - 'a' < k32{
left = 0
}
if 'z' - value < k32{
right = 25
}
for _, number := range lengths[left:right+1]{
temp_max = max(number, temp_max)
}
lengths[value - 'a'] = temp_max + 1
}
return int(slices.Max(lengths))
}
|
day59 2024-04-26
1289. Minimum Falling Path Sum II
Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.
题解
本题为一道难题, 拿到题目首先观察, 可以想到的比较直接的点是如果从第一行直接向下一行行遍历并选择的话, 那么以3*3的矩阵为例, 第一行的第一二列同时选择第二行的第三列, 则对二者来说, 第三行的可选项是相同的. 即除一二列以外的列二者可以选择来累加的元素是相同的. 如第一个示例中的1-6-7,1-6-8,2-6-7,2-6-8. 显然这里对于1,2来说二三列的选择完全相同, 在这种情况下无疑选择1可以得到更小的和. 问题就变成了, 如何把这种已知的对以前的行中的元素的相对大小这一信息保留下来, 很简单, 让每一行的各个元素都保存在其上面行的最小元素和即可. 这样就保证了在能选择该元素的情况下, 以前的路径是从每行中挑出来的可选元素中的最小元素组成的路径. 也就保留了之前各行的元素之间已经判断过的相对大小. 这是一种动态规划的思想, 这里还要解决另外一个问题, 已知n-1行中保留了之前行的最小路径和, 对于第n行的各个元素, 如何高效的从n-1行中的可选元素中选出最小的(同一列的不可选). 显然每个都对n-1行整行做比较是$n^2$的复杂度, 应该高效利用保留信息. 仔细思考一下可以发现, 其实只需要知道最小的和第二小两个值就够了, 因为对于任意一个元素其同一列要么是最小的那个, 那就应该选第二小的, 要么不是最小的, 那就选最小的, 对于求最小值来说, 只需考虑这两种情况就够了(求最小和第二小的值本身也是一个很有趣的小问题, 不用排序, 一次遍历即可, 读者可先自行思考, 然后参考代码中的实现). 思路清晰后, 实现代码即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| func minFallingPathSum(grid [][]int) int {
rowlen := len(grid)
if rowlen == 1{
return grid[0][0]
}
sums := [][]int{}
firstrow := grid[0]
sums = append(sums, firstrow)
// grid[i][j] <= 99
small, second, newsmall, newsecond := math.MaxInt32,math.MaxInt32,math.MaxInt32,math.MaxInt32
for _, value := range firstrow{
if value < small{
second = small
small = value
}else if value < second{
second = value
}
}
for index, row := range grid[1:]{
rowsum := []int{}
newsmall, newsecond = math.MaxInt32, math.MaxInt32
for col, value := range row{
if sums[index][col] != small{
thissum := small + value
rowsum = append(rowsum, thissum)
if thissum < newsmall{
newsecond = newsmall
newsmall = thissum
}else if thissum < newsecond{
newsecond = thissum
}
}else{
thissum := second + value
rowsum = append(rowsum, thissum)
if thissum < newsmall{
newsecond = newsmall
newsmall = thissum
}else if thissum < newsecond{
newsecond = thissum
}
}
}
sums = append(sums, rowsum)
small = newsmall
second = newsecond
}
return small
}
|
总结
Beats 100%
day60 2024-04-27
514. Freedom Trail
In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring” and use the dial to spell a specific keyword to open the door.
Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at the “12:00” direction. You should spell all the characters in key one by one by rotating ring clockwise or anticlockwise to make each character of the string key aligned at the “12:00” direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
You can rotate the ring clockwise or anticlockwise by one place, which counts as one step. The final purpose of the rotation is to align one of ring’s characters at the “12:00” direction, where this character must equal key[i].
If the character key[i] has been aligned at the “12:00” direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.
题解
本题是一道难题, 花了很长时间, 但理解的还是不够透彻, 关键在于保存什么样的状态是可以避免不必要的运算的. 保存的状态必须是在运算过程中必要的且若之前计算过则避免重复运算. 考虑本题中的关键, key中下一个字符要转动到12点方向只于当前12点方向的字符有关, 也就是只与当前12点方向的ring字符串中对应位置上的字符有关, 因此我们想要知道的是在ring字符串的该位置上的字符转动到key的下一个字符的最短距离是多少, ring中可能有多个key的下一个字符, 转动到这些字符中的哪个能获得全局最短距离在当前场景下是未知的, 因此最好的方法就是延迟决定, 递归的对所有可行位置执行搜索, 这样从上到下一层层深入直到key中最后一个字符, 再将各个路径上得到的距离做比较, 取最小的那个作为下一个转动到12点方向的字符位置, 这里在递归过程中要保存子递归中已经计算过的后面的ring对后面的key的字符的最短距离. 这里要理解保存的状态是在子递归过程中运算出来的一系列子结果, 这些子结果后面可能有用, 也可能没用, 但是算过了就要保存下来, 有没有用在比较高的递归层级是未知因素.
这里还有一些比较抽象的思考, 该题的解法中使用动态规划思想最小的子问题是什么, 其实是key中从任一个字符到下一个字符移动的最短距离, 可以将寻找路径的过程想象成一棵树, 每一层代表key中以层数为下标对应字符在ring串中的所有可行位置, 这样一棵非常庞大的演化树, 递归的过程就是遍历这棵树的所有到叶子节点的路径并保存该过程中的状态最终找到最短路. 理解这个状态空间是什么以及为什么保存这个状态是很高效的十分重要, 值得细细品味
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func findRotateSteps(ring string, key string) int {
var m, n = len(ring), len(key)
var pos = make(map[uint8][]int)
for i := 0; i < len(ring); i++ {
pos[ring[i]] = append(pos[ring[i]], i)
}
var mem = make([][]int, m)
for i := range mem {
mem[i] = make([]int, n)
for j := range mem[i] {
mem[i][j] = -1
}
}
var dfs func(i, j int) int // ring[i] is currently at 12 o'clock , j stands for current key[j]
dfs = func(i, j int) (res int) {
if j == n {
return
}
var p = &mem[i][j]
if *p != -1 {
return *p
}
defer func() { *p = res }()
res = math.MaxInt
for _, po := range pos[key[j]] { // scan all the position key[j] in ring
res = min(res, dfs(po, j+1)+min(abs(i-po), m-abs(i-po))) // we need to make po at 12 o'clock by rotating ring clockwise or counterclockwise (choose the smaller one), and then plus dfs(po,j+1)
}
return
}
return n + dfs(0, 0) // every char in key needs to be pressed too
}
|
day61 2024-04-28
834. Sum of Distances in Tree
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.
题解
考虑这棵树,其实将任意一个节点作为树的根节点都不影响结果, 这也意味着这个树中各个元素地位相同, 更像是一张无向图. 对于树中任意一个节点而言, 若将其看作根节点, 只要知道了其所有连通节点到连通节点的的"子树"的距离和和这个"子树"中包含的节点数量, 就能算出根节点到其他所有节点的距离和. 而求其连通节点到连通节点的子树的距离和可以继续采用这种思路, 显然可以通过递归的方式求解, 思想是动态规划的思想. 最直接的解法就是将这个递归式写出来, 同时保存在求解过程中解出的某节点对应的一个连通节点的"子树"的距离和. 但这种方法会超时, 因此需要思考哪里还有重复计算的部分, 考虑一个极端例子, 一共有30000个节点, 其中29999个节点都和节点0相连. 这种情况下, 如果依次遍历各个节点并计算其相邻节点的"子树"距离和, 会发现尽管已经保存了节点0到其余节点的距离和, 但还是要将0到剩余29998个节点都遍历一遍(不用计算,只直接拿结果), 这样显然是$n^2$的复杂度, 显然这里可以简化, 对于节点0, 已经计算得到了它到其余所有节点的距离和, 只需要使用这个距离和减掉从0到当前节点的"子树"包含的距离和再加上0剩余的连通节点的"子树"包含的节点数目(原本的距离是到节点0, 从节点0到当前节点要将每个节点距离加1)就得到了当前节点到其余各节点的距离和.
想到这会发现, 其实只要任选一个节点计算其到其他节点的距离和, 若将这个节点作为根节点, 那么在计算过程中就已经将全部节点的"子树"距离和计算出来, 与真正的节点距离和相比, 只缺少了一个分支的距离和. 则在算出当前节点的距离和后, 可直接继续计算相邻节点的距离和, 计算方式为当前节点距离和减掉当前节点到相邻节点这一分支的距离和加上剩余的节点数, 再加上这个相邻节点到它的其余相邻节点的距离和, 这在之前的递归计算过程中已经保存了. 本题想高效求解, 不但要保存求解过程中的的中间结果, 还要充分利用已经求解出来的结果.
代码
初始版本:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| func sumOfDistancesInTree(n int, edges [][]int) []int {
connected := [][]int{}
dis := make([]map[int][]int,n)
results := []int{}
for i:=0;i<n;i++{
connected = append(connected, []int{})
dis[i] = map[int][]int{}
}
for _,edge := range edges{
connected[edge[0]] = append(connected[edge[0]],edge[1])
connected[edge[1]] = append(connected[edge[1]],edge[0])
}
var recusive func(int, int)(int,int)
recusive = func(parent int, now int)(int,int){
value, exist := dis[parent][now]
if exist{
return value[0], value[1]
}else{
if len(connected[now]) == 1{
return 0,1
}
distance := 0
numbers := 0
for _, neibor := range connected[now]{
if neibor != parent{
subdistance, number := recusive(now, neibor)
distance += subdistance + number
numbers += number
}
}
numbers++
newslice := []int{distance, numbers}
dis[parent][now] = newslice
return distance, numbers
}
}
for index,neibors := range connected{
result := 0
for _, neibor := range neibors{
if neibor < index {
resultverse, numb := recusive(neibor,index)
result += results[neibor] - resultverse - numb + n - numb
}else{
oneway, numbers := recusive(index, neibor)
result += oneway + numbers
}
}
results = append(results, result)
}
return results
}
|
优化版本:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| func dfs0(node int, parent int, t [][]int, dp []int, c []int) {
n := len(t[node])
c[node] = 1
for i := 0; i < n; i++ {
child := t[node][i]
if child != parent {
dfs0(child, node, t, dp, c)
dp[node] += dp[child] + c[child]
c[node] += c[child]
}
}
}
func dfs1(node int, parent int, sum int, t [][]int, dp []int, c []int, res []int) {
res[node] = sum
n := len(t[node])
s := 0
for i := 0; i < n; i++ {
child := t[node][i]
if child != parent {
res[node] += dp[child] + c[child]
s += dp[child] + c[child]
}
}
for i := 0; i < n; i++ {
child := t[node][i]
if child != parent {
dfs1(child, node, sum+(s-dp[child]-c[child])+(len(t)-c[child]), t, dp, c, res)
}
}
}
func sumOfDistancesInTree(n int, e [][]int) []int {
t := make([][]int, n)
for i := 0; i < len(e); i++ {
u, v := e[i][0], e[i][1]
t[u] = append(t[u], v)
t[v] = append(t[v], u)
}
dp := make([]int, n)
c := make([]int, n)
dfs0(0, -1, t, dp, c)
res := make([]int, n)
dfs1(0, -1, 0, t, dp, c, res)
return res
}
|
总结
看讨论区时发现, 这类题目叫作Tree rerooting DP, 的确在本题中计算距离和的过程相当于不断更换树的根节点. 下面这个视频中对这一问题有比较系统的讲解
https://www.youtube.com/watch?v=7_huTWwl5jM
了解下系统性的思路是好的, 但我向来不支持"套用", 要理解其内在的本质并根据实际问题灵活运用才是真正掌握. 就好像动态规划的"状态转移公式", 核心思想在于将大问题分解成小的子问题以及保存解决子问题过程中的信息(中间结果)用于后续处理, 正如我不断强调的核心观点, 利用的有效信息越多, 算法效率就越高.
day62 2024-04-29
2997. Minimum Number of Operations to Make Array XOR Equal to K
You are given a 0-indexed integer array nums and a positive integer k.
You can apply the following operation on the array any number of times:
Choose any element of the array and flip a bit in its binary representation. Flipping a bit means changing a 0 to 1 or vice versa.
Return the minimum number of operations required to make the bitwise XOR of all elements of the final array equal to k.
Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.
题解
本题最终对数组中所有的数进行异或运算, 得到目标k. 考虑到对k中的每一位而言, 数组中的数只需要在该位上做异或运算最终与k的该位相等. 对数组中的数, 对除最后一个数以外的所有数异或, 得到的结果再与最后一个数异或, 只需调整最后一个数的各个位使得最终结果与k相同. 因为调整任意一个数的某个位都是等价的, 而先将前面的数异或相当于保存了前面所有数中各个位异或后的信息. 将结果和最后一个数按位与k比较并调整即可. 只需注意如果一个数的后面的位比较完成前面全是0, 对对应的也要做相应调整.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func minOperations(nums []int, k int) int {
numlen := len(nums)
before := nums[0]
last := 0
if numlen == 1{
last = 0
}else{
for _, value := range nums[1:numlen-1]{
before ^= value
}
last = nums[numlen-1]
}
result := 0
first := 0
second := 0
target := 0
for before != 0 || last != 0 || k != 0{
first = before % 2
second = last % 2
target = k % 2
if first ^ second != target{
result++
}
before /= 2
last /= 2
k /= 2
}
return result
}
|
总结
其实将所有数异或后直接和k进行异或, 得到的结果中如果某位为1则说明和k的这一位不同, 为0则相同, 将结果不断右移并判断最后一位是否为1即可得到需要翻转的次数.
day63 2024-04-30
1915. Number of Wonderful Substrings
A wonderful string is a string where at most one letter appears an odd number of times.
For example, “ccjjc” and “abab” are wonderful, but “ab” is not.
Given a string word that consists of the first ten lowercase English letters (‘a’ through ‘j’), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.
A substring is a contiguous sequence of characters in a string.
题解
这种子字符串的问题大概要保存一些状态以供后续的判断, 关键在于保存什么状态是有用的, 这里可以保存到某个下标为止的前缀字符串中各个字符的数量, 但是注意本题只要求判断字符串中出现了奇数次的字符的数量, 因此关键在于字符串中的某个字符的数量是否为奇数. 考虑这样的情况, 如果以下标3为结尾的字符串中字符’a’出现了奇数次, 以下标5为结尾的字符串中字符’a’也出现了奇数次, 那么这两个下标之间的字符串中’a’必定出现了偶数次(两奇数做差, 必定为偶数). 同样两偶数做差也必定为偶数, 只有偶数和奇数做差时才会出现奇数. 因此只需要保存到某个下标结尾处字符串中各个字符出现次数的奇偶性再与其他下标做比较, 字符奇偶性不同的字符小于2则二者之间的字符串是可行的, 否则不可行.
保存各个字符的奇偶性可以使用位标记, 从a到z每个字母用一个二进制位表示, 用一个十维数组也可行, 但在只需要保存一个二值状态时用位更节省空间. 求出到各个下标的各个字符的奇偶串后, 依次遍历每个位置, 分别与后面的所有位置做异或, 再判断异或后的数字的二进制表示中1的个数是否大于1个, 大于则这两个下标之间的字符串奇数个字符大于1, 判断是否大于一个可以使用n&(n-1)来消掉最低的1, 再判断剩余的数字是否为0, 不为0说明大于1个.
但使用这种方法, 每次都要将当前下标与后面的所有下标都比较一遍, 显然是$n^2$的复杂度. 这里可以发现, 使用这种方法遍历没有考虑到这种字符串差出现的先后位置与结果无关, 即差值的具体数量与结果无关. 例如, 在下标为1处的位串为0101, 在3和5处的位串都为0111, 实际上这两个位置与下标1做异或后的结果相同, 即1-3和1-5之间都只有1个位置是奇数个, 至于这个位置是3个或是5个, 或者3-5之间这个位置没发生变化其他位置多了两个, 都不影响区间字符串的奇偶性质. 这里的思想和用位来表示字符的奇偶性有异曲同工之妙, 即无需考虑具体数量, 只需考虑其拥有的性质即可.
有了这种想法, 那么只需要保存所有的位串, 并统计所有位串的数量, 如0101的位串有五个, 说明这五个位串代表的下标之间的四个间隙的所有字符都是偶数个那么这四个显然是符合要求的结果. 再计算有一个奇数位的情况, 只需要将每个串中的各个位依次翻转并查询翻转后的位串的数量即可. 每个串最多翻转10次(a-j 10个字符), 10位二进制串最多有1024种组合, 意味着最多翻转1024*10=10240次. 降为常数复杂度.
在翻转的过程中, 两种字符串之间翻转后的组合会被计数两次(0101翻转得到0111,0111翻转得到0101), 将最终结果除以2即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| func wonderfulSubstrings(word string) int64 {
masks := map[int]int{}
bytes := []byte(word)
mask := 0
masks[0] = 1
for _, char := range bytes{
mask ^= (1<<(char-'a'))
masks[mask] = masks[mask] + 1
}
result := 0
flip := 0
fmt.Println(masks[0])
for value, number := range masks{
result += number * (number - 1) / 2
for i:=0;i<10;i++{
flip += masks[value ^ (1<<i)] * number
}
}
return int64(result+flip/2)
}
|
总结
本题是一道比较综合的题目, 找到关键状态是解决问题的核心.
day64 2024-05-01
2000. Reverse Prefix of word
Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.
For example, if word = “abcdefd” and ch = “d”, then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be “dcbaefd”.
Return the resulting string.
题解
本题是一道简单题, 显然找到第一个ch的位置翻转字符串即可, 若想在找到后快速翻转字符串, 可以在找到对应字符的下标后除以2找到中间位置字符, 分别从子字符串开头和结尾开始向中间遍历并不断交换首尾字符即可实现翻转,
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func reversePrefix(word string, ch byte) string {
bytes := []byte(word)
first := 0
for index, char := range bytes{
if char == ch{
first = index
break
}
}
mid := first/2
copybytes := []byte(word)
for index,_ := range copybytes[0:mid]{
bytes[index] = copybytes[first-index]
bytes[first-index] = copybytes[index]
}
if first % 2 == 1{
bytes[mid] = copybytes[mid+1]
bytes[mid+1] = copybytes[mid]
}
return string(bytes)
}
|
day65 2024-05-02
2441. Largest Positive Integer That Exists With Its Negative
Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.
Return the positive integer k. If there is no such integer, return -1.
题解
本题是一道简单题, 题目中给出数字的范围为-1000到1000, 因此可以使用一个1001长度的数组来保存每个数字的状态, 状态分为未出现, 出现了一个负数, 出现了一个正数和出现过了这个数的正负两个数四种情况. 因此使用四个数字来表示这四种情况即可, 0表示未出现, -1表示只出现过负数, 1表示只出现过正数, 2表示一正一负, 遍历数组并改变相应状态, 当状态变为2时与当前的最大结果比较并更新最大值即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func findMaxK(nums []int) int {
result := -1
numbers := make([]int,1001)
for _,value := range nums{
if value > 0{
if numbers[value] == -1{
numbers[value] = 2
result = max(result, value)
}else if numbers[value] == 0{
numbers[value] = 1
}
}else{
if numbers[-value] == 1{
numbers[-value] = 2
result = max(result, -value)
}else if numbers[-value] == 0{
numbers[-value] = -1
}
}
}
return result
}
|
day 66 2024-05-03
165. Compare Version Numbers
Given two version numbers, version1 and version2, compare them.
Version numbers consist of one or more revisions joined by a dot ‘.’. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.5.33 and 0.1 are valid version numbers.
To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.
Return the following:
If version1 < version2, return -1.
If version1 > version2, return 1.
Otherwise, return 0.
题解
本题将字符串根据.号分割成字符数组, 再将两个字符数组转换成整数并比较大小.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| func compareVersion(version1 string, version2 string) int {
ver1slice := strings.Split(version1, ".")
ver2slice := strings.Split(version2, ".")
len1 := len(ver1slice)
len2 := len(ver2slice)
shortlen := 0
short := []string{}
long := []string{}
flag := 0
if len1 > len2{
short = ver2slice
long = ver1slice
shortlen = len2
flag = 1
}else{
short = ver1slice
long = ver2slice
shortlen = len1
flag = -1
}
for index, str := range short{
result1,_ := strconv.Atoi(str)
result2,_ := strconv.Atoi(long[index])
if result1 < result2{
return flag
}else if result1 > result2{
return -flag
}
}
for _, str := range long[shortlen:]{
result, _ := strconv.Atoi(str)
if result != 0{
return flag
}
}
return 0
}
|
day67 2024-05-04
881. Boats to Save People
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
题解
本题中每艘船只能乘坐两个人, 则两个人的重量和应小于船的限制limit, 因此重量较小的人可以和重量较大的人乘同一艘船, 但重量大于limit/2的人只能独自乘船, 不能与他人共乘. 则先统计各个重量的人数, 放在数组中, 数组下标表示对应的重量. 值为对应的人数. 从头遍历数组, 对于重量小于limit/2的人, 可以和与其重量和为limit及以下的人共同乘船, 从能与其共同乘船的最大重量开始向前遍历, 直到遍历过的重量的人数和与当前重量人数相同为止. 这些人每两两一组可以共乘同一艘船. 如果还有剩余, 说明后面已经全部遍历完, 考虑当前重量小于等于limit/2, 故两个人可以共同乘船, 将结果加上剩余人数的1/2, 奇数再加上一即可. 对于遍历到重量大于limit/2的情况, 因为不能和他人共同乘船, 直接将结果加上当前重量人数即可.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| func numRescueBoats(people []int, limit int) int {
peoples := make([]int, limit+1)
for _, value := range people{
peoples[value] = peoples[value] + 1
}
peoples[0] = peoples[limit]
result := 0
tail := 0
index := 0
value := 0
half := limit/2
for index <= limit{
value = peoples[index]
tail = limit-index
for tail > index{
value -= peoples[tail]
if value > 0{
result += peoples[tail]
peoples[tail] = 0
tail--
}else{
result += peoples[tail] + value
peoples[tail] = -value
value = 0
break
}
}
if index <= half{
result += value/2 + (value%2)
}else{
result += value
}
index++
}
return result
}
|
总结
本题关键在于船的人数有限制, 只能两个人, 如果船的人数无限而重量有限的话, 要尽可能将船装满, 从后向前遍历时要根据当前遍历到的重量减去对应的比较轻的重量的人数直到将船装满为止.
day68 2024-05-05
237. Delete Node in a Linked List
There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:
The value of the given node should not exist in the linked list.
The number of nodes in the linked list should decrease by one.
All the values before node should be in the same order.
All the values after node should be in the same order.
Custom testing:
For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
We will build the linked list and pass the node to your function.
The output will be the entire list after calling your function.
题解
本题是一道基本的链表操作问题, 给定要删除的节点指针, 则不知道节点的前置节点指针, 只能通过遍历链表并将将后一个节点的值赋给前一个节点的方式来删除掉(覆盖)当前节点的值. 注意对倒数第二个节点, 当将最后一个节点的值赋给它后将其Next指针置为nil从而删掉原来的最后一个节点.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteNode(node *ListNode) {
for node.Next.Next != nil{
node.Val = node.Next.Val
node = node.Next
}
node.Val = node.Next.Val
node.Next = nil
}
|
根据公式直接求出x的值即可, 注意考虑到精度问题, 要对最终得到的运算结果与取整后的数字的差的绝对值进行判断, 小于一定限度即可认为是整数值.
