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;}
回文链表
//使用两个集合来判断
public boolean isPalindrome(ListNode head) {ArrayList<Integer> list = new ArrayList<>();ArrayList<Integer> temp = new ArrayList<>();while (head !=null){list.add(head.val);temp.add(head.val);head=head.next;}Collections.reverse(list);if(temp.equals(list)){return true;}return false;}环形链表
//通过节点的地址来判断，没有环就不会无限循环 有地址相等的话就是有环
public boolean hasCycle(ListNode head) {List<ListNode> list = new ArrayList<>();while (head!=null){list.add(head);if(list.contains(head.next)){//判断下一个节点的地址在集合中是否存在return true;}head = head.next;}return false;}环形链表 II
public ListNode detectCycle(ListNode head) {List<ListNode> list = new ArrayList<>();while (head!=null){list.add(head);if(list.contains(head.next)){return head.next;}head=head.next;}return null;}合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//定义一个虚拟头结点，方便待会返回ListNode dum;ListNode cur = new ListNode();dum=cur;while (list1!=null&&list2!=null){if(list1.val<=list2.val){cur.next=list1;list1=list1.next;}else {cur.next=list2;list2=list2.next;}cur=cur.next;}if(list1!=null){cur.next=list1;}else {cur.next=list2;}return dum.next;}两数相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dum = new ListNode();ListNode cur=dum;int carry=0;while (l1!=null||l2!=null){//位数不够的话 补0int x=l1==null?0:l1.val;int y=l2==null?0:l2.val;int sum=x+y+carry;carry=sum/10;sum=sum%10;cur.next=new ListNode(sum);cur=cur.next;if (l1!=null){l1=l1.next;}if (l2!=null){l2=l2.next;}}//最后两个节点的进位if(carry==1){cur.next=new ListNode(1);}return dum.next;}删除链表的倒数第 N 个结点
public ListNode removeNthFromEnd(ListNode head, int n) {int length=0;ListNode temp=head;while (temp!=null){//先计算出长度length++;temp=temp.next;}if(length==1){//如果长度为1就返回空return null;}ListNode pre=new ListNode(0);//新建一个新节点方便删除操作，记得给初始值不然会报空指针pre.next=head;if(length-n==0){//如果删除的是头节点pre.next=pre.next.next;return pre.next;}for (int i = 0; i < length-n; i++) {//如果删除的不是头结点pre=pre.next;}pre.next=pre.next.next;return head;}两两交换链表中的节点
//四指针，局部反转
public ListNode swapPairs(ListNode head) {ListNode dum=new ListNode();dum.next=head;ListNode pre=dum;ListNode start;ListNode end=dum;ListNode next;while (end.next!=null){for (int i = 0; i < 2&&end!=null; i++) {end=end.next;}if(end== null){break;}start=pre.next;next=end.next;end.next=null;pre.next= reverseList(start);start.next=next;pre=start;end=pre;}return dum.next;}public ListNode reverseList(ListNode head) {//三指针ListNode pre = null;ListNode cur = head;ListNode temp;while (cur!=null){temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}K 个一组翻转链表
把上面那题的2改成K就行
public ListNode reverseKGroup(ListNode head, int k) {ListNode dum=new ListNode();//定义一个虚节点，始终指向第一个节点，方便后面返回dum.next=head;ListNode pre=dum;ListNode start;ListNode end=dum;ListNode next;while (end.next!=null){for (int i = 0; i < k&&end!=null; i++) {//也要判断end为不为空 不然空指针异常end=end.next;}if(end== null){//如果end为空的话就是遍历到了末尾break;}start=pre.next;//指定要翻转链表的开头next=end.next;//保留下一个节点，方便待会找回end.next=null;//把指针断掉，截取要翻转的部分pre.next= reverseList(start);//翻转过后，start 跟 end 位置变了要清楚start.next=next;//把断掉的链表重新连起来pre=start;end=pre;}return dum.next;}public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;ListNode temp;while (cur!=null){temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}排序链表
//转换为集合，排序后，再生成新的链表 比较笨 但是直观 哈哈
public ListNode sortList(ListNode head) {List<Integer> list = new ArrayList<>();ListNode cur=head;while (cur!=null){list.add(cur.val);cur=cur.next;}Collections.sort(list);for (Integer i : list) {System.out.println(i);}ListNode dum=new ListNode();cur=dum;for (Integer integer : list) {cur.next = new ListNode(integer);cur = cur.next;}return dum.next;}