剑指offer——java刷题总结【二】

Note

• 题解汇总：剑指offer题解汇总
• 代码地址：Github 剑指offer Java实现汇总
• 点击目录中的题名链接可直接食用题解~
• 有些解法博文中未实现，不代表一定很难，可能只是因为博主太懒```(Orz)
• 如果博文中有明显错误或者某些题目有更加优雅的解法请指出，谢谢~

目录

正文

11、二进制中1的个数

题目描述

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

题目分析

解法一： 首先需要了解一个前提：将数字n和1做&运算，可以判断n当前最后一位是否是1。有了这个前提后，我们就可以不断将数字n进行无符号右移，将n和1做&操作判断当前数字最后一位是否为1并计数即可。
使用无符号右移>>>而不是带符号右移>>的原因：因为对于带符号右移，正数右移高位补0，负数右移高位补1；而对于无符号右移，无论是正数还是负数，高位通通补0。如果选择带符号右移，当n为负数时，会一直在n的左边补1，n永远不会等于0，程序会进入死循环。

代码实现

解法一： O(1)

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

12、数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。

题目分析

解法一： 使用单层循环对底数base进行累乘即可，但是需要考虑边界0的情况，以及当指数exponent为负数时，结果应该为（base的exponent次方）分之1。
解法二： 使用快速幂的方式进行计算，即x的n次方乘以x的n次方等于x的2n次方，由此二分计算结果。

代码实现

解法一： O(n)

public double Power(double base, int exponent) {
     if (base == 0) return 0;
     if (exponent == 0) return 1;
     double res = 1;
     for (int i = 1; i <= Math.abs(exponent); i++) {
       res *= base;
     }
     return exponent > 0 ? res : 1 / res;
}

解法二： O(logn)

    public double Power(double base, int exponent) {
        long N = n;
        return n >= 0 ? quickCal(x, N) : 1 / quickCal(x, -N);
    }

    public double quickCal(double x, long n) {
        double res = 1.0;
        double tx = x;
        while (n > 0) {
            if ((n & 1) == 1) {
                res *= tx;
            }
            tx *= tx;
            n /= 2;
        }
        return res;
    }

13、调整数组顺序使奇数位于偶数前面

题目描述

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

题目分析

解法一： 开辟一个新数组，对数组进行两次遍历，第一次遍历寻找奇数并存放在新数组中，第二次遍历寻找偶数并存放在新数组中。该解法的空间复杂度为O(n)。
解法二： 本解法参考快排中的partition思想，不开辟新数组，可以将奇数放在偶数前面，但由于partition方法的不稳定性，无法保证数字之间的相对次序不变，时间复杂度为O(n)，空间复杂度为O(1)。如果需要满足题目中所述的“奇数和奇数，偶数和偶数之间的相对位置不变”，就需要通过数组移位实现swap的稳定性，由于需要循环移位，故最终的时间复杂度会退化成O(n²)。

代码实现

解法一： O(n)

public void reOrderArray(int [] array) {
   int[] newArr = new int[array.length];
   int index = 0;
   for (int i = 0; i < array.length; i++) {
      if ((array[i] & 1) == 1) {
         newArr[index++] = array[i];
      }
   }
   for (int i = 0; i < array.length; i++) {
      if ((array[i] & 1) == 0) {
         newArr[index++] = array[i];
      }
   }
   for (int i = 0; i < array.length; i++) {
      array[i] = newArr[i];
   }
}

解法二： O(n²)

public void reOrderArray1(int [] array) {
   int pre = -1;
   int suf = array.length;
   int l = 0;
   while (l < suf) {
      if ((array[l] & 1) == 1) {
         swap(array, ++pre, l++);
      } else {
         swap(array, --suf, l);
      }
   }
}

14、链表中倒数第k个结点

题目描述

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

题目分析

解法一： 双指针法。使用快指针和慢指针两个指针，快指针先走k步，然后快慢指针同时走，当快指针指向null时，慢指针所指结点即为链表中倒数第k个结点。

代码实现

解法一： O(n)

public ListNode FindKthToTail(ListNode head, int k) {
   if (head == null) return null;
   ListNode fast = head;
   ListNode slow = head;
   while (k-- > 0) {
      if (fast != null) {
         fast = fast.next;  
      } else {
          return null;
        }
   }
    while (fast != null) {
      fast = fast.next;
      slow = slow.next;
   }
   return slow;
}

15、反转链表

题目描述

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

题目分析

解法一： 使用pre和next两个指针，分别标识当前节点的前驱和后继，对指针指向进行改变即可。
解法二： 使用递归实现，对当前节点的next进行递归，只需要考虑返回得到的是指向一个末尾节点的指针，然后对指针进行调整即可。

代码实现

解法一： O(n)

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

解法二： O(n)

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

16、合并两个排序的链表

题目描述

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

题目分析

解法一： 设置头结点head和头结点的引用cur。当两个链表都不为空时，cur指向两个链表指向节点中较小的那一个，然后指针后移；当有一个链表为空时，将cur直接指向非空链表的后续头节点。该过程其实就是归并排序中的merge过程。

代码实现

解法一： O(min(m,n))

public ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode cur = head;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    if (list1 != null) {
        cur.next = list1;
    }
    if (list2 != null) {
        cur.next = list2;
    }
    return head.next;
}

17、树的子结构

题目描述

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

题目分析

解法一： 非递归实现。
1、实现isSubTree()方法，传入两个值相同的节点t1和t2，用于判断以t2为根节点的树是否是以t1为根节点的树的子结构；
2、在Main方法中对树A进行遍历，寻找与树B根节点值相同的节点，调用isSubTree()判断是否存在子结构；
3、本解法未使用递归实现，而是实现了两种非递归的遍历，isSubTree()中采用层序遍历，主方法中采用中序遍历。
解法二： 递归实现。
1、由于判断的是tree2是否为tree1的子结构，所以当tree2为空时，tree1无论为什么值，都应该返回true；
2、当tree1为空，tree2不为空时，说明tree2不是tree1的子结构，返回false；
3、当tree1和tree2的当前值不等时，返回false；
4、当tree1和tree2都不为空且值相等时，说明当前节点判断完毕，接下来需要对当前节点的左、右子树进行递归判断。

代码实现

解法一： O(m*n)

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root2 == null) return false;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.empty() || root1 != null) {
        if (root1 != null) {
            stack.push(root1);
            root1 = root1.left;
        } else {
            root1 = stack.pop();
            if (root1.val == root2.val && isSubTree(root1, root2)) {
                return true;
            }
            root1 = root1.right;
        }
    }
    return false;
}

public static boolean isSubTree(TreeNode root1, TreeNode root2) {
    Queue<TreeNode> q1 = new LinkedList<>();
    Queue<TreeNode> q2 = new LinkedList<>();
    q1.add(root1);
    q2.add(root2);
    while (!q2.isEmpty()) {
        TreeNode t1 = q1.poll();
        TreeNode t2 = q2.poll();
        if (t1.val != t2.val) {
            return false;
        } else {
            if (t1.left != null && t2.left != null) {
                q1.add(t1.left);
                q2.add(t2.left);
            } else if (t1.left == null && t2.left != null){
                return false;
            }
            if (t1.right != null && t2.right != null) {
                q1.add(t1.right);
                q2.add(t2.right);
            } else if (t1.right == null && t2.right != null){
                return false;
            }
        }
    }
    return true;
}

解法二： O(m*n)

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) return false;
    return isSubTree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}

public boolean isSubTree(TreeNode tree1, TreeNode tree2){
    if (tree2 == null) return true;
    if (tree1 == null) return false;
    if (tree1.val != tree2.val) return false;
    return isSubTree(tree1.left, tree2.left) && isSubTree(tree1.right, tree2.right);
}

18、二叉树的镜像

题目描述

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

题目分析

解法一： 非递归实现。对该树进行层次遍历，对当前遍历的节点进行判断：
1、如果左右孩子都不为空，则交换两个孩子，并将两个节点入队；
2、如果左右孩子有一个为空，则交换两个孩子，也就是将非空孩子赋给空节点，对非空孩子置空，将交换后的非空节点入队；
3、如果左右子树都为空，则无需处理。
解法二： 递归实现。将当前遍历节点的左右孩子进行交换，然后递归地对左右孩子进行相同操作，当前节点为null时结束递归。

代码实现

解法一： O(n)

public void Mirror(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.left != null && root.right != null) {
            TreeNode t = root.left;
            root.left = root.right;
            root.right = t;
            queue.add(root.left);
            queue.add(root.right);
        } else if (root.left != null && root.right == null) {
            root.right = root.left;
            root.left = null;
            queue.add(root.right);
        } else if (root.left == null && root.right != null) {
            root.left = root.right;
            root.right = null;
            queue.add(root.left);
        }
    }
}

解法二： O(n)

public void Mirror(TreeNode root) {
    if(root == null) return;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    Mirror(root.left);
    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.

题目分析

解法一： 该类题目需要从宏观的角度去考虑。
1、首先定义一个方法printLevel，给定矩阵的左上角和右下角两个点，使用四个循环遍历顺时针输出矩阵的外圈。注：需要考虑只包含一行和一列的情况，当只有一行时，从左往右依次打印；当只有一列时，从上往下依次打印。
2、确定矩阵的左上角和右下角，不断缩小矩阵，递进到内圈矩阵，调用步骤1中的方法打印当前矩阵的最外圈。

代码实现

解法一： O(m*n)

public ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    int row1 = 0;
    int col1 = 0;
    int row2 = matrix.length - 1;
    int col2 = matrix[0].length - 1;
    while (row1 <= row2 && col1 <= col2) {
        printLevel(list, matrix, row1++, col1++, row2--, col2--);
    }
    return list;
}

public static void printLevel(ArrayList<Integer> list, int[][] matrix,
                              int row1, int col1, int row2, int col2) {
    if (row1 == row2) {
        for (int i = col1; i <= col2; i++) {
            list.add(matrix[row1][i]);
        }
    } else if (col1 == col2){
        for (int i = row1; i <= row2; i++) {
            list.add(matrix[i][col1]);
        }
    } else {
        int curRow = row1;
        int curCol = col1;
        while (curCol < col2) {
            list.add(matrix[curRow][curCol++]);
        }
        while (curRow < row2) {
            list.add(matrix[curRow++][curCol]);
        }
        while (curCol > col1) {
            list.add(matrix[curRow][curCol--]);
        }
        while (curRow > row1) {
            list.add(matrix[curRow--][curCol]);
        }
    }
}

20、包含min函数的栈

题目描述

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

题目分析

解法一： 双栈法。使用min栈来存储当前栈的最小元素，对于最小元素相同的连续序列，在min栈中只存储一个，可以压缩部分空间，尽管空间复杂度都为O(n)。
1、当压入栈时，如果min栈为空则直接压入；否则判断当前压入元素是否小于等于min栈的栈顶元素：如果小于等于则说明当前压入的元素是stack的最小元素，则push到min栈，如果大于则说明min栈的栈顶元素依然是stack中的最小元素，则不做任何操作；
2、当弹出栈时，如果stack和min栈的栈顶元素相同，说明stack中的最小元素此时要出栈了，则min栈也执行pop操作。

代码实现

解法一： O(n)

Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();

public void push(int node) {
    stack.push(node);
    if (minStack.empty()) {
        minStack.push(node);
    } else {
        if (node <= minStack.peek()) {
            minStack.push(node);
        }
    }
}

public void pop() {
    if (stack.peek() == minStack.peek()) {
        minStack.pop();
    }
    stack.pop();
}

public int top() {
    return stack.peek();
}

public int min() {
    return minStack.peek();
}