《剑指offer》刷题记录【持续更新中】

面试题3：数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return Integer.MAX_VALUE;
    }
}

面试题4：二维数组中的查找

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

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length < 1 || matrix[0].length < 1) {
            return false;
        }
        int i = 0;
        int j = matrix[i].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
}

面试官5：替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

class Solution {
    public String replaceSpace(String s) {
        char[] cArray = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cArray.length; i++) {
            sb.append(Character.isSpaceChar(cArray[i]) ? "%20" : cArray[i]);
        }
        return sb.toString();
    }
}

面试题6：从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

class Solution {
    List list = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        reverse(head);
        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
        return array;
    }

    public void reverse(ListNode head) {
        if (head.next != null) {
            reversePrint(head.next);
        }
        list.add(head.val);
    }
}

面试题9：用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能(若队列中没有元素，deleteHead 操作返回 -1 )。

class CQueue {
    Stack stack1;
    Stack stack2;

    public CQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void appendTail(int value) {
        stack2.push(value);
    }

    public int deleteHead() {
        int head = -1;
        if (stack1.size() > 0 || stack2.size() > 0) {
            if (stack1.size() == 0 && stack2.size() > 0) {
                while (stack2.size() > 0) {
                    stack1.push(stack2.pop());
                }
            }
            head = stack1.pop();
        }
        return head;
    }
}

面试题10-1：斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

class Solution {
   public int fib(int n) {
        int x = 0;
        int y = 1;
        int z = 1;
        while (n > 0) {
            z = (x + y) % 1000000007;
            x = y;
            y = z;
            n--;
        }
        return x;
    }
}

面试题10-2：青蛙跳台阶问题

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

class Solution {
    Map map = new HashMap();

    public int numWays(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (n > 2) {
            if (map.containsKey(n)) {
                return map.get(n);
            }
            int num = (numWays(n - 1) + numWays(n - 2)) % 1000000007;
            map.put(n, num);
            return num;
        }
        return 1;
    }
}

面试题11：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。

class Solution {
    public int minArray(int[] numbers) {
        if (numbers.length == 0) {
            return Integer.MAX_VALUE;
        }
        int result = numbers[0];
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                return numbers[i + 1];
            }
        }
        return result;
    }
}

面试题18：删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            if (head.val == val) {
                return null;
            } else {
                return head;
            }
        }
        ListNode p1 = new ListNode(0);
        p1.next = head;
        ListNode p2 = head.next != null ? head.next : null;
        ListNode p3 = p1;
        while (p2 != null) {
            if (head.val == val) {
                p1.next = p2;
                break;
            }
            p2 = p2.next != null ? p2.next : null;
            head = head.next;
            p1 = p1.next;
        }
        if (head.val == val) {
            p1.next = p2;
        }
        return p3.next != null ? p3.next : null;
    }
}

面试题22：链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

class Solution {
    int      count = Integer.MIN_VALUE;
    ListNode Kth;

    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        getKth(head, k);
        return Kth;
    }

    public void getKth(ListNode head, int k) {
        if (head.next == null) {
            count = 1;
        } else {
            getKth(head.next, k);
            count++;
        }
        if (count == k) {
            Kth = head;
        }
    }
}

面试题24：反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

class Solution {
    ListNode p1;
    ListNode p2;

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        while (head.next != null) {
            p2 = head.next;
            head.next = p1;
            p1 = head;
            head = p2;
        }
        head.next = p1;
        return head;
    }
}

面试题27：二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

class Solution {
    TreeNode treeNode;

    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        mirror(root);
        return root;
    }

    public void mirror(TreeNode node) {
        treeNode = node.left;
        node.left = node.right;
        node.right = treeNode;
        if (node.left != null) {
            mirror(node.left);
        }
        if (node.right != null) {
            mirror(node.right);
        }
    }
}

面试题28：对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return compare(node1.left, node2.right) && compare(node1.right, node2.left);
    }
}

面试题30：包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack {
    Stack stack1;
    Stack stack2;
    int            min;

    public MinStack() {
        stack1 = new Stack();
        stack2 = new Stack();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        stack1.push(x);
        if (x < min) {
            min = x;
        }
        stack2.push(min);
    }

    public void pop() {
        stack1.pop();
        stack2.pop();
        if (!stack2.empty()) {
            min = stack2.peek();
        } else {
            min = Integer.MAX_VALUE;
        }
    }

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

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

面试题32-1：从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

class Solution {
    List   list  = new ArrayList<>();
    Queue queue = new linkedList<>();

    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        addNode(root);
        while (!queue.isEmpty()) {
            addNode(queue.poll());
        }
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }
        return array;
    }

    public void addNode(TreeNode node) {
        list.add(node.val);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

面试题32-2：从上到下打印二叉树2

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

class Solution {
    List>         lists        = new ArrayList<>(); //result
    Map> levelListMap = new HashMap<>();   //key:level, value:list
    Map      nodeLevelMap = new HashMap<>();   //key:node, value:level
    Queue             queue        = new linkedList<>();

    public List> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        nodeLevelMap.put(root, 1);
        addNode(root);
        while (!queue.isEmpty()) {
            addNode(queue.poll());
        }
        for (int i = 1; true; i++) {
            if (levelListMap.containsKey(i)) {
                lists.add(levelListMap.get(i));
            } else {
                break;
            }
        }
        return lists;
    }

    public void addNode(TreeNode node) {
        if (!levelListMap.containsKey(nodeLevelMap.get(node))) {
            levelListMap.put(nodeLevelMap.get(node), new ArrayList<>());
        }
        levelListMap.get(nodeLevelMap.get(node)).add(node.val);

        if (node.left != null) {
            queue.add(node.left);
            nodeLevelMap.put(node.left, nodeLevelMap.get(node) + 1);
        }
        if (node.right != null) {
            queue.add(node.right);
            nodeLevelMap.put(node.right, nodeLevelMap.get(node) + 1);
        }
    }
}

面试题32-3：从上到下打印二叉树3

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

class Solution {
    List>         lists        = new ArrayList<>();
    Map> levelListMap = new HashMap<>();   //key:level, value:list
    Map      nodeLevelMap = new HashMap<>();   //key:node, value:level
    Queue             queue        = new linkedList<>();

    public List> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        nodeLevelMap.put(root, 1);
        addNode(root);
        while (!queue.isEmpty()) {
            addNode(queue.poll());
        }
        for (int i = 1; true; i++) {
            if (levelListMap.containsKey(i)) {
                lists.add(levelListMap.get(i));
            } else {
                break;
            }
        }
        return lists;
    }

    public void addNode(TreeNode node) {
        if (!levelListMap.containsKey(nodeLevelMap.get(node))) {
            levelListMap.put(nodeLevelMap.get(node), new ArrayList<>());
        }
        if (nodeLevelMap.get(node) % 2 == 1) {
            levelListMap.get(nodeLevelMap.get(node)).add(node.val);
        } else {
            levelListMap.get(nodeLevelMap.get(node)).add(0, node.val); //头插入
        }

        if (node.left != null) {
            queue.add(node.left);
            nodeLevelMap.put(node.left, nodeLevelMap.get(node) + 1);
        }
        if (node.right != null) {
            queue.add(node.right);
            nodeLevelMap.put(node.right, nodeLevelMap.get(node) + 1);
        }
    }
}

面试题35：复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

class Solution {
    Map map = new HashMap<>();
    Node            p1;
    Node            p2;

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        p1 = head;
        Node head2 = new Node(0);
        p2 = head2;
        while (p1 != null) {
            p2.next = new Node(p1.val);
            p2 = p2.next;
            p2.random = p1.random;
            map.put(p1, p2);
            if (p1.next != null) {
                p1 = p1.next;
            } else {
                p1 = null;
            }
        }

        p2 = head2.next;
        while (p2 != null) {
            p2.random = map.get(p2.random);
            if (p2.next != null) {
                p2 = p2.next;
            } else {
                p2 = null;
            }
        }

        return head2.next;
    }
}

面试题42：连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        int maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
            if (nums[i] > 0 && sum > maxSum) {
                maxSum = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
            if (nums[i] > maxNum) {
                maxNum = nums[i];
            }
        }
        if (maxSum < 0) {
            maxSum = maxNum;
        }
        return maxSum;
    }
}

面试题46：把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

class Solution {
    Map map = new HashMap();

    public int translateNum(int num) {
        if (num == 0) {
            return 1;
        }
        List list = new linkedList<>();
        while (num != 0) {
            list.add(0, num % 10);
            num = num / 10;
        }
        return getNum(list, list.size() - 1);
    }

    public int getNum(List list, int index) {
        if (map.containsKey(index)) {
            return map.get(index);
        }
        if (index == 0) {
            return 1;
        }
        if (index == 1) {
            if ((list.get(index - 1) == 1) || (list.get(index - 1) == 2 && list.get(index) <= 5)) {
                return 2;
            }
            return 1;
        }
        if ((list.get(index - 1) == 1) || (list.get(index - 1) == 2 && list.get(index) <= 5)) {
            map.put(index, getNum(list, index - 1) + getNum(list, index - 2));
        } else {
            map.put(index, getNum(list, index - 1));
        }
        return map.get(index);
    }
}

面试题47：礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

class Solution {
    Map map = new HashMap<>();

    public int maxValue(int[][] grid) {
        if (grid.length < 1 || grid[0].length < 1) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int result = getValue(grid, m - 1, n - 1);
        return result;
    }

    public int getValue(int[][] grid, int x, int y) {
        if (x < 0 || y < 0) {
            return 0;
        }
        if (map.containsKey(x + "," + y)) {
            return map.get(x + "," + y);
        } else {
            map.put(x + "," + y,
                grid[x][y] + compare(getValue(grid, x - 1, y), getValue(grid, x, y - 1)));
            return map.get(x + "," + y);
        }
    }

    public int compare(int a, int b) {
        return a >= b ? a : b;
    }
}

面试题48：最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

class Solution {
    Set set = new HashSet<>();

    public int lengthOfLongestSubstring(String s) {
        if ("".equals(s)) {
            return 0;
        }
        char[] arr = s.toCharArray();
        int maxSize = 0;
        int begin = 0;
        int current = 0;
        while (current < arr.length) {
            if (!set.contains(arr[current])) {
                set.add(arr[current]);
                if (maxSize < current - begin + 1) {
                    maxSize = current - begin + 1;
                }
            } else {
                while (arr[begin] != arr[current]) {
                    set.remove(arr[begin]);
                    begin++;
                }
                begin++;
            }
            current++;
        }
        return maxSize;
    }
}

面试题50：第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

class Solution {
    public char firstUniqChar(String s) {
        if ("".equals(s)) {
            return ' ';
        }
        char[] cArray = s.toCharArray();
        Map map = new HashMap<>();
        int count;
        for (int i = 0; i < cArray.length; i++) {
            count = 1;
            if (map.containsKey(cArray[i])) {
                count = map.get(cArray[i]) + 1;
            }
            map.put(cArray[i], count);
        }
        for (int j = 0; j < cArray.length; j++) {
            if (map.get(cArray[j]) == 1) {
                return cArray[j];
            }
        }
        return ' ';
    }
}

面试题53-1：在排序数组中查找数字1

统计一个数字在排序数组中出现的次数。

class Solution {
    public static int search(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right - left) / 2;
        int key = binarySearch(nums, target, left, right, mid);
        if (key == -1) {
            return 0;
        } else {
            int count = 0;
            int cIndex = key;
            while (cIndex >= left) {
                if (nums[cIndex] == target) {
                    count++;
                    cIndex--;
                } else {
                    break;
                }
            }
            cIndex = key + 1;
            while (cIndex <= right) {
                if (nums[cIndex] == target) {
                    count++;
                    cIndex++;
                } else {
                    break;
                }
            }
            return count;
        }
    }

    public static int binarySearch(int[] nums, int target, int left, int right, int mid) {
        if (left > right) {
            return -1;
        }
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            right = mid - 1;
            mid = left + (right - left) / 2;
            return binarySearch(nums, target, left, right, mid);
        }
        if (nums[mid] < target) {
            left = mid + 1;
            mid = left + (right - left) / 2;
            return binarySearch(nums, target, left, right, mid);
        }
        return -1;
    }
}

面试题53-2：0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

class Solution {
    public int missingNumber(int[] nums) {
        if (nums[0] != 0) {
            return 0;
        }
        int sub;
        for (int i = 0; i < nums.length - 1; i++) {
            sub = nums[i + 1] - nums[i];
            if (sub == 2) {
                return nums[i] + 1;
            }
        }
        return nums.length;
    }
}

面试题58-2：左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {
    public String reverseLeftWords(String s, int n) {
        if (n >= s.length()) {
            return s;
        }
        String s1 = s.substring(0, n);
        String s2 = s.substring(n);
        return s2 + s1;
    }
}

面试题63：股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxProfit = Integer.MIN_VALUE;
        int sum = 0;
        int[] subPrices = new int[prices.length - 1];
        for (int i = 0; i < prices.length - 1; i++) {
            subPrices[i] = prices[i + 1] - prices[i];
        }
        for (int j = 0; j < subPrices.length; j++) {
            sum = sum + subPrices[j];
            if (sum < 0) {
                sum = 0;
            }
            if (sum > maxProfit) {
                maxProfit = sum;
            }
        }
        return maxProfit;
    }
}