核心代码模式
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)
{
//输入：abadsadas
Scanner 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);
}
}
核心代码模式
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
{
//双向链表+HashMap
private 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，没有则为-1
public 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; //没有则返回null
Node 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)); //2
lru.put(3,3);
System.out.println(lru.get(1)); //-1
System.out.println(lru.get(3)); //3
}
}
核心代码模式
/**
* 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,5
Scanner 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
}
}
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]
//3
Scanner 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]
//3
Scanner 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;
}
}
核心代码模式
/**
* 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]
// 3
public 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");
}
}