//最小路径和
public static int task25(int[][] nums, int m, int n){
int[][] dp =new int[m][n];
dp[0][0] = nums[0][0];
for(int i =1;i
dp[i][0] = dp[i-1][0] + nums[i][0];
}
for(int j =1;j
dp[0][j] = dp[0][j-1] + nums[0][j];
}
for (int k =1;k
for(int l =1;l
dp[k][l] = Math.max(dp[k-1][l],dp[k][l-1]) + nums[k][l];
}
}
return dp[m-1][n-1];
}
//爬楼梯
public static int task25(int n){
if(n<=1){
return n;
}
return task25(n-1) +task25(n-2);
}
//最小覆盖子串
public static Stringtask26(String s,String patt){
int left =0;
int right =0;
int match =0;
int min = Integer.MAX_VALUE;
int index =0;
HashMap windows =new HashMap<>();
HashMap needs =new HashMap<>();
for(int i =0;i
needs.put(patt.charAt(i),needs.getOrDefault(patt.charAt(i),0)+1);
}
while (right
char cc = s.charAt(right);
right++;
if (needs.containsKey(cc)){
windows.put(cc,windows.getOrDefault(cc,0)+1);
int a = windows.get(cc);
int b = needs.get(cc);
if(windows.get(cc) == needs.get(cc)){
match++;
}
}
while (match == needs.size()){
if(right - left
min = right-left;
index = left;
}
char dd = s.charAt(left);
left++;
if(needs.containsKey(dd)){
if(windows.get(dd) == needs.get(dd)){
match--;
}
int count = windows.get(dd);
windows.put(dd,count--);
}
}
}
return s.substring(index,index+min);
}
//组合
public static ArrayList>rest =new ArrayList<>();
public static Listtask27(int n,int k){
back(n,k,1,new ArrayList());
return rest;
}
public static void back(int n,int k,int start,ArrayList path){
if(path.size() == k){
rest.add(new ArrayList<>(path));
return;
}
for(int i = start;i<=n;i++){
path.add(i);
back(n,k,i+1,path);
path.remove(path.size()-1);
}
}
//子集
public static Listtask28(int[] nums){
backtttttt(nums,0,new ArrayList());
return rest;
}
public static void backtttttt(int[] nums,int start,ArrayList path){
rest.add(new ArrayList<>(path));
for(int i = start;i
path.add(nums[i]);
backtttttt(nums,i+1,path);
path.remove(path.size()-1);
}
}
//删除链表重复
public static LinkedLISTtask29(LinkedLIST head){
LinkedLIST dummy =new LinkedLIST(-1,null);
dummy.next = head;
LinkedLIST pre = dummy;
LinkedLIST curr = head;
while (curr !=null && curr.next !=null){
if(curr.value == curr.next.value){
while (curr.next !=null && curr.value == curr.next.value){
curr = curr.next;
}
pre.next = curr.next;
curr = curr.next;
}else{
pre = pre.next;
curr = curr.next;
}
}
return dummy.next;
}
//合并有序数组
public static int[]task30(int[] nums1, int[] nums2, int m, int n){
int sum = m+n;
for(int i =0;i
if(m>0 && n>0 && nums1[m-1] > nums2[n-1]){
nums1[sum-i-1] = nums1[m-1];
m--;
}else if(m>0 && n<=0){
nums1[sum-i-1] = nums1[m-1];
m--;
}else{
nums1[sum-i-1] = nums2[n-1];
n--;
}
}
return nums1;
}
//二叉树的中序遍历
public static ArrayListtask31(TreeNode root){
ArrayList result =new ArrayList();
Stack stack =new Stack();
while (root !=null || stack.size() !=0){
while (root !=null){
stack.push(root);
root = root.leftchild;
}
if(stack.size() !=0){
root = stack.pop();
result.add(root.value);
root = root.rightchild;
}
}
return result;
}
//对称二叉树
public static boolean task32(TreeNode root){
return ismirrot(root,root);
}
public static boolean ismirrot(TreeNode root1, TreeNode root2){
if(root1 ==null && root2 ==null){
return true;
}
if(root1 ==null || root2 ==null){
return false;
}
return root1.value == root2.value &&
ismirrot(root1.leftchild, root2.rightchild) &&
ismirrot(root1.rightchild,root2.leftchild);
}
//二叉树层次遍历
public static ArrayListtask33(TreeNode root){
ArrayList result =new ArrayList();
ArrayDeque arrayDeque =new ArrayDeque();
arrayDeque.add(root);
while (arrayDeque.size() !=0){
int size = arrayDeque.size();
for(int i =0;i
TreeNode temp = arrayDeque.pop();
result.add(temp.value);
if (temp.leftchild !=null){
arrayDeque.add(temp.leftchild);
}
if(temp.rightchild !=null){
arrayDeque.add(temp.rightchild);
}
}
}
return result;
}
//二叉树最大深度
public static int task34(TreeNode root){
if (root ==null){
return 0;
}
int left =task34(root.leftchild);
int right =task34(root.rightchild);
return Math.max(left,right) +1;
}
//二叉树的层次遍历2
public static ArrayListtask35(TreeNode root){
ArrayList result =new ArrayList();
ArrayDeque arrayDeque =new ArrayDeque();
arrayDeque.add(root);
while (arrayDeque.size() !=0){
int size = arrayDeque.size();
ArrayList node =new ArrayList();
for(int i =0;i
TreeNode temp = arrayDeque.pop();
node.add(temp.value);
if (temp.leftchild !=null){
arrayDeque.add(temp.leftchild);
}
if(temp.rightchild !=null){
arrayDeque.add(temp.rightchild);
}
}
result.add(node);
}
return result;
}
//平衡二叉树
public static boolean task36(TreeNode root){
if(root ==null){
return true;
}
return Math.abs(depth(root.leftchild) -depth(root.rightchild)) <=1
&&task36(root.leftchild)
&&task36(root.rightchild);
}
public static int depth(TreeNode root){
if(root ==null){
return 0;
}
int left =depth(root.leftchild);
int right =depth(root.rightchild);
return Math.max(left,right) +1;
}
网友评论