LeetCode100题

class Solution {public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> ret=new ArrayList<>();HashMap<String,List<String>> map=new HashMap<>();for(String a:strs){char[] sc=a.toCharArray();Arrays.sort(sc);String key=String.valueOf(sc);List<String> list=map.getOrDefault(key,new ArrayList());list.add(a);map.put(key,list);}return new ArrayList<List<String>>(map.values());}
}

class Solution {public int longestConsecutive(int[] nums) {int count=0;HashSet<Integer> set=new HashSet<>();for(int x:nums){set.add(x);}for(int x:set){if(!set.contains(x-1)){int flag=1;while(set.contains(++x)){flag++;}count=Math.max(flag,count);}}return count;}
}

class Solution {public void moveZeroes(int[] nums) {int slow=0;for(int i=0;i<nums.length;i++){if(nums[i]!=0){nums[slow++]=nums[i];}}Arrays.fill(nums,slow,nums.length,0);}
}

class Solution {public int maxArea(int[] height) {int left=0,right=height.length-1;int ans=0;for(int i=0;i<height.length;i++){int high=right-left;int h=Math.min(height[right],height[left]);ans=Math.max(high*h,ans);if(height[right]<height[left]){right--;}else{left++;}}return ans;}
}

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans=new ArrayList<>();if(nums.length<3)return ans;Arrays.sort(nums);for(int i=0;i<nums.length-2;i++){if(nums[i]>0)return ans;if(i>0&&nums[i]==nums[i-1])continue;int left=i+1,right=nums.length-1;while(left<right){int sum=nums[i]+nums[left]+nums[right];if(sum==0){ans.add(new ArrayList(Arrays.asList(nums[i],nums[left],nums[right])));}if(sum>0){while(left<right&&nums[right]==nums[--right]);}else{while(left<right&&nums[left]==nums[++left]);}}}return ans;    }
}

class Solution {public int trap(int[] height) {int ans = 0;int[] maxleft = new int[height.length];int[] maxright = new int[height.length];for (int i = 1; i < height.length; i++) {maxleft[i] = Math.max(height[i - 1], maxleft[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {maxright[i] = Math.max(maxright[i + 1], height[i + 1]);}for (int i = 1; i < height.length; i++) {int h = Math.min(maxleft[i], maxright[i]);if (h > height[i]) {ans += h - height[i];}}return ans;}
}

class Solution {public int lengthOfLongestSubstring(String s) {int count=0,left=0;HashMap<Character,Integer> map=new HashMap<>();for(int i=0;i<s.length();i++){if(map.containsKey(s.charAt(i))){left=Math.max(left,map.get(s.charAt(i))+1);}count=Math.max(count,i-left+1);map.put(s.charAt(i),i);}return count;}
}

class Solution {public List<Integer> findAnagrams(String s, String p) {int len = p.length();List<Integer> ans = new ArrayList<>();char[] pc = p.toCharArray();Arrays.sort(pc);String key = String.valueOf(pc);for (int i = 0; i <= s.length() - len; i++) {char[] sc = s.substring(i, i + len).toCharArray();Arrays.sort(sc);if (key.equals(String.valueOf(sc))) {ans.add(i);}}return ans;}
}

class Solution {public int subarraySum(int[] nums, int k) {int sum=0,ans=0;HashMap<Integer,Integer> map=new HashMap<>();map.put(0,1);for(int i=0;i<nums.length;i++){sum+=nums[i];if(map.containsKey(sum-k)){ans+=map.get(sum-k);}map.put(sum,map.getOrDefault(sum,0)+1);}return ans;}
}

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length==0||k==0)return new int[0];int[] res=new int[nums.length-k+1];Deque<Integer> deque=new LinkedList<>();for(int i=0,j=1-k;i<nums.length;i++,j++){if(j>0&&deque.peekFirst()==nums[j-1]){deque.removeFirst();}while(!deque.isEmpty()&&deque.peekLast()<nums[i]){deque.removeLast();}deque.addLast(nums[i]);if(j>=0){res[j]=deque.peekFirst();}}return res;}
}

class Solution {public int maxSubArray(int[] nums) {int pre=0,ans=Integer.MIN_VALUE;for(int x:nums){pre=Math.max(pre+x,x);ans=Math.max(ans,pre);}return ans;}
}

class Solution {public int[][] merge(int[][] intervals) {List<int[]> ans=new ArrayList<>();Arrays.sort(intervals,(a,b)->{return a[0]-b[0];});for(int i=0;i<intervals.length;i++){if(i<intervals.length-1&& intervals[i][1]>=intervals[i+1][0]){intervals[i+1][0]=intervals[i][0];intervals[i+1][1]=Math.max(intervals[i][1],intervals[i+1][1]);}else{ans.add(intervals[i]);}}return ans.toArray(new int[0][]);}
}

class Solution {public void rotate(int[] nums, int k) {int count=nums.length-k%nums.length-1;reverse(nums,0,count);reverse(nums,count+1,nums.length-1);reverse(nums,0,nums.length-1);   }void reverse(int[] nums,int left,int right){while(left<right){int temp=nums[right];nums[right]=nums[left];nums[left]=temp;left++;right--;}}
}

class Solution {public int[] productExceptSelf(int[] nums) {int len=nums.length;int[] ans=new int[len];int[] L=new int[len];int[] R=new int[len];L[0]=1;for(int i=1;i<len;i++){L[i]=L[i-1]*nums[i-1];}R[len-1]=1;for(int i=len-2;i>=0;i--){R[i]=nums[i+1]*R[i+1];}for(int i=0;i<len;i++){ans[i]=L[i]*R[i];}return ans;}
}

class Solution {public int firstMissingPositive(int[] nums) {// 处理数组为空的情况if (nums == null || nums.length == 0) {return 1;}// 第一次遍历，将元素放到正确的位置for (int i = 0; i < nums.length; i++) {while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}// 第二次遍历，检查元素是否在正确位置for (int i = 1; i <= nums.length; i++) {if (nums[i - 1] != i) {return i;}}// 如果前面都没有找到缺失的正整数，那么缺失的就是数组长度加 1return nums.length + 1;}
}

class Solution {public void setZeroes(int[][] matrix) {boolean[] row=new boolean[matrix.length];boolean[] col=new boolean[matrix[0].length];for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[0].length;j++){if(matrix[i][j]==0){row[i]=true;col[j]=true;}}}for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[0].length;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}
}

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> ans = new ArrayList<>();int up = 0, down = matrix.length - 1, left = 0, right = matrix[0].length - 1;while (true) {for (int i = left; i <= right; i++) {ans.add(matrix[up][i]);}up++;if (up > down)break;for (int i = up; i <= down; i++) {ans.add(matrix[i][right]);}right--;if (right < left)break;for (int i = right; i >= left; i--) {ans.add(matrix[down][i]);}down--;if (down < up)break;for (int i = down; i >= up; i--) {ans.add(matrix[i][left]);}left++;if (left > right)break;}return ans;}
}

class Solution {public void rotate(int[][] matrix) {int n=matrix.length-1;int[][] temp=new int[matrix.length][matrix.length];for(int i=0;i<matrix.length;i++){temp[i]=matrix[i].clone();}for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[0].length;j++){matrix[j][n-i]=temp[i][j];}}}
}

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i=0,j=matrix[0].length-1;while(j>=0&&i<matrix.length){if(target==matrix[i][j]){return true;}else if(target>matrix[i][j]){i++;}else{j--;}}return false;}
}

链表部分：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode l1=headA;ListNode l2=headB;while(l1!=l2){l1=l1==null?headB:l1.next;l2=l2==null?headA:l2.next;}return l1;}
}

class Solution {public ListNode reverseList(ListNode head) {ListNode cur=head,p=null;while(cur!=null){ListNode temp=cur.next;cur.next=p;p=cur;cur=temp;}return p;   }
}

/*** 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 boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}//快慢指针找到中间节点ListNode fast = head, slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}// 翻转后半部分链表ListNode prev = null;ListNode cur = slow.next;while (cur != null) {ListNode temp = cur.next;cur.next = prev;prev = cur;cur = temp;}//分别从链表开头与翻转后的中间节点开始向后比较ListNode p1 = head;ListNode p2 = prev;while (p2 != null) {if (p1.val != p2.val) {return false;}p1 = p1.next;p2 = p2.next;}return true;}
}

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}
}

public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set=new HashSet<>();ListNode cur=head;while(cur!=null){if(set.contains(cur)){return cur;}else{set.add(cur);}cur=cur.next;}return null;}
}

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p=list1,q=list2;ListNode prehead = new ListNode(-1);ListNode prev = prehead;while(p!=null&&q!=null){if(p.val<=q.val){prev.next=p;p=p.next;}else{prev.next=q;q=q.next;}prev=prev.next;}prev.next = p == null ? q : p;return prehead.next;}
}

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre = new ListNode(0);ListNode cur = pre;int carry=0;while(l1!=null||l2!=null){int a=l1==null?0:l1.val;int b=l2==null?0:l2.val;cur.next=new ListNode((a+b+carry)%10);carry=(a+b+carry)/10;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;// 移动到结果链表的下一个节点cur = cur.next;}if(carry==1)cur.next=new ListNode(1);return pre.next;}
}

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dump=new ListNode(0);dump.next=head;ListNode slow=dump,fast=dump;while(n>0){fast=fast.next;n--;}while(fast.next!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;return dump.next;}
}

class Solution {public ListNode swapPairs(ListNode head) {ListNode node=new ListNode(-1,head);ListNode pre=node;while(pre.next!=null&&pre.next.next!=null){ListNode l1=pre.next,l2=pre.next.next;l1.next=l2.next;l2.next=l1;pre.next=l2;pre=l1;}return node.next;}
}

class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k <= 1)return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode prevGroupTail = dummy;int n = countNodes(head);while (n >= k) {ListNode groupHead = prevGroupTail.next;ListNode cur = groupHead;ListNode pre = null;for (int i = 0; i < k; i++) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}prevGroupTail.next = pre;groupHead.next = cur;prevGroupTail = groupHead;n -= k;}return dummy.next;}private int countNodes(ListNode head) {int count = 0;// 遍历链表并计算节点数while (head != null) {count++;head = head.next;}return count;}
}

class Solution {public Node copyRandomList(Node head) {HashMap<Node,Node> map=new HashMap<>();Node cur=head;while(cur!=null){map.put(cur,new Node(cur.val));cur=cur.next;}cur=head;while(cur!=null){map.get(cur).next=map.get(cur.next);map.get(cur).random=map.get(cur.random);cur=cur.next;}return map.get(head);}
}

class Solution {public ListNode sortList(ListNode head) {if(head==null||head.next==null)return head;ListNode slow=head;ListNode fast=head;while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}ListNode nhead=slow.next;slow.next=null;ListNode left= sortList(head);ListNode right=sortList(nhead);ListNode dummy=new ListNode(-1);ListNode cur=dummy;while(left!=null&&right!=null){if(left.val<right.val){cur.next=left;left=left.next;}else{cur.next=right;right=right.next;}cur=cur.next;}cur.next=left==null?right:left;return dummy.next;}
}

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists==null||lists.length==0)return null;PriorityQueue<ListNode> queue=new PriorityQueue<>(lists.length,Comparator.comparingInt(o->o.val));for(ListNode node:lists){if(node!=null)queue.add(node);}ListNode pre=new ListNode(-1);ListNode p=pre;while(!queue.isEmpty()){p.next=queue.poll();p=p.next;if(p.next!=null)queue.add(p.next);}return pre.next;}
}

class LRUCache {HashMap<Integer,Node> map=new LinkedHashMap<>();int _capacity;Node head,tail;class Node{int key;int values;Node pre;Node next;Node(int _key,int _values){key=_key;values=_values;}}public LRUCache(int capacity) {_capacity=capacity;head=new Node(-1,-1);tail=new Node(-1,-1);head.next=tail;tail.pre=head;}public int get(int key) {if(map.containsKey(key)){Node node=map.get(key);cutNode(node);insert(node);return node.values;}else{return -1;}}public void put(int key, int value) {if(map.containsKey(key)){Node node=map.get(key);node.values=value;cutNode(node);insert(node);}else{Node newNode=new Node(key,value);map.put(key,newNode);insert(newNode);if(map.size()>_capacity){Node node=cuttail();map.remove(node.key);}}}void cutNode(Node node){node.pre.next=node.next;node.next.pre=node.pre;node.pre=null;node.next=null;}void insert(Node node){node.next=head.next;head.next.pre=node;head.next=node;node.pre=head;}Node cuttail(){Node last=tail.pre;last.pre.next=tail;tail.pre=last.pre;last.pre=null;last.next=null;return last;}
}

树的定义：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}

class Solution {public int maxDepth(TreeNode root) {if(root==null){return 0;}int maxleft=maxDepth(root.left);int maxright=maxDepth(root.right);return Math.max(maxleft,maxright)+1;}
}

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null)return null;TreeNode left=invertTree(root.left);TreeNode right=invertTree(root.right);root.left=right;root.right=left;return root;}
}

class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}public boolean check(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if ((p == null || q == null)||(p.val != q.val)) {return false;}return  check(p.left, q.right) && check(p.right, q.left);}
}

class Solution {int ans;public int diameterOfBinaryTree(TreeNode root) {ans = 1;depth(root);return ans - 1;}public int depth(TreeNode node) {if (node == null) {return 0; // 访问到空节点了，返回0}int L = depth(node.left); // 左儿子为根的子树的深度int R = depth(node.right); // 右儿子为根的子树的深度ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ansreturn Math.max(L, R) + 1; // 返回该节点为根的子树的深度}
}

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();Queue<TreeNode> queue=new LinkedList<>();if(root!=null)queue.offer(root);while(!queue.isEmpty()){List<Integer> tem=new ArrayList<>();for(int qsize=queue.size();qsize>0;qsize--){TreeNode node=queue.poll();if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);tem.add(node.val);}res.add(tem);}return res;}
}

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node == null) {return true;}if (node.val <= lower || node.val >= upper) {return false;}return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);}
}

class Solution {int count, ans;public int kthSmallest(TreeNode root, int k) {count = k;inOrder(root);return ans;}void inOrder(TreeNode root) {if (root == null || count == 0)return;inOrder(root.left);count--;if (count == 0) {ans = root.val;return;}inOrder(root.right);}
}

class Solution {List<Integer> ans = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {dfs(root, 0);return ans;}private void dfs(TreeNode root, int depth) {if (root == null) return;if (depth == ans.size()) ans.add(root.val);dfs(root.right, depth + 1);dfs(root.left, depth + 1);}
}

class Solution {public void flatten(TreeNode root) {if (root == null) {return;}Stack<TreeNode> s = new Stack<TreeNode>();s.push(root);TreeNode pre = null;while (!s.isEmpty()) {TreeNode temp = s.pop();// 将指针的柚子树指向当前节点if (pre != null) {pre.right = temp;pre.left = null;}if (temp.right != null) {s.push(temp.right);}if (temp.left != null) {s.push(temp.left);}// 将指针移动到当前位置pre = temp;}}
}

class Solution {Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return buildTwo(preorder,0,preorder.length-1,0,inorder.length-1);}TreeNode buildTwo(int[] preorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){if(preorder_left>preorder_right)return null;TreeNode root=new TreeNode(preorder[preorder_left]);int pindex=map.get(preorder[preorder_left]);root.left=buildTwo(preorder,preorder_left+1,pindex-1-inorder_left+preorder_left+1,inorder_left,pindex-1);root.right=buildTwo(preorder,pindex-1-inorder_left+preorder_left+1+1,preorder_right,pindex+1,inorder_right);return root;}
}

class Solution {int ans=0;HashMap<Long,Integer> map=new HashMap<>();public int pathSum(TreeNode root, int targetSum) {map.put(0L,1);dfs(root,targetSum,0L);return ans;}void dfs(TreeNode root,int targetSum,Long sum){if(root==null)return ;sum+=root.val;ans+=map.getOrDefault(sum-targetSum,0);map.put(sum,map.getOrDefault(sum,0)+1);dfs(root.left,targetSum,sum);dfs(root.right,targetSum,sum);map.put(sum,map.getOrDefault(sum,0)-1);return;}
}

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null||root==p||root==q)return root;TreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);if(left==null&&right==null){return null;}if(left==null){return right;}if(right==null){return left;}return root;}
}

class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node) {if (node == null) {return 0;}// 递归计算左右子节点的最大贡献值// 只有在最大贡献值大于 0 时，才会选取对应子节点int leftGain = Math.max(maxGain(node.left), 0);int rightGain = Math.max(maxGain(node.right), 0);// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值int priceNewpath = node.val + leftGain + rightGain;// 更新答案maxSum = Math.max(maxSum, priceNewpath);// 返回节点的最大贡献值return node.val + Math.max(leftGain, rightGain);}
}

class Solution {private int res;public int numIslands(char[][] grid) {res = 0;for (int i = 0; i < grid.length; i ++) {for (int j = 0; j < grid[0].length; j ++) {if (grid[i][j] == '1') {dfsGrid(grid, i, j);res ++;}}}return res;}private void dfsGrid(char[][] grid, int row, int col) {if (row<0 || col<0 || row >= grid.length || col >= grid[0].length || grid[row][col] != '1' )return;grid[row][col] = '0';dfsGrid(grid, row - 1, col);dfsGrid(grid, row + 1, col);dfsGrid(grid, row, col - 1);dfsGrid(grid, row, col + 1);}
}

class Solution {int freshCount=0;public int orangesRotting(int[][] grid) {int row=grid.length;int col=grid[0].length;Queue<int[]> queue=new LinkedList<>();for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]==1){freshCount++;}else if(grid[i][j]==2){queue.add(new int[]{i,j});}}}int round=0;while(freshCount>0&&!queue.isEmpty()){round++;int n=queue.size();for(int i=0;i<n;i++){int[] orange=queue.poll();int x=orange[0];int y=orange[1];if(x-1>=0&&grid[x-1][y]==1){grid[x-1][y]=2;freshCount--;queue.add(new int[]{x-1,y});}if(x+1<row&&grid[x+1][y]==1){grid[x+1][y]=2;freshCount--;queue.add(new int[]{x+1,y});}if(y-1>=0&&grid[x][y-1]==1){grid[x][y-1]=2;freshCount--;queue.add(new int[]{x,y-1});}if(y+1<col&&grid[x][y+1]==1){grid[x][y+1]=2;freshCount--;queue.add(new int[]{x,y+1});}}}if(freshCount>0){return -1;}else{return round;}}
}

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 入度数组，用于记录每门课程的入度int[] inDegree=new int[numCourses];// 邻接表，存储每门课程的后续课程List<List<Integer>> adjList=new ArrayList<>();for(int i=0;i<numCourses;i++){adjList.add(new ArrayList<>());}// 计算每门课程的入度，并构建邻接表for(int[] course:prerequisites){inDegree[course[0]]++;adjList.get(course[1]).add(course[0]);}// 存储入度为 0 的课程的队列Queue<Integer> queue=new LinkedList<>();for(int i=0;i<numCourses;i++){if(inDegree[i]==0){queue.offer(i);}}// 记录已完成课程的数量int count=0;while(!queue.isEmpty()){int selectCourse=queue.poll();count++;// 获取当前课程的后续课程列表for(int x:adjList.get(selectCourse)){// 后续课程的入度减 1,将入度为0的加入队列inDegree[x]--;if(inDegree[x]==0){queue.offer(x);}}}if(count==numCourses)return true;return false;}
}

class Trie {class treeNode{boolean island;treeNode[] child;treeNode(){island=false;child=new treeNode[26];}}treeNode root;public Trie() {root=new treeNode();}public void insert(String word) {treeNode node=root;for(char i:word.toCharArray()){if(node.child[i-'a']==null){node.child[i-'a']=new treeNode();}node=node.child[i-'a'];}node.island=true;}public boolean search(String word) {treeNode node=root;for(char c:word.toCharArray()){if(node.child[c-'a']==null){return false;}node=node.child[c-'a'];}return node.island;}public boolean startsWith(String prefix) {treeNode node=root;for(char c:prefix.toCharArray()){if(node.child[c-'a']==null){return false;}node=node.child[c-'a'];}return true;}
}

class Solution {List<List<Integer>> res = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {var track = new ArrayList<Integer>();backtrack(nums, track);return res;}private void backtrack(int[] nums, ArrayList<Integer> track) {if(track.size() == nums.length) {res.add(new ArrayList<Integer>(track));return;}int n = nums.length;for(int i = 0; i < n; ++i) {if(track.contains(nums[i]))continue;track.add(nums[i]);backtrack(nums, track);track.removeLast();}}
}

class Solution {private final List<List<Integer>> ans = new ArrayList<>();private final List<Integer> path = new ArrayList<>();private int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;dfs(0);return ans;}private void dfs(int i) {if (i == nums.length) { // 子集构造完毕ans.add(new ArrayList<>(path)); // 复制 pathreturn;}// 不选 nums[i]dfs(i + 1);// 选 nums[i]path.add(nums[i]);dfs(i + 1);path.remove(path.size() - 1); // 恢复现场}
}

class Solution {Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};List<String> ans = new ArrayList<String>();public List<String> letterCombinations(String digits) {if(digits.length()==0)return ans;breakf(digits,0,new StringBuilder());return ans;}void breakf(String digits,int start,StringBuilder temp){if(start==digits.length()){ans.add(String.valueOf(temp));return;}char c=digits.charAt(start);String value=phoneMap.get(c);for(int i=0;i<value.length();i++){temp.append(value.charAt(i));breakf(digits,start+1,temp);temp.deleteCharAt(temp.length()-1);}}
}

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,target,0);return res;}void dfs(int[] candidates, int target,int begin){if(target==0){res.add(new ArrayList(path));return;}if(target<0)return;for(int i=begin;i<candidates.length;i++){path.add(candidates[i]);dfs(candidates,target-candidates[i],i);path.removeLast();}}
}

class Solution {StringBuilder s=new StringBuilder();List<String> res=new ArrayList<String>();public List<String> generateParenthesis(int n) {dfs(n,0,0);return res;}public void dfs(int n,int left,int right){if(left==n&&right==n){res.add(String.valueOf(s));}if(left<n){s.append('(');dfs(n,left+1,right);s.deleteCharAt(s.length()-1);}if(right<left){s.append(')');dfs(n,left,right+1);s.deleteCharAt(s.length()-1);}}
}

class Solution {public boolean exist(char[][] board, String word) {if (board.length == 0) {return false;}char[] chars = word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] != chars[0])continue;if (dfs(i, j, board, 0, chars)) {return true;}}}return false;}private boolean dfs(int x, int y, char[][] board, int index, char[] chars) {if (x < 0 || x > board.length - 1 ||y < 0 || y > board[0].length - 1 ||board[x][y] != chars[index]) {return false;}if (index == chars.length - 1) {return true;}board[x][y] = '\0';if (dfs(x + 1, y, board, index + 1, chars) || dfs(x - 1, y, board, index + 1, chars)|| dfs(x, y + 1, board, index + 1, chars) || dfs(x, y - 1, board, index + 1, chars))return true;board[x][y] = chars[index];return false;}
}

class Solution {private final List<List<String>> ans = new ArrayList<>();private final List<String> path = new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s = s;dfs(0, 0);return ans;}// start 表示当前这段回文子串的开始位置private void dfs(int i, int start) {if (i == s.length()) {ans.add(new ArrayList<>(path)); // 复制 pathreturn;}// 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）if (i < s.length() - 1) {dfs(i + 1, start);}// 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）if (isPalindrome(start, i)) {path.add(s.substring(start, i + 1));dfs(i + 1, i + 1); // 下一个子串从 i+1 开始path.remove(path.size() - 1); // 恢复现场}}private boolean isPalindrome(int left, int right) {while (left < right) {if (s.charAt(left++) != s.charAt(right--)) {return false;}}return true;}
}

class Solution {public int searchInsert(int[] nums, int target) {int left=0,right=nums.length-1;while(left<=right){int mid=(right-left)/2+left;if(nums[mid]==target)return mid;if(nums[mid]>=target){right=mid-1;}if(nums[mid]<target){left=mid+1;}}return left;}
}

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n=matrix[0].length;int left=0,right=matrix.length*n-1;while(left<=right){int mid=(right-left)/2+left;int temp=matrix[mid/n][mid%n];if(temp==target)return true;if(temp>target){right=mid-1;}else{left=mid+1;}}return false;}
}

class Solution {/*** 二分查找*/public int[] searchRange(int[] nums, int target) {//寻找左边界(这里寻找第一个 >= target的索引)int leftIndex = search(nums, target);if (leftIndex >= nums.length || nums[leftIndex] != target){return new int[]{-1, -1};}//寻找右边界(这里寻找第一个 >= target+1的索引)int rightIndex = search(nums, target + 1);return new int[]{leftIndex, rightIndex - 1};}/*** 寻找第一个>=目标值的索引, 找不到则返回数组长度*/private int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right){int mid = (right - left) / 2 + left;if (nums[mid] >= target){right = mid - 1;} else {left = mid + 1;}}return left;}
}

class Solution {public int search(int[] nums, int target) {int len = nums.length;if(len == 0) return -1;int left = 0, right = len - 1;// 1. 首先明白，旋转数组后，从中间划分，一定有一边是有序的。// 2. 由于一定有一边是有序的，所以根据有序的两个边界值来判断目标值在有序一边还是无序一边// 3. 这题找目标值，遇到目标值即返回// 4. 注意：由于有序的一边的边界值可能等于目标值，所以判断目标值是否在有序的那边时应该加个等号(在二分查找某个具体值得时候如果把握不好边界值，可以再每次查找前判断下边界值，也就是while循环里面的两个if注释)while(left <= right){// if(nums[left] == target) return left;// if(nums[right] == target) return right;int mid = left + (right - left) / 2;if(nums[mid] == target) return mid;// 右边有序if(nums[mid] < nums[right]){// 目标值在右边if(target > nums[mid] && target <= nums[right]){left = mid + 1;// 目标值在左边}else{right = mid - 1;}// 左边有序}else{// 目标值在左边if(target >= nums[left] && target < nums[mid]){right = mid - 1;// 目标值在右边}else{left = mid + 1;}}}return -1;}
}