niiish32x 's blog

trie树 又名字典树存储单词的集合 在一些特定的问题里 非常有用 比如寻找相同前缀的单词数量等通常附加上题目中有特别强调字符都是小写字母或者大写字母时 就会用到tire树 核心数据结构就是一个son[p][u]其中第一维 表示这个当前字母所在的位置 1p = son[p][u] =idx 第二维 表示这个位置所存储的单词 核心操作 1234567891011121314151617181920212223242526272829# 插入操作def insert(s: str): p = 0 for i in range(len(s)): # 将字母映射成数字 u = ord(s[i]) - ord("a") # 如果当前单词结尾的这个字母不存在 # 则创建新的枝条 if not son[p][u]: # 这里用global 是因为 idx通常会定义成全局的 # 如果用是在一个class内 比如力扣的那种情况 其实nonlocal也可以 global i ...

原题链接：https://leetcode.cn/problems/longest-nice-subarray/这题关键在于想到:1.或运算(|) 可以保存一段连续的数中 互相与运算(&)的结果比如 如果要判断 001 与 101 110相与是否为0其实就是看 001 的1的位置 与 101 110中1的位置是否重合就等价于看001中1的位置是否与 111中1的位置是否重合2.异或运算可以还原或运算的结果或运算的过程其实就是保留1的过程 将之前同样的数与当前与结果按顺序异或相当于不断将保留的1 进行还原 12345678910111213141516171819class Solution: def longestNiceSubarray(self, nums: List[int]) -> int: n = len(nums) if n == 1: return 1 l, r = 0, 1 w = nums[l] ans = 1 while r < n: ...

原题链接:https://leetcode.cn/problems/find-duplicate-subtrees/对于每一种子树以一个三元组进行编号(node.val,l,r) —> (node,idx)node.val为节点的值 l,r 为左右子树的编号node 为节点 idx为该节点的编号这样当我们每发现一种新的子树 那么就给这个子树编号 否则就将该子树 加入结果 与相同的共用一个编号 1234567891011121314151617181920212223242526272829303132333435363738# 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 findDuplicateSubtrees(s ...

原题链接:https://leetcode.cn/problems/jump-game-iv/这题基本思路比较BFS 每次扩展 i-1,i+1,值与arr[i]相同的点但这题数据范围为5 * 10^4 如果arr[i]相等的边有m条 那么由于是一个无向图 那么这样的遍历的将会n^2 次 所以这一步是优化的关键优化的思路是 是使用bfs 求最短路的路径 bfs求最短路只有第一次更新时求出的值是最小值 所以当你一次扩展值均为v的点后 直接删除v即可 下一次不必再遍历 即对于相同值得所有点只走一遍 1234567891011121314151617181920212223242526272829303132333435363738class Solution: def minJumps(self, arr: List[int]) -> int: # 先记录所有与值相同点的下标 h = defaultdict(list) for i, v in enumerate(arr): h[v].append(i) ...

对于一个网站来说 用户登录为第一步 也是最关键的步骤之一 用户登录的过程中会提交自己的用户名以及密码与后台数据库进行核验 然而随着现在网络的发展 网络安全问题也日益突出 保证用户登录过程中的信息安全至关重要 我在我的毕业设计关于这个问题 也思考了许多解决办法 现在将其总结于此 用户的登录流程首先我们分析仪一下用户最基本的登录流程及其可能存在的问题 及相应的解决方案 : 1.用户进入登录页面输入自己的用户名和密码 这个过程可能存在的问题的是 恶意的密码尝试 比如有脚本恶意尝试密码 企图登录系统  解决这种问题的方法是采用验证码 同时将验证码存入redis中还可以设置过期时间进一步增强安全性 2前端获取用户输入将其传到后端  在前端向后端传递密码过程的过程 通常是将密码信息加在http post请求中发送给后端 而这个post请求是可以抓包 解决这种问题的方法是在将密码传输 如使用前端使用rsa算法用公钥加密后 再将加密后的密码传输至后端用私钥解密 3后端调用相应service 进行校验 返回结果给前端 4网页存储用户的登录状态 从而用户可以自己的身份信息访问网页 ...

个人认为很好的一道面试题虽然题目简单但如果直接暴搜的话应该就直接回家等通知了有好几种做法面试的时候都可以说一下 法1: 二分排序后 遍历数组 二分查找是否存在二倍的值复杂度:排序 nlogn 二分 n * lognO(nlogn) 1234567891011121314151617from typing import Listfrom bisect import *class Solution: def checkIfExist(self, arr: List[int]) -> bool: arr.sort() n = len(arr) for i in range(n): v = arr[i] index = bisect_left(arr,2*v) if index >= n or index == i: continue if 2*v == arr[index]: retu ...

拓扑排序 代码实现思路: 1. 入队所有入度为0 的点 2. bfs 取出队头t 枚举t的所有出边 t->j 3. 删掉 t->j 即让 d[j]– (d[j] j的入度) 4. if d[j] == 0 -> 说明j之前所有点均以排好序 -> j 入队 5. 如果图中存在环则无法全部入队 反之则都可以入队 先看一个基础点的题leetcode 210 原题链接:https://leetcode.cn/problems/course-schedule-ii/算是一道经典题 12345678910111213141516171819202122232425262728class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: n = numCourses de ...

2022.2 - 2022.4 天翼阅读文化动笔时已经是已经快要开学 而我也将马上进入下一个阶段 研究生的学习了 也是时候为之前的实习做一个记录与总结 拿到offer的过程比较意外 但也比较幸运 记录于 面试记录2022-2天翼阅读文化公司是在武林广场 杭州市中心的位置 当时三号线还没开 只能靠193 最开始采取的策略是 一开始想到解决办法是 周一早上193路到公司 然后工作日住旁边宾馆的 然后最后一个工作日晚上回学校 住宾馆虽然比较舒服也确实很方便 但感觉花销还是太大了 而且也和一个一直有联系高中同学交流 刚好他也在实习在九堡那里租了一间房子或者说鸽笼比较合适一些 然后就搬到他那边 这在九堡生活的这段经历也算是迷茫与辛苦交织中却也带着一些快乐 毕竟能有一个分享生活的人在一起感觉就会好很多 住的地方离地铁口大概15分钟左右的路 但是从九堡到武林广场算上出入站的等车的时间大概要花上个40分钟左右甚至更多 我是9.30–5.30当然这是在没有特殊情况不需要加班处理的情况下 看上去8小时工作制蛮不错 但算上上下班的时间 还有早晚饭 以及洗漱的时间 我基本每天早上要7.40左右起来才能比较 ...

python 的语法笔记使用python 实现字典与列表的嵌套类似于C++中 12vector<vector<int>>h1;unordered_map<int,vector<int>>h2; python 虽然不能像C++ 这样实现无限套娃 也基本足够 即可可实现 int:list 即一个整数 或 字符/字符串 对应的列表 在建图的时候 会非常方便 但在构造题中还是直接上C++ 的 unordered_map 会舒服一些 12345678"""这个是需要引入的 如果是写一些oj 或者 kickstart 就要注意一下但在leetcode中 整个collections 集合都是 自动帮我们引入好的直接 而且还是这种 from import的形式 所以直接用defaultdict就OK了"""from collections import defaultdicth = defaultdict(list)h[0].append(0)h[1].append(0) pyth ...

原题链接:https://leetcode.cn/problems/factorial-trailing-zeroes/ 想要一个数的结尾多加一个0 最直观的想法就是 * 10 而10 又可以拆解为 2 * 5 也就是说每多一对 2 * 5 就会多一个10 就会多一个0 所以题目转化求 每一个数中的2和5 的数量 有多少对2 5 则结果在就会尾随多少个0进一步优化-> 由于题目求的是0-n的中数的5 那么有5 就一定会有2 也就是说 只要算出5的个数即可 12345678910class Solution: def trailingZeroes(self, n: int) -> int: ans = 0 for i in range(5,n + 1,5): while i % 5 == 0: i//=5 ans = ans + 1 return ans 进一步优化-> 由于0-n中 可能存在前面的数是后面的数的因子 ...