目录
力扣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<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); } @Override public String toString() { return "SequenceManager{" + "set=" + set + '}'; }