Python 真难写啊
7.2199. 二叉树的右视图 - 力扣(LeetCode)广度优先 层序遍历后每层取最右边的结点储存
时间复杂度 : 遍历所有子节点 O(N)
空间复杂度 : 最坏情况下包含一层的所有节点O(n/2);最好情况下(链表树)只包含一个节点O(1)
1234567891011121314class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] q = deque([root]) res = [] while q: n = len(q) res.append(q[0].val) for _ in range(n): node = q.popleft() if node.right: q.append(node.right ...
8.4240. 搜索二维矩阵 II - 力扣(LeetCode)题目说要高效的算法 虽然我写的算法能过但是用了27ms 别人的只用了6ms
12345678910111213141516171819class Solution { public boolean searchMatrix(int[][] matrix, int target) { return searchMatrix(matrix,target,new int[]{0,0},matrix.length-1,matrix[0].length-1); } boolean searchMatrix(int[][] matrix, int target, int[]index, int row, int col) { if(index[0]==col&&index[1]==row) return matrix[row][col]==target; if(index[0]>col||ind ...
8.11面试题 01.04. 回文排列 - 力扣(LeetCode)题目跟常见的那种判断回文不太一样 还有注意字符范围
123456789101112131415161718class Solution { public boolean canPermutePalindrome(String s) { char[] chars = s.toCharArray(); int n = chars.length; int[] ch = new int[128]; for (int i = 0; i < n; i++) { ch[chars[i]]++; } boolean flag = false; for (int i = 0; i < 128; i++) { int num = ch[i]; if (num%2 == 0) continue; ...
7.28374. 猜数字大小 - 力扣(LeetCode)没注意到越界问题 用二分的另一种写法可以避免越界不用long
123456789101112131415public class Solution extends GuessGame { public int guessNumber(int n) { int ans = 1+(n-1)/2; // 注意此处取中间值写法 int res,left=1,right=n; while(true) { res = guess(ans); if(res == 0) break; if(res == -1) { right=ans-1; }else{ left=ans+1; }ans= left+(right-left) /2 ; } ...
(找不到好看的封面图了)
7.21735. 小行星碰撞 - 力扣(LeetCode)REVIEW
本来以为是简简单单的栈 结果条件判断一多就错错错错错 代码写完也很臃肿 我该去好好学一下各种数据结构的函数了
1234567891011121314151617181920212223242526272829class Solution { public int[] asteroidCollision(int[] asteroids) { Deque<Integer> stack = new ArrayDeque<>(),stack2 = new ArrayDeque<>(); for(int num:asteroids){ if(stack.isEmpty()){ if(num>0) stack.push(num); else stack2.push(num); ...
1 过滤1000个违禁词消耗内存对比前言此处假设违禁词都是由小写字母组成的单词 实际上违禁词的字肯定不止26个小写字母, 我目前想到的是用Set存储每个指针 但不管如何, 实际情况中布隆过滤器节省的内存肯定远不止下面计算所得
前缀树(Trie)的内存消耗前缀树的每个节点通常包含以下内容:
一个固定大小的数组(假设只有小写字母,每个节点有26个指针)
一个布尔值或其他标记来指示该节点是否是一个完整单词
假设每个指针占用8个字节(64位系统)和每个布尔值占用1个字节:
每个节点的内存消耗:
数组:26 * 8 字节 = 208 字节
布尔值:1 字节
总计:209 字节
节点数估算: 对于一个前缀树,每个词条大约创建的节点数取决于树内对应的公共前缀的长度。这里取最好情况即1000个词条只需要创建1000+n(单词长度)个节点(即所有单词只有最后一个字母不一样) 。
总内存消耗:
1000+n 个节点 * 209 字节 ≈ 209,000 字节 ≈ 209 KB
布隆过滤器的内存消耗布隆过滤器的内存消耗主要取决于位数组的大小和哈希函数的数量。假设使用合适的哈希函数数 ...
7.1442. 接雨水 - 力扣(LeetCode)REVIEW
双指针dp 说真的想不到能这样dp 左dp一遍最高右遍历一遍最高
12345678910class Solution { public int trap(int[] height) { int []dpL=new int[height.length],dpR = new int[height.length]; int ans = 0;dpL[0] = height[0];dpR[height.length-1] = height[height.length-1]; for(int i=1;i<height.length;i++) dpL[i]=Math.max(dpL[i-1],height[i]); for(int i=height.length-2;i>=0;i--) dpR[i]=Math.max(dpR[i+1],height[i]); for(int i=0;i<height.length;i++) ...
7.7433. 最小基因变化 - 力扣(LeetCode)图的广度优先遍历的题大多都是用队列存储每轮搜索到的结点,再用一个visited记录已经搜索过的结点 理解了其实思路都差不多
123456789101112131415161718192021222324252627282930313233343536class Solution { public int minMutation(String startGene, String endGene, String[] bank) { if (startGene.equals(endGene)) {return 0;} Set<String> visited = new HashSet<String>(); Set<String> bankSet = new HashSet<String>(Arrays.asList(bank)); if (!bankSet.contains(endGen ...
Mybatis-Plus 的默认 Insert 方法不支持 SQLite 主键id自增后返回id写毕设项目的时候遇到的 需要插入一条新的记录然后返回新记录的主键id 这个id是自增的
然后发现Mybatis-Plus的默认Insert方法不支持这个操作 可以插入但是不能返回自增后的id
后来用事务解决了:本来用SQLite就是考虑到项目的数据量较小才用的 所以直接用串行化在插入操作之后查询SELECT last_insert_rowid()获取刚刚插入的记录的id字段
上网查了一下似乎改一下sqlite-jdbc的版本就能解决?不过我没试过:sqlite-jdbc版本导致插入数据自增id问题
CentOS SQLite临时文件溢出
明天着急检查 先用 rm -rf /tmp/sqlite-jdbc-tmp* 指令删了再说 之后再找溢出原因
力扣刷题bug117. 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode)
碰到个bug 力扣给的Node的构造函数是这样的:
123456789"""# Definition fo ...
6.28199. 二叉树的右视图 - 力扣(LeetCode)层序遍历后每层取最右边的结点储存
1234567891011121314151617class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<Integer>(); if(root==null) return ans; Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.add(root); while(!queue.isEmpty()){ int len = queue.toArray().length; while((len--)!=0){ TreeNode treeNode = q ...