Hot100
二叉树
给定一个二叉树的根节点
root，返回 它的 中序 遍历class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stk = new Stack<TreeNode>(); while (root != null || !stk.isEmpty()) { while (root != null) { stk.push(root); root = root.left; } root = stk.pop(); res.add(root.val); root = root.right; } return res; } }思考中序过程就行
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
class Solution { public int maxDepth(TreeNode root) { return Depth(root); } public int Depth(TreeNode root){ if(root==null){ return 0; } int left=Depth(root.left); int right=Depth(root.right); return Math.max(left,right)+1; } }给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点class Solution { public TreeNode invertTree(TreeNode root) { if(root==null)return root; TreeNode left=invertTree(root.left); TreeNode right=invertTree(root.right); root.left=right; root.right=left; return root; } }给你一个二叉树的根节点
root， 检查它是否轴对称class Solution { public boolean isSymmetric(TreeNode root) { return check(root.left,root.right); } public boolean check(TreeNode p1,TreeNode p2){ if(p1==null&&p2==null)return true; if(p1==null||p2==null||p1.val!=p2.val)return false; return check(p1.left,p2.right)&&check(p1.right,p2.left); } }给你一棵二叉树的根节点，返回该树的 直径
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点
root。两节点之间路径的 长度 由它们之间边数表示
class Solution { int res=0; public int diameterOfBinaryTree(TreeNode root) { Depth(root); return res; } public int Depth(TreeNode root){ if(root==null){ return 0; } int left=Depth(root.left); int right=Depth(root.right); int len=left+right; this.res=Math.max(res,len); return Math.max(left,right)+1; } }给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> cur=new ArrayList<>(); Queue<TreeNode> queue=new LinkedList<>(); if(root!=null){ queue.add(root); } while(!queue.isEmpty()){ int n=queue.size(); List<Integer> level=new ArrayList<>(); for(int i=0;i<n;i++){ TreeNode node=queue.poll(); level.add(node.val); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } cur.add(level); } return cur; } }给你一个整数数组
nums，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sort(nums,0,nums.length-1); } public TreeNode sort(int[] nums,int l,int r){ if(l>r){ return null; } int mid=l+(r-l)/2; TreeNode root = new TreeNode(nums[mid]); root.left=sort(nums,l,mid-1); root.right=sort(nums,mid+1,r); return root; } }给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==p||root==q||root==null){ return root; } TreeNode left=lowestCommonAncestor(root.left,p,q); TreeNode right=lowestCommonAncestor(root.right,p,q); if(left!=null&&right!=null){ return root; } return left!=null?left:right; } }左右树都是空不管了，说明root太低了，也不应该有返回结果，就不返回了
二分查找
模板主要是 左闭右开原则
private int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length; // 左闭右开区间 [left, right)
while (left < right) { // 区间不为空
// 循环不变量：
// nums[left-1] < target =< nums[right]
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 范围缩小到 [left, mid)
} else {
left = mid + 1; // 范围缩小到 [mid+1, right)
}
}
// 循环结束后 left = right
// 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
// 所以 left 就是第一个 >= target 的元素下标
return left;
}
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
class Solution { public int searchInsert(int[] nums, int target) { int left=0,right=nums.length; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]==target){ right=mid; }else if(nums[mid]>target){ right=mid; }else{ left=mid+1; } } return left; } }给你一个满足下述两条属性的
m x n整数矩阵：- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target，如果target在矩阵中，返回true；否则，返回falseclass Solution { public boolean searchMatrix(int[][] matrix, int target) { int i=0,j=matrix[0].length-1; while(i<matrix.length&&j>=0){ if(matrix[i][j]==target){ return true; }else if(matrix[i][j]>target){ j--; }else{ i++; } } return false; } }给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length==0){ return new int[]{-1,-1}; } int left=left_N(nums,target); int right=right_N(nums,target); return new int[]{left,right}; } public int left_N(int[]nums,int target){ int l=0,r=nums.length; while(l<r){ int mid=l+(r-l)/2; if(nums[mid]>target){ r=mid; }else if(nums[mid]<target){ l=mid+1; }else{ r=mid; } } if(l==nums.length||nums[l]!=target){ return -1; } return l; } public int right_N(int[]nums,int target){ int l=0,r=nums.length; while(l<r){ int mid=l+(r-l)/2; if(nums[mid]>target){ r=mid; }else if(nums[mid]<target){ l=mid+1; }else{ l=mid+1; } } if(l==0||nums[r-1]!=target){ return -1; } return l-1; } }整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1class Solution { public int search(int[] nums, int target) { int start=0,end=nums.length-1; while(start<=end){ int mid=start+(end-start)/2; if(nums[mid]==target){ return mid; } if(nums[mid]>=nums[start]){ if(target>=nums[start]&&nums[mid]>target){ end=mid-1; }else{ start=mid+1; } }else{ if(target<nums[start]&&nums[mid]<target){ start=mid+1; }else{ end=mid-1; } } } return -1; } }画一个简易线条，思考最好控制的变量条件就行
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素class Solution { public int findMin(int[] nums) { int l=0,r=nums.length-1; while(l<r){ int mid=l+((r-l)>>1); if(nums[mid]<=nums[r]){ r=mid; }else{ l=mid+1; } } return nums[l]; } }- 若旋转
动态规划
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？class Solution { public int climbStairs(int n) { if(n<2){ return n; } int []dp=new int[n+1]; dp[1]=1; dp[2]=2; for(int i=3;i<dp.length;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; } }你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
class Solution { public int rob(int[] nums) { if(nums.length==1){ return nums[0]; } int[] dp=new int[nums.length]; dp[0]=nums[0]; dp[1]=Math.max(nums[1],nums[0]); for(int i=2;i<dp.length;i++){ dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]); } return dp[nums.length-1]; } }给你一个整数
n，返回 和为n的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，
1、4、9和16都是完全平方数，而3和11不是class Solution { public int numSquares(int n) { int []dp=new int[n+1]; for(int i=1;i<=n;i++){ dp[i]=i; for(int j=1;i-j*j>=0;j++){ dp[i]=Math.min(dp[i],dp[i-j*j]+1); } } return dp[n]; } }给你一个整数数组
coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
-1。你可以认为每种硬币的数量是无限的
class Solution { public int coinChange(int[] coins, int amount) { int[]dp=new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0; for(int i=0;i<dp.length;i++){ for(int coin:coins){ if(i<coin){ continue; } dp[i]=Math.min(dp[i],dp[i-coin]+1); } } return dp[amount]==amount+1?-1:dp[amount]; } }给你一个字符串
s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用
class Solution { public boolean wordBreak(String s, List<String> wordDict) { int len=s.length(); boolean[] dp=new boolean[len+1]; dp[0]=true; for(int i=1;i<=len;i++){ for(int j=0;j<i;j++){ if(wordDict.contains(s.substring(j,i))&&dp[j]){ dp[i]=true; break; } } } return dp[len]; } }给你一个整数数组
nums，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列class Solution { public int lengthOfLIS(int[] nums) { int n=nums.length; int[] dp=new int[n]; Arrays.fill(dp,1); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ dp[i]=Math.max(dp[i],dp[j]+1); } } } int res=0; for(int i=0;i<n;i++){ res=Math.max(res,dp[i]); } return res; } }给你一个整数数组
nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数
class Solution { public int maxProduct(int[] nums) { int max=1,min=1; int res=Integer.MIN_VALUE; for(int i=0;i<nums.length;i++){ if(nums[i]<=0){ int temp=min; min=max; max=temp; } max=Math.max(max*nums[i],nums[i]); min=Math.min(min*nums[i],nums[i]); res=Math.max(res,max); } return res; } }最小数：为负数时，在遇到负数就为最大
最大数：为正数时，一致遇到正数为最大
给你一个只包含
'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度class Solution { public int longestValidParentheses(String s) { if(s.length()<=1){ return 0; } int[]dp=new int[s.length()+1];//以第i个字符结尾最多有长度 Stack<Integer>stack=new Stack<>(); for(int i=0;i<s.length();i++){ char c=s.charAt(i); if(c=='('){ stack.add(i); }else{ if(!stack.isEmpty()){ int leftIndex=stack.pop(); int len=(i-leftIndex+1)+dp[leftIndex];//之间长度+第leftIndex字符结尾长度 dp[i+1]=len;//字符索引为i,为第(i+1)个字符;若连续，会被当做字符索引为(i+1)字符，为下一次计算 } } } int res = 0; for (int i = 0; i < dp.length; i++) { res = Math.max(res, dp[i]); } return res; } }从概念上好理解，长度=第left字符末尾长度+之间长度
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等class Solution { public boolean canPartition(int[] nums) { int sum=0,len=nums.length; for(int num:nums){ sum+=num; } if(sum%2==1){ return false; } sum=sum/2; boolean [][]dp=new boolean[len+1][sum+1];//在前i个数中，是否有和为j？ for(int i=0;i<=len;i++){ dp[i][0]=true; } for(int i=1;i<=len;i++){ for(int j=1;j<=sum;j++){ if(j<nums[i-1]){//和太小，自然按前一个就行 dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];//加入这数字或不加入这数字 } } } return dp[len][sum]; } }
多维动态规划
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）
问总共有多少条不同的路径?
class Solution { public int uniquePaths(int m, int n) { int[][]dp=new int[m][n]; for(int i=0;i<m;i++) dp[i][0]=1; for(int j=0;j<n;j++) dp[0][j]=1; for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; } }给定一个包含非负整数的
*m* x *n*网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步
class Solution { public int minPathSum(int[][] grid) { int m=grid.length; int n=grid[0].length; int dp[][]=new int[m][n]; dp[0][0]=grid[0][0]; for(int i=1;i<m;i++){ dp[i][0]=grid[i][0]+dp[i-1][0]; } for(int j=1;j<n;j++){ dp[0][j]=grid[0][j]+dp[0][j-1]; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[m-1][n-1]; } }给你一个字符串
s，找到s中最长的 回文 子串子字符串 是字符串中连续的 非空 字符序列
class Solution { public String longestPalindrome(String s) { String res = ""; for (int i = 0; i < s.length(); i++) { // 以 s[i] 为中心的最长回文子串 String s1 = palindrome(s, i, i); // 以 s[i] 和 s[i+1] 为中心的最长回文子串 String s2 = palindrome(s, i, i + 1); // res = longest(res, s1, s2) res = res.length() > s1.length() ? res : s1; res = res.length() > s2.length() ? res : s2; } return res; } String palindrome(String s, int l, int r) { // 防止索引越界 while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { // 向两边展开 l--; r++; } // 返回以 s[l] 和 s[r] 为中心的最长回文串 return s.substring(l + 1, r); } }给定两个字符串
text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回0。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m=text1.length(); int n=text2.length(); int len=Math.max(m,n); int[][] dp=new int[m+1][n+1];//以第i与第j为结尾的字符，有dp[i][j]个公众序列 for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ char c1=text1.charAt(i-1); char c2=text2.charAt(j-1); if(c1==c2){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; } }- 例如，
给你两个单词
word1和word2， 请返回将word1转换成word2所使用的最少操作数 。你可以对一个单词进行如下三种操作：
- 插入一个字符；删除一个字符；替换一个字符
class Solution { public int minDistance(String word1, String word2) { int m=word1.length(); int n=word2.length(); int [][]dp=new int[m+1][n+1];//前i个字符串到前j个字符串需要步数 for(int i=0;i<=m;i++){ dp[i][0]=i;//删除 } for(int i=0;i<=n;i++){ dp[0][i]=i;//增加 } for(int i=1;i<=m;i++){ char c1=word1.charAt(i-1); for(int j=1;j<=n;j++){ char c2=word2.charAt(j-1); if(c1==c2){ dp[i][j]=dp[i-1][j-1];//相等，不需要改变 }else{ dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1; //不相等，就需要一次改变;按顺序改变分别为:删除，替换，增加 //删除:(i,j)不同，需要i被删，自然(i-1,j)为基础来操作 //替换:(i,j)不同，需要i在变为j，自然以(i-1,j-1)为基础， //增加:(i,j)不同，需要增一个变为j，自然以(i,j-1)为基础来操作 } } } return dp[m][n]; } }给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
class Solution { int[][]nex=new int[][]{{-1,0},{0,1},{1,0},{0,-1}}; int m,n; public boolean exist(char[][] board, String word) { this.m=board.length; this.n=board[0].length; boolean[][]visited=new boolean[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(dfs(board,0,word,i,j,visited)){ return true; } } } return false; } public boolean dfs(char[][] board,int len,String word,int startx,int starty,boolean[][]visited){ if(len==word.length()){ return true; } if(startx<0||starty<0||startx>=m||starty>=n||visited[startx][starty]||board[startx][starty]!=word.charAt(len)){ return false; } visited[startx][starty]=true; for(int ne[]:nex){ if(dfs(board,len+1,word,startx+ne[0],starty+ne[1],visited)){ return true; } } visited[startx][starty]=false; return false; } }数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合class Solution { List<String>res; public List<String> generateParenthesis(int n) { res=new LinkedList<>(); f(n,"",0,0); return res; } public void f(int n,String s,int l,int r){ if(l==n&&r==n){ res.add(s); } if(l>n||r>n||l<r){ return; } f(n,s+"(",l+1,r); f(n,s+")",l,r+1); } }
栈
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈实现
MinStack类:MinStack()初始化堆栈对象void push(int val)将元素val推入堆栈void pop()删除堆栈顶部的元素int top()获取堆栈顶部的元素int getMin()获取堆栈中的最小元素
class MinStack { Stack<Integer>stack1; Stack<Integer>stack2; public MinStack() { stack1=new Stack<>(); stack2=new Stack<>(); } public void push(int val) { if(stack1.isEmpty()){ stack1.push(val); stack2.push(val); }else{ if(val>stack2.peek()){ int t=stack2.peek(); stack2.push(t); }else{ stack2.push(val); } stack1.push(val); } } public void pop() { stack1.pop(); stack2.pop(); } public int top() { return stack1.peek(); } public int getMin() { return stack2.peek(); } }给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
class Solution { public boolean isValid(String s) { if(s.length()==1){ return false; } Stack<Character>had=new Stack<>(); char c1=s.charAt(0); if(c1==')'||c1=='}'||c1==']'){ return false; } had.add(c1); for(int i=1;i<s.length();i++){ char c2=s.charAt(i); if(c2=='['||c2=='{'||c2=='('){ had.add(c2); }else{ char c3=' '; if(had.isEmpty()){ return false; }else{ c3=had.pop(); } if((c3=='['&&c2==']')||(c3=='('&&c2==')')||(c3=='{'&&c2=='}')){ continue; }else{ return false; } } } return had.isEmpty(); } }
堆
给定整数数组
nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素你必须设计并实现时间复杂度为
O(n)的算法解决此问题class Solution { public int findKthLargest(int[] nums, int k) { int len=nums.length; k=len-k; int left=0,right=len-1; while(left<=right){ int tag=sort(nums,left,right); if(tag==k){ return nums[tag]; }else if(tag>k){ right=tag-1; }else{ left=tag+1; } } return -1; } public int sort(int[] nums,int left,int right){ int temp=nums[right]; int l=left,r=right; while(l<r){ while(l<r&&nums[l]<=temp){ l++; } nums[r]=nums[l]; while(l<r&&nums[r]>=temp){ r--; } nums[l]=nums[r]; } nums[l]=temp; return l; } }给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案class Solution { public int[] topKFrequent(int[] nums, int k) { // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } // 遍历map，用最小堆保存频率最大的k个元素 PriorityQueue<Integer> pq = new PriorityQueue<>( (Integer a, Integer b)-> { return map.get(a) - map.get(b);//用value比较，比的就是频率大小，但内部存储key }); for (Integer key : map.keySet()) { if (pq.size() < k) { pq.add(key); } else if (map.get(key) > map.get(pq.peek())) { pq.remove(); pq.add(key); } } // 取出最小堆中的元素 int[]res=new int[pq.size()]; int temp=0; while (!pq.isEmpty()) { res[temp++]=(pq.remove()); } return res; } }