要思考 当超出数组的时候怎么办 这时候有个办法 就是改变数组啊啊啊啊啊 如果解决不了问题 就解决掉提出问题的人 哨兵节点类似于
找不到规律就完了 优化的点在于 拼接S的时候可以考虑使用[]byte
完美二叉树 就用性质就可以解决了 抓到切片里 根据索引干 比较废空间
太猛了 用递归 记得使用别把题目让我链上的next忘记了呀 这个很像mysql里的数据结构了
递归 递归又忘记了 x.next = travel()
虽然我写的丑 但是运行很快啊
直接修改原数组 int[][] matrix 来记录距离和标志是否访问的
Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队；
Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！【 看见很多人说自己的 BFS 超时了，坑就在这里哈哈哈
用map很容易超时 那么我们就用新的res数组 如果res数组值为0 说明还没有被赋值过
很重要 有时候 1.可以修改元数组的值 达到判断的目的
很重要 有时候 2.可以弄一个新的数组 利用新数组和元素组的差异 来判断 哪些已经被赋值过了
res[x][y] == 0 和 mat[x][y] != 0 用来区分 那些没有被修改过的
分类讨论
如果k==0 那么就是首部
如果只有一个元素 那么k为奇数的时候就是空栈 -1 k是偶数的时候 就是这个元素
如果 k 比 数组长度短的话 例如有6个 k==4 实际上 通过枚举可以发现 可以取到的数是 1 2 3 和 5
动态规划
从左上角开始 遍历左边和上边
从右下角开始 遍历右边和下边
优化之后的回溯算法 提高了很多很多
回溯多数情况需要还原
原来打算用map来判断 是否已经加入了
在这里传递的时候 是通过构造了新的切片来传递的 可能会耗时
这里传递的时候 永远认为前一个已经被干完了 通过swap交换的形式
利用交换 来把当前的放到index为0 的位置上
回溯完成后 记得还原回来 否则会影响后面的运算
由于ans是切片引用类型 所以递归的时候已经被加入过了 回溯完成后 记得把ans去掉 否则会影响后面的运算
根据bits 位集合来做 既然每个字母都有2种情况 那么3个字母 就会有2的三次方种排列情况
dp数组代表当前打劫店家的最大金额 这个金额是 2种情况种的最大值
1.这家打劫的钱+dp[i-2]
2.这家不打劫 也就是dp[i-1]
动态规划的本质 选择 与 不选择
动态规划 就是一层一层求 写出状态转移方程 可以优化的点在于空间上只需要这一层和上一层
n&(n-1) 为了去掉最后一位1 如果只有一位为1 n&(n-1) 就变成0了
-n 是反码+1 所以 n和-n与运算的结果等于n的话就说明只有一个1
//位运算 原来的数字不动 每次通过1左移的方式来判断 原数字那一位是不是1 如果是1 再通过左移的方式更新res
func reverseBits1(num uint32) uint32 {
var res uint32
for i := 0; i < 32; i++ {
if (num & (1 << i)) != 0 {
res |= 1 << (31 - i)
}
}
return res
}//位运算 n>> 可能会提前结束
func reverseBits2(num uint32) uint32 {
var res uint32
for i := 0; i < 32; i++ {
if num&1 != 0 {
res |= 1 << (31 - i)
}
num >>= 1
if num == 0 {
break
}
}
return res
}//拆分 分治 最后连接
func reverseBits(num uint32) uint32 {
var concact func(num1, num2 uint32, chai int) uint32
concact = func(num1, num2 uint32, chai int) uint32 {
//默认传递进来num1是原数组左边的 num2是原数组右边的 现在连接的时候要颠倒一下位置 那么就通过左移<<来达到
return num2<<chai | num1
}
var travel func(num uint32, chai int) uint32
travel = func(num uint32, chai int) uint32 {
if chai == 0 {
return num
}
//通过左移获取左半部分的
num1 := travel(num>>chai, chai/2)
//通过笨比方法获取右半部分的
var temp uint32
for i := 0; i < chai; i++ {
temp = temp | ((num & 1) << i)
num = num >> 1
}
num2 := travel(temp, chai/2)
return concact(num1, num2, chai)
}
return travel(num, 16)
}动态规划 dp数组的定义很重要 dp[x]=上到x台阶的花费=dp[x-1]+cost(x-1)或者dp[x-2]+cost(x-2)
dp的特征在于 不走回头路 之前计算过的dp不会再被修改
动态规划 dp数组的定义很重要 dp[i] = max{ dp[i-1]+nums[i] , nums[i] }
空间优化 只使用前一个和这一个 dp[i]定义为 前i个包含i的最大连续子序列和的值
用visited 复杂了 利用hash表的去重特性
降低空间复杂度 o(2*n)=o(n) 只要是常数次遍历n 都可以视为o(n)
123 456 首当其冲的 解决的就是溢出的问题 其次 解决如何转换的问题
转换的巧妙就在于 '7' 的 7 = '7'-'0'
两字符串相加问题
从最后一位开始加起
百分号别忘记了!!!
防止头部丢了
模拟乘法 记一下进位add 叠加一下cur
补0
防止头部丢了
和res相加
只排序k个 其他的不管了
//用堆排序
//归并排序 先拆再排
//快速排序 先拆再拆再排 找到pivot 把大于的放到它后面 把小于的放到它前面 然后递归排序
//信封问题 套娃
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
if envelopes[i][0] != envelopes[j][0] {
return envelopes[i][0] < envelopes[j][0]
}
return envelopes[i][1] > envelopes[j][1]
})
answer := make([]int, 0)
for _, envelope := range envelopes {
//巧妙二分 如果在内部 就更新 防止扩大
ints := sort.SearchInts(answer, envelope[1])
if ints >= len(answer) {
answer = append(answer, envelope[1])
} else {
//如果在外部 就说明应该扩大
answer[ints] = envelope[1]
}
}
return len(answer)
}//动态规划 最长公共子序列
func longestCommonSubsequence(text1 string, text2 string) int {
dp := make([][]int, len(text2)+1, len(text2)+1)
for i := 0; i < len(dp); i++ {
dp[i] = make([]int, len(text1)+1, len(text1)+1)
}
var max func(a, b int) int
max = func(a, b int) int {
if a > b {
return a
}
return b
}
for i := 1; i < len(dp); i++ {
for j := 1; j < len(dp[i]); j++ {
if text2[i-1] == text1[j-1] {
//这里很重要 发现了规律了吗 和背包问题类似 如果要选择他 那么就要扣掉当前的行和列 防止重复
dp[i][j] = dp[i-1][j-1] + 1
} else {
//不选择
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[len(dp)-1][len(dp[len(dp)-1])-1]
}//递归 超时 最短距离
func minDistance1(word1 string, word2 string) int {
res := math.MaxInt
var travel func(cost int, index int, word string)
travel = func(cost int, index int, word string) {
if index == len(word2) {
cost += len(word)
if res > cost {
res = cost
}
return
}
if len(word) == 0 {
//插入
travel(cost+1, index+1, word)
} else if word[0] == word2[index] {
//相等
travel(cost, index+1, word[1:])
} else {
//删除
travel(cost+1, index, word[1:])
//插入
travel(cost+1, index+1, word)
//替换
travel(cost+1, index+1, word[1:])
}
}
travel(0, 0, word1)
return res
}
//这种题目有一点困难啊 完全不懂 动态规划
func minDistance(word1 string, word2 string) int {
dp := make([][]int, len(word1)+1, len(word1)+1)
for i := 0; i < len(dp); i++ {
dp[i] = make([]int, len(word2)+1, len(word2)+1)
}
var min func(a, b, c int) int
min = func(a, b, c int) int {
return int(math.Min(float64(a), math.Min(float64(b), float64(c))))
}
for i := 0; i < len(dp); i++ {
dp[i][0] = i
}
for i := 0; i < len(dp[0]); i++ {
dp[0][i] = i
}
for i := 1; i < len(dp); i++ {
for j := 1; j < len(dp[i]); j++ {
if word1[i-1] == word2[j-1] {
//相等的时候就只需要知道前面是什么就好
dp[i][j] = dp[i-1][j-1]
} else {
//不等的时候 得需要找找
//[i-1][j] 是删除 [i-1][j-1]是替换 [i][j-1]是新增
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
}
}
}
return dp[len(word1)][len(word2)]
}煎饼排序
如果最大值本身就在数组的末尾 就不管他
否则 更新res 翻转数组 把最大值甩到最上面
更新res 翻转数组 把最大值甩到当前数组的最下面
开始递归考虑最后上一层的烧饼
前缀和
前缀和 优化 实际上 preSum[i] = preSum[i]-preSum[0]
前缀和 哈希优化 preSum[i]-preSum[j] == k
只要是等式就可以尝试使用哈希表来代替
筛数法还是超时
筛数法这里有个优化细节 就是可以从i平方开始筛 因为之前的应该都被筛过了 例如当2位质数的时候 6被筛过了 而3位质数的时候 6已经筛过了 所以还是从9开始筛把
没什么事儿就用[]bool 数组来代替hashmap
我觉得应该是因为数组在内存中线性连续的.所以用接近常量v-a的定位算法速度最快.这里的算法效率是o(1).
而map在内存中存储并不是线性连续的,而且要经过hash计算index所以就慢了一些.虽然hash也是o(1)的效率但是在计算步骤上要比v-a复杂, 所以速度上不如.
超级次方
快速幂运算 如何防止溢出 part1和part2可以看作是原数字的拆分 所以原数字的mod 肯定是等于part的mod 和part2的mod的mod 然后在 mod1337
a*b %1337 = a%1337 * b%1337 %1337 所以我认为实际上 part1 已经是a %1337的结果了
超级次方
快速幂 a的b次方 如果b是偶数 就对半拆 如果b是奇数 就拆成 1和b-1
接雨水问题
优化有点不到位呀 就动态更新了一下 从左往右移动的时候 如果当前的比左边的大 不仅要跳过去 还要把左边的最大值更新一下
如果当前的索引超过了右边最大值的索引 那右边就重新开始找当前右边的最大值
//接雨水问题
//备忘录优化
//要求左边的最大值 那么就是索引-1的左边最大值和左边的数字比较 谁大就是目前索引的左边最大值!!!!
func trap(height []int) int {
res := 0
var min func(a, b int) int
min = func(a, b int) int {
if a < b {
return a
}
return b
}
var max func(a, b int) int
max = func(a, b int) int {
if a > b {
return a
}
return b
}
left := make([]int, len(height), len(height))
right := make([]int, len(height), len(height))
left[0] = height[0]
right[len(height)-1] = height[len(height)-1]
//好补! 这里绝了 类似于动态规划了 要求左边的最大值 那么就是索引-1的左边最大值和左边的数字比较 谁大就是目前索引的左边最大值
for i := 1; i < len(left); i++ {
left[i] = max(height[i], left[i-1])
}
for i := len(right) - 2; i >= 0; i-- {
right[i] = max(height[i], right[i+1])
}
for i := 1; i < len(height)-1; i++ {
res += min(left[i], right[i]) - height[i]
}
return res
}删除有序数组的重复元素 使用o1 复杂度
双指针 注意替换规则 如果fast和slow不等 那么就slow+1 跃迁到未知的位置 然后把fast的值拷贝到slow中 然后不论如何fast都要++
跳跃游戏
贪心思路
初始化 最开始能跳跃的最远距离是0 后面更新
//跳跃游戏Ⅱ 动态规划 +备忘录
//跳跃游戏Ⅱ 贪心 贪心的性质是 每一步都能达到局部的最优 到最后就能打到全局的最优
//判断谁更有潜力
//赋值的时候不能赋跳过去的最大值 而应该赋当前的索引值
//思路跟不上 构造回文 使用的是先拿到一半 然后再去添加构造
100001===>先拿到100====>翻转001===>拼接100001
//动态规划 01背包问题
//循环的和之前的做比较 比谁大 这里很烦的地方在于 索引老是搞错呀
//贪心思想 区间重叠问题
func eraseOverlapIntervals(intervals [][]int) int {
res := 0
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
for i := 0; i < len(intervals)-1; {
j := i + 1
//这里非常关键哈 如果判定重复了 就继续下一个判定
for j < len(intervals) && intervals[i][1] > intervals[j][0] {
res++
j++
}
//最后把j赋值给i 这样实际上复杂度还是o(n)
i = j
}
return res
}