3. 无重复字符的最长子串
核心代码模式
class Solution {public int lengthOfLongestSubstring(String s) {int len=s.length();int []num=new int[300];int ans=0;for(int i=0,j=0;i<len;i++){num[s.charAt(i)]++;while(num[s.charAt(i)]>1){num[s.charAt(j)]--;j++;}ans=Math.max(ans,i-j+1);}return ans;}
}
手写输入输出模式
import java.util.*;public class Javaacm
{public static void main(String []args){
//输入：abadsadasScanner scan=new Scanner(System.in);String s=scan.next();int len=s.length();int ans=0;int num[]=new int[300];for(int i=0,j=0;i<len;i++){num[s.charAt(i)]++;while(num[s.charAt(i)]>1){num[s.charAt(j)]--;j++;}ans=Math.max(ans,i-j+1);}System.out.println(ans);}
}
146. LRU 缓存
核心代码模式
class LRUCache {int capacity; Map<Integer,Node> m=new HashMap<>();Node dummy=new Node(0,0);class Node{int key,value;Node pre ,ne;Node(int k,int v){key=k;value=v;}}public LRUCache(int capacity) {this.capacity=capacity;dummy.pre=dummy;dummy.ne=dummy;}public int get(int key) {Node cur=getNode(key);return cur==null?-1:cur.value;}Node getNode(int key){if(!m.containsKey(key))return null;Node cur=m.get(key);remove(cur);pushFront(cur);return cur;}void remove(Node node){node.pre.ne=node.ne;node.ne.pre=node.pre;}void pushFront(Node node){node.ne=dummy.ne;node.pre=dummy;node.pre.ne=node;node.ne.pre=node;}//逻辑最复杂public void put(int key, int value) {Node cur=getNode(key);if(cur!=null){cur.value=value;return ;} cur=new Node(key,value);m.put(key,cur);pushFront(cur);if(capacity<m.size()){m.remove(dummy.pre.key);remove(dummy.pre);}}
}
手写输入输出模式
import java.util.*;
class lrucache
{//双向链表+HashMapprivate final int capacity;//容量private final Node dummy=new Node(0,0);//双向链表头结点Map<Integer,Node> m=new HashMap<>();//哈希表public static class Node{ //node类，构造节点int key ,value;Node pre,ne;Node(int k,int v){key=k;value=v;}}public lrucache(int capacity) //初始化，设定容量{this.capacity=capacity;dummy.pre=dummy;dummy.ne=dummy;}//get，获取节点的value，没有则为-1public int get(int key){Node node=getNode(key); //获取节点并更新到最近使用return node!=null?node.value:-1;}//获取节点病更新到最近使用private Node getNode(int key){if(!m.containsKey(key))return null; //没有则返回nullNode node=m.get(key); //获取该节点linkRemove(node); //双向链表中删除该结点linkPushFront(node); //插入到头部return node;}void linkRemove(Node x){//删除某节点x.ne.pre=x.pre;x.pre.ne=x.ne;}
void linkPushFront(Node x)
{//从头部插入节点x.pre=dummy;x.ne=dummy.ne;x.ne.pre=x;x.pre.ne=x;
}public void put(int key,int value)
{ //先获取节点，顺便更新到最近使用Node node=getNode(key);if(node!=null){node.value=value; return ; //存在则更新值并返回}node=new Node(key,value);m.put(key,node); //哈希表插入linkPushFront(node); //双向链表插入if(m.size()>capacity){ //容量超过上限m.remove(dummy.pre.key); //哈希表删除最久使用linkRemove(dummy.pre); //双向链表移除该节点}
}
}
public class Javaacm
{public static void main(String []args){lrucache lru=new lrucache(2);lru.put(1,1);lru.put(2,2);System.out.println(lru.get(2)); //2lru.put(3,3); System.out.println(lru.get(1)); //-1System.out.println(lru.get(3)); //3}
}
206. 反转链表
核心代码模式
/*** 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 reverseList(ListNode head) {ListNode pre=null,cur=head;//双指针while(cur!=null){ListNode ne=cur.next;//留存剩余节点的头部cur.next=pre; //双指针更新pre=cur;cur=ne;}return pre;//最后cur为null,pre为新的头节点}
}
手写输入输出模式
import java.util.*;
class ListNode
{int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next;}
}
public class Javaacm
{public static void main(String []args){
//输入3,2,1,4,5Scanner scanner=new Scanner(System.in);String inner[]=scanner.next().split(","); //输入ListNode head=new ListNode(Integer.valueOf(inner[0])); //创建第一个节点，这里默认不会传空ListNode pre=null,cur=head;for(int i=1;i<inner.length;i++){ //循环构造链表ListNode curNode =new ListNode(Integer.valueOf(inner[i]));cur.next=curNode;cur=curNode;}//开始反转链表cur=head;while(cur!=null){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}//输出即可while(pre!=null){System.out.print(pre.val+"->");pre=pre.next;}System.out.print("null");//5->4->3->2->1->null}
}
215. 数组中的第K个最大元素
PriorityQueue写法
核心代码模式
class Solution {public int findKthLargest(int[] nums, int k) {Queue<Integer> q=new PriorityQueue<>();for(int i=0;i<nums.length;i++){q.add(nums[i]);if(q.size()>k){q.poll();}}return q.poll();}
}
手写输入输出
import java.util.*;public class Javaacm
{public static void main(String []args){
//输入：
//[3,2,1,5,6,4]
//3Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");Queue<Integer> q=new PriorityQueue<>();for(int i=0;i<str.length;i++){int cur=Integer.valueOf(str[i]);q.add(cur);if(q.size()>k){q.poll();}}System.out.print(q.poll());}
}
快速选择算法
核心代码模式
class Solution {int nums[];public int findKthLargest(int[] num, int k) {nums=num;int n=nums.length;return f(0,n-1,n-k);}void swap(int i,int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;}int f(int l,int r,int k){if(l>=r)return nums[k];int x=nums[l],i=l-1,j=r+1;while(i<j){do i++;while(nums[i]<x);do j--;while(nums[j]>x);if(i<j)swap(i,j);}if(k<=j)return f(l,j,k);return f(j+1,r,k);}
}
手写输入输出
import java.util.*;public class Javaacm
{static int nums[];public static void main(String []args){
//输入：
//[3,2,1,5,6,4]
//3Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");nums=new int[str.length];for(int i=0;i<str.length;i++)nums[i]=Integer.valueOf(str[i]);System.out.print(quickselect(0,nums.length-1,nums.length-k));}static int quickselect(int l,int r,int k){if(l>=r)return nums[k];int x=nums[l],i=l-1,j=r+1;while(i<j){do i++;while(nums[i]<x);do j--;while(nums[j]>x);if(i<j)swap(i,j);}if(k<=j)return quickselect(l,j,k);return quickselect(j+1,r,k);}static void swap(int a,int b){int t=nums[a];nums[a]=nums[b];nums[b]=t;}
}
25. K 个一组翻转链表
核心代码模式
/*** 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 reverseKGroup(ListNode head, int k) {ListNode pre=null,cur=head,hh=new ListNode(0,head);ListNode before=hh;int len=0;while(cur!=null){len++;cur=cur.next;}cur=head;for(int i=len;i>=k;i-=k){for(int j=0;j<k;j++){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}ListNode ne=before.next;before.next=pre;before=ne;ne.next=cur;}return hh.next;}
}
手写输入输出
import java.util.*;class ListNode
{int val;ListNode next;ListNode(){}ListNode(String v){val=Integer.valueOf(v);}ListNode(int v,ListNode ne){val=v;next=ne;}
}
public class Javaacm
{
//输入格式
// [3,2,1,5,6,4]
// 3public static void main(String []args){Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");int len=str.length;ListNode head=new ListNode(str[0]);ListNode pre=head;for(int i=1;i<len;i++){ListNode cur=new ListNode(str[i]);pre.next=cur;pre=cur;}ListNode cur=head;ListNode hh=new ListNode(0,head);ListNode before=hh;for(int l=len;l>=k;l-=k){for(int i=0;i<k;i++){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}ListNode ne=before.next; before.next=pre; //改头部before=ne; //换指针ne.next=cur; //衔尾部}ListNode p=hh.next;for(int i=0;i<len;i++){System.out.print(p.val+"->");p=p.next;}System.out.print("null");}
}
