wellorbetter notes

LRU大概思路就是unordered_map hash+双向链表head,tail拿的时候hahsmap key int value node我能直接get拿到这个node，然后把这个node 先remove，然后插到链表头部put的时候，也是，如果有，就修改这个value，然后remove，再insert如果没有，new一个node，然后再看size和cap的关系，如果大于等于，就要先remove这个tail的一个，然后再insert头 class LRUCache {private: int cap; struct Node { int key, value; struct Node* prev; struct Node* next; Node(int key, int value): key(key), value(value) { } }; struct Node* head; struct Node* tail; unordered_map<int, Node*> m...

无重复字符的最长子串给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。 最开始写成模拟了，后来想了一下，这个是滑动队列，很久之前写过，写不太懂了大概就记得维护一个l到r的一个队列，大概就是进来先放当前的这个i这个值如果重复了，那就弹队头，l++然后每次进来先放，然后r++没啥问题 class Solution {public: map<char, int> mp; int lengthOfLongestSubstring(string s) { if (s.size() == 0) return 0; int l = 0, r = 0, res = 1; mp[s[l]] ++; for (int i = 1; i < s.size(); i ++ ) { mp[s[i]] ++ ; r ++ ; // cout << i <&l...

最长公共子序列 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 咋说呢，这个题没做出来，我的思路是直接暴力枚举，1 << 1000 直接炸了这个dp[i][j] i和j表示俩字符串的最后一位，用闫氏dp法，切割最后一位状态，它这俩字符串这个ij位到底可能有哪些情况比较好想出来的就是字符串是否相等来切割，如果相等，那就直接等于i-1 j-1 + 1，如果不相等，就等于i-1/j-1 取max个人感觉不是很好想出来，看答案了 class Solution {public: int dp[1020][1020]; int longestCommonSubsequence(string text1, string text2) { for (int i = 1; i <...

岛屿数量已解答中等相关标签premium lock icon相关企业给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 咋说，比较简单，dfs秒了但是这个也能用并查集做，就差不多吧，反正遍历挨个合并就行了练一下模板吧 123456789101112131415161718const int N = 1e5 + 10;int parent[N], size[N];int find(x) { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x];}int union(int a, int b) { int ra = find(a), rb = find(b); if (size[ra] < size[rb]) { int t = ra; ra = rb...

验证二叉搜索树 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下： 节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 思路很简单，就他这个，左子树这个大小能递归拿到，右子树大小也能递归拿到然后左子树小于当前的值大于右子树的值然后递归左子树，递归右子树，取并就行了 单纯数据结构，感觉都不用刷了大一基础还是不赖的 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0)...

爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？f[i] = f[i - 1] + f[i - 2]; 寻找峰值中等相关标签premium lock icon相关企业峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 这个题没想出来，这里看了下答案，这个答案是真天才。不过这些题目确实转化一下就有思路了，这里有对称性，因为你这个是峰值，所以沿着峰值是对称的左边是严格上升，右边是严格下降，所以你只需要找到严格上升的就行了同时看到logn，一眼就是二分然后看，如果分成两半，要看的话应该就是严格递增了，如果什么的话，这个峰值在右边呢？check mid < mid+1 递增的在右边，那右边一定有一个峰值，反之一定在左边注意这里的二...

最大正方形 个人思路，0s想出思路，二维前缀和+for nm len 遍历 n^3也能过 这里正解是dp，但是我是感觉这个dp理解起来很费解，感觉很难了。他这个dp ij表示的是边长，因为正方形面积实际上是和边长挂边的，但是边长更简单不用开根号。然后这里你表达的是最大的边长，这里来看的话，我理解你可能会由i-1 j-1 i-j&j-1这三个正方形转化而来110110001比如这个，那就是i-1&j-1011011001 这里就是i-1110110001 这里就是j-1但是实际上能走到扩大的只有111111111因为这三实际上是相互影响的。你如果i-1能扩展到i，那意味着，你这个i-1上面必须至少全部都是1，同理j-1,i-1&j-1要拓展过来，你这部分都得是1那很明显，那就是这三的最小值都得满足满1，然后才能+1那这里dpij >= min(这三个)+1那这里dp ij 能不能不止+1 能+2呢？假设这个最小值是m，然后这个如果dpij >= m+2，那这里就会存在m+2，m+2，这个正方形，它这里面能拆出三个m+1那这...

插入区间 一眼left right二分+合并区间。然后这个合并区间是只有三个区间。然后我就懒得写区间合并，然后就悲剧了 真神了，为什么要模拟，真的是神了，思路出来0s，模拟1h还不对。真不如区间合并板子用一下。就算我过了，不想改了

四级缓存就RV这个东西，它是需要缓存的，就你这个思路很简单，你页面上显示六个view，那我至少得有六个view的这个显示队列，还有随时能用的这个tmp viewScrapScrap 英文原意是「碎片、边角料、废纸」还在屏幕上，只是temp detach了只在一次 layout 的过程中存在。 layout 开始前是空的，layout 结束后也是空的，只在中间短暂存在会触发RV layout的情况 - 调用 notifyXXX（notifyDataSetChanged, notifyItemChanged, notifyItemInserted, …） - Adapter 换了（setAdapter） - LayoutManager 换了 - RV 尺寸变了（屏幕旋转、折叠屏展开） - 主动调 requestLayout()一次 layout 的完整过程假设屏幕上现在有 6 个 VH：notifyItemChanged(3) layout 开始，把屏幕上所有 VH 「暂存」到 Scrap detachAndScrapAttachedViews 把所...

RV 基础理解viewholder，为什么需要viewholder非常显然一个rv，他滑动一定是需要限制展示的view和复用的比如一屏显示6个view，这个时候大概就需要维护一个7~8个显示的view的队列就好了非常直观，然后这个view，inflate的开销是很大的，要去找xml渲染，所以就直接这个存七八个view，就这个队列的view，然后挨个复用，就修改他的内容就行了。然后呢，这里view内部会有一堆东西，比如textview这种东西，你如果不持有这部分引用的话，你挨个bind的时候还得findviewbyId，这部分查找也很麻烦所以就有viewhoder这个概念，就持有view和他内部的资源的引用比如textview一大堆，然后还有一堆本身这块儿复用以及生命周期相关的一些值（比如fragment destroy了，这个viewholder就没有用了，这个就要销毁）场景问题1点击进入一个有rv的fragment，此时rv的pool是空的，因为都还没开始滑动（都没创建），这个时候需要从头创建viewholder，那如果这里view要是多了，这个要创建的viewholder就多...