力扣热题100，力扣148.排序链表力扣.26找出字符串中第一个匹配项的下标力扣146.LRU缓存序列管理器
目录
力扣148.排序链表
力扣.26找出字符串中第一个匹配项的下标
力扣146.LRU缓存
序列管理器
力扣148.排序链表
那个O1,暂时我没有考虑，但是这个nlogn,我就想什么时候会有log呢，应该是2的次幂方向思考，一说2，是否能想到2分呢？
暴力就是你可以枚举一个一个，然后new一个节点，全部串起来
但是二分使用，我不是很熟，而且还是链表(我学的比较浅薄，只知道能排序和搜索东西，但是我没想到还能给链表使用).
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/ class Solution {public ListNode sortList(ListNode head) {if(head==null||head.next==null) return head;//此时必须把一个是head,一个是headnext,不然，假如2个节点的话，就会出现死在一块的问题，因为是你的fast是走两步，就走不了ListNode slow=head,fast=head.next;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//此刻我们找到啦中点ListNode right=slow.next;slow.next=null;//把它给分离开ListNode leftHead=sortList(head); //找到左边的头节点ListNode rightHead=sortList(right); //找到右边的头节点ListNode h=new ListNode();ListNode cur=h; //他来遍历整个数组//合并两个有序数组while(leftHead!=null||rightHead!=null){if(leftHead==null){cur.next=rightHead;break;}//左边和右边都要遍历完成if(rightHead==null){cur.next=leftHead;break;}if(leftHead.val<rightHead.val){cur.next=leftHead;leftHead=leftHead.next;}else {cur.next=rightHead;rightHead=rightHead.next;}cur=cur.next;}return h.next; } }
力扣.26找出字符串中第一个匹配项的下标
思路，开始的时候寻思剪枝啥的，后来一下没必要，我直接暴力就好了
写的时候要注意一些细节，比如
"mississippi" "issip" 我开始没写k直接写的i去操作，这样会导致一段区间内，有可能匹配的是两端，比如 这个issi 前面符合，这个i不符合，但是我已经跳过了啥的
所以，还是使用k方便，然后还面临两个数组长度不同，子数组假如比父亲数组大，直接 跳过，然后还有就是，你找到匹配项之后，你进行k++要注意不要去加越界了。
class Solution {public int strStr(String haystack, String needle) {int n = haystack.length();int m = needle.length();if(m>n)return -1;int ret = 99999;//helwdawdllo llfor (int i = 0; i < n; i++) {int k=i;for (int j = 0; j < m; j++) {if (k<n&&haystack.charAt(k) == needle.charAt(j)) {ret = Math.min(k++, ret);} else {ret = 99999;break;}}if(ret!=99999){return ret;}}return -1;} }
力扣146.LRU缓存
这个题先说答题感受，他这个指针有些复杂，看起来简单，但是实际上操作一下，数据结构很容易弄混
Map<key,DL<key,Value>>map
本质是个这样的东西，然后他这里还有一个精妙设计，就是头节点和尾节点，他这个就像是一个包围圈似的，开始我以为是链表那种，没想到还是有出入
class LRUCache {class DLinkedNode {int key;int value;//前后的指针DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {this.key = _key;this.value = _value;}}//Integer存储未key，方便定位private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;//标记头和尾private DLinkedNode head, tail;//头插private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}//删除节点private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}public LRUCache(int capacity) {this.size=0;this.capacity=capacity;//添加一个头节点head=new DLinkedNode();//尾巴节点就相当于当前节点tail=new DLinkedNode();//头尾节点连接head.next=tail;tail.prev=head;}public int get(int key) {DLinkedNode cur=cache.get(key);if(cur==null)return -1;//他的意思是，最多使用的在队列头,先通过hash表定位moveToHead(cur);return cur.value;}//这里我大概明白他的结构 key -<key,value>//这个key是为了删除里面的key,value 更加方便，它主要核心是有个双向链表和map//这个key是方便查找，说有用也有用，说没用也没用，但是public void put(int key, int value) {DLinkedNode node=cache.get(key);DLinkedNode newnode=new DLinkedNode(key,value);if(node==null){cache.put(key,newnode);addToHead(newnode);size++;if(size>capacity){DLinkedNode tail=removeTail();//删除哈希表中对应的选项cache.remove(tail.key);--size;}}else{removeNode(node);cache.remove(key);//假如我把它删除之后，我的key保持在原地，但是我的链表value还在原先位置cache.put(key,newnode);//你只是做到插入一个节点，但是没有保证是头节点之后，即头插addToHead(newnode);}}
}
序列管理器（某益面试题)
/*** 设计一个序列管理器（SequenceManager）类，维护一个严格递增的正整数序列，提供如下操作：** 获取下一个数（Integer getNext()）* 功能：返回当前序列中缺失的最小正整数，并将该数添加到序列中* 返回值：新添加到序列中的正整数* 特性：保持序列严格递增** 重命名操作（void rename(Integer oldNum, Integer newNum)）* 功能：将序列中的一个数字替换为另一个数字* 参数：* oldNum：要替换的现有数字* newNum：替换后的新数字* 约束条件：* oldNum 必须存在于序列中* newNum 不能存在于序列中* 操作后序列仍保持严格递增** 删除操作（void delete(Integer toDeleteNum)）* 功能：从序列中移除指定的数字* 参数：要删除的数字* 约束条件：待删除的数字必须存在于序列中** 序列特性：* 初始状态：空序列* 有序性：严格递增（即任意相邻两个数字之间不相等）* 元素唯一性：序列中不允许重复数字 Set** 操作示例：* 初始状态：序列为空 {}* getNext() → 返回1，序列变为 {1}* getNext() → 返回2，序列变为 {1, 2}* rename(2, 3) → 序列变为 {1, 3}* getNext() → 返回2，序列变为 {1, 2, 3}* getNext() → 返回4，序列变为 {1, 2, 3, 4}*/核心重点了解TreeSet:有序，不可重复的数字数据结构
TreeSet<Integer> set = new TreeSet<>();/*** 返回当前序列中缺失的最小正整数，并将该数添加到序列中** @return 新添加到序列中的正整数*/public Integer getNext() {int count=1;for(Integer a:set){if(a!=count++){break;}}set.add(count);return count;}/*** 将序列中的一个数字替换为另一个数字** @param oldNum 要替换的现有数字* @param newNum 替换后的新数字*/public void rename(Integer oldNum, Integer newNum) {if (!set.contains(oldNum)) {throw new RuntimeException("oldNum 不存在存在于序列中");}if (set.contains(newNum)) {throw new RuntimeException("newNum 存在存在于序列中");}set.remove(oldNum);set.add(newNum);}/*** 从序列中移除指定的数字** @param toDeleteNum 要删除的数字*/public void delete(Integer toDeleteNum) {if (!set.contains(toDeleteNum)) {throw new RuntimeException("toDeleteNum 不存在存在于序列中");}set.remove(toDeleteNum);}@Overridepublic String toString() {return "SequenceManager{" +"set=" + set +'}';}