Skip to main content
 首页 » 编程设计

Java面试剑指offer系列四

2022年07月19日45myhome

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

       a)这里首先判断两个链表中有没有空表,这个就是依据表头是否为空。然后就是比较节点值的大小,然后就是使用递归求出接下来的节点。

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

17.输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

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) { 
 
    //定义一个变量用来返回树1是否包含树2 
 
        boolean result = false; 
 
        
 
        if(root1 != null && root2 != null){ 
 
            if(root1.val == root2.val) 
 
                result = DoesTree1HaveTree2(root1,root2); 
 
            if(!result) 
 
                result = HasSubtree(root1.left,root2); 
 
            if(!result) 
 
                result = HasSubtree(root1.right,root2); 
 
        } 
 
        
 
        return result; 
 
    } 
 
    
 
//该方法用来判断树1是否包含树2 
 
    public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){ 
 
        if(root2 == null) 
 
            return true; 
 
        if(root1 == null) 
 
            return false; 
 
        if(root1.val != root2.val) 
 
            return false; 
 
        
 
        return DoesTree1HaveTree2(root1.left,root2.left) 
 
&&DoesTree1HaveTree2(root1.right,root2.right); 
 
    } 
 
}

18.操作给定的二叉树,将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义:源二叉树

              8

             /  \

            6   10

           / \   / \

          5  7  9 11

          镜像二叉树

              8

             /  \

            10  6

           / \   / \

          11 9  7  5

class TreeNode { 
 
    int val = 0; 
 
    TreeNode left = null; 
 
    TreeNode right = null; 
 
  
 
    public TreeNode(int val) { 
 
        this.val = val; 
 
  
 
    } 
 
  
 
} 
 
public class Solution { 
 
    public void Mirror(TreeNode root) { 
 
        if(root == null) 
 
            return; 
 
        if(root.left == null && root.right != null){ 
 
            root.left = root.right; 
 
            root.right = null; 
 
        }else if(root.left != null && root.right == null){ 
 
            root.right = root.left; 
 
            root.left = null; 
 
        }else if(root.left != null && root.right != null){ 
 
            TreeNode temp = root.left; 
 
            root.left = root.right; 
 
            root.right = temp; 
 
        } 
 
        
 
        if(root.left!=null) 
 
            Mirror(root.left); 
 
        if(root.right!=null) 
 
            Mirror(root.right); 
 
    } 
 
}

19.输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList; 
 
public class Solution { 
 
    public ArrayList<Integer> printMatrix(int [][] matrix) { 
 
       ArrayList<Integer> result = new ArrayList<Integer> (); 
 
        //如果二维数组的长度为0的话就返回没有值的list 
 
        if(matrix.length==0) 
 
            return result; 
 
        int n = matrix.length; 
 
        int m = matrix[0].length; 
 
        if(m==0) 
 
            return result; 
 
        int lay = (Math.min(n,m)+1)/2;//这个是层数 
 
        for(int i=0;i<lay;i++){ 
 
            for(int k = i;k<m-i;k++) 
 
                result.add(matrix[i][k]);//左至右 
 
            for(int j=i+1;j<n-i;j++) 
 
                result.add(matrix[j][m-i-1]);//右上至右下 
 
            for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--) 
 
                result.add(matrix[n-i-1][k]);//右至左 
 
            for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--) 
 
                result.add(matrix[j][i]);//左下至左上 
 
        } 
 
        return result; 
 
    } 
 
}

20.定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

import java.util.Stack; 
 
public class Solution { 
 
       Stack s1 = new Stack(); 
 
    Stack s2 = new Stack(); 
 
    int min = 0; 
 
    
 
    public void push(int node) { 
 
        if(s1.size() == 0 && s2.size() == 0){ 
 
             s1.push(node); 
 
             s2.push(node); 
 
             min = node; 
 
        }else{ 
 
             s1.push(node); 
 
             if(node<=min){ 
 
                    min = node; 
 
                    s2.push(min); 
 
             }else{ 
 
                    s2.push(min); 
 
             } 
 
        } 
 
             
 
    } 
 
    
 
    public void pop() { 
 
          if(s1.size() == 0 && s2.size() == 0){ 
 
                 System.out.println("栈内没有元素了!"); 
 
          }else{ 
 
                 s1.pop(); 
 
                 s2.pop(); 
 
          } 
 
        
 
    } 
 
    
 
    public int min() { 
 
          int m = 0; 
 
          if(s2.size() != 0){ 
 
                 m = (int) s2.pop(); 
 
                 s2.push(m); 
 
          } 
 
        
 
        return m; 
 
    } 
 
  
 
       public static void main(String[] args) { 
 
              Solution s = new Solution(); 
 
              s.push(1); 
 
              s.push(3); 
 
              s.push(5); 
 
              s.push(0); 
 
              System.out.println(s.min()); 
 
       } 
 
  
 
}

本文参考链接:https://www.cnblogs.com/wgl1995/p/5782075.html