力扣热题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 ll for (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>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 cache = new HashMap(); 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是为了删除里面的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 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); } @Override public String toString() { return \"SequenceManager{\" + \"set=\" + set + \'}\'; }