【剑指Offer】Java题解汇总(上)

【剑指Offer】Java题解汇总(上)

01. 数组中重复的数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i < nums.length; i++){
            while(nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                } else {
                    int temp = nums[i];
                    nums[i] = nums[temp];
                    nums[temp] = temp;
                }
            }
        }
        return -1;
    }
}

02. 二维数组中的查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length == 0){
            return false;
        }

        int row = 0;
        int col = matrix[0].length-1;

        while(row < matrix.length && col >= 0){
            if(target == matrix[row][col]){
                return true;
            } else if(target > matrix[row][col]) {
                row ++;
            } else if(target < matrix[row][col]) {
                col --;
            }
        }
        return false;
    }
}

03. 替换空格

// class Solution {
//     public String replaceSpace(String s) {
//         return s.replaceAll(" ","%20");
//     }
// }

class Solution{
    public String replaceSpace(String s) {
        if(s == null){
            return null;
        }

        int cnt = 0;
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == ' '){
                cnt ++;
            }
        }

        cnt = s.length() + cnt * 2;

        char[] s_char = new char[cnt];

        int p1 = s.length()-1;
        int p2 = cnt-1;

        while(p1>=0 && p2>=0){
            if(s.charAt(p1) != ' '){
                s_char[p2] = s.charAt(p1);
                p2 --;
                p1 --;
            } else{
                s_char[p2] = '0';
                p2 --;
                s_char[p2] = '2';
                p2 --;
                s_char[p2] = '%';
                p2 --;
                p1 --;
            }
        }
        return new String(s_char);
    }
}

04. 从尾到头打印链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

 //用栈的方法
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[]{};
        }
        ListNode temp = head;

        Stack<ListNode> stack = new Stack<ListNode>();
        while(temp != null){
            stack.push(temp);
            temp = temp.next;
        }

        int size = stack.size();
        int[] vec = new int[size];
        for(int i = 0;i < size;i++){
            vec[i] = stack.pop().val;
        }
        return vec;
    }
}

05. 重建二叉树

官方:

方法一:递归
二叉树的前序遍历顺序是:根节点、左子树、右子树,每个子树的遍历顺序同样满足前序遍历顺序。

二叉树的中序遍历顺序是:左子树、根节点、右子树,每个子树的遍历顺序同样满足中序遍历顺序。

前序遍历的第一个节点是根节点,只要找到根节点在中序遍历中的位置,在根节点之前被访问的节点都位于左子树,在根节点之后被访问的节点都位于右子树,由此可知左子树和右子树分别有多少个节点。

由于树中的节点数量与遍历方式无关,通过中序遍历得知左子树和右子树的节点数量之后,可以根据节点数量得到前序遍历中的左子树和右子树的分界,因此可以进一步得到左子树和右子树各自的前序遍历和中序遍历,可以通过递归的方式,重建左子树和右子树,然后重建整个二叉树。

使用一个 Map 存储中序遍历的每个元素及其对应的下标,目的是为了快速获得一个元素在中序遍历中的位置。调用递归方法,对于前序遍历和中序遍历,下标范围都是从 0 到 n-1,其中 n 是二叉树节点个数。

递归方法的基准情形有两个:判断前序遍历的下标范围的开始和结束,若开始大于结束,则当前的二叉树中没有节点,返回空值 null。若开始等于结束,则当前的二叉树中恰好有一个节点,根据节点值创建该节点作为根节点并返回。

若开始小于结束,则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置,从而得到左子树和右子树各自的下标范围和节点数量,知道节点数量后,在前序遍历中即可得到左子树和右子树各自的下标范围,然后递归重建左子树和右子树,并将左右子树的根节点分别作为当前根节点的左右子节点。

/**
 * 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) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        int length = preorder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        if (preorderStart > preorderEnd) {
            return null;
        }
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);
        if (preorderStart == preorderEnd) {
            return root;
        } else {
            int rootIndex = indexMap.get(rootVal);
            int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
            TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
            TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
            root.left = leftSubtree;
            root.right = rightSubtree;
            return root;
        }
    }
}

我的:

/**
 * 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) {
        if(preorder == null || preorder.length == 0){
            return null;
        }

        int length = preorder.length;
        Map<Integer,Integer> indexMap = new HashMap<Integer,Integer>();
        for(int i=0; i<length; i++){
            indexMap.put(inorder[i],i);
        }

        TreeNode root = rebuildTree(preorder,0,length-1,inorder,0,length-1,indexMap);
        return root;

    }

    public TreeNode rebuildTree(int[] preorder,int start_pre,int end_pre,int[] inorder,int start_in,int end_in,Map<Integer,Integer> indexMap){
        if(start_pre > end_pre){
            return null;
        }

        int rootVal = preorder[start_pre];
        TreeNode root = new TreeNode(rootVal);
        if(start_pre == end_pre){
            return root;
        } else {
            int index = indexMap.get(root.val);
            int leftNodes = index - start_in;
            int rightNodes = end_in - index;
            TreeNode leftTree = rebuildTree(preorder,start_pre+1,start_pre+leftNodes,inorder,start_in,index-1,indexMap);
            TreeNode rightTree = rebuildTree(preorder,start_pre+leftNodes+1,end_pre,inorder,index+1,end_in,indexMap);
            root.left = leftTree;
            root.right = rightTree;
            return root;
        }
    }
}

06. 用两个栈实现队列

class CQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.empty()){
            return stack2.pop();
        } else {
            if(stack1.empty()){
                return -1;
            } else{
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

07. 斐波那契数列

class Solution {
    public int fib(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int f0 = 0;
        int f1 = 1;
        int fn = 0;
        for(int i=1; i<n;i++){
            fn = (f0 + f1) % 1000000007;
            f0 = f1;
            f1 = fn;
        }
        return fn;
    }
}

08. 青蛙跳台阶问题

类似于斐波那契数列

class Solution {
    public int numWays(int n) {
        if(n == 1 || n==0){
            return 1;
        }
        if(n == 2){
            return 2;
        }

        int fn_1 = 1;
        int fn_2 = 2;
        int fn_3 = 0;

        for(int i=2; i<n; i++){
            fn_3 = (fn_1+fn_2) % 1000000007;
            fn_1 = fn_2;
            fn_2 = fn_3;
        }
        return fn_3;
    }
}

09. 旋转数组的最小数字

class Solution {
    public int minArray(int[] numbers) {
        int index1 = 0;
        int index2 = numbers.length-1;
        int indexMid;
        if(numbers[index1] < numbers[index2]){
            return numbers[index1];
        }

        while((index2-index1) > 1){
            indexMid = (index1+index2)/2;

            //如果index1和index2和indexMid的值都一样,就只能用顺序查找了
            if(numbers[index1] == numbers[index2] && numbers[index2] == numbers[indexMid]){
                int res = numbers[index1];
                for(int i=index1+1; i<=index2; i++){
                    if(res > numbers[i]){
                        res = numbers[i];
                    }
                }
                return res;
            }

            if(numbers[indexMid] >= numbers[index1]){
                index1 = indexMid;
            } else if(numbers[indexMid] <= numbers[index2]){
                index2 = indexMid;
            }
        }
        return numbers[index2];
    }
}

10. 矩阵中的路径

还有一些问题:

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        int wordLength = word.length();

        if(wordLength>(rows*cols)){
            return false;
        }

        boolean[][] map = new boolean[rows][cols];
        boolean flag = false;;
        for(int row=0; row<rows; row++){
            for(int col=0; col<cols; col++){
                if(board[row][col] == word.charAt(0)){
                    flag = hasPath(board,row,col,map,0,word);
                }
                if(flag == true){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean hasPath(char[][] board, int i, int j, boolean[][] map, int wordIndex, String word){
        if((wordIndex+1) == word.length()){
            return true;
        } else {
            if(i>=0 && i<board.length && j>=0 && j<board[0].length && map[i][j] == false && board[i][j]==word.charAt(wordIndex)){
                map[i][j] = true;
                wordIndex ++;
                if(hasPath(board,i+1,j,map,wordIndex,word)){
                    return true;
                } else if(hasPath(board,i-1,j,map,wordIndex,word)){
                    return true;
                } else if(hasPath(board,i,j+1,map,wordIndex,word)){
                    return true;
                } else if(hasPath(board,i,j-1,map,wordIndex,word)){
                    return true;
                } else{
                    return false;
                }
            } else{
                return false;
            }
        }
    }
}

11. 机器人的运动范围

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[] visited = new boolean[m*n];
        int cnt = mcount(m,n,k,0,0,visited);
        return cnt;
    }

    public int mcount(int m, int n, int k, int row, int col, boolean[] visited){
        int cnt = 0;
        if(check(m,n,k,row,col,visited)){
            visited[row*n+col] = true;
            cnt = 1+mcount(m,n,k,row-1,col,visited) + mcount(m,n,k,row+1,col,visited) + mcount(m,n,k,row,col-1,visited) + mcount(m,n,k,row,col+1,visited);
        }
        return cnt;

    }

    public boolean check(int m, int n, int k, int row, int col, boolean[] visited){
        if(row>=0 && row<m && col>=0 && col<n && getSum(row,col)<=k && !visited[row*n+col]){
            return true;
        }
        return false;
    }

    public int getSum(int row, int col){
        int sum = 0;
        while(row > 0){
            sum = sum + row%10;
            row = row/10;
        }
        while(col > 0){
            sum = sum + col%10;
            col = col/10;
        }
        return sum;
    }
}

12. 剪绳子<动态规划>

class Solution {
    public int cuttingRope(int n) {
        if(n < 2){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        int[] products = new int[n+1];
        products[0] = 0;
        //这里的原因是,如果长度是1、2、3时就不要切分了,因为分了以后更小了
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        int max = 0;
        for(int i=4; i<=n; i++){
            max = 0;
            for(int j=1; j<=i/2; j++){
                int product = products[j]*products[i-j];
                if(max < product){
                    max = product;
                }
            }
            products[i] = max;
        }
        return products[n];
    }
}

13. 剪绳子<贪心算法,大数取余>

参考详解:https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/

class Solution {
    public int cuttingRope(int n) {
        if(n < 2){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        //尽可能多的减去长度为3的绳子段
        int time3 = n/3;

        if(n - time3*3 == 1){
            time3 = time3-1;
        }

        int time2 = (n-time3*3)/2;
        long res = 1;
        //循环取余
        for(int i=0; i<time3; i++){
            res = (res * 3) % 1000000007;
        }
        for(int i=0; i<time2; i++){
            res = (res * 2) % 1000000007;
        }

        // long res = (long)(Math.pow(3,time3)) * (long)(Math.pow(2,time2)) % 1000000007;
        return (int)res;
    }
}

14. 二进制中1的个数

Java提供的位运算符有:左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ )

方法一:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            if((n&1) == 1){
                count ++;
            }
            n= n>>>1;
        }
        return count;
    }
}

牛皮方法二:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        /*
        int count = 0;
        while(n != 0){
            if((n&1) == 1){
                count ++;
            }
            n= n>>>1;
        }
        return count;
        */
        int count = 0;
        while(n != 0){
            count ++;
            n = (n-1)&n;
        }
        return count;
    }
}

15. 数值的整数次方

参考大佬:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/

/*class Solution {
    public double myPow(double x, int n) {
        if((x-0.0) < 0.00000001 && n < 0){
            return 0.0;
        }
        if(n == 0){
            return 1.0;
        }
        if(n < 0){
            double res = 1.0 / powerWithPositiveEx(x,-n);
            return res;
        } 
        double res = powerWithPositiveEx(x,n);
        return res;
        


    }
    /*普通做法
    public double powerWithPositiveEx(double x, int n){
        double res = 1.0;
        for(int i=0; i<n; i++){
            res = res * x;
        }
        return res;
    }
    *//*
    public double powerWithPositiveEx(double x, int n){
        int cnt = (int)(Math.log(n)/Math.log(2)) - 1;
        double res = x;
        for(int i=1; i<cnt; i++){
            res = res*res;
        }
        if(n%2 == 1){
            res = res*x;
        }
        return res;
    }
}*/
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

16. 打印从1到最大的n位数(大数问题)

class Solution {
    int res[];
    int index = 0;

    public int[] printNumbers(int n) {
        if(n <= 0){
            return new int[]{};
        }
        char[] number = new char[n];
        res = new int[(int)Math.pow(10, n) - 1];

        for(int i=0; i<10; i++){
            number[0] = (char)(i+'0');
            printToMax(number,n,0);
        }
        return res;
    }
    public void printToMax(char[] number, int length, int index){
        if(index == length-1){
            printIntoInt(number);
            return;
        }
        for(int i=0; i<10; i++){
            number[index+1] = (char)(i+'0');
            printToMax(number,length,index+1);
        }
    }
    public void printIntoInt(char[] number){
        int nLength = number.length;
        int result = 0;
        int j = 1;
        for(int i=nLength-1; i>=0; i--,j*=10){
            result = result + (number[i]-'0')*j;
        }
        if(result != 0){
            res[index] = result;
            index ++;
        }
        
    }
}

17. 删除链表的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //没有节点
        if(head == null){
            return head;
        }
        //只有一个节点,正好要删除他
        if(head.next == null && head.val == val){
            return null;
        }
        //要删除头节点
        if(head.val == val){
            return head.next;
        }
        ListNode temp = head;
        while(temp != null && temp.next != null){
            if(temp.next.val == val){
                temp.next = temp.next.next;
            }
            temp = temp.next;
        }
        return head;

    }
}

18. 正则表达式匹配(Hard)

有递归和动态规划两种方法,这里只有递归

/*有问题
class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return false;
        }
        int sIndex = 0;
        int pIndex = 0;
        return matchCore(s,p,sIndex,pIndex);
    }
    public boolean matchCore(String s, String p, int sIndex, int pIndex){
        if(sIndex >= s.length()-1 && pIndex >= p.length()-1){
            return true;
        }
        if(sIndex != s.length()-1 && pIndex == p.length()-1){
            return false;
        }
        if((pIndex+1)<p.length() && p.charAt(pIndex+1) == '*'){
            if(p.charAt(pIndex) == s.charAt(sIndex) || (p.charAt(pIndex) == '.' && sIndex != s.length()-1)){
                return matchCore(s,p,sIndex+1,pIndex+2) || matchCore(s,p,sIndex+1,pIndex) || matchCore(s,p,sIndex,pIndex+2);
            } else {
                return matchCore(s,p,sIndex,pIndex+2);
            }
        }
        if(s.charAt(sIndex) == p.charAt(pIndex) || (p.charAt(pIndex) == '.' && sIndex != s.length()-1)){
            return matchCore(s,p,sIndex+1,pIndex+1);
        }
        return false;
    }
}
*/
class Solution {
    public boolean isMatch(String A, String B) {
        // 如果字符串长度为0,需要检测下正则串
        if (A.length() == 0) {
            // 如果正则串长度为奇数,必定不匹配,比如 "."、"ab*",必须是 a*b*这种形式,*在奇数位上
            if (B.length() % 2 != 0) return false;
            int i = 1;
            while (i < B.length()) {
                if (B.charAt(i) != '*') return false;
                i += 2;
            }
            return true;
        }
        // 如果字符串长度不为0,但是正则串没了,return false
        if (B.length() == 0) return false;
        // c1 和 c2 分别是两个串的当前位,c3是正则串当前位的后一位,如果存在的话,就更新一下
        char c1 = A.charAt(0), c2 = B.charAt(0), c3 = 'a';
        if (B.length() > 1) {
            c3 = B.charAt(1);
        }
        // 和dp一样,后一位分为是 '*' 和不是 '*' 两种情况
        if (c3 != '*') {
            // 如果该位字符一样,或是正则串该位是 '.',也就是能匹配任意字符,就可以往后走
            if (c1 == c2 || c2 == '.') {
                return isMatch(A.substring(1), B.substring(1));
            } else {
                // 否则不匹配
                return false;
            }
        } else {
            // 如果该位字符一样,或是正则串该位是 '.',和dp一样,有看和不看两种情况
            if (c1 == c2 || c2 == '.') {
                return isMatch(A.substring(1), B) || isMatch(A, B.substring(2));
            } else {
                // 不一样,那么正则串这两位就废了,直接往后走
                return isMatch(A, B.substring(2));
            }
        }
    }
}

19. 表示数值的字符串

class Solution {
    private int index = 0;//全局索引
    private boolean scanUnsignedInteger(String str) {
        //是否包含无符号数
        int before = index;
        while(str.charAt(index) >= '0' && str.charAt(index) <= '9') 
            index++;
        return index > before;
    }
    private boolean scanInteger(String str) {
        //是否包含有符号数
        if(str.charAt(index) == '+' || str.charAt(index) == '-') 
               index++;
        return scanUnsignedInteger(str);
    }
    public boolean isNumber(String s) {
        //空字符串
        if(s == null || s.length() == 0)
            return false;
        //添加结束标志
        s = s + '|';
        //跳过首部的空格
        while(s.charAt(index) == ' ')
            index++;
        boolean numeric = scanInteger(s); //是否包含整数部分
        if(s.charAt(index) == '.') {  
            index++;
            //有小数点,处理小数部分
            //小数点两边只要有一边有数字就可以,所以用||,
            //注意scanUnsignedInteger要在前面,否则不会进
            numeric = scanUnsignedInteger(s) || numeric;
        }
        if((s.charAt(index) == 'E' || s.charAt(index) == 'e')) { 
            index++;
            //指数部分
            //e或E的两边都要有数字,所以用&&
            numeric = numeric && scanInteger(s);
        }
        //跳过尾部空格
        while(s.charAt(index) == ' ')
            index++;
        return numeric && s.charAt(index) == '|' ;
    }
}

20. 调整数组顺序使奇数位于偶数前面

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length == 0 ||nums.length == 1){
            return nums;
        }
        int indexOne = 0;
        int indexTwo = nums.length-1;
        while(indexTwo > indexOne){
            while(indexOne < indexTwo && nums[indexOne]%2 != 0){
                indexOne ++;
            }
            while(indexTwo > indexOne && nums[indexTwo]%2 != 1){
                indexTwo --;
            }
            if(indexTwo <= indexOne){
                break;
            }
            int temp = nums[indexOne];
            nums[indexOne] = nums[indexTwo];
            nums[indexTwo] = temp;
            indexOne ++;
            indexTwo --;
        }
        return nums;
    }
}

21. 链表中倒数第k个节点

/**
 * 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) {
        if(head == null || k == 0){
            return null;
        }
        ListNode tempOne = head;
        ListNode tempTwo = head;
        for(int i=0; i<k-1; i++){
            if(tempOne.next != null){
                tempOne = tempOne.next;
            } else {
                return null;
            }
        }
        while(tempOne.next != null){
            tempOne = tempOne.next;
            tempTwo = tempTwo.next;
        }
        return tempTwo;
    }
}

22. 反转链表

用的是一个个嵌进去的方法,参考尚学堂数据结构课

/**
 * 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 || head.next == null){
            return head;
        }
        ListNode reverseHead = new ListNode(-1);
        ListNode tempOri = head;
        ListNode tempNext;
        while(tempOri != null){
            tempNext = tempOri.next;
            tempOri.next = reverseHead.next;
            reverseHead.next = tempOri;
            if(tempNext == null){
                break;
            }
            tempOri = tempNext;
            tempNext = tempNext.next;
        }
        return reverseHead.next;
    }
}

23. 合并两个排序的链表

循环迭代:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        ListNode preHead = new ListNode(-1);
        ListNode temp = preHead;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            } else {
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){
            temp.next = l2;
        } else{
            temp.next = l1;
        }
        return preHead.next;
    }
}

递归:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /*
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        ListNode preHead = new ListNode(-1);
        ListNode temp = preHead;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            } else {
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){
            temp.next = l2;
        } else{
            temp.next = l1;
        }
        return preHead.next;
        */

        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

24. 树的子结构

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        boolean res = false;
        if(A != null && B != null){
            if(A.val == B.val){
                res = proveSubStructure(A,B);
            }
            if(res == false){
                res = isSubStructure(A.left,B);
            }
            if(res == false){
                res = isSubStructure(A.right,B);
            }
        }
        return res;
    }
    public boolean proveSubStructure(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null){
            return false;
        }
        if(A.val != B.val){
            return false;
        }
        return proveSubStructure(A.left,B.left) && proveSubStructure(A.right,B.right);
    }
}

25. 二叉树的镜像

/**
 * 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 root;
        }
        if(root.left == null && root.right ==null){
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if(root.left != null){
            mirrorTree(root.left);
        }
        if(root.right != null){
            mirrorTree(root.right);
        }
        return root;
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×