中间20题

128. 最长连续序列

int res=0;
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++){
  set.add(nums[i]);
}
for (Integer integer : set) {
  int cur=integer;
  if(!set.contains(cur-1)){
    while (set.contains(cur)){
      cur+=1;
    }
    res=Math.max(res,cur-integer);
  }
}
return res;

136. 只出现一次的数字

//异或运算是相同为假，不同为真。比如4^1就是
// 0 1 0 0
// 0 0 0 1
// 0 1 0 1 =5
int res=0;
for(int i=0;i<nums.length;i++){
  res^=nums[i];
}
return res;

146. LRU 缓存

class LRUCache {
    private LinkedHashMap<Integer,Integer>map=new LinkedHashMap<>();
    private int cap;
    public LRUCache(int capacity) {
        this.cap=capacity;
    }
    public int get(int key) {
        if(map.containsKey(key)){
            int value=map.get(key);
            flushRecent(key,value);
            return value;
        }else{
            return -1;
        }
    }
    public void put(int key, int value) {
        if(map.containsKey(key)){
            flushRecent(key,value);
        }else{
            map.put(key,value);
            if(map.size()>cap){
                int oldKey = map.keySet().iterator().next();
                map.remove(oldKey);
            }
        }
    }
    private void flushRecent(int key,int value){
        map.remove(key);
        map.put(key,value);
    }
}

解法二：自定义链表

import java.util.HashMap;
import java.util.Map;
class LRUCache {
    private static class ListNode{
        ListNode pre;
        ListNode next;
        int key;
        int value;
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private static class NodeLinkedList{
        ListNode head=null;
        ListNode tail=null;
        public void addNode(ListNode node){
            if(head==null){
                head=node;
                tail=node;
            }else{
                tail.next=node;
                node.pre=tail;
                tail=node;
            }
        }
        public void adjustToTail(ListNode node){
            if(node==tail){
                return;
            }else if(head==node){
                ListNode next=node.next;
                node.next=null;
                next.pre=null;
                head=next;
            }else{
                ListNode pre=node.pre;
                ListNode next=node.next;
                node.pre=null;
                node.next=null;
                pre.next=next;
                next.pre=pre;
            }
            tail.next=node;
            node.pre=tail;
            tail=node;
        }
        public ListNode deleteHead(){
            if(head==null){
                return null;
            }else if(tail==head){
                head=null;
                tail=null;
                return tail;
            }else{
                ListNode hd=head;
                ListNode next=head.next;
                head.next=null;
                next.pre=null;
                head=next;
                return hd;
            }
        }
    }
    private int cap;
    private NodeLinkedList list=new NodeLinkedList();
    private Map<Integer,ListNode> map=new HashMap<>();
    public LRUCache(int capacity) {
        this.cap=capacity;
    }
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }else{
            ListNode node = map.get(key);
            list.adjustToTail(node);
            return node.value;
        }
    }
    public void put(int key, int value) {
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            node.value=value;
            map.put(key,node);
            list.adjustToTail(node);
        }else{
            ListNode node = new ListNode(key, value);
            map.put(key,node);
            list.addNode(node);
            if(map.size()>cap){
                ListNode node1 = list.deleteHead();
                map.remove(node1.key);
            }
        }
    }
}

148. 排序链表

public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode mid = findMid(head);
        ListNode midRight=mid.next;
        mid.next=null;
        ListNode left = sortList(head);
        ListNode right = sortList(midRight);
        return mergeNode(left,right);
    }
    private ListNode findMid(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    private ListNode mergeNode(ListNode node1,ListNode node2){
        ListNode virtualNode = new ListNode(Integer.MIN_VALUE);
        ListNode temp=virtualNode;
        while (node1!=null&&node2!=null){
            if(node1.val<=node2.val){
                temp.next=node1;
                node1=node1.next;
            }else{
                temp.next=node2;
                node2=node2.next;
            }
            temp=temp.next;
        }
        if(node1==null){
            temp.next=node2;
        }else{
            temp.next=node1;
        }
        return virtualNode.next;
    }

152. 乘积最大子数组

int[]maxDp=new int[nums.length];
int[]minDp=new int[nums.length];
maxDp[0]=nums[0];
minDp[0]=nums[0];
int res=nums[0];
for(int i=1;i<nums.length;i++){
  maxDp[i]=Math.max(nums[i],Math.max(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
  minDp[i]=Math.min(nums[i],Math.min(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
  res=Math.max(res,maxDp[i]);
}
return res;

169. 多数元素

int voter=nums[0];
int voteCount=0;
for(int i=1;i<nums.length;i++){
  if(nums[i]==voter){
    voteCount++;
  }else if(nums[i]!=voter&&voteCount>0){
    voteCount--;
  }else{
    voter=nums[i];
    voteCount=0;
  }
}
return voter;

207. 课程表(拓扑排序)

Map<Integer, Integer> map = new HashMap<>();
//用map来保存每个课程的入度。
for(int i=0;i<numCourses;i++){
  map.put(i,0);
}
//用map集合来保存先决关系，比如先完成0才能完成1、2。   0->1、2
Map<Integer, List<Integer>>path=new HashMap<>();
for (int[] prerequisite : prerequisites) {
  int cur=prerequisite[1];
  int next=prerequisite[0];
  map.put(next,map.getOrDefault(next,0)+1);
  if(!path.containsKey(cur)){
    path.put(cur,new ArrayList<>());
  }
  path.get(cur).add(next);
}
//用queue来取出path中的元素，让入度-1
Deque<Integer>queue=new LinkedList<>();
for (Integer integer : map.keySet()) {
  if(map.get(integer)==0){
    queue.addLast(integer);
  }
}
while (!queue.isEmpty()){
  int cur = queue.pollFirst();
  if(!path.containsKey(cur)){
    continue;
  }
  for (Integer integer : path.get(cur)) {
    map.put(integer,map.getOrDefault(integer,0)-1);
    if(map.get(integer)==0){
      queue.addLast(integer);
    }
  }
}
for (Integer integer : map.keySet()) {
  if(map.get(integer)!=0){
    return false;
  }
}
return true;

208. 实现 Trie (前缀树)

class Trie {
    //前缀树根节点不保存数据，每个节点都有26个字符数组，在word末尾设置boolean标志位
    private TrieNode root=new TrieNode();
    class TrieNode{
        boolean end;
        TrieNode[]tns=new TrieNode[26];
    }
    public Trie() {
    }
    public void insert(String word) {
        TrieNode temp=root;
        for(int i=0;i<word.length();i++){
            int location=word.charAt(i)-'a';
            if(temp.tns[location]==null){
                temp.tns[location]=new TrieNode();
            }
            temp=temp.tns[location];
        }
        temp.end=true;
    }
    public boolean search(String word) {
        TrieNode temp=root;
        for(int i=0;i<word.length();i++){
            int location=word.charAt(i)-'a';
            if(temp.tns[location]==null){
                return false;
            }else{
                temp=temp.tns[location];
            }
        }
        return temp.end;
    }
    public boolean startsWith(String prefix) {
        TrieNode temp=root;
        for(int i=0;i<prefix.length();i++){
            int location=prefix.charAt(i)-'a';
            if(temp.tns[location]==null){
                return false;
            }else{
                temp=temp.tns[location];
            }
        }
        return true;
    }
}

215. 数组中的第K个最大元素

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int res=0;
        for(int i=0;i<nums.length;i++){
            queue.add(nums[i]);
        }
        while (k>0){
            res=queue.poll();
            k--;
        }
        return res;

221. 最大正方形

int[][]dp=new int[matrix.length][matrix[0].length];
        int res=0;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j]=1;
                    res=Math.max(res,dp[i][j]);
                }
            }
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(dp[i][j]==0){
                    continue;
                }else{
                    if(dp[i-1][j]>0&&dp[i][j-1]>0&&dp[i-1][j-1]>0){
                        dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                        res=Math.max(res,dp[i][j]);
                    }
                }
            }
        }
        return res*res;

234. 回文链表

//先寻找链表中间节点
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //如果fast.next=null说明是奇数个节点，否则是偶数个节点
        if(fast.next==null){
            ListNode last=slow.next;
            //反转前半部分的链表
            ListNode pre=null;
            ListNode temp=head;
            while (temp!=slow){
                ListNode next=temp.next;
                temp.next=pre;
                pre=temp;
                temp=next;
            }
            //执行判断的逻辑
            while (pre!=null&&last!=null){
                if(pre.val!=last.val){
                    return false;
                }
                pre=pre.next;
                last=last.next;
            }
            return true;
        //如果是偶数个节点的情况
        }else{
            ListNode last=slow.next;
            //反转前半部分的链表
            ListNode pre=null;
            ListNode temp=head;
            while (temp!=last){
                ListNode next=temp.next;
                temp.next=pre;
                pre=temp;
                temp=next;
            }
            //执行判断的逻辑
            while (pre!=null&&last!=null){
                if(pre.val!=last.val){
                    return false;
                }
                pre=pre.next;
                last=last.next;
            }
            return true;

238. 除自身以外数组的乘积

//可以定义两个dp数组，分别保存从左边相乘的数和从右边相乘的数
        int[] leftDp=new int[nums.length];
        int[] rightDp=new int[nums.length];
        int[] res=new int[nums.length];
        leftDp[0]=nums[0];
        rightDp[rightDp.length-1]=nums[nums.length-1];
        for(int i=1;i<leftDp.length;i++){
            leftDp[i]=nums[i]*leftDp[i-1];
        }
        for(int i=rightDp.length-2;i>=0;i--){
            rightDp[i]=nums[i]*rightDp[i+1];
        }
        res[0]=rightDp[1];
        res[res.length-1]=leftDp[leftDp.length-2];
        for(int i=1;i<res.length-1;i++){
            res[i]=leftDp[i-1]*rightDp[i+1];
        }
        return res;

239. 滑动窗口最大值

int[]res=new int[nums.length-k+1];
Deque<Integer>queue=new LinkedList<>();
int index=0;
for(int i=0;i<nums.length;i++){
  //头(清除头部元素)
  if(!queue.isEmpty()&&queue.peekFirst()==i-k){
    queue.pollFirst();
  }
  //尾(维持一个单调递增的队列)
  while (!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()]){
    queue.pollLast();
  }
  //尾
  queue.addLast(i);
  //头
  if(i>=k-1){
    res[index++]=nums[queue.peekFirst()];
  }
}
return res;

240. 搜索二维矩阵 II

//从矩阵的左下角入手开始找
int row=matrix.length-1;
int col=0;
while (row>=0&&row<=matrix.length-1&&col>=0&&col<=matrix[0].length-1){
  if(target==matrix[row][col]){
    return true;
  }else if(target>matrix[row][col]){
    col++;
  }else{
    row--;
  }
}
return false;

287. 寻找重复数(二分法)

int left=1;
int right=nums.length-1;
while (left<=right){
  int count=0;
  int mid=(left+right)/2;
  for(int i=0;i<nums.length;i++){
    if(nums[i]<=mid){
      count++;
    }
  }
  if(count<=mid){
    left=mid+1;
  }else{
    right=mid-1;
  }
}
        return left;

297. 二叉树的序列化与反序列化

public class Codec {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value) {
            this.val = value;
        }
        public TreeNode() {
        }
        public TreeNode(int value,TreeNode left,TreeNode right) {
            this.val = value;
            this.left = left;
            this.right = right;
        }
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null){
            return null;
        }
        StringBuilder builder = new StringBuilder();
        Deque<TreeNode>queue=new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.pollFirst();
            if(node!=null) {
                builder.append(node.val).append(",");
            }else{
                builder.append("null").append(",");
                continue;
            }
            queue.addLast(node.left);
            queue.addLast(node.right);
        }
        return builder.toString().substring(0,builder.length()-1);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("null")||data.length()==0){
            return null;
        }
        String[] split = data.split(",");
        int index=1;
        Deque<TreeNode>queue=new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        queue.addLast(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.pollFirst();
            if(!split[index].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(split[index]));
                node.left=left;
                queue.addLast(left);
            }
            index++;
            if(!split[index].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(split[index]));
                node.right=right;
                queue.addLast(right);
            }
            index++;
        }
        return root;
    }
}

300. 最长递增子序列*

int[]dp=new int[nums.length];
Arrays.fill(dp,1);
int res=1;
for(int i=1;i<nums.length;i++){
  for(int j=0;j<i;j++){
    if(nums[i]>nums[j]){
      dp[i]=Math.max(dp[j]+1,dp[i]);
      res=Math.max(res,dp[i]);
    }
  }
}
return res;

301. 删除无效的括号

class Solution {
    private StringBuilder builder=new StringBuilder();
    private Set<String> set=new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        int leftCount=0;
        int rightCount=0;
        //这里的逻辑是判断看需要删除多少个左括号、右括号
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                leftCount++;
            }else if(s.charAt(i)==')'){
                if(leftCount>0){
                    leftCount--;
                }else{
                    rightCount++;
                }
            }
        }
        backTrack(0,s,leftCount,rightCount);
        return new ArrayList<>(set);
    }
    private void backTrack(int index,String s,int left,int right){
        if(index==s.length()){
            if(left==0&&right==0&&check(builder)){
                set.add(builder.toString());
            }
            return;
        }
        char c = s.charAt(index);
        if(c=='('){
            builder.append(c);
            backTrack(index+1,s,left,right);
            builder.deleteCharAt(builder.length()-1);
            if(left>0){
                backTrack(index+1,s,left-1,right);
            }
        }else if(c==')'){
            builder.append(c);
            backTrack(index+1,s,left,right);
            builder.deleteCharAt(builder.length()-1);
            if(right>0){
                backTrack(index+1,s,left,right-1);
            }
        }else{
            builder.append(c);
            backTrack(index+1,s,left,right);
            builder.deleteCharAt(builder.length()-1);
        }
    }
    private boolean check(StringBuilder builder){
        int left=0;
        int right=0;
        for(int i=0;i<builder.length();i++){
            if(builder.charAt(i)=='('){
                left++;
            }else if(builder.charAt(i)==')'){
                if(left==0){
                    return false;
                }else{
                    left--;
                }
            }
        }
        return left==0;
    }
}

338. 比特位计数

int[]dp=new int[n+1];
dp[0]=0;
for(int i=n;i>=1;i--){
  int oneCount=0;
  int temp=i;
  while (temp!=0){
    temp&=temp-1;
    oneCount++;
  }
  dp[i]=oneCount;
}
return dp;

347. 前 K 个高频元素

//大顶堆+哈希表
int[]dp=new int[k];
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
  map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
PriorityQueue<Map.Entry<Integer,Integer>>queue=new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
  @Override
  public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
    return o2.getValue()-o1.getValue();
  }
});
for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
  queue.add(integerIntegerEntry);
}
for(int i=0;i<k;i++){
  dp[i]=queue.poll().getKey();
}
return dp;