剑指Offer【11-20】Java实现

古城微笑少年丶 2022-05-19 03:47 187阅读 0赞

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

public class Solution {
        public int NumberOf1(int n) {
            int num = 0;
            int[] arr = new int[32];
            if(n > 0){
                arr = getT(n);
    
            }
            else if(n < 0){
                arr = getC(n);
            }
            else{
                return 0;
            }
            for(int i=0; i<arr.length; i++){
                if(arr[i] == 1){
                    num++;
                }
            }
            return num;
        }
        public int[] getT(int n){
            int[] arr = new int[32];
            if(n == 0){
                return arr;
            }
            int m = n>0?n:-n;
            int cur = arr.length-1;
            while(m!=0){
                int x = m%2;
                arr[cur] = x;
                m = m/2;
                cur--;
            }
            if(n < 0){
                arr[0] = 1;
            }
            else{
                arr[0] = 0;
            }
            return arr;
        }
        public int[] getR(int n){
            int[] arr = new int[32];
            arr = getT(n);
            for(int i=arr.length-1; i>0; i--){
                if(arr[i] == 0){
                    arr[i] = 1;
                }
                else{
                    arr[i] = 0;
                }
            }
            return arr;
        }
        public int[] getC(int n){
            int[] arr = new int[32];
            arr = getR(n);
    
            boolean flag = false;
            for(int i=arr.length-1; i>0; i--){
                if(arr[i] == 0){
                    arr[i] = 1;
                    break;
                }
                else if(arr[i] == 1 && flag == false){
                    arr[i] = 0;
                }
            }
    
            return arr;
        }
    }

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

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

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

public class Solution {
        public void reOrderArray(int [] array) {
            int[] arr = new int[array.length];
            int j = 0;
            for(int i=0; i<array.length; i++){
                if(isJ(array[i])){
                    arr[j] = array[i];
                    j++;
                }
            }
            for(int i=0,k=j;i<array.length;i++){
                if(!isJ(array[i])){
                    arr[k] = array[i];
                    k++;
                }
            }
            for(int i=0; i<array.length; i++) {
                array[i] = arr[i];
            }
        }
        public boolean isJ(int a){
            if(a%2 == 0){
                return false;
            }
            return true;
        }
    }

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

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            if(head == null){
                return null;
            }
            ListNode p1 = head;
            ListNode p2 = head;
            int num = k;
            while(num>0 && p1!=null){
                num--;
                p1 = p1.next;
            }
            if(num>0){
                return null;
            }
            //System.out.print(p1.val);
            while(p1 != null){
                p2 = p2.next;
                p1 = p1.next;
            }
            return p2;
        }
    }

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

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

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

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            ListNode node = null;
            ListNode head = null;
            if(list1==null){
                return list2;
            }
            if(list2==null){
                return list1;
            }
            if(list1.val<list2.val){
                head = list1;
                node = head;
                list1 = list1.next;
            }
            else{
                head = list2;
                node = head;
                list2 = list2.next;
            }
            while(list1!=null && list2!=null){
                //ListNode nodeNext = null;
                if(list1.val<list2.val){
    
                    node.next = list1;
    
                    //node.next = nodeNext;
                    node = node.next;
                    list1 = list1.next;
                }
                else{
                    node.next = list2;
    
                    //node.next = nodeNext;
                    node = node.next;
                    list2 = list2.next;
                }
            }
            if(list1!=null){
                node.next = list1;
            }
            if(list2!=null){
                node.next = list2;
            }
            return head;
        }
    }

17、输入两棵二叉树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){
                return false;
            }
            if(root2 == null){
                return false;
            }
            if(root1 == root2){
                return true;
            }
            boolean flag = false;
            flag = match(root1,root2);
            if(flag){
                return true;
            }
            else{
                return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
            }   
        }
        public boolean match(TreeNode node1,TreeNode node2){
            if(node2 == null){
                return true;
            }
            if(node1 == null){
                return false;
            }
            if(node1.val == node2.val){
                return match(node1.left,node2.left)&&match(node1.right,node2.right);
            }
            return false;
        }
    }

18、操作给定的二叉树，将其变换为源二叉树的镜像。  
输入描述:  
二叉树的镜像定义：源二叉树  
8  
/ \\  
6 10  
/ \\ / \\  
5 7 9 11  
镜像二叉树  
8  
/ \\  
10 6  
/ \\ / \\  
11 9 7 5

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

19、输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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> arr = new ArrayList<Integer>();
               if(matrix == null){
                   return arr;
               }
               boolean flag = true;
               while(flag){
                   for(int i=0; i<matrix[0].length; i++){
                       arr.add(matrix[0][i]);
                   }
                   //System.out.println(arr.toString());
                   matrix = delFirstRow(matrix);
                   if(matrix.length == 0){
                       break;
                   }
                   matrix = rotate(matrix);  
               }
               //System.out.println(arr.toString());
               return arr;
        }
        public int[][] delFirstRow(int[][] matrix){
            int[][] arr = new int[matrix.length-1][matrix[0].length];
            for(int i=1,k=0; i<matrix.length; i++,k++){
                for(int j=0; j<matrix[i].length; j++){
                    arr[k][j] = matrix[i][j];
                }
            }
            /*for(int i=0; i<arr.length; i++){
                for(int j=0; j<arr[i].length; j++){
                    System.out.print(arr[i][j] + " ");
                }
            }*/
            return arr;
        }
        /**
         * 旋转数组
         * 1 2 3     3 6
         * 4 5 6     2 5
         *           1 4
         * @param matrix
         * @return
         */
        public int[][] rotate(int[][] matrix){
            int[][] arr = new int[matrix[0].length][matrix.length];
            for(int j=matrix[0].length-1,k=0; j>=0; j--,k++){
                for(int i=0; i<matrix.length; i++){
                    arr[k][i] = matrix[i][j];
                }
            }
            /*for(int i=0; i<arr.length; i++){
                for(int j=0; j<arr[i].length; j++){
                    System.out.print(arr[i][j] + " ");
                }
            }*/
            return arr;
        }
    }

20、定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

import java.util.Stack;
    
    public class Solution {
    
    
        Stack<Integer> stack = new Stack<Integer>();
        int min = 0;
        Stack<Integer> stack2 = new Stack<Integer>();
        public void push(int node) {
            if(stack.isEmpty()){
                min = node;
                stack.push(node);
                return;
            }
            stack.push(node);
            while(!stack.isEmpty()){
                int tmp = stack.peek();
                min = min<tmp?min:tmp;
                stack2.push(stack.pop());
            }
            while(!stack2.isEmpty()){
                stack.push(stack2.pop());
            }
        }
    
        public void pop() {
            if(stack.isEmpty()){
                return;
            }
            stack.pop();
            min = stack.peek();
            while(!stack.isEmpty()){
                int tmp = stack.peek();
                min = min<tmp?min:tmp;
                stack2.push(stack.pop());
            }
            while(!stack2.isEmpty()){
                stack.push(stack2.pop());
            }
    
        }
    
        public int top() {
            return stack.peek();
        }
    
        public int min() {
            return min;
        }
    }