niiish32x 's blog

难度值:4统计定界子数组的数目 滑动窗口其实是属于双指针的一种 但这种题目特征更强难度值:3美观的花束水果成篮 例1美观的花束 原题链接:https://leetcode.cn/problems/1GxJYY/ 12345678910111213141516171819202122const MOD = 1e9 + 7func beautifulBouquet(flowers []int, cnt int) int { h := map[int]int{} left := 0 ans := 0 for right,x := range flowers{ h[x]++ for h[x] > cnt{ y := flowers[left] h[y]-- if h[y] == 0{ delete(h,y) } left+ ...

括号类各种括号题 基本上算是栈的经典应用了 难度值1:删除最外层的括号难度值3: 括号的分数移除无效的括号 例1括号的分数原题链接https://leetcode.cn/problems/score-of-parentheses/ 12345678910111213141516171819202122232425package mainfunc max(a, b int) int { if a > b { return a } return b}func scoreOfParentheses(s string) int { stk := make([]int, 1) for _, ch := range s { if ch == '(' { stk = append(stk, 0) } else { v := max(1, stk[len(stk)-1]*2) stk = stk[:len(stk)-1] stk[len(stk)-1] += v ...

很早之前报名的一个课程 但一直没时间(其实是忘了)去完成现在刚好又开始学了go 也差不多又要到这个阶段 就算是一个flag 这次要把所有题都完成 1 蛇形矩阵原题链接:https://www.acwing.com/problem/content/758/模拟 但却是有技巧的模拟主要就是转向条件那里 如果没有做过一次真的在现场很容易被绕进去 123456789101112131415161718192021222324252627282930313233343536373839package mainimport ( "fmt")const N, M int = 110, 110func main() { n, m := 0, 0 fmt.Scanf("%d %d", &n, &m) var g [N][M]int // 右 下 左 上 dx := [...]int{0, 1, 0, -1} dy := [...]int{1, 0, -1, 0 ...

字符串哈希思路非常简单 但具体实现细节比较非常麻烦C++等有unsigned long long 类型的语言实现起来是最容易的 因为不用取模 靠unsigned long long自然溢出 就能得出正确的结果 而其他语言在这个取模上要注意很多当然由于字符串哈希这个算法本身泛用性很好 而且可以简化很多问题 背一背相关细节还是值得的下面就以python为例给出模板 以及正确的模值 1234567891011121314# 这个MOD 值 可以保证最终答案是正确的MOD = 10**13 + 7P = 131n = len(s)h = (n + 1) * [0]p = (n + 1) * [0]# 这里一定要注意 这个初值一定要给 !!!p[0] = 1for i in range(1,n + 1): h[i] = (h[i - 1] * P % MOD + ord(s[i])) % MOD p[i] = p[i - 1] * P % MODdef get(l,r): return (h[r] - h[l - 1] * p[r - l + 1] % MOD) % MOD ...

并查集模板12345678# 每个点初始化的时候指向自己p = list(range(n))def find(x): # 当前值并不指向其根 if x != p[x]: # 不断递归直到找到自己的根 p[x] = find(p[x]) return p[x] 经典例题总结难度值:1 对于模板的基本应用合并集合连通块内点的数量格子游戏 (二维并查集) 难度值:2 结合一些基本场景省份数量冗余链接连通网络的操作次数难度值:3 对实际问题进行解读转换 但还只涉及并查集这一种算法搭配购买 (并查集结合01背包问题)好的路径数量删除操作后的最大字段和 例1acwing836 合并集合 模板的直接应用 难度值: 1原题链接：https://www.acwing.com/problem/content/description/838/ 123456789101112131415161718192021n,m = map(int,input().split())p = list(range(n + 1))def find(x): if p[x]!=x: p[x] = find( ...

原题链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/ 首先明确题目的意思就是排序后的序列 与 将数组分隔后的再将每一个小分组排序后拼接的顺序是一样的也就是分隔的小分组内的数与排序后相应位置所出现的数频率一定要是一样的接下来可以用 贪心 来思考如果排序后的数与分割后的小数组的数是全部对应的话 那么数组划分时必然需要先满足左边 因为如果左边的数都对应不上的话 那么整体必然无法对应由此可得 法1: 哈希同时遍历当前数组 以及排序后的数组以hash表记录当前区间出现的 元素:出现频率在原数组出现则将频率+1 在排序数组出现则-1当频率恰好为0时 删除这个键值当整个hash表长度为0时 此时的划分应恰好为符合条件的最短序列长度 将 ans + 1 123456789101112131415class Solution: def maxChunksToSorted(self, arr: List[int]) -> int: # 元素 -> 出现频次 d = defaultdict ...

原题链接:https://leetcode.cn/problems/sort-integers-by-the-power-value/ 法1 暴搜基础暴搜的方式 就是按照题意模拟的即可 123456789101112131415161718class Solution: def getKth(self, lo: int, hi: int, k: int) -> int: ans = [] for x in range(lo,hi + 1): w = 0 t = x while x!=1: w = w + 1 if x%2 == 0: x//=2 else: x = x * 3 + 1 ans.append([w,t]) res = sorted(ans,key=la ...

原题链接:https://leetcode.cn/problems/trim-a-binary-search-tree/比较好的一道递归后序遍历的思路 先处理好下面的结点然后依次返回结果处理方式 按照bst的定义1.如果node为空 直接返回2.如果右子树为空 直接返回左子树1.如果右子树非空 则将左子树接在右子树的最左侧 然后返回右子树 12345678910111213141516171819202122232425262728293031# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> ...

原卷地址:https://www.nowcoder.com/test/39959332/summary T1:比较基础的一题 只需要知道只有2的幂对应二进制肯定只有一个1即可 123class Solution: def minCnt(self , s: str) -> int: return s.count("1") - 1 T2:贪心+二分先对数组进行排序每次将最后一个数即最大的数减去x 然后再通过二分寻找该数减去x后的合适位置 并将其放入排序是nlogn 二分 klogn总复杂度 (n+k)logn 123456789101112131415from typing import Listfrom bisect import bisect_leftclass Solution: def minMax(self, a: List[int], k: int, x: int) -> int: a.sort() r = len(a) - 1 while k: k = ...

原题链接:https://leetcode.cn/problems/maximum-rows-covered-by-columns/枚举题 基础做法很简单 枚举出所有可选列的组合 模拟题意操作一遍 然后返回结果即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution: """ 先枚举出出所有列==cols的可能组合 然后再按照枚举结果 将所有列覆盖 然后返回结果 """ def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int: m = len(matrix) n = len(matrix[0]) h = [] # 当前所选择的列 所选的列数总和 def dfs(c ...