浙江网站建设价位,seo优化的网站,做企业网站服务商,海南网站建设基本流程文章目录 51. 缺失的第一个正数题目描述代码与解题思路 52. 训练计划 II题目描述代码与解题思路 53. 子集题目描述代码与解题思路 54. 最小覆盖子串题目描述代码与解题思路 55. 从前序与中序遍历序列构造二叉树题目描述代码与解题思路 56. 零钱兑换题目描述代码与解题思路 57. … 文章目录 51. 缺失的第一个正数题目描述代码与解题思路 52. 训练计划 II题目描述代码与解题思路 53. 子集题目描述代码与解题思路 54. 最小覆盖子串题目描述代码与解题思路 55. 从前序与中序遍历序列构造二叉树题目描述代码与解题思路 56. 零钱兑换题目描述代码与解题思路 57. 最小栈题目描述代码与解题思路 58. 最长有效括号题目描述代码与解题思路 59. 反转字符串中的单词题目描述代码与解题思路 60. 字符串相乘题目描述代码与解题思路 51. 缺失的第一个正数
题目链接41. 缺失的第一个正数
题目描述 代码与解题思路
func firstMissingPositive(nums []int) int {for i : 0; i len(nums); i {for nums[i] 0 nums[i] len(nums) nums[i] ! nums[nums[i]-1] {nums[i], nums[nums[i]-1] nums[nums[i]-1], nums[i]}}for i : 0; i len(nums); i {if nums[i] ! i1 {return i1}}return len(nums)1
}这道题不难做难在怎么用 O(N) 的时间复杂读和 O(1) 的空间复杂度来做如果忽略这两个条件可以用排序二分可以用哈希存储
而想要达成这个复杂度的目标就必须用原地哈希来做而具体思路就是这个哥们的神之比喻
52. 训练计划 II
题目链接LCR 140. 训练计划 II
题目描述 代码与解题思路
func trainingPlan(head *ListNode, cnt int) *ListNode {slow, fast : head, headfor fast ! nil cnt 0 {fast fast.Nextcnt--}for fast ! nil {slow slow.Nextfast fast.Next}return slow
}这道题刷的次数太多太多一看到 DNA 都动了直接快慢指针fast 先走 cnt 步然后再一起走就行了。
53. 子集
题目链接78. 子集
题目描述 代码与解题思路
func subsets(nums []int) (ans [][]int) {tmp : []int{}var dfs func(int)dfs func(start int) {ans append(ans, append([]int(nil), tmp...))for i : start; i len(nums); i {tmp append(tmp, nums[i])dfs(i1)tmp tmp[:len(tmp)-1]}}dfs(0)return ans
}经典的 dfs 模板题求子集还有一个模板是 dfs 求全排列前段时间刷过。
54. 最小覆盖子串
题目链接76. 最小覆盖子串
题目描述 代码与解题思路
func minWindow(s string, t string) string {if len(s) len(t) {return }win : map[byte]int{}cmp : map[byte]int{}// 初始化 cmpfor i, _ : range t {cmp[t[i]]}start, end, match, minLen : 0, 0, 0, 100010for left, right : -1, 0; right len(s); right {// 1. 将 s[right] 加入区间ch1 : s[right]win[ch1]// 2. 更新状态if win[ch1] cmp[ch1] {match}// 3. 满足条件, 出窗口for match len(cmp) {// 更新窗口长度的最小值if right - left minLen {start, end left, rightminLen right - left}// 出窗口, 更新状态leftch2 : s[left]if win[ch2] cmp[ch2] {match--}win[ch2]--}}return s[start1:end1]
}这道题是典型的比较复杂的滑动窗口题目考察对细节的把控以及对滑动窗口算法思想的掌握程度省流考察基本功我现在基本功也不够扎实希望下一次能轻松写出这道题目
55. 从前序与中序遍历序列构造二叉树
题目链接105. 从前序与中序遍历序列构造二叉树
题目描述 代码与解题思路
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) 0 {return nil}root : TreeNode{preorder[0], nil, nil}i : 0for i 0; i len(inorder); i { // 找到与前序遍历数对应的中序遍历数if inorder[i] preorder[0] {break}}root.Left buildTree(preorder[1:len(inorder[:i])1], inorder[:i]) // 构建左子树root.Right buildTree(preorder[len(inorder[:i])1:], inorder[i1:]) // 构建右子树return root
}这道题目的关键是得知道怎么用前序遍历和中序遍历的性质推出一棵树只需要知道这一点这道题就很好做了具体来说就是根据两个性质
前序遍历数组的第一个数就是根节点中序遍历数组的数在左边的就是在他的左子树在右边就是在他的右子树举个例子 根节点 3中序数组中9 在 3 的左边所以他在左子树剩下的其他节点在右边所以他们是右子树。
根据这两个性质就能推出一整棵树了也通过这个性质来构建一颗树。
56. 零钱兑换
题目链接322. 零钱兑换
题目描述 代码与解题思路
func coinChange(coins []int, amount int) int {dp : make([]int, amount1)for i, _ : range dp {dp[i] math.MaxInt}dp[0] 0for i : 0; i len(coins); i {for j : coins[i]; j amount; j {if dp[j-coins[i]] ! math.MaxInt {dp[j] min(dp[j], dp[j-coins[i]]1)}} }if dp[amount] ! math.MaxInt {return dp[amount]}return -1
}我背包问题没怎么学明白看的这个哥们的思路https://leetcode.cn/problems/coin-change/discussion/comments/79896
57. 最小栈
题目链接155. 最小栈
题目描述 代码与解题思路
这道题真的只有做过才能想的出来虽然我之前做过一次但是现在已经忘记了所以就先凭感觉刷了一遍
type MinStack struct {arr []int min int
}func Constructor() MinStack {return MinStack{arr: []int{},min: math.MaxInt,}
}func (this *MinStack) Push(val int) {if this.min val {this.min val}this.arr append(this.arr, val)
}func (this *MinStack) Pop() {top : this.arr[len(this.arr)-1]this.arr this.arr[:len(this.arr)-1]if top this.min {minVal : math.MaxIntfor _, v : range this.arr {minVal min(minVal, v)}this.min minVal}
}func (this *MinStack) Top() int {return this.arr[len(this.arr)-1]
}func (this *MinStack) GetMin() int {return this.min
}O(1) 取最小O(N) 维护
之后看了一下官方题解记忆回归
type MinStack struct {st1 []intst2 []int
}func Constructor() MinStack {return MinStack {st1: []int{},st2: []int{math.MaxInt},}
}func (t *MinStack) Push(val int) {t.st1 append(t.st1, val)t.st2 append(t.st2, min(t.st2[len(t.st2)-1], val))
}func (t *MinStack) Pop() {t.st1 t.st1[:len(t.st1)-1]t.st2 t.st2[:len(t.st2)-1]
}func (t *MinStack) Top() int {return t.st1[len(t.st1)-1]
}func (t *MinStack) GetMin() int {return t.st2[len(t.st2)-1]
}官方给定的方法是维护两个栈一个栈正常放值正常出值另一个最小栈每次入栈都是最小值
58. 最长有效括号
题目链接32. 最长有效括号
题目描述 代码与解题思路
用栈模拟
func longestValidParentheses(s string) (ans int) {st : []int{-1}for i, v : range s {if v ( {st append(st, i)} else { // v )st st[:len(st)-1]if len(st) 0 { // 栈不为空, 更新最大长度ans max(ans, i - st[len(st)-1])} else { // 栈为空, 将)对应的索引入栈作为新的参照物st append(st, i)}}}return ans
}核心思想
保留一个参照位置通过当前索引值 - 参照位置的索引求出最长括号的长度参照位置初识为 -1之后为初识位置的前一个位置当 v ‘(’ 时入栈遇到 ‘)’ 出栈匹配并更新最长长度当遇到 ‘)’ 而没有 ‘(’ 匹配的话就让它作为新的参照物
其实还有动态规划的解法但是对我现在来说太难了
59. 反转字符串中的单词
题目链接151. 反转字符串中的单词
题目描述 代码与解题思路
func reverseWords(s string) string {s strings.TrimSpace(s)left, right : len(s)-1, len(s)-1resSlice : make([]string, 0)for left 0 {// left 找单词左边界for left 0 s[left] ! {left--}resSlice append(resSlice, s[left1:right1])// left 跳过空格for left 0 s[left] {left--}right left}return strings.Join(resSlice, )
}这道题主要是用了 s strings.TrimSpace(s)以及 strings.Join(resSlice, ) 两个字符串相关的 api之后我会总结一份 Golang 专属的刷算法 api 库到时候会收录进去的
60. 字符串相乘
题目链接43. 字符串相乘
题目描述 代码与解题思路
func multiply(num1 string, num2 string) string {if num1 0 || num2 0 {return 0}ans : 0m, n : len(num1), len(num2)for i : n - 1; i 0; i-- {curr : add : 0for j : n - 1; j i; j-- { // 竖式乘法, 每乘一个数后面会多一个 0curr 0}y : int(num2[i] - 0)for j : m - 1; j 0; j-- {x : int(num1[j] - 0)product : x * y addcurr strconv.Itoa(product % 10) curr // 把新计算的数拼接到 curr 前面add product / 10}if add ! 0 { // 处理最后一次进位curr strconv.Itoa(add % 10) curr}ans addStrings(ans, curr)}return ans
}func addStrings(num1, num2 string) string { // 竖式乘法的每一轮相加i, j : len(num1) - 1, len(num2) - 1add : 0ans : for ; i 0 || j 0 || add ! 0; i, j i - 1, j - 1 {x, y : 0, 0if i 0 {x int(num1[i] - 0)}if j 0 {y int(num2[j] - 0)}result : x y addans strconv.Itoa(result % 10) ansadd result / 10}return ans
}这道题不简单但并不是不能做一定要做好分析正确的模拟竖式乘法的过程主要是分为两个步骤一个是对竖式乘法每一行乘积的模拟一个是将竖式乘法每一行的乘积相加的模拟把这两个核心步骤实现了这道题目就做出来了
考察的是对字符串操作和代码的把控能力现在我的代码把控能力还没有非常的强我希望寒假的这一个月能有一个不小的进步
