常用的算法总结
数组 模块
两数之和
1 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap map= new HashMap<Integer,Integer>();
int[] arr=new int[2];
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int targetNum= target-nums[i];
if(map.get(targetNum)!=null&&(int)map.get(targetNum)!=0){
if(i!=(int)map.get(targetNum)){
arr[0]=i;
arr[1]=(int)map.get(targetNum);
break;
}
}]
}
return arr;
}
}
盛最多水的容器
2 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 1
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
class Solution {
public int maxArea(int[] height) {
int start=0;
int end=height.length-1;
int maxArea=0;
while(start<end){
if(height[start]<height[end]){
int max= (end-start)*height[start];
if(maxArea<max){
maxArea=max;
}
start++;
}else{
int max= (end-start)*height[end];
if(maxArea<max){
maxArea=max;
}
end--;
}
}
return maxArea;
}
}三数之和
3 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> integers = new ArrayList<>();
if (nums == null || nums.length < 3) {
return integers;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) continue; //去掉重复的情况 因为前面排序了 隔壁一样就是一样重复的
int target = -nums[i];
int left = i + 1, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
integers.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
left++;
right--;
while (left<right&&nums[left]==nums[left-1]){
left++;
}
while (left<right&&nums[right]==nums[right+1]){
right--;
}
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
}
return integers;
}
}
组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res=new ArrayList<>();
Arrays.sort(candidates);
ArrayList<Integer> path =new ArrayList();
backTrace(candidates,target,path,0); //采用回溯递归的方式
return res;
}
private void backTrace(int[] candidates,int target,ArrayList<Integer> path, int start ){
if(target==0){ //如果等于0 那么这个组合就是满足条件的 可以加入
res.add(new ArrayList(path));
return;
}
for(int i=start;i<candidates.length;i++){//对根树来说的
if(candidates[i]>target){ //如果当前都大于目标 那么就说明没有这个组合了因为 target会累加
return;
}
path.add(candidates[i]);//将这个路径放进去
backTrace(candidates,target-candidates[i],path,i);//判断这个路径相减 然后要注意i是起始的意思 有这个start的话可以做到不考虑前面的数组,注意 因为是递归也就是从树的根部开始算起的，根节点触发的才不能用前面的树 也就是说第一轮for遍历是对根数组来说的，剩下的是底部数组
path.remove(path.size()-1);//删除的是顶部的那个，这样才会回溯的效果 类似于最底部的删除重新尝试
}
}
}
螺旋矩阵
4 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int left=0;
int right=matrix[0].length-1;
int top=0;
int bottom=matrix.length-1;
List<Integer> list=new ArrayList<Integer>();
while(right>left&&bottom>top){
for(int i=left;i<=right;i++){
list.add(matrix[top][i]);
}
top++;
for(int i=top;i<=bottom;i++){
list.add(matrix[i][right]);
}
right--;
for(int i=right;i>=left;i--){
list.add(matrix[bottom][i]);
}
bottom--;
for(int i=bottom;i>=top;i--){
list.add(matrix[i][left]);
}
left++;
}
if(left<right&&top==bottom){
for(int i=left;i<=right;i++){
list.add(matrix[top][i]);
}
}
if(top<bottom&&left==right){
for(int i=top;i<=bottom;i++){
list.add(matrix[i][left]);
}
}
if(left==right&&top==bottom){
list.add(matrix[top][left]);
}
return list;
}
}
合并区间
5 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[] interval1,int[] interval2){
return interval1[0]-interval2[0];
}
});
ArrayList<int[]> list=new ArrayList<int[]>();
for(int i=0;i<intervals.length;i++){
int L=intervals[i][0];
int R=intervals[i][1];
if(list.size()==0||list.get(list.size()-1)[1]<L){
list.add(new int[]{L,R});
}else{
list.get(list.size()-1)[1]=Math.max(list.get(list.size()-1)[1],R);
}
}
return list.toArray(new int[list.size()][]);
}
}
最小路径和
6 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
输入：grid = [[1,2,3],[4,5,6]]
输出：12
class Solution {
public int minPathSum(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[][] arr=new int[m][n];
arr[0][0]=grid[0][0];
for(int i=1;i<n;i++){
arr[0][i]=arr[0][i-1]+grid[0][i];
}
for(int i=1;i<m;i++){
arr[i][0]=arr[i-1][0]+grid[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
arr[i][j]=Math.min(arr[i-1][j],arr[i][j-1])+grid[i][j];
}
}
return arr[m-1][n-1];
}
}
子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList());
for(int i=0;i<nums.length;i++){
int all =res.size();
System.out.print(all);
for(int j=0;j<all;j++){
List<Integer> tmp=new ArrayList<>(res.get(j));
tmp.add(nums[i]);
res.add(tmp);
}
}
return res;
}
}
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if(n==0){
return;
}
if(m==0){
for(int i=0;i<n;i++){
nums1[i]=nums2[i];
}
}
for(int i=m;i<m+n;i++){
nums1[i]=nums2[i-m];
}
Arrays.sort(nums1);
}
}
将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树
/**
* 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 TreeNode sortedArrayToBST(int[] nums) {
if(nums==null){
return null;
}
return getMidTree(nums,0,nums.length-1);
}
public TreeNode getMidTree(int[] nums,int left,int right){
if(left>right){
return null;
}
int mid=left+(right-left)/2;
System.out.print("mid:"+nums[mid]);
TreeNode tree= new TreeNode(nums[mid]);
tree.left=getMidTree(nums,left,mid-1);
tree.right=getMidTree(nums,mid+1,right);
return tree;
}
}
买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public int maxProfit(int[] prices) {
int maxValue=0;
int min=Integer.MAX_VALUE;
for(int i=0;i<prices.length;i++){
min=Math.min(min,prices[i]);
int tempValue= prices[i]-min;
maxValue=Math.max(maxValue,tempValue);
}
return maxValue;
}
}
买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public int maxProfit(int[] prices) {
int maxValue=0;
for(int i=prices.length-1;i>0;i--){
if(prices[i]>prices[i-1]){
maxValue+=prices[i]-prices[i-1];
}
}
return maxValue;
}
}
最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
class Solution {
public int longestConsecutive(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]);
}
int maxLength=1;
int finalMax=1;
for(int i=0;i<nums.length-1;i++){
if(nums[i+1] - nums[i]==1){
maxLength++;
}else if(nums[i+1]-nums[i]==0){
continue;
}else{
finalMax= Math.max(maxLength,finalMax);
maxLength=1;
}
}
finalMax= Math.max(maxLength,finalMax);
return finalMax;
}
}
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
class Solution {
public int singleNumber(int[] nums) {
HashMap map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])!=null){
map.put(nums[i],(int)map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
Set<Integer> sets= map.keySet();
for(Integer key: sets){
if((int)map.get(key)==1){
return key;
}
}
return -1;
}
}
只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
提示：
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
class Solution {
public int singleNumber(int[] nums) {
//搞一个集合来存储
HashMap map=new HashMap<Integer,Integer>();
//遍历将数据存进去 map
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])==null){
map.put(nums[i],1);
}else{
map.put(nums[i],(int)map.get(nums[i])+1);
}
}
// 遍历map 如果存在一个值为1的话 那么就返回
Set<Integer> sets=map.keySet();
for(Integer key:sets){
if((int)map.get(key)==1){
return key;
}
}
return 0;
}
}
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {
public int maxProduct(int[] nums) {
if(nums==null){
return 0;
}
if(nums.length==0){
return nums[0];
}
int max=Integer.MIN_VALUE;
int imax=1;
int imin=1;
for(int i=0;i<nums.length;i++){
if(nums[i]<0){
int tmp=imax;
imax=imin;
imin=tmp;
}
imax=Math.max(imax*nums[i],nums[i]);
imin=Math.min(imin*nums[i],nums[i]);
max=Math.max(max,imax);
}
return max;
}
}峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length==1||nums.length==0){
return 0;
}
if(nums.length==2){
if(nums[0]>nums[1]){
return 0;
}else{
return 1;
}
}
for(int i=1;i<nums.length-1;i++){
if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]){
return i;
}
}
if(nums[nums.length-1]>nums[nums.length-2]){
return nums.length-1;
}
return 0;
}
}轮转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
class Solution {
public void rotate(int[] nums, int k) {
//求余数为了避免k大于nums
k=k%nums.length;
//这个是为了放在前面
ArrayList<Integer> firstList= new ArrayList<Integer>();
//这个是为了放在后面
ArrayList<Integer> secondList= new ArrayList<Integer>();
//这个把后面的切割下来
for(int i=nums.length-1;i>=nums.length-k;i--){
firstList.add(nums[i]);
}
// 这个添加到后面
for(int i=0;i<nums.length-k;i++){
secondList.add(nums[i]);
}
for(int i=0;i<firstList.size();i++){
nums[i]=firstList.get(firstList.size()-i-1);
}
for(int i=0;i<secondList.size();i++){
nums[i+firstList.size()]=secondList.get(i);
}
}
}
岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1
示例 2：
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’
class Solution {
int count=0;
public int numIslands(char[][] grid) {
//判空
if(grid[0].length==0||grid.length==0){
return 0;
}
//拿出这个矩阵的横和列
int right=grid[0].length;
int bottom=grid.length;
//
for(int i=0;i<bottom;i++){
for(int j=0;j<right;j++){
//遍历整个矩阵 如果发现有一个是1的开启深度搜索 找到后给这个计数器加一
if(grid[i][j]=='1'){
dfs(grid,i,j);
count++;
}
}
}
return count;
}
//深度邮箱搜索
public void dfs(char[][] grid,int i,int j){
//关键就是这个判断标准，超出不可以 为0不可以
if(i<0||i>grid.length-1||j<0||j>grid[0].length-1||grid[i][j]=='0'){
return;
}
//递归调用了上下左右，这个方法结束的时候就一个岛屿
grid[i][j]='0';
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
}
最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：4
示例 2：
输入：matrix = [[“0”,”1”],[“1”,”0”]]
输出：1
示例 3：
输入：matrix = [[“0”]]
输出：0
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
// 遇到一个 1 作为正方形的左上角
maxSide = Math.max(maxSide, 1);
// 计算可能的最大正方形边长
int currentMaxSide = Math.min(rows - i, columns - j);
for (int k = 1; k < currentMaxSide; k++) {
// 判断新增的一行一列是否均为 1
boolean flag = true;
if (matrix[i + k][j + k] == '0') {
break;
}
for (int m = 0; m < k; m++) {
if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
flag = false;
break;
}
}
if (flag) {
maxSide = Math.max(maxSide, k + 1);
} else {
break;
}
}
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
}
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length<=1){
return nums.length;
}
int n=nums.length;
int arr[]=new int[n];
for(int i=0;i<nums.length;i++){
arr[i]=1;
}
int result=1;
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
arr[i]=Math.max(arr[i],arr[j]+1);
}
}
result=Math.max(arr[i],result);
}
return result;
}
}
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
//正序遍历：完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
//这道题还不是很懂
}
}给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
前 K 个高频元素
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
//遍历将出现的次数和值放到一个map中
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])==null){
map.put(nums[i],1);
}else{
map.put(nums[i],(int)map.get(nums[i])+1);
}
}
//这个是一个关键 对一个包着map的list进行排序
List<Map.Entry<Integer,Integer>> list=new ArrayList<>(map.entrySet());
// 如果b值大于a值那么就排前面
Collections.sort(list,(a,b)->{
return b.getValue()-a.getValue();
});
//最后遍历 就拿前面k个值
int[] arr=new int[k];
for(int i=0;i<k;i++){
arr[i]=(int)list.get(i).getKey();
}
return arr;
}
}
三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3]
输出：6
示例 2：
输入：nums = [1,2,3,4]
输出：24
示例 3：
输入：nums = [-1,-2,-3]
输出：-6
class Solution {
public int maximumProduct(int[] nums) {
int max=Integer.MIN_VALUE;
if(nums==null||nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return nums[1]*nums[0];
}
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int tempMax=nums[i]*nums[i+1]*nums[i+2];
max=Math.max(max,tempMax);
}
int n=nums.length;
int sum= Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
max=Math.max(max,sum);
return max;
}
}
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
class Solution {
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
int mid=0;
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
right=mid-1;
}else {
left=mid+1;
}
}
return -1;
}
}
二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//判空操作
if(matrix==null){
return false;
}
if(matrix.length==0){
return false;
}
//right top 是右上角 为什么选右上角 因为右上角 往左边永远是减往下面永远是加
int right=matrix[0].length-1;
int top=0;
//当top不大于最低 right 不小于0 那么找到就是true 找不到判断大小继续找大了就往左边挪 小了往下边加
while(right>=0&&top<matrix.length){
if(matrix[top][right]==target){
return true;
}else if(matrix[top][right]>target){
right--;
}else if(matrix[top][right]<target){
top++;
}
}
return false;
}
}
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n=preorder.length;
//判空
if(n==0){
return null;
}
//先找出 这个前序根在中序的那个位置
int rootValue=preorder[0];
int rootIndex=0;
TreeNode rootTree = new TreeNode(rootValue);
for(int i=0;i<n;i++){
if(inorder[i]==rootValue){
rootIndex=i;
}
}
//左子树就是前序
rootTree.left=buildTree(Arrays.copyOfRange(preorder,1,1+rootIndex),Arrays.copyOfRange(inorder,0,0+rootIndex));
rootTree.right=buildTree(Arrays.copyOfRange(preorder,1+rootIndex,n)
,Arrays.copyOfRange(inorder,rootIndex+1,n));
return rootTree;
}
}
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
class Solution {
public int minArray(int[] numbers) {
Arrays.sort(numbers);
return numbers[0];
}
}
调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
class Solution {
public int[] exchange(int[] nums) {
ArrayList firstList=new ArrayList<Integer>();
ArrayList secondList=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
if(nums[i]%2==0){
secondList.add(nums[i]);
}else{
firstList.add(nums[i]);
}
}
for(int i=0;i<firstList.size();i++){
System.out.print(firstList.get(i));
nums[i]=(int)firstList.get(i);
}
for(int i=0;i<secondList.size();i++){
System.out.print(secondList.get(i));
nums[firstList.size()+i]=(int)secondList.get(i);
}
return nums;
}
}
顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
class Solution {
public int[] spiralOrder(int[][] matrix) {
//如果为空或者集合就一个 那么返回一个
if(matrix==null||matrix.length==0||matrix[0].length==0){
int [] arr=new int[0];
return arr;
}
//左边
int left=0;
//右边
int right=matrix[0].length-1;
//上边
int top=0;
//下边
int botton=matrix.length-1;
//存储集合的边界
ArrayList<Integer> list=new ArrayList<Integer>();
//如果左边小于右边 或者下边大于上边
while(left<=right&&botton>=top){
//先从左到右加入
for(int i=left;i<=right;i++){
list.add(matrix[top][i]);
}
//从上到下加入
for(int i=top+1;i<=botton;i++){
list.add(matrix[i][right]);
}
//从右到左加入 但是要求上下不能相等 不然会给上面重复计算
for(int i=right-1;i>=left&&botton!=top;i--){
list.add(matrix[botton][i]);
}
//从下到上，但是要求左和右不能相等
for(int i=botton-1;i>=top+1&&left!=right;i--){
list.add(matrix[i][left]);
}
top++;
right--;
botton--;
left++;
}
int [] arr=new int[list.size()];
for(int i=0;i<list.size();i++){
arr[i]=list.get(i);
}
return arr;
}
}
数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
class Solution {
public int majorityElement(int[] nums) {
HashMap map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])!=null){
map.put(nums[i],(int)map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
Set<Integer> sets =map.keySet();
for(Integer value : sets ){
System.out.println("key"+value);
System.out.println("value"+map.get(value));
if((int)map.get(value)>nums.length/2){
return value;
}
}
return -1;
}
}
最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
int[] result=new int[k];
for(int i=0;i<k;i++){
result[i]=arr[i];
}
return result;
}
}连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1){
return nums[0];
}
//这个是最后的值大小
int max=nums[0];
//这个是临时的一个最大值 因为是连续的一个最大值 所以需要这个临时的，
int tempMax=nums[0];
for(int i=1;i<nums.length;i++){
//这个最大值就是之前积累的加上这个值大 还是单个这个大
tempMax=Math.max(nums[i],tempMax+nums[i]);
//把连续加上的判断的值和之前积累的最大值做 最大留存就得出了
max=Math.max(max,tempMax);
}
return max;
}
}
在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
class Solution {
public int search(int[] nums, int target) {
HashMap map= new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])==null){
map.put(nums[i],1);
}else{
int temp=(int)map.get(nums[i]);
map.put(nums[i],temp+1);
}
}
if(map.get(target)==null){
return 0;
}else{
return (int)map.get(target);
}
}
}
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
class Solution {
public int missingNumber(int[] nums) {
for(int i=0;i<nums.length;i++){
if(nums[i]!=i){
return i;
}
}
return nums[nums.length-1]+1;
}
}
扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
class Solution {
public boolean isStraight(int[] nums) {
//先排序一下
Arrays.sort(nums);
//搞
int zoreNumber=0;
for(int i=0;i<nums.length-1;i++){
if(nums[i]==0){
zoreNumber++;
continue;
}
if(nums[i+1]==nums[i]){
return false;
}
zoreNumber=zoreNumber-(nums[i+1]-nums[i]-1);
}
System.out.print("zoreNumber"+zoreNumber);
if(zoreNumber>=0){
return true;
}else{
return false;
}
}
}
股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public int maxProfit(int[] prices) {
int minValue=Integer.MAX_VALUE;
int maxResult=0;
for(int i=0;i<prices.length;i++){
minValue =Math.min(minValue,prices[i]);
int tempResult =prices[i]-minValue;
maxResult=Math.max(maxResult,tempResult);
}
return maxResult;
}
}
数组中和为 0 的三个数
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
ArrayList<List<Integer>> result= new ArrayList<List<Integer>>();
ArrayList<Integer> arrList= new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
int target=-nums[i];
int start=i+1;
int end=nums.length-1;
while(start<end&&start<=nums.length-1&&end<=nums.length-1){
if(nums[start]+nums[end]==target){
ArrayList<Integer> list=new ArrayList();
list.add(nums[start]);
list.add(nums[end]);
list.add(nums[i]);
if(!result.contains(list)){
result.add(list);
}
start++;
end--;
}else if(nums[start]+nums[end]<target){
start++;
}else{
end--;
}
}
}
return result;
}
}
合并排序的数组
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int i=m;i<m+n;i++){
A[i]=B[i-m];
}
Arrays.sort(A);
}
}
搜索旋转数组
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
示例2:
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）
class Solution {
public int search(int[] arr, int target) {
for(int i=0;i<arr.length;i++){
if(arr[i]==target){
return i;
}
}
return -1;
}
}
排序矩阵查找
给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null||matrix.length==0){
return false;
}
// 遍历的做法
// int colume=-1;
// int m=matrix.length;
// int n=matrix[0].length;
// for(int i=0;i<m;i++){
// for(int j=0;j<n;j++){
// if(matrix[i][j]==target){
// return true;
// }
// }
// }
int m=0;
int n=matrix[0].length-1;
while(m<matrix.length&&n>=0){
if(matrix[m][n]==target){
return true;
}else if(matrix[m][n]>target){
n--;
}else{
m++;
}
}
return false;
}
}
连续数列
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
class Solution {
public int maxSubArray(int[] nums) {
if(nums==null||nums.length==0){
return -1;
}
int max=nums[0];
int current=nums[0];
for(int i=1;i<nums.length;i++){
if(current+nums[i]>nums[i]){
current=current+nums[i];
}else{
current=nums[i];
}
max=Math.max(current,max);
}
return max;
}
}
字符串
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “”
输出: 0
class Solution {
public int lengthOfLongestSubstring(String s) {
char chars[]= s.toCharArray();
int max=0;
ArrayList<Character> list= new ArrayList();
if(s==null||s.length()==0){
return 0;
}
for(int i=0;i<chars.length;i++){
Character character= new Character(chars[i]);
if(list.contains(character)){
int index=list.indexOf(character);
for(int j=index;j>=0;j--){
list.remove(j);
}
if(!list.contains(character)){
list.add(character);
}
}else{
list.add(character);
max=Math.max(max,list.size());
}
}
return max;
}
}最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：”bb”
示例 3：
输入：s = “a”
输出：”a”
示例 4：
输入：s = “ac”
输出：”a”
class Solution {
public String longestPalindrome(String s) {
char chars[]=s.toCharArray();
int length=s.length();
if(length<2){
return s;
}
Boolean arr[][]=new Boolean[length][length];
for(int i=0;i<length;i++){
arr[i][i]=true;
}
int maxhublength=1;
int start=0;
for(int j=1;j<length;j++){
for(int i=0;i<j;i++){
if(chars[j]!=chars[i]){
arr[i][j]=false;
}else{
if(j-i<3){
arr[i][j]=true;
}else{
arr[i][j]=arr[i+1][j-1];
}
}
if(((j-i+1)>maxhublength)&&arr[i][j]){
maxhublength=j-i+1;
start=i;
}
}
}
//不会
String result=s.substring(start,start+maxhublength);
return result;
}
}
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。
class Solution {
public String longestCommonPrefix(String[] strs) {
//先判空一下
if(strs==null||strs.length==0){
return "";
}
// 拿第一个为基准
String firstString=strs[0];
//这个是一个字符串的建造器
StringBuilder build= new StringBuilder();
//遍历第一个字符串的字符
for(int i=0;i<firstString.length();i++){
char c=firstString.charAt(i);
//如果某一个字符串的字符没有对应字符就会被return 因为是要连续一样的字符串
for(int j=1;j<strs.length;j++){
if(strs[j].length()<=i||c!=strs[j].charAt(i)){
return build.toString();
}
}
build.append(c);
}
return build.toString();
}
}
有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([)]”
输出：false
示例 5：
输入：s = “{[]}”
输出：true
class Solution {
public boolean isValid(String s) {
//搞一个栈
Stack<Character> stack= new Stack<>();
//遍历这个字符串
for(int i=0;i<s.length();i++){
//因为只有三种类型，看到某一个就放入相反的即可
char c=s.charAt(i);
if(c=='('){
stack.push(')');
}else if(c=='{'){
stack.push('}');
}else if(c=='['){
stack.push(']');
//如果遍历还没有为空 或者弹出来的字符跟放进去的不一样 那么就返回false
}else if (stack.isEmpty()||c!=stack.pop()){
return false;
}
}
return stack.isEmpty();
}
}
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1
输出：[“()”]
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res=new ArrayList<String>();
generate(res,"",0,0,n);
return res;
}
public void generate(List<String> res,String ans,int count1,int count2,int n){
if(count1>n||count2>n){
return;
}
if(count2==n&&count1==n){
res.add(ans);
}
if(count1>=count2){
String ans1 = new String(ans);
generate(res, ans+"(", count1+1, count2, n);
generate(res, ans1+")", count1, count2+1, n);
}
//不是很懂
}
}
字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
String ans = "0";
int m = num1.length(), n = num2.length();
for (int i = n - 1; i >= 0; i--) {
StringBuffer curr = new StringBuffer();
int add = 0;
for (int j = n - 1; j > i; j--) {
curr.append(0);
}
int y = num2.charAt(i) - '0';
for (int j = m - 1; j >= 0; j--) {
int x = num1.charAt(j) - '0';
int product = x * y + add;
curr.append(product % 10);
add = product / 10;
}
if (add != 0) {
curr.append(add % 10);
}
ans = addStrings(ans, curr.reverse().toString());
}
return ans;
}
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
ans.reverse();
return ans.toString();
//这个题不会 想不明白
}
}
复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,”255.255.111.35”]
示例 2：
输入：s = “0000”
输出：[“0.0.0.0”]
示例 3：
输入：s = “1111”
输出：[“1.1.1.1”]
示例 4：
输入：s = “010010”
输出：[“0.10.0.10”,”0.100.1.0”]
示例 5：
输入：s = “101023”
输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
class Solution {
public List<String> restoreIpAddresses(String s) {
ArrayList<String> strings = new ArrayList<>();
for (int i = 1; i < 4; i++) {
for (int j = 1; j < 4; j++) {
for (int k = 1; k < 4; k++) {
for (int l = 0; l < 4; l++) {
if (i + j + k + l == s.length()) {
String s1 = s.substring(0, i);
String s2 = s.substring(i, i+j);
String s3 = s.substring(i + j, i + j + k);
String s4 = s.substring(i + j + k, i + j + k + l);
if (checkout(s1) && checkout(s2) && checkout(s3) && checkout(s4)) {
StringBuilder builder = new StringBuilder();
String ip = builder.append(s1).append(".").append(s2).append(".").append(s3).append(".").append(s4).toString();
strings.add(ip);
}
}
}
}
}
}
return strings;
}
public boolean checkout(String s) {
if (s.equals("")){
return false;
}
if (s.charAt(0) == '0' && s.length() != 1) {
return false;
} else if (s.charAt(0) == '0' && s.length() == 1) {
return true;
}
try {
if (Integer.valueOf(s) <= 255) {
if (s.charAt(0) != '0') {
return true;
} else {
return false;
}
}
} catch (Exception e) {
return false;
}
return false;
}
//这个题也是不太会的
}
验证回文串
class Solution {
public boolean isPalindrome(String s) {
if(s==null||s.length()==0){
return false;
}
//先把它搞成小写的字母
s=s.toLowerCase();
//搞一个列表存储
ArrayList<Character> list=new ArrayList<Character>();
//遍历 判断是否是空和字母 数字 只加字母和数字
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c!=' '&&c-'a'<26&&c-'a'>=0){
list.add(c);
}
if(c>='0'&&c<='9'){
list.add(c);
}
}
//判断头尾是否相等就可以了
for(int i=0;i<(list.size()/2);i++){
if(list.get(i)!=list.get(list.size()-i-1)){
return false;
}
}
return true;
}
}
比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。
示例 1：
输入：version1 = “1.01”, version2 = “1.001”
输出：0
解释：忽略前导零，”01” 和 “001” 都表示相同的整数 “1”
示例 2：
输入：version1 = “1.0”, version2 = “1.0.0”
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 “0”
示例 3：
输入：version1 = “0.1”, version2 = “1.1”
输出：-1
解释：version1 中下标为 0 的修订号是 “0”，version2 中下标为 0 的修订号是 “1” 。0 < 1，所以 version1 < version2
class Solution {
public int compareVersion(String version1, String version2) {
//先根据. 切割字符
String [] a1 = version1.split("\\.");
String [] a2 = version2.split("\\.");
//例子1 需要把前面的0给删除但是 Integer.valueOf 已经能满足这一点
//例子2 需要缺少下标的时候把值默认为0
//这个题就是题目太难理解了
for(int n=0;n<Math.max(a1.length,a2.length);n++){
int i=(n<a1.length?Integer.valueOf(a1[n]):0);
int j=(n<a2.length?Integer.valueOf(a2[n]):0);
if(i<j){
return -1;
}else if(i>j){
return 1;
}
}
return 0;
}
}
最大数
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出：”210”
示例 2：
输入：nums = [3,30,34,5,9]
输出：”9534330”
示例 3：
输入：nums = [1]
输出：”1”
示例 4：
输入：nums = [10]
输出：”10”
class Solution {
public String largestNumber(int[] nums) {
//进行冒泡排序 排序的核心是 将两个字符加起来，然后进行排序大的排前面 小的排后面
for(int i=0;i<nums.length;i++){
for(int j=i+1;i<nums.length;j++){
if(i>=nums.length||j>=nums.length){
break;
}
String temp1=nums[i]+""+nums[j];
String temp2=nums[j]+""+nums[i];
if(Long.parseLong(temp1)<Long.parseLong(temp2)){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
}
//排完序的数组进行拼接 最后完成
StringBuilder build= new StringBuilder();
for(int i=0;i<nums.length;i++){
if("0".equals(build.toString())&&nums[i]==0){
continue;
}
build.append(nums[i]);
}
return build.toString();
}
}
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
class Solution {
public void reverseString(char[] s) {
// 遍历列表 将最后一个和第一个取出来 然后进行调换就可以了
for(int i=0;i<s.length/2;i++){
char first=s[i];
char last=s[s.length-1-i];
char temp =first;
first=last;
last=temp;
s[i]=first;
s[s.length-1-i]=last;
}
}
}
字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = “11”, num2 = “123”
输出：”134”
示例 2：
输入：num1 = “456”, num2 = “77”
输出：”533”
示例 3：
输入：num1 = “0”, num2 = “0”
输出：”0”
class Solution {
public String addStrings(String num1, String num2) {
//将字符串长度
int l1=num1.length()-1;
int l2=num2.length()-1;
//标志是否进位了
int add=0;
//字符串建造者
StringBuilder build=new StringBuilder();
//
while(add!=0||l1>=0||l2>=0){
//获取最低位然后减去’0‘拿到数值 如果长度低于0了 那么就返回0
int x=l1>=0?num1.charAt(l1)-'0':0;
int y=l2>=0?num2.charAt(l2)-'0':0;
System.out.print("x"+x);
System.out.print("y"+y);
//两个数相加 然后加上进位的那个数
int sum=x+y+add;
//这个数取模
int result=sum%10;
//除以10 看是否有进位
add=sum/10;
//将这个进位放到字符串数组中，但是这个是一个反序的
build.append(result);
//当然要长度同时减1
--l1;
--l2;
}
//将字符串反转
return build.reverse().toString();
}
}
验证IP地址
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
如果是有效的 IPv4 地址，返回 “IPv4” ；
如果是有效的 IPv6 地址，返回 “IPv6” ；
如果不是上述类型的 IP 地址，返回 “Neither” 。
IPv4 地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为 0 - 255， 用(“.”)分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6 地址由 8 组 16 进制的数字来表示，每组表示 16 比特。这些组数字通过 (“:”)分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
示例 1：
输入：IP = “172.16.254.1”
输出：”IPv4”
解释：有效的 IPv4 地址，返回 “IPv4”
示例 2：
输入：IP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
输出：”IPv6”
解释：有效的 IPv6 地址，返回 “IPv6”
示例 3：
输入：IP = “256.256.256.256”
输出：”Neither”
解释：既不是 IPv4 地址，又不是 IPv6 地址
示例 4：
输入：IP = “2001:0db8:85a3:0:0:8A2E:0370:7334:”
输出：”Neither”
示例 5：
输入：IP = “1e1.4.5.6”
输出：”Neither”
class Solution {
public String validIPAddress(String ip) {
//先将ip进行切割
String[] ipv4=ip.split("\\.");
String[] ipv6=ip.split(":");
//按正常的规则
if(ipv4.length==4&&ip.charAt(0)!='.'&&ip.charAt(ip.length()-1)!='.'){
//遍历ip
for(String s : ipv4){
if(s.length()==0||s.length()>=4||(s.charAt(0)=='0'&&s.length()>1)){
return "Neither";
}
int num=0;
//遍历数组下面的规则 每个小数组 只能是数字 且数字相加不能超过256
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch<'0'||ch>'9'){
return "Neither";
}else{
num=num*10+(ch-'0');
}
System.out.print("num"+num);
if(num>=256){
return "Neither";
}
}
}
return "IPv4";
}
//ipv6 数组长度不能超过8 全部能不能超过16 不能 :开头或者结尾
if (ipv6.length == 8 && ip.length() >= 15 && ip.charAt(0) != ':'
&& ip.charAt(ip.length() - 1) != ':') {
for (String s : ipv6) {
if (s.length() == 0 || s.length() > 4) return "Neither";
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
System.out.print(ch);
if (!(ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'F'
|| ch >= 'a' && ch <= 'f')) return "Neither";
}
}
return "IPv6";
}
return "Neither";
}
}
最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
class Solution {
public int longestPalindromeSubseq(String s) {
int n=s.length();
int [][] dp=new int[n][n];
for(int i=n-1;i>=0;i--){
dp[i][i]=1;
char c1=s.charAt(i);
for(int j=i+1;j<n;j++){
char c2=s.charAt(j);
if(c1==c2){
dp[i][j]=dp[i+1][j-1]+2;
}else{
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
//不太会
return dp[0][n-1];
}
}
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m=text1.length();
int n=text2.length();
// 为了把第一行和第一列给空出来
int[][] arr=new int [m+1][n+1];
// 从1行开始 第一列开始
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
//如果相等那么就是大家的上一个加1也就是左上角
char c1= text1.charAt(i-1);
char c2=text2.charAt(j-1);
if(c1==c2){
arr[i][j]=arr[i-1][j-1]+1;
}else{
//如果不相等，那么就取上面和左边的最大值，也就是两个长度的数组的最大值
arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
}
}
}
return arr[m][n];
}
}
字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
class Solution {
public String[] permutation(String s) {
Set<String> list=new HashSet<>();
char[]arr=s.toCharArray();
StringBuilder sb =new StringBuilder();
boolean[] visited=new boolean[arr.length];
dfs(arr,"",visited,list);
return list.toArray(new String[0]);
}
public void dfs(char[] arr,String s,boolean[] visited,Set<String> list){
if(s.length()==arr.length){
list.add(s);
return;
}
for(int i=0;i<arr.length;i++){
if(visited[i]){
continue;
}
visited[i]=true;
dfs(arr,s+String.valueOf(arr[i]),visited,list);
visited[i]=false;
}
//不太会
}
}
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”
class Solution {
public int translateNum(int num) {
//因为问的是个数
//如果小于9 那么就只有一种可能
if(num<=9){
return 1;
}
//先拿最后两位出来
int ba=num%100;
if(ba>=26||ba<=9){
//如果小于9且大于26 那么切割一次
return translateNum(num/10);
}else{
//如果在26和9之间的那么有两种可能 一种是切一次 种是切两次
return translateNum(num/10)+translateNum(num/100);
}
}
}
第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = “abaccdeff”
输出：’b’
示例 2:
输入：s = “”
输出：’ ‘
class Solution {
public char firstUniqChar(String s) {
char result=' ';
//存储字符和对应的次数
HashMap<Character,Integer> map= new HashMap<Character,Integer>();
//将字符串和次数整理到map中
for(int i=0;i<s.length();i++){
char at= s.charAt(i);
if(map.get(at)==null){
map.put(at,1);
}else{
int value= (int)map.get(at);
map.put(at,value+1);
}
}
//遍历map找出次数为1的
Set<Character> sets= map.keySet();
ArrayList<Character> list= new ArrayList<Character>();
for(Character c:sets){
if((int)map.get(c)==1){
list.add(c);
}
}
//通过字符串遍历 如果存在次数为1的返回，可以完成第一次的设定
for(int i=0;i<s.length();i++){
if(list.contains(s.charAt(i))){
return s.charAt(i);
}
}
return result;
}
}
翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
class Solution {
public String reverseWords(String s) {
if(s==null||s.length()==0){
return "";
}
//先把字符串的前面和后面空格去掉
s=s.trim();
String result="";
//将字符串按空格切割
String [] strArr=s.split(" ");
//将数组的前面和后面进行调转
for(int i=0;i<strArr.length/2;i++){
String firstStr=strArr[i];
String secondStr=strArr[strArr.length-1-i];
String tempStr=firstStr;
firstStr=secondStr;
secondStr=tempStr;
strArr[i]=firstStr;
strArr[strArr.length-1-i]=secondStr;
}
//最后拼接回来
for(int i=0;i<strArr.length;i++){
result=result.trim()+" "+strArr[i];
}
return result.trim();
}
}
把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: “42”
输出: 42
示例 2:
输入: “ -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。
示例 4:
输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
class Solution {
public int strToInt(String str) {
//字符串先去空格
str=str.trim();
int result=0;
//标志是否应该取反
boolean reverse=false;
//字符串为空 或者长度为0
if(str==null||str.length()==0){
return 0;
}
//看第一位是不是负数
if(str.charAt(0)=='-'){
reverse=true;
str=str.substring(1,str.length());
}else if(str.charAt(0)=='+'){
reverse=false;
str=str.substring(1,str.length());
}
//将字符串切割开然后放进去 字符串建造器
StringBuilder build=new StringBuilder();
for(int i=0;i<str.length();i++){
char at=str.charAt(i);
if(at-'0'<=9&&at-'0'>=0){
build.append(at);
}else{
break;
}
}
//如果长度为0 那么
if(build.length()==0){
return result;
}
//如果数值大于int的最大值
long tempResult=0;
//如果超过了返回integer最大值
for(int i=0;i<build.length();i++){
tempResult=tempResult*10+Integer.valueOf(build.charAt(i)-'0');
if(tempResult>Integer.MAX_VALUE){
if(reverse){
return Integer.MIN_VALUE;
}else{
return Integer.MAX_VALUE;
}
}
}
//将long转成int 然后取反 返回
result=(int)tempResult;
if(reverse){
result=-result;
}
return result;
}
}
字符串轮转
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
示例1:
输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:
输入：s1 = “aa”, s2 = “aba”
输出：False
class Solution {
public boolean isFlipedString(String s1, String s2) {
//如果有一个空 那么就返回false
if(s1==null||s2==null){
return false;
}
//如果长度不相等
if(s1.length()!=s2.length()){
return false;
}
//将两个 s2进行拼接 因为无论怎么转 只要一拼接 那么就会有出现 一样的
String ss=s2+s2;
// 看有没有包含住就可以了
return ss.contains(s1);
}
}
无重复字符串的排列组合
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
示例2:
输入：S = “ab”
输出：[“ab”, “ba”]
class Solution {
List<String> list = new ArrayList<String>();
StringBuffer s=new StringBuffer();
public String[] permutation(String S) {
dfs(S,list,s);
return list.toArray(new String[list.size()]);
}
public void dfs(String S,List<String> list,StringBuffer s){
if(s.length() == S.length()){
list.add(new String(s));
return;
}
for(int i=0;i<S.length();i++){
String zz=new String(s);
if(zz.contains(S.charAt(i)+"")){
continue;
}
s.append(S.charAt(i));
dfs(S,list,s);
s.deleteCharAt(s.length()-1);
}
//没有看懂
}
}
有重复字符串的排列组合
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:
输入：S = “qqe”
输出：[“eqq”,”qeq”,”qqe”]
示例2:
输入：S = “ab”
输出：[“ab”, “ba”]
class Solution {
LinkedList<String> list= new LinkedList<String>();
public String[] permutation(String S) {
dfs(S.toCharArray(),0);
return list.toArray(new String[0]);
}
public void dfs(char[] c,int k){
if(k==c.length){
list.add(new String(c));
return;
}
HashSet<Character> set= new HashSet<>();
for(int i=k;i<c.length;i++){
if(!set.contains(c[i])){
set.add(c[i]);
swap(c,i,k);
dfs(c,k+1);
swap(c,i,k);
}
}
//这个题还没有
}
public void swap(char[] c,int x,int y){
char temp=c[x];
c[x]=c[y];
c[y]=temp;
}
}
树
二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
/**
* 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) {
//搞个列表
ArrayList<Integer> list =new ArrayList<Integer>();
//如果为空就返回空
if(root==null){
return list;
}
rebuildTree(root,list);
return list;
}
public void rebuildTree(TreeNode root,ArrayList<Integer> list){
//如果为空就是返回这个是定递归的退出条件
if(root==null){
return;
}
//如果左子树不为空 那么就将左子树放进去
if(root.left!=null){
rebuildTree(root.left,list);
}
//放一个根节点
list.add(root.val);
//如果右子树不为空 那么就将右子树放进去
if(root.right!=null){
rebuildTree(root.right,list);
}
}
}
验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4
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) {
//如果为空返回true
if (node == null) {
return true;
}
//这个值小于下界 或者这个值大于上界就返回false
if (node.val <= lower || node.val >= upper) {
return false;
}
//继续分隔两边的根进行
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
}
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
/**
* 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<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> list= new ArrayList<List<Integer>>();
// 如果为空 返回空
if(root==null){
return list;
}
//队列
LinkedBlockingQueue<TreeNode> queue=new LinkedBlockingQueue<TreeNode>();
//先加一个根进去
queue.add(root);
//当根不为空的时候
while(!queue.isEmpty()){
ArrayList<Integer> tempList=new ArrayList<Integer>();
//先拿出目前长度
int size=queue.size();
//长度大于0的时候
while(size>0){
//从队列中拉一个出来
TreeNode node=queue.poll();
//放进去列表中
tempList.add(node.val);
//队列的左边不为空 加入
if(node.left!=null){
queue.add(node.left);
}
//队列的右边不为空 加入
if(node.right!=null){
queue.add(node.right);
}
//长度一直在递减
--size;
}
//列表加入这个字符串
list.add(tempList);
}
//列表返回
return list;
}
}
平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
/**
* 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 boolean isBalanced(TreeNode root) {
//如果为空那么可以
if(root==null){
return true;
}
//左右子树的深度
int left=depth(root.left);
int right=depth(root.right);
//还有子树的左右子树也需要是平衡树
return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
}
//算出以一个树为基础的深度为多少
public int depth(TreeNode root){
if(root==null){
return 0;
}
return Math.max(depth(root.left),depth(root.right))+1;
}
}
求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
/**
* 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 int sumNumbers(TreeNode root) {
return count(root,0);
}
//递归调用左边和右边相加
int count(TreeNode root,int sum){
if(root==null){
return 0;
}else if(root.left==null&&root.right==null){
return sum*10+root.val;
}else{
return count(root.left,sum*10+root.val)+count(root.right,sum*10+root.val);
}
}
}
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
/**
* 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> preorderTraversal(TreeNode root) {
//搞个列表
ArrayList<Integer> list = new ArrayList<Integer>();
//如果为空就直接返回
if(root==null){
return list;
}
//递归
createTree(root,list);
return list;
}
public void createTree(TreeNode root, ArrayList list){
if(root==null){
return;
}
//注意顺序 先序就把根放前面
list.add(root.val);
//如果左子树不为空 递归左子树
if(root.left!=null){
createTree(root.left,list);
}
//如果右子树不为空 递归右子树
if(root.right!=null){
createTree(root.right,list);
}
}
}
二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
/**
* 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> postorderTraversal(TreeNode root) {
ArrayList<Integer> list= new ArrayList<Integer>();
if(root==null){
return list;
}
createTree(root,list);
return list;
}
public void createTree(TreeNode root,ArrayList list){
if(root==null){
return ;
}
if(root.left!=null){
createTree(root.left,list);
}
if(root.right!=null){
createTree(root.right,list);
}
list.add(root.val);
}
}二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
/**
* 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> rightSideView(TreeNode root) {
//搞一个作为结果
ArrayList<Integer> result=new ArrayList<Integer>();
if(root==null){
return result;
}
//搞个列表存储
ArrayList<List<Integer>> list=new ArrayList<List<Integer>>();
//搞个队列
LinkedBlockingQueue<TreeNode> queue= new LinkedBlockingQueue<TreeNode>();
//队列接入一个根
queue.add(root);
//根不为空的时候 这个模型就是把树转成了列表
while(!queue.isEmpty()){
int size=queue.size();
ArrayList<Integer> tempList= new ArrayList<Integer>();
while(size>0){
TreeNode tree=queue.poll();
if(tree.left!=null){
queue.add(tree.left);
}
if(tree.right!=null){
queue.add(tree.right);
}
tempList.add(tree.val);
size--;
}
list.add(tempList);
}
//把列表的最后一个放进另外一个列表即可
for(int i=0;i<list.size();i++){
List<Integer> tempList=list.get(i);
result.add(tempList.get(tempList.size()-1));
}
return result;
}
}
完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
/**
* 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 int countNodes(TreeNode root) {
//如果为空 那么返回0
if(root==null){
return 0;
}
//搞一个队列
LinkedBlockingQueue<TreeNode> queue=new LinkedBlockingQueue<TreeNode>();
//队列加入一个根节点
queue.add(root);
//列表
ArrayList<Integer> list=new ArrayList<Integer>();
//当队列不为空的时候
while(!queue.isEmpty()){
//队列长度
int size=queue.size();
//当大小大于0
while(size>0){
TreeNode tree=queue.poll();
//将左右子树加入
if(tree.left!=null){
queue.add(tree.left);
}
if(tree.right!=null){
queue.add(tree.right);
}
//列表加入
list.add(tree.val);
size--;
}
}
//这个数字就是节点的数字
return list.size();
}
}
二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
/**
* 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 int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null){
return 0;
}
//这个还是那个层次遍历的模型 然后搞成一个列表 然后搞成一个数组，然后对数组进行排序 然后 就可以看到第k小的数字了
LinkedBlockingQueue<TreeNode> queue=new LinkedBlockingQueue<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size>0){
TreeNode tree= queue.poll();
if(tree.left!=null){
queue.add(tree.left);
}
if(tree.right!=null){
queue.add(tree.right);
}
list.add(tree.val);
--size;
}
}
int[] arr=new int[list.size()];
for(int i=0;i<list.size();i++){
arr[i]=list.get(i);
}
Arrays.sort(arr);
return arr[k-1];
}
}
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<Integer, TreeNode> parent = new HashMap<>();
HashSet<Integer> visited = new HashSet<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
//从下往上访问父节点 map存的是父节点
q = parent.get(q.val);
}
return null;
}
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
//没看懂
}
}
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
/**
* 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 {
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 并更新ans
return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
}
}
合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
/**
* 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//如果2为空 返回1
if(root2==null){
return root1;
}
//如果1位空 返回2
if(root1==null){
return root2;
}
//如果都不会空 相加
root1.val=root1.val+root2.val;
//递归 左边和左边
root1.left=mergeTrees(root1.left,root2.left);
//递归 右边和右边
root1.right=mergeTrees(root1.right,root2.right);
return root1;
}
}
二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/
2 7
/ \ /
1 3 6 9
镜像输出：
4
/
7 2
/ \ /
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
//如果为空那么返回为空
if(root==null){
return null;
}
//这个本质上是调换两个子树
TreeNode leftTree= root.left;
TreeNode temp=leftTree;
root.left= root.right;
root.right=temp;
//然后递归继续去换子树
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
//如果为空也是一个镜像函数
if(root==null){
return true;
}
//判断是否镜像
return isSame(root,root);
}
public boolean isSame(TreeNode root,TreeNode monitorTree){
//如果为空可以
if(root==null&&monitorTree==null){
return true;
}
//如果有一个不为空 一个为空不行
if(root==null||monitorTree==null){
return false;
}
//如果值相等 那么 对应镜像的值去匹配 左子树的跟另外一个右子树比 右子树的跟左子树比
if(root.val==monitorTree.val){
return isSame(root.left,monitorTree.right)&&isSame(root.right,monitorTree.left);
}else{
return false;
}
}
}
从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//存储结果的列表
ArrayList<List<Integer>> result= new ArrayList<List<Integer>>();
//如果为空的话 直接返回
if(root==null){
return result;
}
LinkedBlockingQueue<TreeNode> queue= new LinkedBlockingQueue<TreeNode>();
//队列中放进一个根的数值
queue.add(root);
//如果不为空那么就继续
while(!queue.isEmpty()){
//先取出当期的队列长度
int size =queue.size();
//搞一个列表
ArrayList<Integer> tempList=new ArrayList<Integer>();
//如果队列长度大于0
while(size>0){
//从队列中搞一个出来
TreeNode tree=queue.poll();
//如果左子树不为空就放进去
if(tree.left!=null){
queue.add(tree.left);
}
//如果右子树不为空也放进去
if(tree.right!=null){
queue.add(tree.right);
}
//把值放到一个列表之中
tempList.add(tree.val);
//大小减一
--size;
}
//将结果返回回去
result.add(tempList);
}
return result;
}
}
从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//搞一个结果的列表
ArrayList<List<Integer>> result=new ArrayList<List<Integer>>();
//如果为空返回
if(root==null){
return result;
}
//这个是要不要反转的标志
boolean flag=false;
//队列
LinkedBlockingQueue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>();
//先放一个根目录
queue.add(root);
//当队列不为空的时候
while(!queue.isEmpty()){
//队列长度
int size=queue.size();
//临时的数组长度
ArrayList<Integer> list=new ArrayList<Integer>();
while(size>0){
//从队列拿出第一个
TreeNode tree=queue.poll();
//如果存在左右子树就放进去
if(tree.left!=null){
queue.add(tree.left);
}
if(tree.right!=null){
queue.add(tree.right);
}
//列表放这个数的值
list.add(tree.val);
//
--size;
}
//控制是否需要反转
if(flag){
Collections.reverse(list);
}
//标志位取反
flag=!flag;
//将结果加进去
result.add(list);
}
return result;
}
}
二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
/**
* 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 {
//搞个结果的容器
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
//深度优先
dfs(root,target,new ArrayList());
return result;
}
public void dfs(TreeNode root, int target,List list){
//如果为空的话就返回
if(root==null){
return ;
}
//列表加入根的值
list.add(root.val);
//如果这个值是跟目标匹配
if(root.left==null&&root.right==null&&root.val==target){
result.add(new ArrayList<>(list));
}
//进行左边和右边目标值
dfs(root.left,target-root.val,list);
dfs(root.right,target-root.val,list);
//列表删除前面那个
list.remove(list.size()-1);
}
}
二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
//搞一个队列来存树
LinkedBlockingQueue<TreeNode> queue=new LinkedBlockingQueue<TreeNode>();
if(root==null){
return 0;
}
//先加一个根进去
queue.add(root);
//深度为0
int depth=0;
//当队列不为空的时候继续搞
while(!queue.isEmpty()){
int size = queue.size();
//当队列长度大于0的时候
while(size>0){
//队列搞一个出来
TreeNode tree= queue.poll();
//当队列不为空 队列加入
if(tree.left!=null){
queue.add(tree.left);
}
//当队列不为空 队列加入
if(tree.right!=null){
queue.add(tree.right);
}
//队列递减
size--;
}
//当走出一个循环的时候 深度会加1
depth++;
}
return depth;
}
}
平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/
4 4
返回 false 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
//
//左树的最大深度
int left=depth(root.left);
//右子树的最大深度
int right=depth(root.right);
//其实就是一直找 以这个根为节点的左右最大深度
return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
}
//这个功能主要是以某一个根为节点的最大深度
public int depth(TreeNode root){
if(root==null){
return 0;
}
return Math.max(depth(root.left),depth(root.right))+1;
}
}
求和路径
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> result=new ArrayList<>();
public int pathSum(TreeNode root, int sum) {
//当根为空的时候 返回0
if(root==null){
return 0;
}
//深度优先
dfs(root,sum,new ArrayList());
//而且要递归根的左边和右边
pathSum(root.left,sum);
//递归根的左边和右边
pathSum(root.right,sum);
return result.size();
}
//深度优先的套路 这个模型主要是用来解决路径的值等于某一个值的
public void dfs(TreeNode root,int target,ArrayList list){
//如果为空返回
if(root==null){
return;
}
//列表加入一个值
list.add(root.val);
//深度递归 将目标值改成目标值减去树的根值
dfs(root.left,target-root.val,list);
dfs(root.right,target-root.val,list);
//如果目标等于跟的值 那么这个结果加入列表
if(target==root.val){
result.add(new ArrayList(list));
}
//将值减去1 达到一个回溯的效果
list.remove(list.size()-1);
}
}
链表
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
/**
* 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 ListNode removeNthFromEnd(ListNode head, int n) {
//基本的思路就是把链表转成数组 然后删掉倒数几个 然后再把数组还原回去
ArrayList<Integer> list=new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head=head.next;
}
list.remove(list.size()-n);
if(list.size()<=0){
return null;
}
ListNode root=new ListNode(list.get(0));
ListNode index=root;
for(int i=1;i<list.size();i++){
System.out.print(list.get(i));
ListNode temp = new ListNode(list.get(i));
index.next=temp;
index=temp;
}
return root;
}
}
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
/**
* 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 ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//如果list2 为空 返回list1
if(list2==null){
return list1;
}
//如果list1为空返回list2
if(list1==null){
return list2;
}
//搞两个数组存储
ArrayList<Integer> arrayList1= new ArrayList<Integer>();
ArrayList<Integer> arrayList2= new ArrayList<Integer>();
//当列表不为空的时候 装进去数组
while(list1!=null){
arrayList1.add(list1.val);
list1=list1.next;
}
//当列表2不为空的时候装进去数组
while(list2!=null){
arrayList2.add(list2.val);
list2=list2.next;
}
int length=arrayList1.size()+arrayList2.size();
int[] arr=new int[length];
//搞一个可以容纳这么多的数组
for(int i=0;i<arrayList1.size();i++){
arr[i]=arrayList1.get(i);
}
//都装进去
for(int i=arrayList1.size();i<(arrayList1.size()+arrayList2.size());i++){
arr[i]=arrayList2.get(i-arrayList1.size());
}
//对数组进行排序
Arrays.sort(arr);
ListNode root= new ListNode(arr[0]);
ListNode tempNode=root;
//将 数组按列表复原
for(int i=1;i<arr.length;i++){
ListNode node= new ListNode(arr[i]);
tempNode.next=node;
tempNode=node;
}
return root;
}
}
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
/**
* 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 ListNode mergeKLists(ListNode[] lists) {
if(lists==null||lists.length==0||(lists.length==1&&lists[0]==null)){
return null;
}
ArrayList<Integer> list=new ArrayList<Integer>();
for(int i=0;i<lists.length;i++){
ListNode node= lists[i];
while(node!=null){
list.add(node.val);
node=node.next;
}
}
int length=list.size();
if(length<=0){
return null;
}
int[] arr = new int[length];
for(int i=0;i<list.size();i++){
arr[i]=list.get(i);
}
Arrays.sort(arr);
ListNode root= new ListNode(arr[0]);
ListNode index=root;
for(int i=1;i<arr.length;i++){
System.out.print(arr[i]);
ListNode node= new ListNode(arr[i]);
index.next=node;
index=node;
}
return root;
}
}
删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
/**
* 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 ListNode deleteDuplicates(ListNode head) {
if(head==null||head.next==null){
return head;
}
HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();
ArrayList<Integer> list= new ArrayList<>();
while(head!=null){
if(!list.contains(head.val)){
list.add(head.val);
}
if(map.get(head.val)==null){
map.put(head.val,1);
}else{
map.put(head.val,map.get(head.val)+1);
}
head=head.next;
}
// for(int i=0;i<list.size();i++){
// System.out.print(list.get(i));
// System.out.print(map.get(list.get(i)));
// }
ListNode result=null;
ListNode index=null;
for(int i=0;i<list.size();i++){
if(map.get(list.get(i))==1){
if(result==null){
result= new ListNode(list.get(i));
index=result;
}else{
System.out.print(list.get(i));
ListNode temp= new ListNode(list.get(i));
index.next=temp;
index=index.next;
}
}
}
//暂时没有时间看看
return result;
}
}
删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
/**
* 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 ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
//当node不为空的时候就会往下移动，但是只有当下一个不等于当前这个的时候才会移动
ListNode temp=head;
while(temp!=null){
if(temp.next!=null){
if(temp.val==temp.next.val){
temp.next=temp.next.next;
}
}
if(temp.next==null||temp.next.val!=temp.val){
temp=temp.next;
}
}
return head;
}
}
反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
/**
* 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 ListNode reverseBetween(ListNode head, int left, int right) {
ArrayList<Integer> list=new ArrayList<Integer>();
ListNode temp=head;
while(temp!=null){
list.add(temp.val);
temp=temp.next;
}
int[] arr=new int[list.size()];
for(int i=0;i<list.size();i++){
arr[i]=list.get(i);
}
for(int i=0;i<(right-left+1)/2;i++){
int tempValue=arr[left+i-1];
arr[left+i-1]=arr[right-i-1];
arr[right-i-1]=tempValue;
}
for(int i=0;i<list.size();i++){
System.out.print(arr[i]);
}
ListNode result=null;
ListNode index=null;
for(int i=0;i<arr.length;i++){
if(result==null){
result= new ListNode(arr[i]);
index=result;
}else{
index.next=new ListNode(arr[i]);
index=index.next;
}
}
//没有看懂
return result;
}
}
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//如果为空那就返回
if(head==null){
return false;
}
ListNode temp;
//将链表放在中间
temp=head;
//搞两个中间件
ListNode temp1=temp;
ListNode temp2=temp;
//当这个不为空或者下一个不为空
while(temp2!=null&&temp2.next!=null){
temp1=temp1.next;
temp2=temp2.next.next;
//如果是环形的话他们就一定会重复 如果不是环形的 那么跑一次就没有了
if(temp1==temp2){
return true;
}
}
return false;
}
}
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
class LRUCache {
//要搞这个LUR需要搞一个map加一个双向链表
private int capacity;
//容量大小
private int size = 0;
//map
private Map<Integer, Entry> cache = new HashMap<Integer, Entry>();
//这个是双向链表的头和尾
private Entry head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new Entry();
tail = new Entry();
head.next = tail;
tail.prev = head;
}
// 获取的时候从map取出来 发现为空就返回 不为空就插入到头那边
public int get(int key) {
Entry node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
//插入到头那边就是先从尾巴删掉 然后加入到头那边
private void moveToHead(Entry node) {
removeNode(node);
addToHead(node);
}
//加入到头那边 添加节点就是 这个节点的前一个为头，节点的下一个是头的下一个 头的前一个为这个 头的下一个为这个
private void addToHead(Entry node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//删除这个节点 删除节点就是 这个节点的前面的下一个变成这的下一个 这个节点的下一个的前一个变成节点的前一个
private void removeNode(Entry node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
//放进去的话 从map拿出来 如果存在就刷新 如果不存在的话 就加入 加入的时候如果发现已经超过了最大的话那么就删掉最后一个
public void put(int key, int value) {
Entry node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
Entry newNode = new Entry(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
Entry tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
} else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
//删掉最后一个就是双向链表的尾结点的前一个
private Entry removeTail() {
Entry res = tail.prev;
removeNode(res);
return res;
}
class Entry {
int key;
int value;
Entry prev;
Entry next;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
public Entry() {
}
}
}
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
/**
* 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 ListNode sortList(ListNode head) {
if(head==null){
return null;
}
//这个思路是把链表搞成数组 然后数组排序 然后再组装成链表
ArrayList<Integer> list= new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head=head.next;
}
int[] arr= new int[list.size()];
for(int i=0;i<list.size();i++){
arr[i]=list.get(i);
}
Arrays.sort(arr);
ListNode root=new ListNode(arr[0]);
ListNode index=root;
for(int i=1;i<arr.length;i++){
System.out.print(arr[i]);
ListNode node= new ListNode(arr[i]);
index.next=node;
index=node;
}
return root;
}
}
奇偶链表
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
/**
* 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 ListNode oddEvenList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode l1=new ListNode(0);
ListNode l2=new ListNode(0);
ListNode tempHead=head;
ListNode temp1=l1;
ListNode temp2=l2;
boolean isOdd=true;
while(tempHead!=null){
if(isOdd){
l1.next=tempHead;
l1=l1.next;
}else{
l2.next=tempHead;
l2=l2.next;
}
isOdd=!isOdd;
tempHead=tempHead.next;
}
if(l1.next!=null){
l1.next=null;
}
if(l2.next!=null){
l2.next=null;
}
l1.next=temp2.next;
return temp1.next;
}
}
两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
/**
* 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 ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//搞两个栈来存储 因为刚好满足这个特性
Stack<Integer> stack1= new Stack<Integer>();
Stack<Integer> stack2= new Stack<Integer>();
while(l1!=null){
stack1.push(l1.val);
l1=l1.next;
}
while(l2!=null){
stack2.push(l2.val);
l2=l2.next;
}
//进位的标志
int carry=0;
//根
ListNode head=null;
while(!stack1.isEmpty()||!stack2.isEmpty()||carry>0){
//进位的
int sum=carry;
//从栈弹一个出来
sum+=stack1.isEmpty()?0:stack1.pop();
//从栈弹一个出来
sum+= stack2.isEmpty()?0:stack2.pop();
//只取一位
ListNode node=new ListNode(sum%10);
//下一位指向头
node.next=head;
//下一个
head=node;
//除以时
carry=sum/10;
}
//返回这个头
return head;
}
}
链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
//先把链表放到列表中
ArrayList<ListNode> list= new ArrayList<ListNode>();
while(head!=null){
list.add(head);
head=head.next;
}
//然后从列表中拿出倒数第几个元素
return list.get(list.size()-k);
}
}
反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return head;
}
//先搞一个列表 将链表按值放进去
ArrayList<Integer> list= new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head=head.next;
}
//对列表进行排序
Collections.reverse(list);
// 把列表按链表的方式排序回来
ListNode root= new ListNode(list.get(0));
ListNode index=root;
for(int i=1;i<list.size();i++){
int temp=list.get(i);
ListNode tree =new ListNode(temp);
index.next=tree;
index=tree;
}
return root;
}
}
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
/**
* 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) {
//链表a 链表b
ListNode headATemp=headA;
ListNode headBTemp=headB;
//当A 不为空的时候 取出一个A 遍历b 如果遍历到的了话 那么就返回回去
while(headATemp!=null){
while(headBTemp!=null){
if(headATemp==headBTemp){
return headATemp;
}
headBTemp=headBTemp.next;
}
headBTemp=headB;
headATemp=headATemp.next;
}
return null;
}
}
链表中环的入口节点
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null){
return null;
}
ListNode fastNode=head;
ListNode slowNode=head;
while(fastNode != null && fastNode.next != null){
fastNode=fastNode.next.next;
slowNode=slowNode.next;
if(fastNode==slowNode){
fastNode = head;
while(slowNode != fastNode){
slowNode = slowNode.next;
fastNode = fastNode.next;
}
return slowNode;
}
}
//环在第一个
return null;
}
}
回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
/**
* 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) {
//如果列表为空 返回false
if(head==null){
return false;
}
//搞一个列表长度
ArrayList<ListNode> arr=new ArrayList<ListNode>();
//把链表搞成列表
while(head!=null){
arr.add(head);
head=head.next;
}
//看一下列表是不是一个回文树
for(int i=0;i<arr.size()/2;i++){
if(arr.get(i).val!=arr.get(arr.size()-1-i).val){
return false;
}
}
return true;
}
}
其他
整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
class Solution {
public int reverse(int x) {
if(x==0){
return 0;
}
//这个flag是用来标志负
boolean flag=false;
//如果小于0 就取反 标记这个负
if(x<0){
flag=true;
x=-x;
}
//搞一个列表
ArrayList<Integer> list= new ArrayList<Integer>();
//把数字切割然后放到列表
while(x>0){
int last=x%10;
list.add(last);
x=x/10;
}
//把列表还原 主要要判断如果大小大于integer 的最大值 那么久返回0
long result=0;
for(int i=0;i<list.size();i++){
if(result*10+list.get(i)>Integer.MAX_VALUE){
return 0;
}else{
result=result*10+list.get(i);
}
}
if(flag){
result=-result;
}
return (int)result;
}
}
回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
示例 4：
输入：x = -101
输出：false
class Solution {
public boolean isPalindrome(int x) {
//如果数值小于0那么返回false
if(x<0){
return false;
}
//搞个列表
ArrayList<Integer> list = new ArrayList<Integer>();
//当数值大于0的时候 取余10 然后加入列表 然后除以10
while(x>0){
int last=x%10;
list.add(last);
x=x/10;
}
//然后就直接对比
for(int i=0;i<list.size()/2;i++){
if(list.get(i)!=list.get(list.size()-1-i)){
return false;
}
}
return true;
}
}
x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
//二分查找的思路
//左边
int left=0;
//右边
int right=x;
//用来返回结果
int index=0;
//当左边小于右边的时候
while(left<=right){
//获取中间的那一个
int mid=left+(right-left)/2;
//中间的数平方 如果小于 从中间的左边算起 如果大于从中间右边算起
if((long)mid*mid<=x){
index=mid;
left=mid+1;
}else{
right=mid-1;
}
}
//返回下标
return index;
}
}
阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
class Solution {
public int trailingZeroes(int n) {
//其实就是算5的个数
int zoreCount=0;
while(n >= 5) {
zoreCount += n / 5;
n /= 5;
}
return zoreCount;
}
}
K 进制表示下的各位数字总和
给你一个整数 n（10 进制）和一个基数 k ，请你将 n 从 10 进制表示转换为 k 进制表示，计算并返回转换后各位数字的 总和 。
转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。
示例 1：
输入：n = 34, k = 6
输出：9
解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
示例 2：
输入：n = 10, k = 10
输出：1
解释：n 本身就是 10 进制。 1 + 0 = 1 。
class Solution {
public int sumBase(int n, int k) {
//搞一个结果
int result=0;
//当n不等于0的时候
while(n!=0){
//结果等于结果加上n 余上k进制
result=result+(n%k);
//这个数出于k
n=n/k;
}
return result;
}
}
用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
class CQueue {
//用两个栈来实现一个队列 就是先把栈的数据导出来 然后 弹出一个 然后在倒回去
Stack<Integer> firstStack= new Stack<Integer>();
Stack<Integer> secondStack= new Stack<Integer>();
public CQueue() {
}
public void appendTail(int value) {
firstStack.push(value);
}
public int deleteHead() {
if(firstStack.isEmpty()){
return -1;
}
while(!firstStack.isEmpty()){
int value= firstStack.pop();
secondStack.push(value);
}
int temp=secondStack.pop();
while(!secondStack.isEmpty()){
int value=secondStack.pop();
firstStack.push(value);
}
return temp;
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
class Solution {
public int fib(int n) {
//用一个数组来进行递归添加
if(n==0){
return 0;
}
if(n==1){
return 1;
}
int[] arr=new int[n+1];
arr[0]=0;
arr[1]=1;
for(int i=2;i<=n;i++){
arr[i]=(arr[i-1]+arr[i-2])%1000000007;
}
return arr[n];
}
}
青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
class Solution {
public int numWays(int n) {
//如果n小于等于1那么返回1
if(n<=1){
return 1;
}
//搞个数组加1
int[] arr=new int[n+1];
//数组 最终长度为 arr[i]=arr[i-1]+arr[i-2]
arr[0]=1;
arr[1]=2;
for(int i=2;i<n;i++){
arr[i]=(arr[i-1]+arr[i-2])%1000000007;
}
return arr[n-1];
}
}
二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
//这个就是拿1 进行不断的左移 然后匹配到了就加1
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0){
count++;
}
flag<<=1;
}
return count;
}
}
求平方根
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例 1:
输入: x = 4
输出: 2
示例 2:
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2
class Solution {
public int mySqrt(int x) {
//这个题用二分法然后接近结果
int left=0;
int right=x;
int result=0;
while(left<=right){
int mid=(left+(right-left)/2);
if((long)mid*mid<=x){
result=mid;
left=mid+1;
}else{
right=mid-1;
}
}
return result;
}
}
栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.
class MinStack {
/** initialize your data structure here. */
//搞两个栈 一个放最小值 一个放正常值 每次放正常值的时候会先把最小值拿出来 然后比较一下 一起同步塞一个最小值进去
Stack<Integer> stack= new Stack<Integer>();
Stack<Integer> minStack= new Stack<Integer>();
public MinStack() {
}
public void push(int x) {
stack.push(x);
if(minStack.size()>0){
int min=minStack.peek();
min=Math.min(min,x);
minStack.push(min);
}else{
minStack.push(x);
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
