niiish32x 's blog

原题链接:https://leetcode.cn/problems/global-and-local-inversions/本质是一个判断逆序对的问题 法1 推理全局倒置 全局内 逆序的数对局部倒置 相邻的逆序对因此局部倒置 一定是 全局倒置即 全局倒置 >= 局部倒置因此全局逆序对的产生方式 必须与局部逆序对相同即 存在所有逆序对必须都是相邻逆序 如果不是相邻逆序 则为false 1234567891011121314151617181920package mainfunc max(a, b int) int { if a > b { return a } return b}func isIdealPermutation(nums []int) bool { mx := nums[0] n := len(nums) for i:=2 ; i < n ; i++{ mx = max(mx,nums[i-2]) if mx > nums[i]{ ...

毕业设计时 我使用redis与token结合的方式来实现商城用户信息的验证 redis的部署采用了 主从复制 以及哨兵模式 保证了高可用性 最后实现的效果也很不错 现将其总结如下:为什么要采取主从复制+哨兵模式集群部署主要基于以下原因: 1.由于用户的验证信息存储于redis 只要redis宕机 那么所有用户将不可登录网页2.2.主从模式只能实现信息的备份 也就是说主机redis宕机后虽然从机会存储有主机的信息 但客户端与redis的连接无法自动从主机切换到从机 这是因为在springboot 的yml文件配置 客户端与redis以ip:端口的形式进行 绑定除非手动配置文件 3.想要实现redis自动主从切换 就要使用到哨兵 每个哨兵监视整个redis集群 只要有一个哨兵就能实现主从切换 但是因为哨兵存在宕机的可能所以哨兵也要集群化部署 redis集群部署架构示意图 redis集群 linux环境下的配置 如上图所示在conf/ 中创建以下配置文件: 3台用做redis服务器redis-6379.conf，redis-6380.conf，redis-6381.conf，3台用做哨 ...

我最开始是在1月份寒假的时候投简历 那时候考研成绩还悬而未决 加上网上又在散播焦虑 觉得自己也不能这样闲着 就在学redis\docker 这些想自己搞一个小项目出来 最好是能整出一个小网站来(当然这个目标在暑假的时候才实现 当时还提前买了服务器和域名)快到2月份时开始在实习僧上投简历 投的都是实习岗 其实这个时候投实习岗已经有些不合适了 因为那时我已经马上要大四下了 自然也吃了比较多的闭门羹 记的刚开始几天实习僧上的回复都是已查看 然后就没了回复 又过了几天出现了几个不合适 可能是因为我简历包装的不错 有几个hr 问了我一下2022应届 还是2023应届 我说是22的 然后就婉拒说抱歉只要23应届的(好像是阿里的一个hr) 这之后就是一直等待 然后一边准备项目学学springboot那套 一边准备复试然后就在一个下午收到了 天翼阅读的面试电话 当是接到电话的时候我都有些蒙 那边的人说我的简历经过了二轮 才到他的手上 不得不说当时真的是运气好 但也是真的卷 当时真的是有些没反应过来 匆匆忙忙的自我介绍后 面试官就就开始提问了 可能当时真的蛮紧张有几个基础的问题都答的不是很好 我硬憋了几 ...

原题链接:https://leetcode.cn/problems/cinema-seat-allocation/这题首先要注意到的一个信息是 1 <= n <= 10^9 即n 范围为10^9 也就是说 即使O(n) 也不行但是有注意到 1 <= reservedSeats.length <= min(10*n, 10^4) 即要占座位的数量只有10^4 是一个比较小的数 因此可以考虑逆向求解 求出最大正确答案数 2 * n(关于正确答案也比较简单 因为根据题意最多每行只能放两个家庭 )然后就是可以进行二进制优化 用一个二进制数代表每行的座位排列 1 表示该位已经被占 0 表示空位 将占座信息记录到hash表中 然后反向排除即可 12345678910111213141516171819class Solution: def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int: d = defaultd ...

sort.Search (二分)sort.Search 需要自己实现接口 也比较简单当然有很多实现方式 以下所展示的方式 是sort.SearchInts() 等中的实现方式 12345678910111213141516package mainimport ( "fmt" "sort")func main() { a := []int{2, 4, 6} // 第一个参数为数组长度 第二个实现函数 id := sort.Search(len(a), func(i int) bool { return a[i] >= 1 }) fmt.Println(id)} 当然也可以更简单一些直接调用sort.SearchInts()/ sort.SearchStrings()如下 1234567891011121314151617181920212223242526272829package mainimport ( "fmt" "sort" ...

法1: 记忆化搜索简而言之 就是把已经搜索的值记录到一个hash表 如果已经搜索过 那么就不用继续往下搜索了 123456789101112131415161718192021222324252627282930MOD = 10 ** 9 + 7class Solution: def numberOfWays(self, startPos: int, endPos: int, k: int) -> int: # hash 存储记忆化的中间结果 memo = defaultdict(int) # 记忆化搜索 # 当前距离为cur 已经走了d步 的方案数 # 写python 记忆化搜索一定要加个@cache 不然就会超时 @cache def dfs(cur: int, d: int) -> int: # 剪枝 剩余步数小于 终点起点之间的距离则方案肯定不行 if k - d < abs(endPos - cur): ...

原题链接:https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/蛮综合的一道题尤其是边界情况的条件处理比较巧妙当前bst判断不成立时 将当前子树的最小值设置为inf 最大值设置-inf返回则接下来任意 包含该子树的判断 均不会满足 左子树最大值<node.val<右子树最小值 这一条件 即不会更新ans 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556# 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: ...

原题链接:https://leetcode.cn/problems/removing-stars-from-a-string/这题虽然披着字符串的外衣 但其实是栈的应用关键在于相邻两个字 然后是消除 如果没有提取好特征直接用遍历去写那这题就十分麻烦了 1234567891011121314class Solution: def removeStars(self, s: str) -> str: stk = [] n = len(s) for i in range(n): # 题目保证一定给有解所以无需判空 if s[i] == "*": stk.pop() else: stk.append(s[i]) return ''.join(stk) leetcode 包括很多算法题都是在原题基础上 或者一些经典算法的基础上改编而来 周赛的时 ...

区间问题统计一个区间内的数据 如区间 (l,r) 内 的点个数 前缀和当数组不发生改变时 即区间内的点数 不发生变动 只不过查询的时候是换了区间查询 那么简单的方法使用前缀和 不仅代码简单 而且可以使得每次查询都做到O(1) 使用树状数组 和 线段树 也可以但复杂度太高了 尤其是线段树 不到万不得已 不要使用 12345678910111213141516171819202122# 一维度非常简单 关键是要想到s[i] = a[1] + a[2] + .... a[i]# 查询区间 (l,r) 内点的数量 即a[l] + a[l+1] + ... + a[r] = s[r] - s[l-1]# 二维s[i,j] = 第i行 第j列 左上角所有元素的和"""以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]"""# 记数组元素为c 二维前缀和 的初始化为for i in range(1,n+ ...

主要思路是辗转相除法 1234int gcd(int a, int b){ return b != 0 ? gcd(b, a % b) : a;} 一个常考性质 一个数可以整除所有数 y1 y2 ..% x等价这个数 可以整除所有数的最大公约数 y1 y2 …(的公约数) % x