102. 二叉树的层序遍历
递归法
核心代码模式
不断递归根节点，根据深度来判断加在哪一层上。
/**
* 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) {
List<List<Integer>> ans=new ArrayList<>();
layerselect(ans,root,0);
return ans;
}
void layerselect(List<List<Integer>> ans,TreeNode root,int deep)
{
if(root==null)return ;
if(ans.size()==deep)ans.add(new ArrayList<>());
ans.get(deep).add(root.val);
layerselect(ans,root.left,deep+1);
layerselect(ans,root.right,deep+1);
}
}手写输入输出
首先是构造树的节点类。
然后输入进来建树，特判一下为空的时候。这里是根据二叉树的性质，子节点下标等于父结点的2倍+1或2，不断递归建树
建好后进行层序遍历最后输出。
import java.util.*;
class TreeNode
{
int val;
TreeNode left,right;
TreeNode (){}
TreeNode(int val){this.val=val;}
TreeNode(String str){val=Integer.valueOf(str);}
TreeNode(int val,TreeNode left,TreeNode right)
{
this.val=val;
this.right=right;
this.left=left;
}
}
public class Javaacm
{
//输入格式
//[3,9,20,null,null,15,7]
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
if(s.equals("[]"))
{
System.out.print(s);return ;
}
String str[]=s.substring(1,s.length()-1).split(",");
TreeNode root=buildTree(str,0);
List<List<Integer>> ans=new ArrayList<>();
layerselect(ans,root,0);
System.out.print(ans);
//[[3], [9, 20], [15, 7]]
}
static void layerselect(List<List<Integer>> ans,TreeNode root,int deep)
{
if(root==null)return ;
if(deep==ans.size())ans.add(new ArrayList<>());
ans.get(deep).add(root.val);
layerselect(ans,root.left,deep+1);
layerselect(ans,root.right,deep+1);
}
private static TreeNode buildTree(String [] tree,int idx)
{
if(idx>=tree.length||tree[idx].equals("null"))
{
return null;
}
TreeNode node=new TreeNode(tree[idx]);
node.left=buildTree(tree,idx*2+1);
node.right=buildTree(tree,idx*2+2);
return node;
}
}迭代法
核心代码模式
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans=new ArrayList<>();
Queue<TreeNode> q=new ArrayDeque<>();
if(root==null)return ans;
q.offer(root);
while(!q.isEmpty())
{
int n=q.size();
List<Integer> layer=new ArrayList<>();
for(int i=0;i<n;i++)
{
TreeNode cur=q.poll();
layer.add(cur.val);
if(cur.left!=null)q.offer(cur.left);
if(cur.right!=null)q.offer(cur.right);
}
ans.add(layer);
}
return ans;
}
}手写输入输出
import java.util.*;
class TreeNode
{
int val;
TreeNode left,right;
TreeNode(){}
TreeNode(int val){this.val=val;}
TreeNode(String str){val=Integer.valueOf(str);}
TreeNode(int val,TreeNode left,TreeNode right)
{
this.val=val;
this.left=left;
this.right=right;
}
}
public class Javaacm
{
//输入格式
//[3,9,20,null,null,15,7]
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
if(s.equals("[]"))
{ System.out.print(s);return ;}
String str[]=s.substring(1,s.length()-1).split(",");
TreeNode root=buildTree(str,0);
List<List<Integer>> ans=new ArrayList<>();
Queue<TreeNode> q=new ArrayDeque<>();
q.offer(root);
while(!q.isEmpty())
{
int n=q.size();
List<Integer> layer=new ArrayList<>();
for(int i=0;i<n;i++)
{
TreeNode cur=q.poll();
layer.add(cur.val);
if(cur.left!=null)q.offer(cur.left);
if(cur.right!=null)q.offer(cur.right);
}
ans.add(layer);
}
System.out.println(ans);
return ;
}
private static TreeNode buildTree(String [] tree,int idx)
{
if(idx>=tree.length||tree[idx].equals("null"))
{
return null;
}
TreeNode node=new TreeNode(tree[idx]);
node.left=buildTree(tree,idx*2+1);
node.right=buildTree(tree,idx*2+2);
return node;
}
}1. 两数之和
核心代码模式
哈希表，将元素，下标键值对存储进去，然后遍历查找即可。
时空复杂度都为O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
int len=nums.length;
Map<Integer,Integer> m=new HashMap<>();
for(int i=0;i<len;i++)
{
if(m.containsKey(target-nums[i]))
return new int[]{i,m.get(target-nums[i])};
m.put(nums[i],i);
}
return null;
}
}手写输入输出
string数组转为int数组再遍历，最后输出答案
import java.util.*;
public class Javaacm
{
//输入格式
//[2,7,11,15]
//9
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
String str[]=s.substring(1,s.length()-1).split(",");
int target=scanner.nextInt();
int len=str.length;
int nums[]=new int[len];
for(int i=0;i<len;i++)
{
nums[i]=Integer.valueOf(str[i]);
}
Map<Integer,Integer> m=new HashMap<>();
int ans[]=null;
for(int i=0;i<len;i++)
{
if(m.containsKey(target-nums[i]))
{
ans=new int[]{i,m.get(target-nums[i])};
break;
}
m.put(nums[i],i);
}
if(ans==null)System.out.println("null");
else System.out.println("["+ans[0]+","+ans[1]+"]");
return ;
}
}33. 搜索旋转排序数组 - 力扣（LeetCode）
核心代码模式
class Solution {
public int search(int[] nums, int target) {
int minidx=findmin(nums);
int n=nums.length;
if(target>nums[n-1])
return lowerbound(nums,0,minidx,target);
return lowerbound(nums,minidx,n,target);
}
int findmin(int []nums)
{
int l=0,r=nums.length;
int n=nums.length;
while(l<r)
{
int mid=(l+r)/2;
if(nums[mid]<=nums[n-1])r=mid;
else l=mid+1;
}
return l;
}
int lowerbound(int []nums,int l,int r,int target)
{
while(l<r)
{
int mid=(l+r)/2;
if(nums[mid]>=target)r=mid;
else l=mid+1;
}
return target!=nums[l]?-1:l;
}
}手写输入输出
import java.util.*;
public class Javaacm
{
//输入格式
// [4,5,6,7,0,1,2]
// 0
static int nums[];
static int n;
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
String str[]=s.substring(1,s.length()-1).split(",");
int target=scanner.nextInt();
n=str.length;
nums=new int[n];
for(int i=0;i<n;i++)
nums[i]=Integer.valueOf(str[i]);
int minidx=findmin(target);
if(target>nums[n-1])
System.out.println(lowerbound(0,minidx,target));
else System.out.println(lowerbound(minidx,n,target));
return ;
}
static int findmin(int target)
{
int l=0,r=n;
while(l<r)
{
int mid=(l+r)/2;
//mid的值<=末尾
if(nums[mid]<=nums[n-1]) r=mid;
else l=mid+1;
}
return l;
}
static int lowerbound(int l,int r,int target)
{
while(l<r)
{
int mid=(l+r)/2;
if(nums[mid]>=target)r=mid;
else l=mid+1;
}
return target!=nums[l]?-1:l;
}
}200. 岛屿数量 - 力扣（LeetCode）
核心代码模式
class Solution {
int dx[]=new int[]{-1,0,1,0};
int dy[]=new int[]{0,1,0,-1};
boolean visit[][];
int n,m;
public int numIslands(char[][] grid) {
n=grid.length;
m=grid[0].length;
int ans=0;
visit=new boolean[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]=='1'&&visit[i][j]==false)
{
bfs(i,j,grid);
ans++;
}
}
}
return ans;
}
void bfs(int x,int y,char[][]grid)
{
visit[x][y]=true;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||yy<0||xx>=n||yy>=m)continue;
if(grid[xx][yy]=='1'&&!visit[xx][yy])
bfs(xx,yy,grid);
}
}
}手写输入输出
import java.util.*;
public class Javaacm
{
//输入格式
// 2 3 行数、列数
// 001
// 100
static int dx[]=new int[]{-1,0,1,0};
static int dy[]=new int[]{0,1,0,-1};
static int n,m;
static boolean visit[][];
static char grid[][];
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
m=scanner.nextInt();
grid=new char[n][m];
visit=new boolean[n][m];
for(int i=0;i<n;i++)
{
String s=scanner.next();
grid[i]=s.toCharArray();
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!visit[i][j]&&grid[i][j]=='1')
{
dfs(i,j);
ans++;
}
}
}
System.out.println(ans);
return ;
}
static void dfs(int x,int y)
{
visit[x][y]=true;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||yy<0||xx>=n||yy>=m)continue;
if(!visit[xx][yy]&&grid[xx][yy]=='1')
dfs(xx,yy);
}
}
}46. 全排列 - 力扣（LeetCode）
核心代码模式
class Solution {
List<List<Integer>> ans=new ArrayList<>();
int []num;
public List<List<Integer>> permute(int[] nums) {
num=nums;
Integer path[]=new Integer[nums.length];
boolean visit[]=new boolean[nums.length];
dfs(0,path,visit);
return ans;
}
void dfs(int deep,Integer []path,boolean visit[])
{
if(deep==visit.length)
{
ans.add(new ArrayList<>(Arrays.asList(path)));
return ;
}
for(int i=0;i<visit.length;i++)
{
if(visit[i])continue;
visit[i]=true;
path[deep]=num[i];
dfs(deep+1,path,visit);
visit[i]=false;
}
}
}手写输入输出
import java.util.*;
public class Javaacm
{
//输入格式
//[1,2,3]
static List<List<Integer>> ans=new ArrayList<>();
static Integer nums[];
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
String[] str=s.substring(1,s.length()-1).split(",");
int len=str.length;
nums=new Integer[len];
for(int i=0;i<len;i++)
nums[i]=Integer.valueOf(str[i]);
boolean visit[]=new boolean[len];
Integer path[]=new Integer[len];
dfs(0,path,visit);
System.out.println(ans);
return ;
}
static void dfs(int deep,Integer[]path,boolean visit[])
{
if(deep==nums.length)
{
ans.add(new ArrayList(Arrays.asList(path)));
return ;
}
for(int i=0;i<nums.length;i++)
{
if(visit[i])continue;
visit[i]=true;
path[deep]=nums[i];
dfs(deep+1,path,visit);
visit[i]=false;
}
}
}