剑指Offer | Yuuki的经验总结

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

找出数组中重复的数字。

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

示例 1：

1
2
3

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

1	2 <= n <= 100000

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

剑指 Offer 05. 替换空格

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

示例 1：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

限制：

0 <= s 的长度 <= 10000

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}

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

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

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

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

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

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        // 如果第二个栈为空
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        } 
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

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

难度简单75收藏分享切换为英文接收动态反馈

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

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

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

示例 1：

1 2	输入：n = 2 输出：1

示例 2：

1 2	输入：n = 5 输出：5

提示：

0 <= n <= 100

class Solution {
    public int fib(int n) {
        int f0 = 0, f1= 1;
        for(int i=0; i<n; i++) {
            int sum = (f0 + f1)%1000000007;
            f0 = f1;
            f1 = sum;
        }
        return f0;
    }
}

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

难度简单87收藏分享切换为英文接收动态反馈

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

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

示例 1：

1 2	输入：n = 2 输出：2

示例 2：

1 2	输入：n = 7 输出：21

示例 3：

1 2	输入：n = 0 输出：1

提示：

0 <= n <= 100

class Solution {
    public int numWays(int n) {
        int n0 = 1, n1 = 1;
        int sum;
        for(int i=0; i<n; i++) {
            sum = (n0 + n1)%1000000007;
            n0 = n1;
            n1 = sum;
        }
        return n0;
    }
}

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

难度简单175收藏分享切换为英文接收动态反馈

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1 2	输入：[3,4,5,1,2] 输出：1

示例 2：

1 2	输入：[2,2,2,0,1] 输出：0

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

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

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

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

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

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

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

用返回一个整数列表来代替打印
n 为正整数

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

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

难度简单43

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

示例：

1
2
3

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10000

class Solution {
    public int[] exchange(int[] nums) {
        int p=0,q=nums.length-1;
        for(int i=0; i<nums.length;) {
            if(i>=q) break;
            if(nums[i]%2==0) {
                int t = nums[q];
                nums[q--] = nums[i];
                nums[i] = t;
            } else {
                i++;
            }
        }
        return nums;
    }
}

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

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

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

剑指 Offer 24. 反转链表

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

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

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

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

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

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

/**
 * 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) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode ans= new ListNode();
        ListNode p1=l1, p2=l2,tail=ans;
        while(p1!=null&&p2!=null) {
            if(p1.val<p2.val) {
                tail.next=p1;
                p1=p1.next;
            } else {
                tail.next=p2;
                p2=p2.next;
            }
            tail=tail.next;
        }
        if(p1==null) {
            tail.next = p2;
        }
        if(p2==null) {
            tail.next = p1;
        }
        return ans.next;
    }
}

剑指 Offer 27. 二叉树的镜像

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

例如输入：

/
2 7
/ \ /
1 3 6 9
镜像输出：

/
7 2
/ \ /
9 6 3 1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return reverse(root);
    }
    private static TreeNode reverse(TreeNode node) {
        if(node==null)
            return null;
        TreeNode temp = node.right;
        node.right = node.left;
        node.left = temp;
        reverse(node.left);
        reverse(node.right);
        return node;
    }
}

剑指 Offer 28. 对称的二叉树

难度简单82收藏分享切换为英文关注反馈

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1 / \ 2 2 / \ / \3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1	1 / \ 2 2 \ \ 3 3

示例 1：

1 2	输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

1 2	输入：root = [1,2,2,null,3,null,3] 输出：false

限制：

1	0 <= 节点个数 <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

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

难度简单152收藏分享切换为英文接收动态反馈

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

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1 2	输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

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;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int[] order = new int[total];
        int row = 0, column = 0;
        int[][] directions = \{\{0, 1}, {1, 0}, {0, -1}, {-1, 0\}\};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

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

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

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

/**
 * 难点实现 min() 的时间复杂度为 O(1)，
 * 实现思路：维护两个栈，栈 A 存储数据，栈 B 用于存储最小值，
 * 当栈 A push(x), x 比目前最小值还要小的数据时，B push(x);
 * 例如
 * 如果 A [ 5 2 1 4 7 6 ]
 * 那么 B [ 5 2 1 ]
 */
class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}
/**
作者：jyd
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

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

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

/
9 20
/
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

提示：

节点总数 <= 1000

/**
 * 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) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

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

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

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

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

难度简单45收藏分享切换为英文关注反馈

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

1	0 <= s 的长度 <= 50000

class Solution {
    public char firstUniqChar(String s) {
        int[][] arr = new int[26][2];
        for(int i=0; i<s.length(); i++) {
            int index = s.charAt(i)- 97;
            arr[index][0]=i;
            arr[index][1]++;
        }
        char ans=' ';
        int min=100000;
        for(int i=0; i<arr.length; i++) {
            if(arr[i][1]==1 && arr[i][0]<min) {
                min = arr[i][0];
                ans =(char)(i+97);
            }
        }
        return ans;
    }
}

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.ArrayList;
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ArrayList<ListNode> listA = new ArrayList<>();
        ArrayList<ListNode> listB = new ArrayList<>();
        ListNode p = headA;
        while(p != null) {
            listA.add(p);
            p = p.next;
        }
        p = headB;
        while(p != null) {
            listB.add(p);
            p = p.next;
        }
        int i=listA.size()-1, j = listB.size()-1;
        if(i<0||j<0)
            return null;
        ListNode t=null;
        while(i>=0&&j>=0) {
            if(listA.get(i)!=listB.get(j))
                break;
            else {
                t=listA.get(i);
                i--;
                j--;
            }
        }
        return t;
    }
}

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

难度简单75

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

示例 1:

1 2	输入: nums = [5,7,7,8,8,10], target = 8 输出: 2

示例 2:

1 2	输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

限制：

1	0 <= 数组长度 <= 50000

class Solution {
    public int search(int[] nums, int target) {
        int ans=0;
        for(int i=0; i<nums.length; i++) {
            if(nums[i]==target)
                ans++;
        }
        return ans;
    }
}

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

难度简单76收藏分享切换为英文接收动态反馈

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

示例 1:

1 2	输入: [0,1,3] 输出: 2

示例 2:

1 2	输入: [0,1,2,3,4,5,6,7,9] 输出: 8

限制：

1	1 <= 数组长度 <= 10000

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

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

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

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/
1 4

2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        ArrayList<Integer> arr = new ArrayList<>();
        toArray(arr,root);
        return arr.get(arr.size()-k);
    }
    //中序遍历
    private static void toArray(ArrayList<Integer> arr, TreeNode node) {
        if(node==null)
            return;
        toArray(arr,node.left);
        arr.add(node.val);
        toArray(arr,node.right);
    }

}

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

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

例如：

给定二叉树 [3,9,20,null,null,15,7]，

/
9 20
/
15 7
返回它的最大深度 3 。

提示：

节点总数 <= 10000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
    }
}

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

难度简单65收藏分享切换为英文关注反馈

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 import java.lang.Math;
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        if(root.left==null && root.right==null)
            return true;
        boolean lr,rr;
        lr = isBalanced(root.left);
        rr = isBalanced(root.right);
        int l,r;
        l=depth(root.left);
        r=depth(root.right);
        return lr&&rr&&Math.abs(l-r)<=1?true:false;
    }
    public static int depth(TreeNode root) {
        if(root==null)
            return 0;
        if(root.left==null && root.right==null)
            return 1;
        int l,r;
        l = depth(root.left)+1;
        r = depth(root.right)+1;
        return Math.max(l,r);
    }
}

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

来源：力扣（LeetCode）

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

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

难度简单47收藏分享切换为英文接收动态反馈

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

示例 1：

1 2	输入: "the sky is blue" 输出: "blue is sky the"

示例 2：

1
2
3

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

1
2
3

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() <= 0 || s.trim().length() <= 0) {
            return "";
        }

        String[] strs = s.split(" ");
        int length = strs.length;
        for (int i = 0; i < length / 2; i++) {
            String tempStr = strs[i].trim();
            strs[i] = strs[length - 1 - i].trim();
            strs[length - 1 - i] = tempStr;
        }

        StringBuilder builder = new StringBuilder(strs[0]);
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() > 0) {
                builder.append(" ").append(strs[i]);
            }
        }
        return builder.toString();
    }
}

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

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

示例 1：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例 2：

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制：

1 <= k < s.length <= 10000

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n)+s.substring(0,n);
    }
}

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

难度简单145收藏分享切换为英文接收动态反馈

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

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。\

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null || nums.length == 0)
            return new int[0];
        int[] ans = new int[nums.length-k+1];
        int index = 0;
        for(int i=k-1; i<nums.length; i++) {
            for(int j=0; j<k; j++) {
                if(j==0)
                    ans[index] = nums[i-j];
                else if(ans[index] < nums[i-j])
                    ans[index] = nums[i-j];
            }
            index++;
        }
        return ans;
    }
}

剑指 Offer 61. 扑克牌中的顺子

难度简单78

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

示例 1:

1 2	输入: [1,2,3,4,5] 输出: True

示例 2:

1 2	输入: [0,0,1,2,5] 输出: True

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; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

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

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

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

示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

题解

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

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

难度中等227收藏分享切换为英文接收动态反馈

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

示例 1：

1 2	输入: n = 3 输出: 6

示例 2：

1 2	输入: n = 9 输出: 45

限制：

1 <= n <= 10000

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

作者：jyd
来源：力扣（LeetCode）

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

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

示例:

输入: a = 1, b = 1
输出: 2

提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

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

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

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

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