算法题总结

灰太狼 2021-12-11 00:09 183阅读 0赞

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][] ###

### [1. 两数之和][1.] ###

*  给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，
 *  并返回他们的数组下标。
 *  你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 *  示例:
 *  给定 nums = \[2, 7, 11, 15\], target = 9
 *  因为 nums\[0\] + nums\[1\] = 2 + 7 = 9
 *  所以返回 \[0, 1\]

class Solution {
       public int[] twoSum(int[] nums, int target) {
           Map<Integer,Integer> map = new HashMap<>();
            for(int i = 0; i<nums.length;i++){
    
                if(map.containsKey(nums[i])){
                    return new int[]{
                            map.get(nums[i]),i};
                }
                map.put(target-nums[i],i);
            }
            return null;
        }
        
    }

### 2[. 无重复字符的最长子串][.] ###

*  给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *  示例 1:
 *  输入: "abcabcbb"
 *  输出: 3 
 *  解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *  示例 2:
 *  输入: "bbbbb"
 *  输出: 1
 *  解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *  示例 3:
 *  输入: "pwwkew"
 *  输出: 3
 *  解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *       请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            int[] index = new int[128]; // current index of character
            for (int j = 0, i = 0; j < n; j++) {
                i = Math.max(index[s.charAt(j)], i);
                ans = Math.max(ans, j - i + 1);
                index[s.charAt(j)] = j + 1;
            }
            return ans;
        }
    }

### 3 [整数反转][Link 1] ###

*  给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
 *  示例 1:
 *  输入: 123   输出: 321
 *   示例 2:
 *  输入: -123  输出: -321
 *  示例 3:
 *  输入: 120   输出: 21
 *  注意:
 *  假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−231,  231 − 1\]。
 *  请根据这个假设，如果反转后整数溢出那么就返回 0。

class Solution {
        public int reverse(int x) {
            int rev = 0;
            while (x != 0) {
                int pop = x % 10;
                x /= 10;
                if (rev > Integer.MAX_VALUE/10 || 
            (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
                if (rev < Integer.MIN_VALUE/10 || 
            (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
                rev = rev * 10 + pop;
            }
            return rev;
        }
    }

### 4[. 罗马数字转整数][. 1] ###

*  罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
 *  字符          数值
 *  I             1
 *  V             5
 *  X             10
 *  L             50
 *  C             100
 *  D             500
 *  M             1000
 *  例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。
 *  27 写做  XXVII, 即为 XX + V + II 。
 *  通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，
 *  而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，
 *  数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
 *  I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
 *  X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
 *  C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
 *  给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
 *  示例 1:
 *  输入: "III" 输出: 3
 *  示例 2:
 *  输入: "IV" 输出: 4
 *  示例 3:
 *  输入: "IX"  输出: 9
 *  示例 4:
 *  输入: "LVIII"  输出: 58
 *  解释: L = 50, V= 5, III = 3.
 *  示例 5:
 *  输入: "MCMXCIV"  输出: 1994
 *  解释: M = 1000, CM = 900, XC = 90, IV = 4.

public class RomanCInt {
        public static int romanToInt(String s) {
                int n = s.length();
                int roman_int = 0;
                for(int i=0;i<n;i++) {
                    switch(s.charAt(i)) {
                        case 'I' : roman_int = roman_int + 1;break;
                        case 'V' : roman_int = roman_int + 5;break;
                        case 'X' : roman_int = roman_int + 10;break;
                        case 'L' : roman_int = roman_int + 50;break;
                        case 'C' : roman_int = roman_int + 100;break;
                        case 'D' : roman_int = roman_int + 500;break;
                        case 'M' : roman_int = roman_int + 1000;break;
                        default: System.out.println("default");break;
                    }
                    if(i!=0) {
                        if(((s.charAt(i)=='V')||(s.charAt(i)=='X')) 
                          &&(s.charAt(i-1)=='I')) roman_int = roman_int -1*2;
                        if(((s.charAt(i)=='L')||(s.charAt(i)=='C')) 
                          &&(s.charAt(i-1)=='X')) roman_int = roman_int -10*2;
                        if(((s.charAt(i)=='D')||(s.charAt(i)=='M'))
                          &&(s.charAt(i-1)=='C')) roman_int = roman_int -100*2;
                    }
                }
                return roman_int;
            }
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入罗马数字");
            String s = in.nextLine();
            System.out.println(romanToInt(s));
            }
    }

### 5 [删除链表的倒数第N个节点][N] ###

*  给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *  示例：
 *  给定一个链表: 1->2->3->4->5, 和 n = 2.
 *  当删除了倒数第二个节点后，链表变为 1->2->3->5.

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
         public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode fast = head;
           while (n-- >0){
               fast = fast.next;
           }
            ListNode slow = head;
            if (fast == null) return head.next;
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return head;
        }
    }

### **6 有效的括号** ###

*  给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。
 *  有效字符串需满足：
 *  左括号必须用相同类型的右括号闭合。
 *  左括号必须以正确的顺序闭合。
 *  注意空字符串可被认为是有效字符串。
 *  示例 1:
 *  输入: "()"  输出: true
 *  示例 2:
 *  输入: "()\[\]\{\}" 输出: true
 *  示例 3:
 *  输入: "(\]"  输出: false
    
        class Solution {
           public boolean isValid(String s) {
                Stack<Character> stack = new Stack<>();
                for(int i = 0; i < s.length(); i++){
                    char ch = s.charAt(i);
                    switch (ch){
                        case '(':
                        case '{':
                        case '[':
                            //压栈
                            stack.push(ch);
                            break;
                        case ')':
                        case '}':
                        case ']':
                            if(stack.isEmpty()){
                                return false;
                            } else {
                                //出栈并匹配括号
                                char left = stack.pop();
                                if(!((left == '(' && ch == ')') || 
        (left == '{' && ch == '}') ||(left == '[' && ch == ']'))){
                                    return false;
                                }
                                break;
                            }
                            default:
                                break;
                    }
                }
                //空栈
                if(stack.isEmpty()){
                    return true;
                } else {
                    return false;
                }
            }
        }
    
    ### **7 环形链表** ###

给定一个链表，判断链表中是否有环。

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

/**
     * 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||head.next==null){
                return false;
            }
            ListNode p1 = head;
            ListNode p2 = head;
            while(p2!=null&&p2.next!=null){
                p1 = p1.next;
                p2 = p2.next.next;
                if(p1==p2){
                return true;
                }
            }
            return false;
        }
    }

### **8 环形链表2** ###

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `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 slow = head;
            ListNode fast = head;
            while(fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow==fast){
                    slow =head;
                    while(slow!=fast){
                        slow = slow.next;
                        fast = fast.next;
                    }
                    if(slow==fast) return slow;
                }
            }
            return null;
        }
    }

### ![4a18acda10c1606aa5d1132b9de26d61.png][]![4a18acda10c1606aa5d1132b9de26d61.png][]![4a18acda10c1606aa5d1132b9de26d61.png][]9 [ 最小栈][Link 2] ###

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。  
pop() -- 删除栈顶的元素。  
top() -- 获取栈顶元素。  
getMin() -- 检索栈中的最小元素。

class MinStack {
         Stack<Integer>stack;
        Stack<Integer>minstack;
        /** initialize your data structure here. */
        public MinStack() {
            stack   =new Stack<Integer>();
            minstack=new Stack<Integer>();
        }
    
        public void push(int x) {
            if(minstack.isEmpty()||x<minstack.peek())
                minstack.push(x);
            else
                minstack.push(minstack.peek());
            stack.push(x);
        }
    
        public void pop() {
            minstack.pop();
            stack.pop();
        }
    
        public int top() {
            return stack.peek();
        }
    
        public int getMin() {
            return minstack.peek();
        }

### **10 [相交链表][Link 3]** ###

找到两个单链表相交的起始节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70 1][]

/**
     * 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) {
            if(headA==null||headB==null){
                return null;
            }
            ListNode p1 = headA;
            ListNode p2 = headB;
            
            int count1 =0;
            while(p1!=null){
                p1 =p1.next;
                count1++;
            }
            int count2 = 0 ;
            while(p2!=null){
                p2 = p2.next;
                count2 ++;
            }
            int flag = count1-count2;
            if(flag>0){
                while(flag>0){
                    headA =headA.next;
                    flag --;
                }
                while(headA!=headB){
                    headA =headA.next;
                    headB =headB.next;
                }
                return headA;
            }
            if(flag<=0){
                while(flag<0){
                    headB = headB.next;
                    flag++;
                }
                while(headA!=headB){
                    headB = headB.next;
                    headA = headA.next;
                    
                }
                return headA;
            }
            return null;
            
        }
    }

### 11 设计循环队列 ###

*  设计你的循环队列实现。 循环队列是一种线性数据结构，
 *  其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
 *  它也被称为“环形缓冲器”

class MyCircularQueue {
        
        private int[] data;
        private int head;
        private int tail;
        private int size;
    
        public MyCircularQueue(int k) {
            data = new int[k];
            head = -1;
            tail = -1;
            size = k;
        }
        
        public boolean enQueue(int value) {
            if (isFull() == true) {
                return false;
            }
            if (isEmpty() == true) {
                head = 0;
            }
            tail = (tail + 1) % size;
            data[tail] = value;
            return true;
        }
    
        public boolean deQueue() {
            if (isEmpty() == true) {
                return false;
            }
            if (head == tail) {
                head = -1;
                tail = -1;
                return true;
            }
            head = (head + 1) % size;
            return true;
        }
        public int Front() {
            if (isEmpty() == true) {
                return -1;
            }
            return data[head];
        }
    
        public int Rear() {
            if (isEmpty() == true) {
                return -1;
            }
            return data[tail];
        }
    
        public boolean isEmpty() {
            return head == -1;
        }
        
        public boolean isFull() {
            return ((tail + 1) % size) == head;
        }
    }

12 二分查找

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

### 13 二维数组中的查找 ###

*  在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 *  每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
 *  判断数组中是否含有该整数。

public class Solution {
        
         public static boolean Find(int target, int [][] array) {
            if(array==null||array.length<1||array[0].length<1){
                return  false;
            }
            int rows = array.length;  //数组的行数
            int cols = array[1].length;  //数组行的列数
    
            int row =0;     //起始开始的行号
            int col =cols-1; //起始开始的列号
    
            //要查找的位置确定在数组之内
            while(row>=0&&row<rows&&col>=0&&col<cols){
                if(array[row][col]==target){
                    return  true;
                }else if(array[row][col]>target){
                    col--;
                }else{
                    row++;
                }
            }
            return  false;
        }
    }

### 14 替换空格 ###

*  请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，
 *  当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
        public static String replaceSpace(StringBuffer str) {
            if(str==null){
                return null;
            }
            StringBuilder newStr = new StringBuilder();
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)==' '){
                    newStr.append('%');
                    newStr.append('2');
                    newStr.append('0');
                }else{
                    newStr.append(str.charAt(i));
                }
            }
            return newStr.toString();
        }
    }

### 15 从尾到头打印链表 ###

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

import java.util.Stack;
    import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            Stack<Integer> stack = new Stack<>();
            while (listNode != null) {
                stack.push(listNode.val);
                listNode = listNode.next;
            }
     
            ArrayList<Integer> list = new ArrayList<>();
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }
            return list;       
        }
    }

### 16 重建二叉树 ###

*  输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和
 *  中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和
 *  中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

public class Solution {
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
            return root;
        }
        //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
        private TreeNode reConstructBinaryTree(int [] pre,int startPre,
       int endPre,int [] in,int startIn,int endIn) {
             
            if(startPre>endPre||startIn>endIn)
                return null;
            TreeNode root=new TreeNode(pre[startPre]);
             
            for(int i=startIn;i<=endIn;i++)
                if(in[i]==pre[startPre]){
                    root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                    root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                          break;
                }
                     
            return root;
        }
    }

### 17 用两个栈实现队列 ###

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

import java.util.Stack;
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();   
       public void push(int node) {   
               stack1.push(node);       
        }
        public int pop() throws Exception {
            if(stack2.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            if (stack2.isEmpty()){
                 throw new Exception("queue is empty");
            }else{
                 return stack2.pop();
            }             
        }
    }

### 18 旋转数组的最小数字 ###

*  把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 *  输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
 *  例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。
 *  NOTE：给出的所有元素都大于0，若数组大小为0，请返回0

import java.util.ArrayList;
    public class Solution {
        public static  int minNumberInRotateArray(int[] array){
            int i ;
            for( i=0;i<array.length;i++){
                if(array[i]==0){
                    return 0;
                }else {
                   if(array[i+1]<array[i]){
                       return array[i+1];
                   }
                }
            }
            return array[i+1];
        }
    }

### 19 斐波那契数列 ###

*  大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
 *  n<=39

public class Solution {
       public int Fibonacci(int n) {
            int a=1,b=1,c=0;
            if(n<0){
                return 0;
            }else if(n==1||n==2){
                return 1;
            }else{
                for (int i=3;i<=n;i++){
                    c=a+b;
                    b=a;
                    a=c;
                }
                return c;
            }
        }
    }

### 20 跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级。

求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

public class Solution {
        public static int JumpFloor(int target) {
            int one =1, two=2;
            int result=0;
            if(target<0){
                return -1;
            }else if(target==1||target==2){
                return target ;
            }else{
                for(int i=3;i<=target;i++){
                    result =one+two;
                    one = two ;
                    two = result;
                }
            }
            return result;
        }
    }

### 21 变态跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {
        public int JumpFloorII(int target) {
              int one = 1;
            int two = 2;
            if(target<0) return  -1;
            if(target ==1) return 1;
            for(int i =2;i<=target;i++){
                two = 2*one;
                one = two ;
            }
            return one;
        }
    }

### 22 矩形覆盖 ###

*  我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。
 *  请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

public class Solution {
        public int RectCover(int target) {
            if (target <= 2)
                return target;
            int a = 2 ;
            int b =1 ;
            int result =0;
            for(int i= 3;i<=target;i++){
                result = a+b ;
                b = a;
                a =result;
            }
            return result;
        }
    }

### 23 二进制中1的个数 ###

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

public class Solution {
        public  int NumberOf1(int n) {
            int count =0;
            while(n!=0){
                count++;
                n = n&(n-1);
            }
            return count;
        }
    }

### 24 数值的整数次方 ###

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

public class Solution {
     public static double Power(double base, int exponent) {
            if(exponent==0){
                return 1;
            }
            if(exponent==1){
                return base;
            }
            if(exponent==-1){
                return 1/base;
            }
           double sum =base;
            double sum1 =0;
            if(exponent>=2){
                for(int i =2;i<=exponent;i++){
                    sum = base*sum;
                     sum1 = sum;
                }
            }else if(exponent<0){
                for(int i =-2;i>=exponent;i--){
                    sum =base*sum;
                     sum1 = 1/sum;
                }
            }
            return sum1;
        }
    }

### 25 调整数组顺序使奇数位于偶数前面 ###

*  输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 *  使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
 *  并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution {
        public void reOrderArray(int [] array) {
          for(int i =0;i<array.length-1;i++){
              for(int j = 0; j< array.length-1-i;j++){
                  if(array[j]%2==0&&array[j+1]%2==1){
                          int num = array[j];
                          array[j] = array[j+1];
                          array[j+1] = num ;
                  }
              }
          }
        }
    }

### 26 链表中倒数第k个结点 ###

输入一个链表，输出该链表中倒数第k个结点。

public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            if(head ==null){
                return null;
            }
            ListNode p1 = head;
            while(p1!=null&& k-- >0)
                p1 = p1.next;
                if(k>0)
                    return null ;
            ListNode p2 =head;
             while(p1!=null){
                 p1 =p1.next;
                 p2 = p2.next;
             }
            return p2;
        }
    }

### 27 反转链表 ###

输入一个链表，反转链表后，输出新链表的表头。

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode ReverseList(ListNode head) {
    
            ListNode pre = null;
            ListNode curr = head;
            while(curr!=null){
                ListNode nextNode = curr.next;
                curr.next = pre;
                pre = curr;
                 curr = nextNode;
            }
            return pre;
        }
    }

### 28 合并两个排序的链表 ###

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1==null){
                return list2;
            }
            if (list2 == null)
            return list1;
            if(list1.val<=list2.val){
                list1.next = Merge(list1.next,list2);
                return list1;
            }else{
                list2.next = Merge(list1,list2.next);
                return list2;
            }
        }
    }

### 29 树的子结构 ###

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
             if (root1 == null || root2 == null)
            return false;
            return  isSubtreeWithRoot(root1, root2)||
    HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
        }
        public boolean isSubtreeWithRoot(TreeNode root1,TreeNode root2){
            if(root2==null) return true;
            if(root1==null) return false;
            if(root1.val!=root2.val) 
                return false;
            return isSubtreeWithRoot(root1.left,root2.left)
             &&isSubtreeWithRoot(root1.right,root2.right);
        }  
    }

### 30 栈的压入、弹出序列 ###

*  输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 *  假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
 *  序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        public boolean IsPopOrder(int [] pushA,int [] popA) {
          if(pushA.length==0||popA.length==0||pushA.length!=popA.length){
                return false;
            }
             Stack<Integer> stack=new Stack<Integer>();
    		int j=0;
    		for (int i = 0; i < pushA.length; i++) {
    			stack.push(pushA[i]);
    			while (j<popA.length&&popA[j]==stack.peek()) {
    				stack.pop();
    				j++;
    			}
    		}
    		return stack.empty()==true;
        }
    }

### 31数组中出现次数超过一半的数字 ###

*  数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 *  例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，
 *  超过数组长度的一半，因此输出2。如果不存在则输出0。

import java.util.*;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
           if(array.length<1){
               return -1;
           }
            int count =0;
            int num = array[array.length/2];
            for(int i =0;i<array.length;i++){
                if(num==array[i]){
                    count++;
                }
            }
            if(count<=array.length/2){
                num=0;
            }
            return num;
            
        }
    }

### 32 连续子数组的最大和 ###

例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。

public class Solution {
        public int FindGreatestSumOfSubArray(int[] array) {
            if(array==null||array.length==0){
                return 0;
            }
            int max = Integer.MIN_VALUE;
            int sum =0;
            for(int val : array){
               if(sum<=0){
                   sum = val;
               }else{
                  sum = sum+val; 
               }
                max = Math.max(max,sum);
            }
            return max;
        }
    }

### 33把数组排成最小的数 ###

*  输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
 *  打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，
 *  则打印出这三个数字能排成的最小数字为321323。

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    public class Solution {
        public String PrintMinNumber(int [] numbers) {
            int n;
            String s="";
            ArrayList<Integer> list=new ArrayList<Integer>();
            n=numbers.length;
             
            for(int i=0;i<n;i++){
                list.add(numbers[i]);//将数组放入arrayList中
            }
            //实现了Comparator接口的compare方法，将集合元素按照compare方法的规则进行排序
            Collections.sort(list,new Comparator<Integer>(){
             
                @Override
                public int compare(Integer str1, Integer str2) {
                    // TODO Auto-generated method stub         
                        String s1=str1+""+str2;
                        String s2=str2+""+str1;
                         
                        return s1.compareTo(s2);
                    }
                });
             
            for(int j:list){
                s+=j;
            }
            return s;
        }
    }

### 34 字符串最后一个单词的长度 ###

*  计算字符串最后一个单词的长度，单词以空格隔开。一行字符串，非空，长度小于5000。
 *  整数N，最后一个单词的长度。
 *  示例1
 *  hello world      5

import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            while(input.hasNext()){
                String str = input.nextLine();
                String[] str2=str.split(" ");
                System.out.println(str2[str2.length-1].length());
            }
        }
    }

### 35 计算字符个数 ###

*  写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，
 *  然后输出输入字符串中含有该字符的个数。不区分大小写。
 *      输入 ABCDEF A     输出 1

import java.util.*;
    public class Main{     
        public static void main(String[] args){                    
            int count=0;       
            Scanner in = new Scanner(System.in);
            String str = in.nextLine().toUpperCase();        
            char target  = in.nextLine().toUpperCase().toCharArray()[0];       
            for(int i=0;i<str.length();i++){
                if(str.charAt(i) == target){
                    count++;
                }
            }                       
            System.out.println(count); 
        }             
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70]: /images/20211210/9f141d90ccf34ce899957fc00765b79e.png
[1.]: https://leetcode-cn.com/problems/two-sum/
[.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Link 1]: https://leetcode-cn.com/problems/reverse-integer/
[. 1]: https://leetcode-cn.com/problems/roman-to-integer/
[N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[4a18acda10c1606aa5d1132b9de26d61.png]: /images/20211210/10b703e342894168ac86c06b783830f7.png
[Link 2]: https://leetcode-cn.com/problems/min-stack/
[Link 3]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70 1]: /images/20211210/f6ddfe89233a4438bc12f0cb6c9e72bb.png