LeetCode hot100面试背诵版（自用）

点击题目可以跳转到LeetCode

哈希

两数之和

public int[] twoSum(int[] nums, int target) {int length=nums.length;int[] ans = new int[2];for (int i = 0; i <length-1 ; i++) {for (int j = i+1; j < length; j++) {if(nums[i]+nums[j]==target){ans[0]=i;ans[1]=j;}}}return ans;}

字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>();List<List<String>> res = new ArrayList<>();for (String str : strs) {char[] chars = str.toCharArray();//把字符串转为数组Arrays.sort(chars);//排序String sortedStr = new String(chars);//把数组转为字符串List<String> tempList = map.getOrDefault(sortedStr, new ArrayList<>());//有就加入，没有就创建新的列表tempList.add(str);map.put(sortedStr,tempList);}res.addAll(map.values());return res;}

最长连续序列

public int longestConsecutive(int[] nums) {if(nums.length==0){return 0;}Set<Integer> set = new HashSet<>();//去重List<Integer> list = new ArrayList<>();for (int i : nums) {set.add(i);}list.addAll(set);Collections.sort(list);int cnt=0;int max=0;for (int i = 1; i < list.size(); i++) {if(list.get(i)-1==list.get(i-1)){cnt++;}else {cnt=0;}max=Math.max(cnt,max);}return max+1;}

双指针

移动零

public void moveZeroes(int[] nums) {int temp=0;for (int i = 0; i < nums.length; i++) {if(nums[i]!=0){//用一个临时值，把所有非0的元素全都移动到前面nums[temp]=nums[i];temp++;}}while (temp<nums.length){//后面的补上0nums[temp]=0;temp++;}}

盛最多水的容器

//左右两个指针
//每次移动最短的  因为移动最短的面积有可能增大  移动长的面积一定变小
public int maxArea(int[] height) {int i=0;int j=height.length-1;int res=0;while (i<j){int value=Math.min(height[i],height[j])*(j-i);if(height[i]<height[j]){res=Math.max(res,value);i++;}else {res=Math.max(res,value);j--;}}return res;}

三数之和

//三重for循环超时public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();HashSet<List<Integer>> set = new HashSet<>();//去重for (int i = 0; i < nums.length-2; i++) {for (int j = i+1; j < nums.length-1; j++) {for (int k = j+1; k < nums.length; k++) {if(nums[i]+nums[j]+nums[k]==0){List<Integer> list= new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);Collections.sort(list);set.add(list);}}}}res.addAll(set);return res;}

接雨水

//按列来看  装的水的高度为左右两边的最低高度减去自身的高度
public int trap(int[] height) {int sum=0;for (int i = 0; i < height.length; i++) {if(i==0||i==height.length-1){continue;}int left=height[i];int right=height[i];for (int j = i-1; j >=0 ; j--) {//记录左边最高高度if(height[j]>left){left=height[j];}}for (int j = i+1; j <=height.length-1 ; j++) {//记录右边最高高度if(height[j]>right){right=height[j];}}sum+=Math.min(left,right)-height[i];}return sum;}

 滑动窗口

滑动窗口算法框架

//左闭右开
public class SlidingWindow {/* 滑动窗口算法框架 */void slidingWindow(string s, string t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for (char c:t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0;int valid = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/System.out.printf("window: [%d, %d]\n", left, right);/********************/// 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小while (window needs shrink) {// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新...}}}
}

无重复字符的最长子串

public int lengthOfLongestSubstring(String s) {Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0;int res=0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新window.put(c,window.getOrDefault(c,0)+1);// 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小while (window.get(c)==2) {;// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新window.put(d,window.get(d)-1);}res=Math.max(res,right-left);//注意是在这里更新}return res;}

 找到字符串中所有字母异位词

public List<Integer> findAnagrams(String s, String p) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();List<Integer> list = new ArrayList<>();for (char c:p.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0;int valid = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if(window.get(c).equals(need.get(c))) valid++;}// 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小while (right-left>=p.length()) {if(valid==p.length()){list.add(left);}// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新if(need.containsKey(d)){if(window.get(d).equals(need.get(d))) valid--;window.put(d,window.get(d)-1);}}}return list;}

子串 

前缀和数组：其中每个元素是原始数组中从开始到当前元素的元素之和（子数组求和问题）

和为 K 的子数组

//前缀和加哈希表
public int subarraySum(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap<>();int count=0;int presum=0;map.put(0,1);// 初始化，前缀和为0出现1次for(int x:nums){presum+=x;if(map.containsKey(presum-k)){count+=map.get(presum-k);}map.put(presum,map.getOrDefault(presum,0)+1);}return count;}

 滑动窗口最大值

//超时 37/51
public int[] maxSlidingWindow(int[] nums, int k) {int[] res=new int[nums.length-k+1];//存放所有计算出来的值List<Integer> temp = new ArrayList<>();List<Integer> list = new ArrayList<>();for (int i = 0; i < k; i++) {temp.add(nums[i]);}list.add(Collections.max(temp));for (int i = k; i < nums.length; i++) {temp.removeFirst();temp.add(nums[i]);list.add(Collections.max(temp));}for (int i = 0; i < res.length; i++) {res[i]=list.get(i);}return res;}

 最小覆盖子串

public String minWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();String res="";int min=Integer.MAX_VALUE;for (char c:t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0;int valid = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if(window.get(c).equals(need.get(c))) valid++;}// 判断左侧窗口是否要收缩  有时候需要控制窗口的固定大小while (valid==need.size()) {if(right-left<min){res=s.substring(left,right);min=right-left;}// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新if(need.containsKey(d)){if(window.get(d).equals(need.get(d))) valid--;window.put(d,window.get(d)-1);}}}return res;

普通数组 

矩阵置零

public void setZeroes(int[][] matrix) {//记录行和列中有0的坐标Set<Integer> rowSet = new HashSet<>();Set<Integer> columnSet = new HashSet<>();for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if(matrix[i][j]==0){rowSet.add(i);columnSet.add(j);}}}//把行中有0的行  全部置为0for (Integer i : rowSet) {for (int j = 0; j < matrix[0].length; j++) {matrix[i][j]=0;}}//把所有列中有0的列 全部置为0for (Integer i : columnSet) {for (int j = 0; j < matrix.length; j++) {matrix[j][i]=0;}}}

螺旋矩阵

public List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();int m=matrix.length;int n=matrix[0].length;int up=0,down=m,left=0,right=n;while (true){//处理上边界for (int i = left; i <right ; i++) {res.add(matrix[up][i]);}up++;if(up>=down) break;//处理右边界for (int i = up; i < down; i++) {res.add(matrix[i][right-1]);}right--;if (right<=left) break;//处理下边界for (int i = right-1; i >=left ; i--) {res.add(matrix[down-1][i]);}down--;if(down<=up) break;//处理左边界for (int i = down-1; i >up-1 ; i--) {res.add(matrix[i][left]);}left++;if(left>=right) break;}return res;}

旋转图像

//没有用原地算法
public void rotate(int[][] matrix) {//clone是浅克隆   新new深克隆int length=matrix[0].length;int[][] temp = new int[length][length];for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {temp[i][j] = matrix[i][j];}}for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {matrix[i][j]=temp[length-1-j][i];}}System.out.println(Arrays.deepToString(matrix));}

 搜索二维矩阵 II

//直接两层for循环
public boolean searchMatrix(int[][] matrix, int target) {int row=matrix.length;int column=matrix[0].length;for (int i = 0; i <row ; i++) {for (int j = 0; j < column; j++) {if(matrix[i][j]==target){return true;}}}return false;}

链表 

相交链表

//核心代码
指针指向的是地址   移动的距离相同  指向的地址一样
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa=headA,pb=headB;while(pa!=pb){pa=pa==null?headB:pa.next;pb=pb==null?headA:pb.next;}return pa;}

 反转链表

//三指针
public ListNode reverseList(ListNode head) {ListNode pre=null;ListNode cur=head;//保留头结点ListNode temp=null;while (cur!=null){//循环的次数temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}
​