leetcode刷题——剑指 Offer

第 1 天：栈与队列

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（Leetcode）

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

/**
 * 用两个栈实现队列
 * https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
 * @author : ctc
 * @createTime : 2023/2/18 19:34
 */
class CQueue {

    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public CQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

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

    public int deleteHead() {
        if (outStack.isEmpty()){
            if (inStack.isEmpty()){
                return -1;
            }
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
}

剑指 Offer 30. 包含min函数的栈

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

剑指 Offer 30. 包含min函数的栈 - 力扣（Leetcode）

/**
 * 30. 包含min函数的栈
 * https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
 * @author : ctc
 * @createTime : 2023/2/18 19:52
 */
class MinStack {

    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new ArrayDeque<Integer>();
        minStack = new ArrayDeque<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(),x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

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

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

第 2 天 链表

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表 - 力扣（Leetcode）

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

1、先反转链表，再求数组

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        int n = 0;
        ListNode prev = null;
        while (head != null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
            n++;
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = prev.val;
            prev = prev.next;
        }
        return res;
    }
}

2、采用递归。一步到位

剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表 - 力扣（Leetcode）

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head!=null){
            ListNode node = head.next;
            head.next = prev;
            prev = head;
            head = node;
        }
        return prev;
    }
}

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        while (head == null || head.next == null){
            return head;
        }
        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }
}

剑指 Offer 35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制 - 力扣（Leetcode）

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

1、哈希表

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        Node code = new Node(head.val);
        Map<Node, Node> map = new HashMap<>();
        while(head!=null){
            map.put(head.random, new Node(head.val));
            head = head.next;
        }

        Node node = code;
        while(head!=null){
            if(map.containsKey(head)){
                node.next = map.get(head.next);
            }else{
                node.next = new Node(head.val);
            }
            node.random = map.get(head.random);
        }

        return code;
    }
}

2、原地修改

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }

        for (Node cur = head; cur!=null; cur = cur.next.next) {
            Node node = new Node(cur.val);
            // 插入
            Node temp = cur.next;
            cur.next = node;
            node.next = temp;
        }

        for (Node cur = head; cur!=null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

      //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        Node newHead = head.next;
        for (Node cur = head, temp = null; cur!=null && cur.next!=null;) {
            temp = cur.next;
            cur.next = temp.next;
            cur = temp;
        }


        return newHead;
    }
}

第 3 天 字符串

剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格 - 力扣（Leetcode）

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

/**
 * @author : ctc
 * @createTime : 2023/2/20 9:06
 */
public class ReplaceSpace {
    /**
     * 使用String中的方法
     */
    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }

    /**
     * 使用StringBuilder
     */
    public String replaceSpace2(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch==' '){
                sb.append("%20");
            }else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }

    /**
     * 使用char[]
     */
    public String replaceSpace3(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (ch==' '){
                array[size++]='%';
                array[size++]='2';
                array[size++]='0';
            }else {
                array[size++]=ch;
            }
        }
        return new String(array,0,size);
    }
}

剑指 Offer 58 - II. 左旋转字符串

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

/**
 * @author : ctc
 * @createTime : 2023/2/20 9:26
 */
public class ReverseLeftWords {
    /**
     * 使用String方法切割
     */
    public String reverseLeftWords(String s, int n) {
        String s1 = s.substring(0,n);
        String s2 = s.substring(n);
        return s2+s1;
    }

    /**
     * 使用StringBuilder
     */
    public String reverseLeftWords2(String s, int n) {
        StringBuilder res = new StringBuilder();
        for (int i = n; i < s.length(); i++) {
            res.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            res.append(s.charAt(i));
        }
        return res.toString();
    }

    /**
     * 只使用String
     */
    public String reverseLeftWords3(String s, int n) {
        String res = "";
        for (int i = n; i < s.length(); i++) {
            res+=s.charAt(i);
        }
        for (int i = 0; i < n; i++) {
            res+=s.charAt(i);
        }
        return res;
    }

    /**
     * 使用求余方法，一次循环实现
     */
    public String reverseLeftWords4(String s, int n) {
        String res = "";
        for (int i = n; i < s.length()+n; i++) {
            res+=s.charAt(i % s.length());
        }
        return res;
    }
}

第 4 天 查找算法

剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字 - 力扣（Leetcode）

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

方法一：采用哈希表实现

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num: nums){
            if(!set.add(num)){
                return num;
            }
        }
        return 0;
    }
}

方法二：原地交换

• 遍历数组 numsnumsnums ，设索引初始值为 i=0 :
  • 若 nums[i]=i： 说明此数字已在对应索引位置，无需交换，因此跳过；
  • 若 nums[nums[i]]=nums[i] ： 代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i] ；
  • 否则： 交换索引为 iii 和 nums[i]nums[i]nums[i] 的元素值，将此数字交换至对应索引位置。
• 若遍历完毕尚未返回，则返回 −1 。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i<nums.length) {
            if (nums[i] == i){
                i++;
                continue;
            }
            if (nums[nums[i]] == nums[i]){
                return nums[i];
            }

            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return 0;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（Leetcode）

统计一个数字在排序数组(非递减)中出现的次数。

解法：二分法

可以直接遍历，但这个题就没意义了。

先在数组中找到其中一个相同元素的位置，在计算左右两边该元素的数量。

class Solution {
    public int search(int[] nums, int target) {
                if (nums.length==0){
            return 0;
        }
                int l = 0, r = nums.length-1;
        while (l<=r){
            int x = l+(r-l)/2;
            if (nums[x]==target){
                while (nums[x]==target){
                    if (x==0 || nums[x-1]!=target){
                        break;
                    }
                    x--;
                }
                int n = x;
                while (nums[x]==target){
                    if (x==nums.length-1 || nums[x+1]!=target){
                        break;
                    }
                    x++;
                }
                return x-n+1;
            }

            if (nums[x]>target){
                r = x - 1;
            }else {
                l = x + 1;
            }
        }
        return 0;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

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

解法

解法很多，遍历，二分，数学，直接上代码，一看就懂。也可以用位运算，这里没有给出，感兴趣可以自己查查。

/**
 * @author : ctc
 * @createTime : 2023/2/21 19:48
 */
public class MissingNumber {
    /**
     * 遍历
     */
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if(i != nums[i]){
                return i-1;
            }
        }
        return nums.length;
    }

    /**
     * 二分法
     */
    public int missingNumber2(int[] nums) {
        int l = 0, r = nums.length-1;
        while (l<=r){
            int a = (l+r)/2;
            if (nums[a]==a){
                l = a+1;
            }else {
                r = a-1;
            }
        }
        return l;
    }

    /**
     * 数学
     */
    public static int missingNumber3(int[] nums) {
        int n = nums.length + 1;
        int total = n * (n - 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n - 1; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }

}

第 5 天 查找算法

剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找 - 力扣（Leetcode）

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

题解

如下图所示，我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

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

剑指 Offer 11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字 - 力扣（Leetcode）

题解

使用二分法，在二分过程中总共有3种可能。

• numbers[mid]<numbers[high]，最小值在左半区。
• numbers[mid]>numbers[high]，最小值在右半区。
• numbers[mid]==numbers[high]，有重复元素，将右半区左移动一个单位。

class Solution {
    public int minArray(int[] numbers) {
                int l = 0, r = numbers.length-1;
        while (l<r){
            int mid = (l+r)/2;
            if (numbers[mid] < numbers[r]){
                r = mid;
            }else if (numbers[mid] > numbers[r]){
                l = mid+1;
            } else {
                r--;
            }
        }
        return numbers[l];
    }
}

剑指 Offer 50. 第一个只出现一次的字符

剑指 Offer 50. 第一个只出现一次的字符 - 力扣（Leetcode）

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

题解

使用哈希表。

class Solution {
    public char firstUniqChar(String s) {
        int[] nums = new int[26];
        for(int i = 0; i< s.length(); i++){
            nums[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (nums[s.charAt(i)-'a']==1){
                return s.charAt(i);
            }
        }
        return ' ';
    }
}

第 6 天 搜索与回溯算法

剑指 Offer 32 - I. 从上到下打印二叉树

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

题解

这里因为要返回数组类型，导致多了一个转化的步骤。

class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root!=null) {
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        
        return res;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

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

题解

因为这里需要每层一起输出，一开始采用了两个队列的方式，但存在多次入队，出队的过程，当然也可以让两个队列循环来当出队的一组，但这样代码结构就太复杂了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue1 = new ArrayDeque<>();
        Queue<TreeNode> queue2 = new ArrayDeque<>();
        if(root != null){
            queue1.offer(root);
        }
        while(!queue1.isEmpty()){
            while(!queue1.isEmpty()){
                queue2.offer(queue1.poll());
            }
            List<Integer> list = new ArrayList<>();
            while(!queue2.isEmpty()){
                TreeNode node = queue2.poll();
                list.add(node.val);
                if(node.left != null){
                    queue1.offer(node.left);
                }
                if(node.right != null){
                    queue1.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

最后注意到，每次遍历一开始时，队列内部的所有数据就是同一行的，这时记录一下，然后连续出队该次数就可以了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size-->0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

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

题目

采用了双向队列，奇数行从后面入队，偶数行从前面入队。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null){
            queue.offer(root);
        }
        boolean flag = true;
        while(!queue.isEmpty()){
            int size = queue.size();
            Deque<Integer> deque = new LinkedList<>();
            while(size-->0){
                TreeNode node = queue.poll();
                if (flag){
                    deque.offerLast(node.val);
                }else {
                    deque.offerFirst(node.val);
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }

            res.add(new LinkedList<Integer>(deque));
            flag = !flag;
        }
        return res;
    }
}

第 7 天 搜索与回溯算法

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

题解

层序遍历

/**
 * 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) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(A);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(equal(node, B)){
                return true;
            }
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return false;
    }

    public boolean equal(TreeNode A, TreeNode B){
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (A!=null && B!=null) {
            queue.offer(A);
            queue.offer(B);
        }else {
            return false;
        }
        while(!queue.isEmpty()){
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if(node1.val != node2.val){
                return false;
            }
            if(node1.left != null && node2.left != null){
                queue.offer(node1.left);
                queue.offer(node2.left);
            }else if(node1.left == null && node2.left != null){
                return false;
            }

            if(node1.right != null && node2.right != null){
                queue.offer(node1.right);
                queue.offer(node2.right);
            }else if(node1.right == null && node2.right != null){
                return false;
            }
        }

        return true;
    }
}

先序遍历

• recur(A, B) 函数：
  • 终止条件：
    • 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
    • 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
    • 当节点 A 和 B 的值不同：说明匹配失败，返回 false ；
  • 返回值：
    • 判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
    • 判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
• isSubStructure(A, B) 函数：
  • 特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ；
  • 返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
    • 以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
    • 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
    • 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B==null){
            return false;
        }
        return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    public boolean recur(TreeNode A, TreeNode B) {
        if (B==null){
            return true;
        }
        if (A == null || A.val != B.val){
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

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

题解

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

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

题解

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p==null && q==null){
            return true;
        }
        if (p==null || q==null){
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return check(p.left, q.right) && check(p.right, q.left);
    }

第 8 天 动态规划

剑指 Offer 10- I. 斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

题解

class Solution {
    public int fib(int n) {
        if(n<=1){
            return n;
        }
        int p = 0, q = 1;
        for(int i = 2; i<=n; i++){
           int r = (p+q)%1000000007;
           p = q;
           q = r;
        }
        
        return q;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

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

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

题解

class Solution {
    public int numWays(int n) {
        if(n==0){
            return 1;
        }
        int p = 1, q = 1;
        for(int i = 2; i <= n; i++){
            int r = (p + q)%1000000007;
            p = q;
            q = r;
        }

        return q;
    }
}

剑指 Offer 63. 股票的最大利润

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

题解

记录股票最小值，让其在最高的卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

第 9 天 动态规划

剑指 Offer 42. 连续子数组的最大和

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

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

题解

设dp为以i为最后一个元素时，子数组的最大值。这里直接打nums当作dp数组使用。

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            nums[i] += Math.max(nums[i-1], 0);
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}

剑指 Offer 47. 礼物的最大价值

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

题解

class Solution {
    public int maxValue(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n][m];
        // 数据初始化
        dp[0][0] = grid[0][0];
        for(int i = 1; i < n; i++){
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for(int i = 1; i < m; i++){
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }

        // 动态规划求解
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = Math.max(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
            }
        }
        return dp[n-1][m-1];
    }
}

第 10 天 动态规划

剑指 Offer 46. 把数字翻译成字符串

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

题解

经典问题爬楼梯的变种，给的num就是爬num.length级台阶，一次可以爬一级或者爬两级，只是这次爬两级需要做一个值小于26的判断。

class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int res = 1, p = 1, q = 1;
        for (int i = 1; i < str.length(); i++) {
            String substring = str.substring(i - 1, i + 1);
            if (substring.compareTo("25")<=0 && substring.compareTo("10")>=0){
                res+=p;
            }
            p = q;
            q = res;
        }

        return res;
    }
}

剑指 Offer 48. 最长不含重复字符的子字符

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

题解

双指针，l代表上次重复元素的位置，i代表当前所遍历元素的位置。用哈希表记录遍历过元素的位置，如果遇到相同元素则更新l。在遍历过程中时刻更新最大长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || "".equals(s)){
            return 0;
        }
        int res = 1, l = -1;
        Map<Character, Integer> map = new HashMap<>(26);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Integer integer = map.get(c);
            if (integer!=null){
                l = Math.max(l,integer);
            }
            res = Math.max(res, i-l);
            map.put(c,i);
        }

        return res;
    }
}

第 11 天 双指针

剑指 Offer 18. 删除链表的节点

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

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

题解

/**
 * 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.val == val){
            return head.next;
        }
        ListNode p = head, q = head.next;
        while(q!=null && q.val!=val){
            p = q;
            q = q.next;

        }
        if(p!=null){
            p.next = q.next;
        }
        return head;
    }
}

剑指 Offer 22. 链表中倒数第k个节点

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

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

题解

/**
 * 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) {
        ListNode p = head, q = head;
        for(int i = 0; i < k; i++){
            q = q.next;
        }
        while(q != null){
            p = p.next;
            q = q.next;
        }

        return p;
    }
}

第 12 天 双指针

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

题解

迭代(虚拟头节点)

/**
 * 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) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

递归方法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        Liif(l1==null){
            return l2;
        }else if(l2==null){
            return l1;
        }else if(l1.val < l2.val){
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }
}

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode a = headA, b = headB;
        while(a!=b){
            a = a==null ? headB:a.next;
            b = b==null ? headA:b.next;
        }

        return a;
    }
}

第 13 天 双指针

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

题解

class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length-1;
        while(l<=r){
            if(nums[l]%2==0 && nums[r]%2==1){
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
            if(nums[l]%2==1){
                l++;
            }
            if(nums[r]%2==0){
                r--;
            }
        }
        return nums;
    }
}

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

题解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while(l<r){
            int x = nums[l]+nums[r];
            if(x==target){
                return new int[]{nums[l], nums[r]};
            }
            if(x>target){
                r--;
            }
            if(x<target){
                l++;
            }
        }

        return new int[]{};
    }
}

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

题解

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int l = s.length()-1, r = s.length()-1;
        while (l>=0 && r>=0){
            while (r>=0 && s.charAt(r) == ' '){
                r--;
            }
            l=r-1;
            while (l>=0 && s.charAt(l) != ' '){
                l--;
            }
            if (l>=-1){
                sb.append(s, l+1, r+1).append(" ");
                r = l;
            }
        }
        return sb.toString().trim();
    }
}

第 14 天 搜索与回溯算法

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

题解

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] == word.charAt(0) && dfs(board, i, j, words, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int i, int j, char[] words, int n){
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || n>=words.length || board[i][j] != words[n]){
            return false;
        }
        if(n == words.length-1){
            return true;
        }
        board[i][j] = '0';
        boolean res = dfs(board, i+1, j, words, n+1) ||  dfs(board, i-1, j, words, n+1)
                ||  dfs(board, i, j+1, words, n+1) || dfs(board, i, j-1, words, n+1);

        board[i][j] = words[n];
        return res;
    }
}

面试题13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

题解

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue= new ArrayDeque<int[]>();
        queue.add(new int[] { 0, 0, 0, 0 });
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int i = poll[0], j = poll[1], sumi = poll[2], sumj = poll[3];
            if(i >= m || j >= n || k < sumi + sumj || visited[i][j]) {
                continue;
            }
            visited[i][j] = true;
            res++;
            queue.offer(new int[]{i+1, j, getSum(i+1), sumj});
            queue.offer(new int[]{i, j+1, sumi, getSum(j+1)});
        }

        return res;
    }

    public int getSum(int x) {
        int sum = 0;
        while (x != 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
}

第 15 天 搜索与回溯算法

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

题解

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) {
            return;
        }
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null){
            res.add(new LinkedList(path));
        }
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

题解

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) {
            return;
        }
        dfs(cur.left);
        if (pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

题解

遍历顺序: 右->中->后

class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.right);
        if(k == 0) {
            return;
        }
        if(--k == 0) {
            res = root.val;
        }
        dfs(root.left);
    }
}

第 16 天 排序

面试题45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

题解

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        quick(strs,0,strs.length-1);
        StringBuilder res = new StringBuilder();
        for(String s : strs) {
            res.append(s);
        }
        return res.toString();
    }

    private void quick(String[] strs, int l, int r) {
        if (l>=r){
            return;
        }
        String pv = strs[l];
        int i = l, j = r;
        while (i<j){
            while ((strs[j]+strs[l]).compareTo(strs[l]+strs[j])>=0 && i<j){
                j--;
            }
            while ((strs[i]+strs[l]).compareTo(strs[l]+strs[i])<=0 && i<j){
                i++;
            }
            pv = strs[i];
            strs[i] = strs[j];
            strs[j] = pv;
        }
        strs[i] = strs[l];
        strs[l] = pv;
        quick(strs, l, i-1);
        quick(strs, i+1, r);
    }
}

面试题61. 扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

题解

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for (int num : nums) {
            if (num == 0) {
                continue;
            }
            max = Math.max(max, num);
            min = Math.min(min, num);
            if (repeat.contains(num)) {
                return false;
            }
            repeat.add(num);
        }
        return max - min < 5;
    }
}

第 17 天 排序

剑指 Offer 40. 最小的k个数

题解

快速搜索

class Solution {
     public static int[] getLeastNumbers(int[] arr, int k) {
        quick(arr, 0, arr.length-1);

        int[] res = new int[k];
        for (int i = 0; i < res.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
    private static void quick(int[] arr, int l, int r) {
        if (l>=r){
            return;
        }
        int i = l, j = r;
        int pv = arr[l];
        while (i<j){
            while (pv<=arr[j] && i<j){
                j--;
            }
            while (pv>=arr[i] && i<j){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,l);

        quick(arr, l, i-1);
        quick(arr, i+1, r);
    }
}

根据题意改进改进

class Solution {
     public static int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.length - 1);
    }
    private static int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i<j){
            while (arr[l]<=arr[j] && i<j){
                j--;
            }
            while (arr[l]>=arr[i] && i<j){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,l);
        if (i>k) {
            quickSort(arr, k, l, i - 1);
        }
        if (i<k) {
            quickSort(arr, k, i + 1, r);
        }
        return Arrays.copyOf(arr, k);
    }
}

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

题解

用两个优先队列 queMax 和 queMin 分别记录大于中位数的数和小于等于中位数的数。

class MedianFinder {
    PriorityQueue<Integer> minQueue;
    PriorityQueue<Integer> maxQueue;

    public MedianFinder() {
        minQueue = new PriorityQueue<Integer>((a,b)->b-a);
        maxQueue = new PriorityQueue<Integer>((a,b)->a-b);
    }

    public void addNum(int num) {
        if (maxQueue.isEmpty() || maxQueue.peek()<num){
            maxQueue.offer(num);
            if (maxQueue.size()-1 > minQueue.size()) {
                minQueue.offer(maxQueue.poll());
            }
        }else {
            minQueue.offer(num);
            if (maxQueue.size() < minQueue.size()) {
                maxQueue.offer(minQueue.poll());
            }
        }
    }

    public double findMedian() {
        if ((minQueue.size()+maxQueue.size())%2==0){
            return (minQueue.peek() + maxQueue.peek())/2.0;
        }
        return maxQueue.peek();
    }
}

第 18 天 搜索与回溯算法

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

题解

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

}

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

题解

思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

class Solution {
    public boolean isBalanced(TreeNode root) {
          return recur(root) != -1;
    }

    public int recur(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = recur(root.left);
        if(left==-1){
            return -1;
        }
        int right = recur(root.right);
        if(right==-1){
            return -1;
        }
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

第 19 天 搜索与回溯算法

剑指 Offer 64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

题解

class Solution {
    public int sumNums(int n) {
        boolean flag = n>0 && (n+=sumNums(n-1))>0;
        return n;
    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

题解

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = null;
        while(root!=p || root!=q){
            res = root;
            if(root.val>p.val && root.val>q.val){
                root = root.left;
            }else if(root.val<p.val && root.val<q.val){
                root = root.right;
            }else{
                break;
            }
        }
        return res;
    }
}

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

题解

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root.val==p.val || root.val==q.val){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left==null && right==null){
            return null;
        }
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }
}

第 20 天 分治算法

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length-1);
    }

    TreeNode recur(int root, int left, int right) {
        if(left>right){
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int i = map.get(preorder[root]);

        node.left = recur(root+1, left, i-1);
        node.right = recur(i-left+root+1, i+1, right);

        return node;
    }
}

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

题解

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -n);
    }
    public double quickMul(double x, long N) {
        if(N==0){
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y*y : y*y*x;
    }

}

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

题解

• 遍历后序遍历的 [i,j] 区间元素，寻找 第一个大于根节点 的节点，索引记为 m 。此时，可划分出左子树区间 [i,m−1] 、右子树区间 [m,j−1] 、根节点索引 j 。
• 判断左区间节点是否都小于根节点，右区间节点都大于根节点。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i>=j){
            return true;
        }
        int p = i;
        while(postorder[p] < postorder[j]){
            p++;
        }
        int m = p;
        while(postorder[p] > postorder[j]){
            p++;
        }

        return p==j && recur(postorder, i, m-1) && recur(postorder, m, j-1);
    }
}

第 21 天 位运算

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。

题解

1. 循环检查二进制位
   • 循环检查给定整数 n 的二进制位的每一位是否为 1
2. 巧用 n&(n−1);
   • (n−1) ： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
   • n&(n−1) ： 二进制数字 n 最右边的 1 变成 0 ，其余不变。

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

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

题解

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。

class Solution {
    public int add(int a, int b) {
        while(b != 0){
            int c = (a&b)<<1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

第 22 天 位运算

剑指 Offer 56 - I. 数组中数字出现的次数进制中1的个数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

题解

异或运算有个重要的性质，两个相同数字异或为 0 ，即对于任意整数 a 有 a⊕a=0 。因此，若将 nums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 x.

1. 遍历 numsnumsnums 执行异或。得到x⊕y；
2. 循环左移计算 m。得到x和y数值不同的进制位，作为分组依据。
3. 运用m进行分组异或，分别得出x和y。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = 0;
        for(int num: nums){
            n ^= num;
        }
        int m = 1;
        while((n&m)==0){
            m<<=1;
        }
        int x = 0, y = 0;
        for(int num: nums){
            if((num & m)!=0){
                x^=num;
            }else{
                y^=num;
            }
        }

        return new int[]{x,y};
    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

题解

如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。 因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num: nums){
             for(int j = 0; j < 32; j++) {
                 counts[j] += num & 1;
                 num>>>=1;
             }
        }
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res<<=1;
            res |= counts[31-i]%3;
        }
        return res;
    }
}

第 23 天 数学

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

题解

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

题解

创建两个数组，分别记录该数字左边和右边的乘机。

class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        if(a==null || n==0){
            return new int[]{};
        }
        int[] l = new int[n];
        int[] r = new int[n];
        l[0] = 1;
        r[n-1] = 1;
        for(int i = 1; i<n; i++){
            l[i]=l[i-1]*a[i-1];
        }
        for(int i = n-1; i>0; i--){
            r[i-1]=r[i]*a[i];
        }
        int[] b = new int[n];
        for(int i = 0; i<n; i++){
            b[i]=l[i]*r[i];
        }

        return b;
    }
}

第 24 天 数学

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

题解

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        } else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

题解

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i<j){
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++){
                    ans[k - i] = k;
                }
                res.add(ans);
            }

            if(s>target){
                s -= i;
                i++;
            }else{
                j++;
                s += j;
            } 
        }
        return res.toArray(new int[0][]);
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

题解

class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}

第 25 天 模拟

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

题解

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

1. 从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。
2. 从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。
3. 如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[] order = new int[rows * columns];
        int index = 0;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while(left<=right && top<=bottom){
            for(int i = left; i <= right; i++){
                order[index++] = matrix[top][i];
            }
            for (int i = top + 1; i <= bottom; i++) {
                order[index++] = matrix[i][right];
            }
            if (left < right && top < bottom) {
                for (int i = right - 1; i > left; i--) {
                    order[index++] = matrix[bottom][i];
                }
                for (int i = bottom; i > top; i--) {
                    order[index++] = matrix[i][left];
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

题解

1. 遍历数组 pushed，将 pushed 的每个元素依次入栈；
2. 每次将 pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈，同时遍历数组 popped，直到栈为空或栈顶元素与 popped 的当前元素不同。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = pushed.length;
        for (int i = 0, j = 0; i < n; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

第 26 天 字符串

剑指 Offer 20. 表示数值的字符串

题解

class Solution {
    public boolean isNumber(String s) {
        if(s == null || s.length() == 0) return false; // s为空对象或 s长度为0(空字符串)时, 不能表示数值
        boolean isNum = false, isDot = false, ise_or_E = false; // 标记是否遇到数位、小数点、‘e’或'E'
        char[] str = s.trim().toCharArray();  // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符
        for(int i=0; i<str.length; i++) {
            if(str[i] >= '0' && str[i] <= '9') isNum = true; // 判断当前字符是否为 0~9 的数位
            else if(str[i] == '.') { // 遇到小数点
                if(isDot || ise_or_E) return false; // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
                isDot = true; // 标记已经遇到小数点
            }
            else if(str[i] == 'e' || str[i] == 'E') { // 遇到‘e’或'E'
                if(!isNum || ise_or_E) return false; // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
                ise_or_E = true; // 标记已经遇到‘e’或'E'
                isNum = false; // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
            }
            else if(str[i] == '-' ||str[i] == '+') { 
                if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E') return false; // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
            }
            else return false; // 其它情况均为不合法字符
        }
        return isNum;
    }
}

面试题67. 把字符串转换成整数

题解

class Solution {
    public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();
        if(length == 0) {
            return 0;
        }
        while(str.charAt(i) == ' '){
            if(++i == length) {
                return 0;
            }
        }
        if(str.charAt(i) == '-') {
            sign = -1;
        }
        if(str.charAt(i) == '-' || str.charAt(i) == '+') {
            i++;
        }
        for(int j = i; j < length; j++) {
            if(str.charAt(j) < '0' || str.charAt(j) > '9') {
                break;
            }
            if(res > bndry || res == bndry && str.charAt(j) > '7'){
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + (str.charAt(j) - '0');
        }
        
        return sign * res;
    }
}

第 27 天 栈与队列

剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

题解

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new ArrayDeque<Integer>();
        int len = nums.length;
        int[] res = new int[len-k+1];
        for(int i = 0; i < k; i++) {
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.pollLast();
            }
            deque.offer(nums[i]);
        }
        res[0] = deque.peekFirst();
        for(int i = k; i < len; i++) {
            if(deque.peekFirst() == nums[i-k]){
                deque.poll();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.pollLast();
            }
            deque.offer(nums[i]);
            res[i-k+1] = deque.peekFirst();
        }
        return res;
    }
}

面试题59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

题解

为了实现此递减列表，需要使用 双向队列 ，假设队列已经有若干元素：

• 当执行入队 push_back() 时： 若入队一个比队列某些元素更大的数字 x ，则为了保持此列表递减，需要将双向队列 尾部所有小于 x 的元素 弹出。
• 当执行出队 pop_front() 时： 若出队的元素是最大元素，则 双向队列 需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。

class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;
    public MaxQueue() {
        queue = new ArrayDeque<Integer>();
        deque = new ArrayDeque<Integer>();
    }
    
    public int max_value() {
        return deque.isEmpty() ? -1:deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.offer(value);
        while(!deque.isEmpty() && deque.peekLast() < value){
            deque.pollLast();
        }
        deque.offer(value);
    }
    
    public int pop_front() {
        if(queue.isEmpty()) {
            return -1;
        }
        if(queue.peek().equals(deque.peekFirst())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}

第 28 天 搜索与回溯算法

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

题解

为了保证可以反序列化，使用层序遍历，并记录null值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    StringBuilder sb = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "[]";
        }
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else {
                res.append("null,");
            }
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) {
            return null;
        }
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

题解

• 使用回溯法
• 进行排序，保证重复字符只会被填入一次。

class Solution {
    List<String> rec;
    boolean[] vis;
    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer perm = new StringBuffer();
        backtrack(arr, 0, n, perm);
        return rec.toArray(new String[0]);
    }

    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if(i==n){
            rec.add(perm.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }
}

第 29 天 动态规划

剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

题解

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                     if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                }else{
                    if(matches(s,p,i,j)){
                        f[i][j] = f[i-1][j-1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

题解

用2，3，5乘出来。

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}

剑指 Offer 60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

题解

class Solution {
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

第 30 天 分治算法

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

题解

class Solution {
    public int[] printNumbers(int n) {
        int end = (int)Math.pow(10, n);
        int[] res = new int[end-1];
        for(int i = 1; i < end; i++){
            res[i-1] = i;
        }
        return res;
    }
}

大数版

class Solution {
    // 存储最终结果集合
    private List<String> list = new ArrayList<>();
    // 回溯过程中使用
    private StringBuffer track = new StringBuffer();
    // 注意：这里改为返回 String[] 类型，配合大数的情况
    public String[] printNumbers(int n) {
        backtrack(n, 1);
        String[] ans = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    private void backtrack(int n, int cur) {
        // 说明得到了一个可行的字符串数字
        if (cur > n) {
            // 如果 track 长度为 0，则不加入
            // 为了避免全 0 的情况
            if (track.length() != 0) list.add(track.toString());
            return ;
        }
        for (int i = 0; i <= 9; i++) {
            // 如果 track 长度为 0 且 i = 0，则不加入
            // 以长度 3 为例，为了避免 000，001，010 等情况
            boolean isNotAdd = track.length() == 0 && i == 0;
            if (!isNotAdd) track.append(i);
            backtrack(n, cur + 1);
            // 回溯时，也需要判断前面是否加入
            if (!isNotAdd) track.deleteCharAt(track.length() - 1);
        }
    }
}

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

题解

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums,int left,int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        merge(nums,left,mid,right);
    }
    public void merge(int[] nums,int left,int mid,int right){
        int[] temp = new int[right-left+1];
        int i = left, j = mid+1, t = 0;
        while(i<=mid && j<=right){
            if(nums[i]<=nums[j]){
                temp[t++] = nums[i++];
            }else{
                temp[t++] = nums[j++];
                count += mid-i+1;
            }
        }
        while(i<=mid){
            temp[t++] = nums[i++];
        }
        while(j<=right){
            temp[t++] = nums[j++];
        }
        for(int k =0; k < temp.length; k++){
            nums[left+k] = temp[k];
        }
    }
}

第 31 天 数学

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

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

题解

class Solution {
    public int cuttingRope(int n) {
        if(n<=3){
            return n-1;
        }
        long res = 1, mod = 1000000007;
        for(int i = 0; i < n/3-1; i++){
            res = (res*3)%mod;
        }
        if(n%3==0){
            return (int)(res*3%mod);
        }else if (n%3==1){
            return (int)(res*4%mod); 
        }else{
            return (int)(res*6%mod); 
        }
    }
}

剑指 Offer 43. 1～n 整数中 1 出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

题解

class Solution {
    public int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;
        while(n>=mulk){
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}

剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

题解

class Solution {
    public int findNthDigit(int n) {
        int d = 1, count = 9;
        while (n > (long) d * count) {
            n -= d * count;
            d++;
            count *= 10;
        }
        int index = n - 1;
        int start = (int) Math.pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
}