数组双指针刷题总结
双指针技巧分为快慢指针和左右指针 快慢指针 原地修改数组 遍历fast 去探路,探到符合条件的将其赋值给slow,并slow++ 去除有序数组/链表中去重 和上边类似,例如删除指定元素v: 遍历fast ,判断不符合该条件的(!=v),slow++; num[slow] == num[fast] 左右指针1.二分查找 * 有序,直接找中间的点,判断中间是否符合对应的题目逻辑,将中间点赋值为左边界或者右边界2.N sum 之和 * 一般是有序数组,然后左右相加,利用右边向内部移动数值减小和左边向内部移动数组变大3.反转字符串 * 终止条件是i>j4.回文串判断 * 判断条件s[i] == s[j]
leetcode 1170. 比较字符串最小字母出现频次
1170. 比较字符串最小字母出现频次 - 力扣(Leetcode) 后缀和(Prefix Sum)是一种常用于区间和计算的技巧。它通过预处理把一个数组的前缀和先计算出来,然后在查询某个区间的和时,只需要构造两个前缀和相减即可得到所求的区间和。 具体而言,假设有一个长度为 n 的整数数组 A,记 S[i] 为 A[0]+A[1]+…+A[i-1] 的前缀和,其中 0≤i<n。那么对于任何 0≤l≤r<n,A[l]+A[l+1]+…+A[r] = S[r+1]-S[l]。 在实际的应用中,如果需要进行多次区间和查询,可以利用后缀和技巧预处理出 A 数组的前缀和,并存储在一个新的数组 S 中。这样,对于任意区间 [l,] 查询,只需要计算 S[r+1]-S[l] 即可,时间复杂度为 O(1)。 不使用后缀和1234567891011121314151617181920212223242526272829303132func f(s string) int { cnt := 0 ch := 'z' for _, c...
什么是二进制的按位或和按位异或
按位或(bitwise OR)和按位异或(bitwise XOR)是两种二进制位运算。但是这两个概念很容易忘记或者混淆,今天我们就来加深一下印象吧! 按位或运算符(|)对两个二进制数的每一位都执行逻辑或操作,返回一个新的二进制数。其真值表如下 123456input bit a | input bit b | output ------------------------------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1 例如,执行 6 (二进制位 110) 和 3 (二进制位 011) 的按位或运算 会得到 7 (二进制位 111): 12345 110| 011----- 111 按位异或运算符(^)对两个二进制数的每一位都执行逻辑异或操作,返回一个新的二进制数。其真值表如下: 1234567input bit a | input bit b |...
leetcode 2460.对数组执行操作 2023.05.06每日一题
2460. 对数组执行操作 - 力扣(Leetcode) 思路直接模拟 Code第一版时间复杂度:O(n)空间复杂度:O(n) 123456789101112131415161718192021func applyOperations(nums []int) []int { var res []int res = make([]int, len(nums)) index := 0 // 第一次遍历 进行赋值操作 for i := 0; i < len(nums)-1; i++ { if nums[i] == nums[i+1] { nums[i] *= 2 nums[i+1] = 0 } } // 第二次遍历 将非0移动到前边 for i := 0; i < len(nums); i++ { if nums[i] != 0 { res[index] = nums[i] index++ } } return...
leetcode 28.找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣(Leetcode) 简单解法利用split 函数,判断是否能够拆分,如果 12345678910111213func strStr(haystack string, needle string) int { // 使用split 函数,如果存在needle,则会把其切分为至少两个元素的切片 splitList := strings.Split(haystack, needle) // 如果长度为1,且needle!=haystack 说明没找到匹配项,返回-1 if len(splitList)== 1 && needle!=haystack { return -1 } if len(splitList) > 1 { return len(splitList[0]) } // needle 在haystack的最开头,返回0 return 0} 123456789101112 func main() { ...
leetcode 104.二叉树的深度
个人网站:https://leiqicn.gitee.io/categories/leetcode/104. 二叉树的最大深度 - 力扣(Leetcode) 二叉树节点的深度指的是该节点到根节点的距离,也就是从根节点到该节点的路径长度。而二叉树节点的高度指的是该节点到其子树中最远叶子节点的距离,也就是该节点为根的子树的高度。 所以,可以将整个二叉树的高度定义为根节点的高度,也就是从根节点到最远叶子节点的距离。而整个二叉树的深度则没有固定的定义,通常是指二叉树中节点深度的最大值。 递归123456789101112131415func max (a, b int) int { if a > b { return a; } return b;}// 递归func maxdepth(root *treenode) int { if root == nil { return 0; } return max(maxdepth(root.left),...
leetcode 122买动态股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣(Leetcode) 每次只允许在一天买入一支股票,在之后某个时间卖出它。同时,你也可以选择不进行任何交易。 相比于第一题买卖股票的最佳时机(只能进行一次交易),这道题没有限制交易次数,因此我们应该从一个更灵活的角度去考虑如何进行交易。 下面是代码解释: 首先定义变量 sum 记录当前总利润。然后从第二个价格开始遍历,计算当日价格与前一天价格之差。如果价格上涨了,则将当前利润加上买卖差价,否则不进行操作。最后返回累计的总利润。这样做的原理在于,如果在 i 天买入,在 j 天卖出(j > i),我们可以等价于在 i+1、i+2……j-1、j 这些连续的日子里都进行了购入和卖出,而我们所需获得的利润即为这些差价的总和。因此,代码中只统计了所有价格差大于 0 的部分,而将其他价格差为负值的日子抛弃掉了。 12345678910func maxProfit(prices []int) int { var sum int for i := 1; i < len(prices); i++ { ...
leetcode 1091.二进制矩阵中的最短路径
1091. 二进制矩阵中的最短路径 - 力扣(Leetcode)DFS 超时版本: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950type point struct { x int y int}func shortestPathBinaryMatrix(grid [][]int) int { n := len(grid) if grid[0][0] == 1 || grid[n-1][n-1] == 1 { return -1 } res := 0 dirs := [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1,...
leetcode 53.最大子数和
Problem: 53. 最大子数组和 个人网站: https://leiqicn.gitee.io/categories/leetcode/[TOC] 思路 这里是经典的最大子序和的问题。我们可以很容易想到贪心的思想。就是如果前边的子序和是正数,则我们会把当前的数添加到前面的子序和上。否则,重新从当前位置开始子序和,丢弃前边的子序和。 解题方法 方法1 算法通过遍历整个数组nums,维护一个当前连续子序列的和count,同时记录一个最大值res。每遍历一个元素,就将其加入到count中,并比较它与之前计算过的最大子序和res的大小关系,如果大于res,则更新res。并且当count变成负数时,就说明需要重新寻找连续子序列,因此将count重置为0。 方法2 使用了类似动态规划的思想,用nums 数组代表dp数组; dp[i]含义:dp 表示最大子序列,i 代表当前位置的最大子序列的值;dp[i+1] = dp[i] +dp[i+1] ;max 初始化为第一个元素nums0; 遍历顺序,从idx = 1 开始遍历。 复杂度 时间复杂度: ...
go语言-回调函数(钩子)
在Go语言中,回调函数和钩子函数通常是使用函数类型作为参数传递给函数或方法,以便在特定事件发生时被调用。这种机制非常灵活,可以让你编写出高效的、可复用的代码。 以下是一个简单的例子,展示了如何使用回调函数来实现一个函数,当输出文本时会同时调用传入的回调函数: 123456789101112131415161718package mainimport ( "fmt")func printWithCallback(callback func(string)) { text := "Hello, world!" fmt.Println(text) callback(text)}func main() { callback := func(text string) { fmt.Printf("Printed: %s\n", text) } ...