leetcode刷题集

数组

1. 两数之和

/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 * 你可以按任意顺序返回答案。
 * 示例 1：
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _1_两数之和 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            int val = target - nums[i];     //计算目标值和当前元素的差
            if(map.containsKey(val)){
                return new int[]{map.get(val),i};
            }else{
                map.put(nums[i],i);
            }
        }
        return new int[]{-1,-1};
    }
}

15. 三数之和

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
 * 请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 * 示例 2：
 * 输入：nums = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _15_三数之和 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null){
            return null;
        }
        if(nums.length < 3){
            return list;
        }
        //先对数组进行排序
        Arrays.sort(nums);
        int lastIndex = nums.length - 2;
        //i用来扫描三元组的第一个元素
        for(int i = 0;i < lastIndex;i++){
            if(i > 0 && nums[i] == nums[i - 1]){  //减少重复
                continue;
            }
            int l = i + 1;             //l用来扫描三元组的第二个元素
            int r = nums.length - 1;  //r用来扫描三元组的第三个元素
            int remain = -nums[i];  // 0 - nums[i]
            while(l < r){
                int sum = nums[l] + nums[r];
                if(sum == remain){  //找到了符合条件的三元组
                    list.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //去重,跳过相同的值，往中间逼近
                    while(l < r && nums[l] == nums[l + 1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r - 1]){
                        r--;
                    }
                    //此时已经跳过了相同的元素,再接着比较
                    l++;
                    r--;
                }else if(sum < remain){
                    l++;
                }else{
                    r--;
                }
            }
        }
        return list;
    }

}

27. 移除元素

/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 *
 * 示例 1:
 * 给定 nums = [3,2,2,3], val = 3,
 * 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
 * 你不需要考虑数组中超出新长度后面的元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _27_移除元素 {

    //双指针
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int l = 0;  //左指针
        int r = nums.length - 1;  //右指针
        int temp = 0;
        while(l < r){
            while(l < r && nums[l] != val){  //找到第一个等于val的元素下标
                l++;
            }
            while(l < r && nums[r] == val){  //找到第一个不等于val的元素下标
                r--;
            }
            //交换
            temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        if(nums[l] == val){
            return l;
        }else{
            return l + 1;
        }
    }

}

54. 螺旋矩阵

/**
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 * 示例 1：
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/spiral-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _54_螺旋矩阵 {

    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix == null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        if(matrix.length == 0){
            return list;
        }
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while(top <= bottom && left <= right){
            // left top -> right top
            for(int i = left;i <= right;i++){
                list.add(matrix[top][i]);
            }
            top++;
            // right top -> right bottom
            for(int i = top;i <= bottom;i++){
                list.add(matrix[i][right]);
            }
            right--;

            //奇数行、偶数列的时候有问题
            if(top > bottom || left > right){
                break;
            }

            //right bottom -> left bottom
            for(int i = right;i >= left;i--){
                list.add(matrix[bottom][i]);
            }
            bottom--;
            //left bottom -> left top
            for(int i = bottom;i >= top;i--){
                list.add(matrix[i][left]);
            }
            left++;
        }
        return list;
    }

}

485. 最大连续1的个数

/**
 * 给定一个二进制数组， 计算其中最大连续1的个数。
 *
 * 示例 1:
 * 输入: [1,1,0,1,1,1]
 * 输出: 3
 * 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-consecutive-ones
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _485_最大连续1的个数 {

    public int findMaxConsecutiveOnes(int[] nums) {
        int res = 0;    //记录最后的结果
        int count = 0;  //记录连续1的个数
        //遍历数组
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 1){
                count++;
            }else{
                res = Math.max(res,count);
                count = 0;
            }
        }
        return Math.max(res,count);
    }

}

283. 移动零

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 示例:
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/move-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _283_移动零 {

    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0){
            return;
        }
        int index = 0;
        for(int i = 0;i < nums.length;i++){
            //将所有不为0的元素全部移动到数组的最前面，再将后面所有的元素置为0
            if(nums[i] != 0){
                nums[index] = nums[i];
                index++;
            }
        }
        for(int i = index;i < nums.length;i++){
            nums[i] = 0;
        }
    }

}

88. 合并两个有序数组

/**
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，
 * 这样它就有足够的空间保存来自 nums2 的元素。
 *
 * 示例 1：
 * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
 * 输出：[1,2,2,3,5,6]
 *
 * 示例 2：
 * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
 * 输出：[1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _88_合并两个有序数组 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i1 = m - 1;
        int i2 = n - 1;
        int cur = nums1.length - 1;  //从后往前遍历
        while(i2 >= 0){  //只要i2 < 0 就表示结束
            if(i1 >= 0 && nums2[i2] < nums1[i1]){
                nums1[cur--] = nums1[i1--];
            }else{
                nums1[cur--] = nums2[i2--];
            }
        }
    }

}

75. 颜色分类

/**
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，
 * 并按照红色、白色、蓝色顺序排列。
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * 示例 1：
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 *
 * 示例 2：
 * 输入：nums = [2,0,1]
 * 输出：[0,1,2]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[0]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-colors
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _75_颜色分类 {

    public void sortColors(int[] nums) {
        //三指针
        int red = 0;   //扫描所有元素
        int white = 0; //指向0
        int blue = nums.length - 1;  //指向2
        while(red <= blue){
            if(nums[red] == 0){
                swap(nums,red++,white++);
            }else if(nums[red] == 1){
                red++;
            }else{
                swap(nums,red,blue--);
            }
        }
    }

    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

252. 会议室

/**
 * 给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，
 * 请你判断一个人是否能够参加这里面的全部会议。
 *
 * 示例 1:
 * 输入: [[0,30],[5,10],[15,20]]
 * 输出: false
 *
 * 示例 2:
 * 输入: [[7,10],[2,4]]
 * 输出: true
 */
public class _252_会议室 {

    public boolean canAttendMeetings(int[][] intervals){
        if(intervals == null || intervals.length == 0){
            return true;
        }
        //按照会议的开始时间，从小到大进行排序
        Arrays.sort(intervals,(m1,m2) -> {
            return m1[0] - m2[0];
        });
//        Arrays.sort(intervals, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[0] - o2[0];
//            }
//        });
        //遍历每一个会议
        for(int i = 1;i < intervals.length;i++){
            //如果当前会议的开始时间小于前一个会议的结束时间，说明无法参加
            if(intervals[i][0] < intervals[i - 1][1]){
                return false;
            }
        }
        return true;
    }

}

253. 会议室Ⅱ

/**
 * 给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，
 * 为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
 *
 * 示例 1:
 * 输入: [[0, 30],[5, 10],[15, 20]]
 * 输出: 2
 *
 * 示例 2:
 * 输入: [[7,10],[2,4]]
 * 输出: 1
 */
public class _253_会议室Ⅱ {

    //小顶堆
    public int minMeetingRooms(int[][] intervals){
        if(intervals == null || intervals.length == 0){
            return 0;
        }
        //按照会议的开始时间，从小到大进行排序
        Arrays.sort(intervals,(m1,m2) -> {
            return m1[0] - m2[0];
        });
        //创建一个最小堆，存放每一个会议结束的时间
        PriorityQueue<Integer> heap = new PriorityQueue<>();  //默认创建最小堆
        heap.add(intervals[0][1]);  //添加0号会议的结束时间
        for(int i = 1;i < intervals.length;i++){
            //i号会议的开始时间大于堆顶 (堆顶: 目前占用的会议室中最早结束的会议时间)
            if(intervals[i][0] >= heap.peek()){
                heap.poll();
            }
            heap.add(intervals[i][1]);
        }
        return heap.size();  //最终堆里存放的元素个数就是需要的会议室数量
    }

    //分开排序
    public int minMeetingRooms2(int[][] intervals){
        if(intervals == null || intervals.length == 0){
            return 0;
        }
        //存放所有会议的开始时间
        int[] begins = new int[intervals.length];
        //存放所有会议的结束时间
        int[] ends = new int[intervals.length];
        for(int i = 0;i < intervals.length;i++){
            begins[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        //排序
        Arrays.sort(begins);
        Arrays.sort(ends);
        int room = 0;
        int endIndex = 0;
        for(int begin : begins){
            if(begin >= ends[endIndex]){  //能重复利用会议室
                endIndex++;
            }else{
                //需要新开一个会议室
                room++;
            }
        }
        return room;
    }

}

11. 盛最多水的容器

/**
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，
 * 垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，
 * 使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 说明：你不能倾斜容器。

 * 示例 1：
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 *
 * 示例 2：
 * 输入：height = [1,1]
 * 输出：1
 *
 * 示例 3：
 * 输入：height = [4,3,2,1,4]
 * 输出：16
 *
 * 示例 4：
 * 输入：height = [1,2,1]
 * 输出：2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _11_盛最多水的容器 {

    //双指针
    public int maxArea(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int l = 0;
        int r = height.length - 1;
        int water = 0;
        while(l < r){
            if(height[l] <= height[r]){
                int min = height[l];
                water = Math.max(water,(r - l) * min);
                while(l < r && height[l] <= min){
                    l++;  //去掉不必要的比较
                }
            }else{
                int min = height[r];
                water = Math.max(water,(r - l) * min);
                while(l < r && height[r] <= min){
                    r--;
                }
            }
        }
        return water;
    }

}

42. 接雨水

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
 * 在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _42_接雨水 {

    public int trap(int[] height) {
        if(height == null || height.length == 0) {
            return 0;
        }
        int water = 0;
        int lastIndex = height.length - 2;
        int[] leftMax = new int[height.length];  //存放左边比我大的最大的那根柱子
        //动态规划
        for(int i = 1;i <= lastIndex;i++){
            leftMax[i] = Math.max(leftMax[i - 1],height[i - 1]);
        }
        int[] rightMax = new int[height.length];  //存放右边比我大的最大的那根柱子
        for(int i = lastIndex;i >= 1;i--){
            rightMax[i] = Math.max(rightMax[i + 1],height[i + 1]);
        }
        //遍历每一根柱子，看看每一根柱子能放多少水
        for(int i = 1;i <= lastIndex;i++){
            //求出左边最大、右边最大的较小者
            int min = Math.min(leftMax[i],rightMax[i]);
            if(min <= height[i]){
                continue;
            }
            //说明这跟柱子能放水
            water += min - height[i];
        }
        return water;
    }

}

链表

2. 两数相加

/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 示例 1：
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _2_两数相加 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummyHead = new ListNode(0);  //虚拟头结点
        ListNode last = dummyHead;
        //进位值
        int carry = 0;
        while(l1 != null || l2 != null){
            int v1 = 0;
            int v2 = 0;
            if(l1 != null){
                v1 = l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                v2 = l2.val;
                l2 = l2.next;
            }
            int sum = v1 + v2 + carry;
            carry = sum / 10;  //设置进位值
            //将sum的个位数当作新结点的值
            last.next = new ListNode(sum % 10);
            last = last.next;
        }
        //最后还有检查最后一个数的进位
        if(carry > 0){
            last.next = new ListNode(1);
        }

        return dummyHead.next;
    }

}

203. 移除链表元素

/**
 * 删除链表中等于给定值 val 的所有节点。
 *
 * 示例:
 * 输入: 1->2->6->3->4->5->6, val = 6
 * 输出: 1->2->3->4->5
 *
 * https://leetcode-cn.com/problems/remove-linked-list-elements/
 */
public class _203_移除链表元素 {

    public ListNode removeElements(ListNode head, int val) {
        //如果只有一个元素
        if(head == null || (head.val == val && head.next == null)){
            head = null;
            return head;
        }
        ListNode pre = new ListNode(0);  //虚拟头结点
        pre.next = head;
        ListNode node = pre;
        //遍历
        while(head != null){
            if(head.val == val){
                node.next = head.next;
            }else{
                node = head;
            }
            head = head.next;
        }

        return pre.next;
    }

}

237. 删除链表中的节点

/**
 * 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点
 *
 * 输入：head = [4,5,1,9], node = 5
 * 输出：[4,1,9]
 * 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
 *
 * 链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list
 */
public class _237_删除链表中的节点 {

    public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) {
             val = x;
         }
     }

    public void deleteNode(ListNode node) {
        //让当前指针指向的节点的值重新赋值为下一个节点的值
        node.val = node.next.val;
        //让当前节点指向下一个节点的下一个节点
        node.next = node.next.next;
    }

}

206. 反转链表

/**
 * 反转一个单链表。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 * 你可以迭代或递归地反转链表
 *
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class _206_反转链表 {

    //递归
    public ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList1(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    //迭代
    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = null;
        ListNode temp = null;
        while(head != null){
            temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }

        return newHead;
    }

}

141. 环形链表

/**
 * 给定一个链表，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
 * 我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * 注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle
 */
public class _141_环形链表 {

    //快慢指针
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;  //定义慢指针
        ListNode fast = head.next;  //定义快指针
        //快指针走的快，所以结束条件就是快指针走完了
        while(fast != null && fast.next != null){
            if(slow == fast){
                return true;
            }
            slow = slow.next;  //慢指针移定一步
            fast = fast.next.next;  //快指针移动两步
        }

        return false;
    }

}

160. 相交链表

/**
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 * 示例 1：
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，
 * 链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；
 * 在 B 中，相交节点前有 3 个节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _160_相交链表 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA != curB){
            curA = (curA == null) ? headB : curA.next;
            curB = (curB == null) ? headA : curB.next;

            //这段代码在两个链表不相交的时候会死循环
            //curA = (curA.next == null) ? headB : curA.next;
            //curB = (curB.next == null) ? headA : curB.next;
        }
        return curA;
    }

}

86. 分隔链表

/**
 * 给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
 * 你应当保留两个分区中每个节点的初始相对位置。
 *
 * 示例：
 * 输入：head = 1->4->3->2->5->2, x = 3
 * 输出：1->2->2->4->3->5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _86_分隔链表 {

    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return head;
        }
        //创建两个虚拟头结点
        ListNode lHead = new ListNode(0);
        ListNode lTail = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rTail = rHead;
        while(head != null){
            if(head.val < x){
                //放在lTail后面
                lTail.next = head;
                lTail = head;
            }else{
                //放在rTail后面
                rTail.next = head;
                rTail = head;
            }
            head = head.next;
        }
        rTail.next = null;
        lTail.next = rHead.next;
        return lHead.next;
    }

}

234. 回文链表

/**
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 *
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
public class _234_回文链表 {

    public boolean isPalindrome(ListNode head) {
        //如果是空链表或者只有一个结点，都算回文链表
        if(head == null || head.next == null){
            return true;
        }
        //如果有两个结点
        if(head.next.next == null){
            return head.val == head.next.val;
        }
        //先找到中间结点
        ListNode mid = middleNode(head);
        //然后翻转链表的右半部分(也就是中间结点的右半部分)
        ListNode rHead = reverse(mid.next);
        ListNode lHead = head;
        //两边对着比较
        while(rHead != null){
            if(rHead.val != lHead.val){
                return false;
            }
            rHead = rHead.next;
            lHead = lHead.next;
        }
        return true;
    }

    //利用快慢指针找到中间结点(必须掌握)
    //例如: 1>2>2>3>2>2>1  3是中间结点
    //例如: 1>2>2>1  左边的2是中间结点
    public ListNode middleNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            //快指针走两步，慢指针走一步
            fast = fast.next.next;
            slow = slow.next;
        }
        //慢指针指向的就是中间结点,最后返回慢指针
        return slow;
    }

    //翻转链表,返回翻转之后链表的头结点(必须掌握)
    public ListNode reverse(ListNode head){
        ListNode newHead = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

}

21. 合并两个有序链表

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 *
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 *
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _21_合并两个有序链表 {

    //迭代
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode head = new ListNode(0);  //虚拟头结点
        ListNode dummy = head;  //辅助指针
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                dummy.next = l1;
                l1 = l1.next;
            }else{
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;
        }
        if(l1 == null){
            dummy.next = l2;
        }
        if(l2 == null){
            dummy.next = l1;
        }
        return head.next;
    }

    //递归
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        //结束条件
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists2(l1,l2.next);
            return l2;
        }
    }

}

23. 合并k个升序链表

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 示例 1：
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 * 示例 2：
 * 输入：lists = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：lists = [[]]
 * 输出：[]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _23_合并k个升序链表 {

    //思路一: 最笨的解法
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        //将链表的所有结点添加到数组中
        List<ListNode> nodes = new ArrayList<>();
        for(ListNode node : lists){
            while(node != null){
                nodes.add(node);
                node = node.next;
            }
        }
        //排序
        nodes.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        //将排好序的结点都串起来
        ListNode head = new ListNode(0);
        ListNode dummy = head;
        for(ListNode node : nodes){
            dummy.next = node;
            dummy = dummy.next;
        }
        return head.next;
    }

    //思路二: 逐一比较
    public ListNode mergeKLists2(ListNode[] lists){
        if(lists == null || lists.length == 0){
            return null;
        }
        ListNode head = new ListNode(0);
        ListNode dummy = head;
        while(true){
            //最小链表结点所在的索引
            int minIndex = -1;
            for(int i = 0;i < lists.length;i++){
                if(lists[i] == null){
                    continue;
                }
                if(minIndex == -1 || lists[i].val < lists[minIndex].val){
                    minIndex = i;
                }
            }
            //所有的结点都已经串起来了
            if(minIndex == -1){
                break;
            }
            dummy.next = lists[minIndex];
            dummy = dummy.next;
            lists[minIndex] = lists[minIndex].next;
        }
        return head.next;
    }

    //思路三: 逐一两两比较
    public ListNode mergeKLists3(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        for(int i = 1;i < lists.length;i++){
            lists[0] = mergeTwoLists(lists[0],lists[i]);
        }
        return lists[0];
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode head = new ListNode(0);  //虚拟头结点
        ListNode dummy = head;  //辅助指针
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                dummy.next = l1;
                l1 = l1.next;
            }else{
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;
        }
        if(l1 == null){
            dummy.next = l2;
        }
        if(l2 == null){
            dummy.next = l1;
        }
        return head.next;
    }

    //思路四: 优先级队列(小顶堆
    public ListNode mergeKLists4(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode head = new ListNode(0);
        ListNode dummy = head;
        //创建小顶堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        //将所有的链表的头结点添加到堆中
        for(ListNode node : lists){
            if(node == null){
                continue;
            }
            heap.add(node);
        }
        //不断删除堆顶元素，并把堆顶元素的next添加到堆中
        while(!heap.isEmpty()){
            ListNode node = heap.poll();
            dummy = dummy.next = node;
            if(node.next != null){
                heap.add(node.next);
            }
        }
        return head.next;
    }

    //思路五: 分治
    public ListNode mergeKLists5(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int step = 1;
        while(step < lists.length){
            int nextStep = step << 1;
            for(int i = 0;i + step < lists.length;i += nextStep){
                lists[i] = mergeTwoLists(lists[i],lists[i + step]);
            }
            step = nextStep;
        }
        return lists[0];
    }

}

栈

20. 有效的括号

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 示例 1:
 * 输入: "()"
 * 输出: true
 *
 * 示例 2:
 * 输入: "()[]{}"
 * 输出: true
 *
 * 示例 3:
 * 输入: "(]"
 * 输出: false
 *
 * 示例 4:
 * 输入: "([)]"
 * 输出: false
 *
 * 示例 5:
 * 输入: "{[]}"
 * 输出: true
 *
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 */
public class _20_有效的括号 {

    //方式一
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(c == '(' || c == '{' || c == '['){  //左括号
                stack.push(c);
            }else{   //右括号
                if(stack.isEmpty()){
                    return false;
                }
                Character left = stack.pop();
                if(left == '(' && c != ')'){
                    return false;
                }
                if(left == '[' && c != ']'){
                    return false;
                }
                if(left == '{' && c != '}'){
                    return false;
                }
            }
        }
        //匹配完之后，判断栈中是否还有元素
        return stack.isEmpty();
    }

    //方式二
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){  //左括号
                stack.push(c);
            }else{   //右括号
                if(stack.isEmpty()){
                    return false;
                }
                Character left = stack.pop();
                if(c != map.get(left)){
                    return false;
                }
            }
        }
        //匹配完之后，判断栈中是否还有元素
        return stack.isEmpty();
    }
}

232. 用栈实现队列

/**
 * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
 *
 * 实现 MyQueue 类：
 * void push(int x) 将元素 x 推到队列的末尾
 * int pop() 从队列的开头移除并返回元素
 * int peek() 返回队列开头的元素
 * boolean empty() 如果队列为空，返回 true ；否则，返回 false

 * 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
 */
public class _232_用栈实现队列 {

    private Stack<Integer> inStack;

    private Stack<Integer> outStack;

    public _232_用栈实现队列() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public void checkOutStack(){
        //将instack栈中的所有元素都压入到outStack中，进行出队
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
    }

    public int pop() {
        checkOutStack();
        return outStack.pop();
    }

    public int peek() {
        checkOutStack();
        return outStack.peek();
    }

    public boolean empty() {
        if(inStack.isEmpty() && outStack.isEmpty()){
            return false;
        }
        return true;
    }

}

155. 最小栈

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _155_最小栈 {

    private Stack<Integer> stack;  //存放正常数据

    private Stack<Integer> minStack;  //存放最小数据

    public _155_最小栈() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty()){
            minStack.push(x);
        }else{
            minStack.push(Math.min(x,minStack.peek()));
        }
    }

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

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

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

}

739. 每日温度

/**
 * 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
 * 你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/daily-temperatures
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _739_每日温度 {

    //栈
    public int[] dailyTemperatures1(int[] T) {
        if(T == null || T.length == 0){
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        int[] ris = new int[T.length];  //存放右边比它大的数
        int[] res = new int[T.length];
        for(int i = 0;i < T.length;i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int topIndex = stack.peek();
                res[topIndex] = i - topIndex;
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }

    //倒推法
    public int[] dailyTemperatures2(int[] T) {
        if(T == null || T.length == 0){
            return null;
        }
        int[] res = new int[T.length];
        for(int i = T.length - 2;i >= 0;i--){
            int j = i + 1;
            while(true){
                if(T[i] < T[j]){
                    res[i] = j - i;
                    break;
                }else if(res[j] == 0){
                    res[i] = 0;
                    break;
                }
                j = j + res[j];
            }
        }
        return res;
    }

}

150. 逆波兰表达式求值

/**
 * 根据 逆波兰表示法，求表达式的值。
 * 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式
 * 说明：
 * 整数除法只保留整数部分。
 * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 *  
 * 示例 1：
 * 输入: ["2", "1", "+", "3", "*"]
 * 输出: 9
 * 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
 *
 * 示例 2：
 * 输入: ["4", "13", "5", "/", "+"]
 * 输出: 6
 * 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
 *
 * 示例 3：
 * 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
 * 输出: 22
 * 解释:
 * 该算式转化为常见的中缀算术表达式为：
 *   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
 * = ((10 * (6 / (12 * -11))) + 17) + 5
 * = ((10 * (6 / -132)) + 17) + 5
 * = ((10 * 0) + 17) + 5
 * = (0 + 17) + 5
 * = 17 + 5
 * = 22
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _150_逆波兰表达式求值 {

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

    public int evalRPN(String[] tokens) {
        for(String token : tokens){
            if(isOperator(token)){  //运算符
                Integer right = stack.pop();
                Integer left = stack.pop();
                stack.push(calculate(left,right,token));
            }else{  //数字
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    //判断是否是符号
    private boolean isOperator(String token){
        return "+-*/".contains(token);
    }

    //计算
    private int calculate(Integer left,Integer right,String token){
        switch (token){
            case "+": return left + right;
            case "-": return left - right;
            case "*": return left * right;
            default: return left / right;
        }
    }

}

队列

239. 滑动窗口最大值

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回滑动窗口中的最大值。
 *
 * 示例 1：
 * 输入：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
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _239_滑动窗口最大值 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1){
            return new int[0];
        }
        if(k == 1){
            return nums;
        }
        int[] result = new int[nums.length - (k - 1)];
        //创建双端队列，里面存放索引
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0;i < nums.length;i++){
            //只要nums[队尾] <= nums[i]，就将队尾去掉,直到nums[队尾] > nums[i]
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);  //将i加入队尾
            //检查窗口的索引是否正常
            int w = i - k + 1;
            if(w < 0){
                continue;
            }
            //检查对头的合法性
            if(deque.peekFirst() < w){
                //说明对头不合法，不在滑动窗口范围内
                deque.pollFirst();
            }
            //说明此时的对头就是滑动窗口最大值，可以加入数组
            result[w] = nums[deque.peekFirst()];
        }

        return result;
    }

    //暴力法
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        if (k == 1) {
            return nums;
        }
        int[] result = new int[nums.length - (k - 1)];
        int maxIdx = 0;
        //求出前k个元素的最大值的索引
        for(int i = 1;i < k;i++){
            if(nums[i] > nums[maxIdx]){
                maxIdx = i;
            }
        }
        //li是滑动窗口的最左边，ri是滑动窗口的最右边
        for(int li = 0;li < result.length;li++){
            int ri = li + k - 1;
            if(maxIdx < li){   //表示最大值的索引不在滑动窗口的合理范围内
                //这个时候就需要求出[li,ri]范围内的最大值的索引
                maxIdx = li;
                for(int i = li + 1;i <= ri;i++){
                    if(nums[i] > nums[maxIdx]){
                        maxIdx = i;
                    }
                }
            }else if(nums[ri] >= nums[maxIdx]){  //在合理范围内
                maxIdx = ri;
            }
            //此时的nums[maxIdx]就是滑动窗口的最大值
            result[li] = nums[maxIdx];
        }

        return result;
    }

}

字符串

151. 翻转字符串里的单词

/**
 * 给定一个字符串，逐个翻转字符串中的每个单词。
 *
 * 无空格字符构成一个 单词 。
 * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * 示例 1：
 * 输入："the sky is blue"
 * 输出："blue is sky the"
 *
 * 示例 2：
 * 输入："  hello world!  "
 * 输出："world! hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *
 * 示例 3：
 * 输入："a good   example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * 示例 4：
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 *
 * 示例 5：
 * 输入：s = "Alice does not even like bob"
 * 输出："bob like even not does Alice"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _151_翻转字符串里的单词 {

    public String reverseWords(String s) {
        if(s == null){
            return s;
        }
        char[] chars = s.toCharArray();
        //先消出多余的空格
        int len = 0;  //字符串最终的长度
        int cur = 0;  //当前字符存放的位置
        boolean space = true;  //判断前一个字符是否为空格字符
        for(int i = 0;i < chars.length;i++){
            if(chars[i] != ' '){  //chars[i]是非空格字符
                chars[cur++] = chars[i];
                space = false;
            }else if(space == false){  //chars[i]是空格字符，chars[i-1]是非空格字符
                chars[cur++] = ' ';
                space = true;
            }
        }
        len = space ? (cur - 1) : cur;
        //这里需要判断一下字符串是否全是空格字符
        if(len <= 0){
            return "";
        }
        reverse(chars,0,len - 1);  //先对整体进行逆序
        //再对每个单词进行逆序
        int preIndex = -1;
        for(int i = 0;i < len;i++){
            if(chars[i] != ' '){
                continue;
            }
            //来到这里表示遇到了空格
            reverse(chars,preIndex + 1,i - 1);
            preIndex = i;
        }
        //再对最后一个单词进行翻转
        reverse(chars,preIndex + 1,len - 1);
        return new String(chars,0,len);
    }

    //将l-r范围内的字符串进行逆序
    private void reverse(char[] chars,int l,int r){
        while(l < r){
            swap(chars,l,r);
            l++;
            r--;
        }
    }

    private void swap(char[] chars,int l,int r){
        char temp = chars[l];
        chars[l] = chars[r];
        chars[r] = temp;
    }

}

3. 无重复字符的最长字串

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _3_无重复字符的最长字串 {

    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        //用来保存每一个字符上一次出现的位置
        int[] arr = new int[128];
        for(int i = 0;i < arr.length;i++){
            arr[i] = -1;
        }
        char[] chars = s.toCharArray();
        arr[chars[0]] = 0;
        int li = 0;  //保存以i-1位置的字符结尾的最长不重复子串的开始索引
        int max = 1;
        for(int i = 1;i < chars.length;i++){
            //pi是i字符上一次出现的位置
            Integer pi = arr[chars[i]];
            if(li <= pi){
                li = pi + 1;
            }
            //存储这个字符出现的位置
            arr[chars[i]] = i;
            //最长字串的长度
            max = Math.max(max,i - li + 1);
        }
        return max;
    }

}

242. 有效的字母异位词

/**
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 *
 * 示例 1:
 *
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * 示例 2:
 *
 * 输入: s = "rat", t = "car"
 * 输出: false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-anagram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _242_有效的字母异位词 {

    public boolean isAnagram(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        if(s.length() != t.length()){
            return false;
        }
        char[] schars = s.toCharArray();
        char[] tchars = t.toCharArray();
        int[] res = new int[26];
        for(int i = 0;i < schars.length;i++){
            res[schars[i] - 'a']++;
        }
        for(int i = 0;i < tchars.length;i++){
            if(--res[tchars[i] - 'a'] < 0){
                return false;
            }
        }
        return true;
    }

}

排序

二叉树

144. 二叉树的前序遍历

/**
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历
 *
 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 */
public class _144_二叉树的前序遍历 {

    private List<Integer> list = new ArrayList<>();

    //递归
    public List<Integer> preorderTraversal1(TreeNode root) {
        if(root == null){
            return list;
        }
        list.add(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);

        return list;
    }

    //非递归
    public List<Integer> preorderTraversal2(TreeNode root) {
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            //因为栈是后进先出，所以先遍历右子树，再遍历左子树
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }

        return list;
    }

}

94. 二叉树的中序遍历

/**
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 *
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class _94_二叉树的中序遍历 {

    private List<Integer> list = new ArrayList<>();

    //递归
    public List<Integer> inorderTraversal1(TreeNode root) {
        if(root == null){
            return list;
        }
        inorderTraversal1(root.left);
        list.add(root.val);
        inorderTraversal1(root.right);

        return list;
    }

    //非递归
    public List<Integer> inorderTraversal2(TreeNode root) {
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){  //先将根节点和左边的结点压入栈中
                stack.push(root);
                root = root.left;
            }
            //依次取出
            root = stack.pop();
            list.add(root.val);
            root = root.right;  //再将右边的结点压入
        }

        return list;
    }

}

145. 二叉树的后序遍历

226. 翻转二叉树

/**
 * 将所有结点的子结点进行交换
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 *
 * 输出
 *
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 *
 * https://leetcode-cn.com/problems/invert-binary-tree/
 */
public class _226_翻转二叉树 {

    //前序遍历
    public TreeNode invertTree1(TreeNode root) {
        if(root == null){
            return root;
        }
        //交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree1(root.left);
        invertTree1(root.right);

        return root;
    }

    //中序遍历
    public TreeNode invertTree2(TreeNode root) {
        if(root == null){
            return root;
        }
        invertTree2(root.left);
        //交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //invertTree2(root.right);  //此时左右已经交换
        invertTree2(root.left);

        return root;
    }

    //后序遍历
    public TreeNode invertTree3(TreeNode root) {
        if(root == null){
            return root;
        }
        invertTree3(root.left);
        invertTree3(root.right);
        //交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        return root;
    }

    //层序遍历
    public TreeNode invertTree4(TreeNode root) {
        if(root == null){
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            //交换
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }

        return root;
    }

}

654. 最大二叉树

/**
 * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 * 二叉树的根是数组 nums 中的最大元素。
 * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 返回有给定数组 nums 构建的 最大二叉树 。 
 *
 * 示例 1：
 * 输入：nums = [3,2,1,6,0,5]
 * 输出：[6,3,5,null,2,0,null,null,1]
 * 解释：递归调用如下所示：
 * - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 *     - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 *         - 空数组，无子节点。
 *         - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 *             - 空数组，无子节点。
 *             - 只有一个元素，所以子节点是一个值为 1 的节点。
 *     - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 *         - 只有一个元素，所以子节点是一个值为 0 的节点。
 *         - 空数组，无子节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _654_最大二叉树 {

    public TreeNode constructMaximumBinaryTree1(int[] nums) {
        if(nums == null || nums.length == 0){
            return null;
        }
        return findRoot(nums,0,nums.length);
    }

    //找出[l,r)范围内的根结点
    private TreeNode findRoot(int[] nums,int l,int r){
        if(l == r){
            return null;
        }
        //找出[l,r)范围内的最大值的索引
        int maxIdx = l;
        for(int i = l;i < r;i++){
            if(nums[i] > nums[maxIdx]){
                maxIdx = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxIdx]);
        //递归
        root.left = findRoot(nums,l,maxIdx);
        root.right = findRoot(nums,maxIdx + 1,r);

        return root;
    }


    //题目变化:
    //由已知的数组创建一颗最大二叉树，然后返回一个数组，数组里面存放着每个结点的父结点的索引(如果没有父结点，就返回-1)
    public static int[] parentIndexs(int[] nums) {
        if(nums == null || nums.length == 0){
            return new int[0];
        }
        //利用栈获取到左边、右边第一个比它大的数，然后得到的两个数当中较小的那个数就是父结点的索引
        Stack<Integer> stack = new Stack<>();  //存放索引,按照单调递减的顺序存储
        int[] lis = new int[nums.length];   //存放左边比它大的数
        int[] ris = new int[nums.length];  //存放右边比它大的数
        int[] res = new int[nums.length];
        for(int i = 0;i < nums.length;i++){
            ris[i] = -1;    //先默认全部设置为-1
            lis[i] = -1;
            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                ris[stack.pop()] = i;
            }
            if(!stack.isEmpty()){
                lis[i] = stack.peek();
            }
            stack.push(i);
        }
        //比较
        for(int i = 0;i < nums.length;i++){
            if(lis[i] == -1 && ris[i] == -1){
                //说明是根结点
                res[i] = -1;
            }
            if(lis[i] == -1){
                res[i] = ris[i];
            }else if(ris[i] == -1){
                res[i] = lis[i];
            }else if(nums[lis[i]] < nums[ris[i]]){
                res[i] = lis[i];
            }else{
                res[i] = ris[i];
            }
        }
        System.out.println(Arrays.toString(lis));
        System.out.println(Arrays.toString(ris));

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,1,6,0,5};
        System.out.println(Arrays.toString(parentIndexs(arr)));
    }

}

572. 另一个树的子树

/**
 * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
 * s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
 *
 * 示例 1:
 * 给定的树 s:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 t：
 *
 *    4
 *   / \
 *  1   2
 * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subtree-of-another-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _572_另一个树的子树 {

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null || t == null){
            return false;
        }
        return postSerialize(s).contains(postSerialize(t));
    }

    //利用后序遍历的方式对二叉树进行序列化
    private String postSerialize(TreeNode root){
        StringBuilder s = new StringBuilder();
        postSerialize(root,s);
        return s.toString();
    }

    private void postSerialize(TreeNode node,StringBuilder s){
        if(node.left == null){
            s.append("#!");
        }else{
            postSerialize(node.left,s);
        }
        if(node.right == null){
            s.append("#!");
        }else{
            postSerialize(node.right,s);
        }
        s.append(node.val).append("!");
    }

}

236. 二叉树的最近公共祖先

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 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。
 *
 * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出: 5
 * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _236_二叉树的最近公共祖先 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }
        /*
            1. 如果p,q同时存在于这颗二叉树中，就能成功返回它们的最近公共祖先
            2. 如果p,q都不存在于这棵二叉树中，返回null
            3. 如果只有p存在于这颗二叉树中，返回p
            4. 如果只有q存在于这颗二叉树中，返回q
         */
        //在以root.left为根结点的二叉树中查找p,q的最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //在以root.right为根结点的二叉树中查找p,q的最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){  //说明p,q分别在root的左右两边
            return root;
        }
        return (left != null) ? left : right;
    }

}

98. 验证二叉搜索树

/**
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 假设一个二叉搜索树具有如下特征：
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 示例 1:
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 *
 * 示例 2:
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 * 根节点的值为 5 ，但是其右子节点值为 4 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _98_验证二叉搜索树 {

    private Integer last;   //上一个遍历的结点的最大值

    //思路一: 中序遍历递归
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false;
        }
        //是否是升序 last != null 是为了处理第一个元素
        if(last != null && root.val <= last){
            return false;
        }
        last = root.val;
        if(!isValidBST(root.right)){
            return false;
        }
        return true;
    }

    //思路二: 遍历的同时指定范围
    //在遍历每一个结点的时候，都指定它的上界和下界，节点的取值范围为(下界，上界)
    public boolean isValidBST2(TreeNode root) {
        return isValidBST2(root,null,null);
    }

    private boolean isValidBST2(TreeNode node,Integer min,Integer max){
        if (node == null) {
            return true;
        }
        if(min != null && node.val <= min){
            return false;
        }
        if(max != null && node.val >= max){
            return false;
        }
        //递归遍历左右子树
        if(!isValidBST2(node.left,min,node.val)){
            return false;
        }
        if(!isValidBST2(node.right,node.val,max)){
            return false;
        }
        return true;
    }

    //思路三: 层序遍历
    public boolean isValidBST3(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> nodes = new LinkedList<>();  //存放结点
        Queue<Integer> mins = new LinkedList<>();  //存放结点的下界
        Queue<Integer> maxes = new LinkedList<>(); //存放结点的上界
        nodes.offer(root);
        mins.offer(null);
        maxes.offer(null);
        while(!nodes.isEmpty()){
            Integer min = mins.poll();
            Integer max = maxes.poll();
            TreeNode node = nodes.poll();
            if(min != null && node.val <= min){
                return false;
            }
            if(max != null && node.val >= max){
                return false;
            }
            if(node.left != null){
                nodes.offer(node.left);
                mins.offer(min);
                maxes.offer(node.val);
            }
            if(node.right != null){
                nodes.offer(node.right);
                mins.offer(node.val);
                maxes.offer(max);
            }
        }
        return true;
    }

}

99. 恢复二叉搜索树

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
 *
 * 示例 1：
 * 输入：root = [1,3,null,null,2]
 * 输出：[3,1,null,null,2]
 * 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 *
 * 输入：root = [3,1,4,null,null,2]
 * 输出：[2,1,4,null,null,3]
 * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _99_恢复二叉搜索树 {

    private TreeNode prev;   //保留当前结点的前一个结点

    private TreeNode first;  //第一个错误结点

    private TreeNode second;  //第二个错误结点

    public void recoverTree(TreeNode root) {
        if(root == null){
            return;
        }
        //inOrder(root);
        morris(root);
        //交换
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        find(root);
        inOrder(root.right);
    }

    //Morris遍历二叉树
    public void morris(TreeNode root){
        TreeNode node = root;
        while(node != null){
            if(node.left != null){
                //找到前驱结点
                TreeNode pred = node.left;
                while(pred.right != null && pred.right != node){
                     pred = pred.right;
                }
                if(pred.right == null){
                    pred.right = node;
                    node = node.left;
                }else{
                    pred.right = null;
                    find(node);
                    node = node.right;
                }
            }else{
                find(node);
                node = node.right;
            }
        }
    }

    public void find(TreeNode root){
        //这里就出现了逆序对,最多出现两个逆序对
        if(prev != null && prev.val > root.val){
            second = root;  //最后一个逆序对中较小的那个结点
            if(first != null){  //first已经是最大的了,防止最后一个逆序对中较大的值覆盖掉当前的first
                return;
            }
            first = prev;  //第一个逆序对中较大的那个结点
        }
        prev = root;  //保留当前结点，进行下一次遍历
    }

}

124. 二叉树中的最大路径和

/**
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
 * 该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 * 示例 1：
 * 输入：root = [1,2,3]
 * 输出：6
 * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 *
 * 示例 2：
 * 输入：root = [-10,9,20,null,null,15,7]
 * 输出：42
 * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _124_二叉树中的最大路径和 {

    private int sum = Integer.MIN_VALUE;  //最大路径和，保证足够小

    //后序遍历
    public int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        maxValue(root);
        return sum;
    }

    //计算node提供给父结点的最大路径值
    private int maxValue(TreeNode node){
        if(node == null){
            return 0;
        }
        int leftValue = Math.max(maxValue(node.left),0);
        int rightValue = Math.max(maxValue(node.right),0);
        //这里比较了穿过每一个结点但是不穿过父结点的最大路径和
        sum = Math.max(sum,node.val + leftValue + rightValue);  
        return node.val + Math.max(leftValue,rightValue);
    }

}

114. 二叉树展开为链表

/**
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *  
 * 示例 1：
 * 输入：root = [1,2,5,3,4,null,6]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6]
 *
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：root = [0]
 * 输出：[0]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _114_二叉树展开为链表 {

    //思路一: 前序遍历
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        if(root.left != null){
            //保留之前的right
            TreeNode oldRight = root.right;
            //将left嫁接到right
            root.right = root.left;
            //清空left
            root.left = null;
            //将旧的right嫁接到root的最右下角
            TreeNode rightMost = root;
            while(rightMost.right != null){
                rightMost = rightMost.right;
            }
            rightMost.right = oldRight;
        }
        //这个时候root的左子树已经为null了，所以只需要遍历右子树即可
        flatten(root.right);
    }

    //非递归
    public void flatten2(TreeNode root) {
        if (root == null) {
            return;
        }
        while(root != null){
            if(root.left != null){
                TreeNode oldRight = root.right;
                //将left嫁接到right
                root.right = root.left;
                //清空left
                root.left = null;
                //将旧的right嫁接到root的最右下角
                TreeNode rightMost = root;
                while(rightMost.right != null){
                    rightMost = rightMost.right;
                }
                rightMost.right = oldRight;
            }
            root = root.right;
        }
    }

    //后序遍历,先右后左再根结点
    //每遍历到一个结点，就让它的right指向上一个遍历到的结点，并清空它的left
    private TreeNode prev;  //上一个遍历到的结点
    public void flatten3(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        if(prev != null){
            root.right = prev;
            root.left = null;
        }
        prev = root;
    }

}

图

递归

回溯

哈希表

36. 有效的数独

/**
 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 *
 * 示例 1:
 * 输入:
 * [
 *   ["5","3",".",".","7",".",".",".","."],
 *   ["6",".",".","1","9","5",".",".","."],
 *   [".","9","8",".",".",".",".","6","."],
 *   ["8",".",".",".","6",".",".",".","3"],
 *   ["4",".",".","8",".","3",".",".","1"],
 *   ["7",".",".",".","2",".",".",".","6"],
 *   [".","6",".",".",".",".","2","8","."],
 *   [".",".",".","4","1","9",".",".","5"],
 *   [".",".",".",".","8",".",".","7","9"]
 * ]
 * 输出: true
 *
 * 示例 2:
 * 输入:
 * [
 *   ["8","3",".",".","7",".",".",".","."],
 *   ["6",".",".","1","9","5",".",".","."],
 *   [".","9","8",".",".",".",".","6","."],
 *   ["8",".",".",".","6",".",".",".","3"],
 *   ["4",".",".","8",".","3",".",".","1"],
 *   ["7",".",".",".","2",".",".",".","6"],
 *   [".","6",".",".",".",".","2","8","."],
 *   [".",".",".","4","1","9",".",".","5"],
 *   [".",".",".",".","8",".",".","7","9"]
 * ]
 * 输出: false
 * 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
 * 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-sudoku
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _36_有效的数独 {

    //思路一: HashSet
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new Set[9];
        Set<Character>[] cols = new Set[9];
        Set<Character>[] boxes = new Set[9];
        for(int i = 0;i < 9;i++){
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for(int row = 0;row < 9;row++){
            for(int col = 0;col < 9;col++){
                char num = board[row][col];
                if(num == '.'){
                    continue;
                }
                if(rows[row].contains(num)){
                    return false;
                }
                if(cols[col].contains(num)){
                    return false;
                }
                //位于哪一个小九宫格的计算公式
                int boxIndex = (row / 3) * 3 + col / 3;
                if(boxes[boxIndex].contains(num)){
                    return false;
                }
                rows[row].add(num);
                cols[col].add(num);
                boxes[boxIndex].add(num);
            }
        }
        return true;
    }

    //思路二: boolean数组
    public boolean isValidSudoku2(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] boxes = new boolean[9][9];
        for(int row = 0;row < 9;row++){
            for(int col = 0;col < 9;col++){
                char num = board[row][col];
                if(num == '.'){
                    continue;
                }
                num -= '1';  //获取对应的下标
                if(rows[row][num]){
                    return false;
                }
                if(cols[col][num]){
                    return false;
                }
                //位于哪一个小九宫格的计算公式
                int boxIndex = (row / 3) * 3 + col / 3;
                if(boxes[boxIndex][num]){
                    return false;
                }
                rows[row][num] = true;
                cols[col][num] = true;
                boxes[boxIndex][num] = true;
            }
        }
        return true;
    }

}

146. LRU缓存机制

/**
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，
 * 则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，
 * 从而为新的数据值留出空间。
 * 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
 *
 * 示例：
 * 输入
 * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * 输出
 * [null, null, null, 1, null, -1, null, -1, 3, 4]
 * 解释
 * LRUCache lRUCache = new LRUCache(2);
 * lRUCache.put(1, 1); // 缓存是 {1=1}
 * lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
 * lRUCache.get(1);    // 返回 1
 * lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 * lRUCache.get(2);    // 返回 -1 (未找到)
 * lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 * lRUCache.get(1);    // 返回 -1 (未找到)
 * lRUCache.get(3);    // 返回 3
 * lRUCache.get(4);    // 返回 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lru-cache
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _146_LRU缓存机制 {

    private Map<Integer,Node> map;

    private int capacity;

    private Node first;  //虚拟头结点

    private Node last;   //虚拟尾结点

    //结点类
    private class Node{

        public int key;

        public int value;

        public Node prev;

        public Node next;

        public Node(){

        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //使用哈希表 + 双向链表
    public _146_LRU缓存机制(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
    }

    public int get(int key) {
        Node node = map.get(key);
        if(node == null){
            return -1;
        }
        //移除当前元素
        removeNode(node);
        //把当前元素添加到first后面
        addAfterFirst(node);
        return node.value;
    }

    //将node结点添加到first后面
    private void addAfterFirst(Node node) {
        node.next = first.next;
        first.next.prev = node;
        first.next = node;
        node.prev = first;
    }

    //从双向链表中删除node结点
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null){
            node.value = value;  //更新value
            removeNode(node);
            addAfterFirst(node);
        }else{
            if(map.size() == capacity){
                //淘汰最近最少使用的key-value
                removeNode(map.remove(last.prev.key));
            }
            Node newNode = new Node(key,value);
            map.put(key,newNode);
            addAfterFirst(newNode);
        }
    }

}

双指针

27. 移除元素

/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 *
 * 示例 1:
 * 给定 nums = [3,2,2,3], val = 3,
 * 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
 * 你不需要考虑数组中超出新长度后面的元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _27_移除元素 {

    //双指针
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int l = 0;  //左指针
        int r = nums.length - 1;  //右指针
        int temp = 0;
        while(l < r){
            while(l < r && nums[l] != val){  //找到第一个等于val的元素下标
                l++;
            }
            while(l < r && nums[r] == val){  //找到第一个不等于val的元素下标
                r--;
            }
            //交换
            temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        if(nums[l] == val){
            return l;
        }else{
            return l + 1;
        }
    }

}

二分查找

位运算

分治算法

50. Pow(x,n)

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
 *
 * 示例 1：
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 *
 * 示例 2：
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 *
 * 示例 3：
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/powx-n
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _50_Pow函数 {

    //分治思想: 快速幂递归
    public double myPow(double x, int n) {
        if(n == 0){
            return 1;
        }
        if(n == -1){     // -1 >> 1 == -1 如果是负数，最终还是会等于-1
            return 1 / x;
        }
        boolean odd = (n & 1) == 1;  //是否为奇数
        double half = myPow(x,n >> 1);       //注意: 如果是负奇数 -7 >> 1 == -4  也就是说会多一个-1
        half *= half;                        //那这里就相当于(-4 + -4) == -8
        return odd ? (half * x) : half;     //-8 + 1 == -7  巧妙的处理了负奇数的问题
    }

    //快速幂补充
    // 2 ^ 100 % 6 == (2 ^ 50 * 2 ^ 50) % 6 == ((2 ^ 50 % 6) * (2 ^ 50 % 6)) % 6
    // 2 ^ 101 % 6 == (2 ^ 50 * 2 ^ 50 * 2) % 6 == ((2 ^ 50 % 6) * (2 ^ 50 % 6) * (2 % 6)) % 6
    public static int powMod(int x,int y,int z){
        if(y < 0 || z == 0){
            return 0;
        }
        if(y == 0){
            return 1 % z;
        }
        int half = powMod(x,y >> 1,z);
        half *= half;
        if((y & 1) == 0){  //偶数
            return half % z;
        }
        //奇数
        return (half * (x % z)) % z;
    }

    public static void main(String[] args) {

        System.out.println(powMod(123,456,789));

        System.out.println(powMod(123,455,789));

        System.out.println(powMod(-123,456,789));

    }

}

贪心算法

动态规划

5. 最长回文子串

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _5_最长回文子串 {

    //动态规划
    public String longestPalindrome(String s) {
        if(s == null){
            return null;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        if(len == 0){
            return s;
        }
        boolean[][] dp = new boolean[len][len];   //判断所有的子串是否是回文串
        int maxLen = 1;   //最长回文子串的长度
        int begin = 0;   //最长回文子串的开始索引
        for(int i = len;i >= 0;i--){  //从下到上
            for(int j = i;j < len;j++){  //从左到右
                int length = j - i + 1;
                dp[i][j] = (chars[i] == chars[j] && (length <= 2 || dp[i + 1][j - 1]));
                if(dp[i][j] && length > maxLen){  //说明s[i,j]子串是回文子串
                    maxLen = length;
                    begin = i;
                }
            }
        }
        return new String(chars,begin,maxLen);  //从begin开始，长度为maxLen的子串
    }

    //扩展中心法
    public String longestPalindrome2(String s) {
        if (s == null) {
            return null;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (len <= 1) {
            return s;
        }
        int maxLen = 1;   //最长回文子串的长度
        int begin = 0;   //最长回文子串的开始索引
        for(int i = len - 2;i >= 1;i--){  //从倒数第二个元素开始遍历
            //以字符为中心向左右扩展
            int len1 = getMaxLength(chars,i - 1,i + 1);
            //以字符右边的间隙为中心向左右扩展
            int len2 = getMaxLength(chars,i,i + 1);
            len1 = Math.max(len1,len2);
            if(len1 > maxLen){
                maxLen = len1;
                begin = i - ((maxLen - 1) >> 1);   //这样既可以兼容子串最大长度是偶数的情况，也可以兼容奇数的情况
            }
        }
        //以下标为0的位置的字符的右边的间隙单独进行扩展(这个间隙比较特殊，最长回文子串的长度 <= 2)
        if(chars[0] == chars[1] && maxLen < 2){
            begin = 0;
            maxLen = 2;
        }
        return new String(chars,begin,maxLen);
    }

    //从l开始向左、从r开始向右扫描，获取的最长回文子串的长度
    private int getMaxLength(char[] chars,int l,int r){
        while(l >= 0 && r <= chars.length - 1 && chars[l] == chars[r]){
            l--;
            r++;
        }
        return r - l - 1;  //l和r中间的才是最终的长度
    }

    //扩展中心法优化
    public String longestPalindrome3(String s) {
        if (s == null) {
            return null;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (len <= 1) {
            return s;
        }
        int maxLen = 1;   //最长回文子串的长度
        int begin = 0;   //最长回文子串的开始索引
        int i = 0;
        while(i < len){
            int l = i - 1;
            //找到右边第一个不等于chars[i]的位置
            int r = i;
            while(++r < len && chars[i] == chars[r]);
            //让i成为新的r

            i = r;
            //l向左扩展，r向右扩展
            while(l >= 0 && r < len && chars[l] == chars[r]){
                l--;
                r++;
            }
            //扩展结束
            l++;  // l++后就是新的开始索引
            int length = r - l;  //l和r之间的距离就是最大回文子串的长度
            if(length > maxLen){
                maxLen = length;
                begin = l;
            }
        }
        return new String(chars,begin,maxLen);
    }

    //再次优化: 马拉车算法
    public String longestPalindrome4(String s) {
        if (s == null) {
            return null;
        }
        char[] oldChars = s.toCharArray();
        if (oldChars.length <= 1) {
            return s;
        }
        //预处理
        char[] newChars = preprocess(oldChars);
        int[] m = new int[newChars.length];
        int maxLen = 0;   //最长回文子串的长度
        int begin = 0;   //最长回文子串的开始索引
        //c、r一开始的赋值只要满足<2即可
        int c = 1;
        int r = 1;
        int lastIndex = m.length - 3;
        for(int i = 2;i <= lastIndex;i++){
            if(r > i){
                int li = (c << 1) - i;   //c == (li + i) / 2
                if(i + m[li] <= r){
                    m[i] = m[li];
                }else{
                    m[i] = r - i;  //至少是r-i
                }
            }
            //如果i >= r,就以i为中心，向左右扩展
            while(newChars[i + m[i] + 1] == newChars[i - m[i] - 1]){  //最左边和最右边相等
                m[i]++;
            }
            //更新c,r
            if(i + m[i] > r){
                c = i;
                r = i + m[i];
            }
            //找出最大回文子串
            if(m[i] > maxLen){
                maxLen = m[i];
                begin = i;   //先不计算最终的索引，先保留i
            }
        }
        begin = (begin - maxLen) >> 1;
        return new String(oldChars,begin,maxLen);
    }

    //预处理
    private char[] preprocess(char[] oldChars){
        char[] chars = new char[(oldChars.length << 1) + 3];
        chars[0] = '^';
        chars[1] = '#';
        chars[chars.length - 1] = '$';
        for(int i = 0;i < oldChars.length;i++){
            int index = (i + 1) << 1;
            chars[index] = oldChars[i];
            chars[index + 1] = '#';
        }
        return chars;
    }

}

121. 买卖股票的最佳时机

/*
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

public class _121_买卖股票的最佳时机 {

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        //前面扫描过的最小价格
        int minPrice = prices[0];
        //前面扫描过的最大利润
        int maxProfit = 0;
        for(int i = 1;i < prices.length;i++){
            if(prices[i] < minPrice){
                minPrice = prices[i];
            }else{
                //把第i天的股票卖出
                maxProfit = Math.max(prices[i] - minPrice,maxProfit);
            }
        }
        return maxProfit;
    }

}

72. 编辑距离

/**
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 * 示例 1：
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _72_编辑距离 {

    public int minDistance(String word1, String word2) {
        if(word1 == null || word2 == null){
            return 0;
        }
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int m = chars1.length;
        int n = chars2.length;
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        for(int i = 1;i <= m;i++){
            dp[i][0] = i;
        }
        for(int j = 1;j <= n;j++){
            dp[0][j] = j;
        }
        /*
            dp[i][j]是s1的[0,i)转换为s2的[0,j)的最少操作数
            从表格的上面、左面、斜对角线三个方向
            若 A 和 B 的最后一个字母相同：
                dp[i][j] = min(D[i][j−1],D[i−1][j],D[i−1][j−1]) + 1
            若 A 和 B 的最后一个字母不同：
                dp[i][j] = min(D[i][j−1],D[i−1][j],D[i−1][j−1]) + 2
        */
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                int top = dp[i - 1][j] + 1;
                int left = dp[i][j - 1] + 1;
                int leftTop = dp[i - 1][j - 1];
                //如果i和j位置对应的字符相同
                if(chars1[i - 1] != chars2[j - 1]){
                    leftTop++;
                }
                dp[i][j] = Math.min(Math.min(left,top),leftTop);
            }
        }

        return dp[m][n];
    }

}

198. 打家劫舍

/**
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，
 * 系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * 示例 1：
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4
 *
 * 示例 2：
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)
 * 偷窃到的最高金额 = 2 + 9 + 1 = 12
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _198_打家劫舍 {

    //思路一: 递归调用,会超时 时间复杂度类似与斐波那契数列 为T(2^n) 效率极低
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        /*
            针对每一个房屋，有2种选择，
                偷: sum1 = nums[0] + rob([2,3,4,5])
                不偷: sum2 = rob([1,2,3,4,5])|
            sum = max(sum1,sum2)
         */
        return rob(nums,0);
    }

    //从begin号房屋开始偷
    private int rob(int[] nums,int begin){
        if(begin == nums.length - 1){
            return nums[begin];
        }
        if(begin == nums.length - 2){
            return Math.max(nums[begin],nums[begin + 1]);
        }
        int robCur = nums[begin] + rob(nums,begin + 2);
        int robNext = rob(nums,begin + 1);
        return Math.max(robCur,robNext);
    }

    //思路二: 动态规划
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        //初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i < nums.length;i++){
            dp[i] = Math.max(nums[i] + dp[i - 2],dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    //优化
    public int rob3(int[] nums) {
//        if (nums == null || nums.length == 0) {
//            return 0;
//        }
//        if(nums.length == 1){
//            return nums[0];
//        }
//        //初始化
//        int first = nums[0];
//        int second = Math.max(nums[0],nums[1]);
//        for(int i = 2;i < nums.length;i++){
//            int temp = second;
//            second = Math.max(nums[i] + first,second);
//            first = temp;
//        }
//        return second;

        //继续优化
        if (nums == null) {
            return 0;
        }
        //初始化
        int first = 0;
        int second = 0;
        for(int i = 0;i < nums.length;i++){
            int temp = second;
            second = Math.max(nums[i] + first,second);
            first = temp;
        }
        return second;
    }

}

堆

347. 前K个高频元素

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 * 示例 1:
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 *
 * 示例 2:
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _347_前K个高频元素 {

    //思路一: Map + 排序
    public int[] topKFrequent(int[] nums, int k) {
        //利用Map存储每个整数出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            //Integer count = map.get(num);
            //count = count == null ? 0 : count;
            //Integer count = map.getOrDefault(num,0);
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        int[] res = new int[k];
        Map.Entry<Integer,Integer>[] entry = new Map.Entry[map.size()];
        //转化为entry数组
        map.entrySet().toArray(entry);
        //按照value从大到小进行排序
        Arrays.sort(entry, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        for(int i = 0;i < k;i++){
            res[i] = entry[i].getKey();
        }
        return res;
    }

    //思路二: Map + 小顶堆
    public int[] topKFrequent2(int[] nums, int k) {
        int[] res = new int[k];
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        //创建小顶堆
        PriorityQueue<Map.Entry<Integer,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
        });
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(heap.size() < k){
                heap.offer(entry);
            }else if(entry.getValue() > heap.peek().getValue()){
                heap.poll();
                heap.offer(entry);
            }
        }
        for(int i = k - 1;i >= 0;i--){
            if(!heap.isEmpty()){
                res[i] = heap.poll().getKey();
            }
        }
        return res;
    }

    //思路三: 桶排序
    public int[] topKFrequent3(int[] nums, int k) {
        List<Integer> res = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //创建桶
        List<Integer>[] buckets = new List[nums.length + 1];
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int no = entry.getValue();
            List<Integer> bucket = buckets[no];
            //刚开始，桶全部为null
            if(bucket == null){
                bucket = new LinkedList<>();
                buckets[no] = bucket;
            }
            bucket.add(entry.getKey());
        }
        for(int i = nums.length;i > 0 && res.size() < k;i--){
            if(buckets[i] == null){
                continue;
            }
            res.addAll(buckets[i]);
        }
        int[] val = new int[res.size()];
        for(int i = 0;i < val.length;i++){
            val[i] = res.get(i);
        }
        return val;
    }

}

数学

7. 整数反转

/**
 * 给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。
 * 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
 * 假设环境不允许存储 64 位整数（有符号或无符号）。
 *  
 * 示例 1：
 * 输入：x = 123
 * 输出：321
 *
 * 示例 2：
 * 输入：x = -123
 * 输出：-321
 *
 * 示例 3：
 * 输入：x = 120
 * 输出：21
 *
 * 示例 4：
 * 输入：x = 0
 * 输出：0
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-integer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _7_整数反转 {

    public int reverse(int x) {
        long res = 0;
        while(x != 0){
            res = res * 10 + x % 10;
            if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE){
                res = 0;
                return (int)res;
            }
            x /= 10;
        }
        return (int)res;
    }

    //优化
    public int reverse2(int x) {
        int res = 0;
        while(x != 0){
            int preRes = res;  //保留之前的res
            res = res * 10 + x % 10;
            if((res - (x % 10)) / 10 != preRes){   //如果不能还原回去，说明溢出了
                return 0;
            }
            x /= 10;
        }
        return res;
    }

}

并查集

广度优先搜索(BFS)

深度优先搜索(DFS)

17. 电话号码的字母组合

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 *
 * 示例 3：
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _17_电话号码的字母组合 {

    private char[] string;

    private char[][] letterArray = {
            {'a','b','c'},{'d','e','f'},{'g','h','i'},
            {'j','k','l'},{'m','n','o'},{'p','q','r','s'},
            {'t','u','v'},{'w','x','y','z'}
    };

    public List<String> letterCombinations(String digits) {
        if(digits == null){
            return null;
        }
        List<String> list = new ArrayList<>();
        char[] chars = digits.toCharArray();
        if(chars.length == 0){
            return list;
        }
        string = new char[chars.length];
        dfs(chars,0,list);  //搜索第0层

        return list;
    }

    //搜索第index层
    public void dfs(char[] chars,int index,List<String> list){
        if(index == chars.length){
            //已经进入最后一层了，不能再继续搜索了，即已经得到了一个正确的解
            list.add(new String(string));
            return;
        }
        //先枚举这一层可以做的所有选择
        char ch = chars[index];  //先获取数字,再获取对应的字母
        char[] letters = letterArray[ch - '2'];
        for(char c : letters){
            string[index] = c;
            dfs(chars,index + 1,list);  //进入下一层
        }
    }

}

46. 全排列

/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出:
 * [
 *   [1,2,3],
 *   [1,3,2],
 *   [2,1,3],
 *   [2,3,1],
 *   [3,1,2],
 *   [3,2,1]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

//第一种方式: 借助额外空间
public class _46_全排列 {

    private boolean[] used;  //用来标记nums数组中的每一个元素是否已经被使用过

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return list;
        }
        int[] arr = new int[nums.length];  //保留中间结果
        used = new boolean[nums.length];
        dfs(0,nums,arr,list);
        return list;
    }

    private void dfs(int index,int[] nums,int[] arr,List<List<Integer>> lists){
        if(index == nums.length){
            List<Integer> list = new ArrayList<>();
            for(int val : arr){
                list.add(val);
            }
            lists.add(list);
            return;
        }
        //处理当前层所有的选择
        for(int i = 0;i < nums.length;i++){
            if(used[i]){
                continue;
            }
            arr[index] = nums[i];
            used[i] = true;
            dfs(index + 1,nums,arr,lists);
            used[i] = false;  //还原
        }
    }

}


//第二种方式: 不需要借助额外空间
public class _46_全排列 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return list;
        }
        dfs(0,nums,list);
        return list;
    }

    private void dfs(int index,int[] nums,List<List<Integer>> lists){
        if(index == nums.length){
            List<Integer> res = new ArrayList<>();  //保存中间结果
            for(int num : nums){
                res.add(num);
            }
            lists.add(res);
            return;
        }
        //处理当前层所有的选择
        for(int i = index;i < nums.length;i++){
            swap(nums,index,i);
            dfs(index + 1,nums,lists);
            swap(nums,index,i);  //还原
        }
    }

    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

47. 全排列Ⅱ

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 *
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _47_全排列Ⅱ {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return list;
        }
        dfs(0,nums,list);
        return list;
    }

    private void dfs(int index,int[] nums,List<List<Integer>> lists){
        if(index == nums.length){
            List<Integer> res = new ArrayList<>();  //保存中间结果
            for(int num : nums){
                res.add(num);
            }
            lists.add(res);
            return;
        }
        //处理当前层所有的选择
        for(int i = index;i < nums.length;i++){
            if(isRept(nums,index,i)){  //如果出现了重复的，就不用记录,保证一个数字在index位置处只会出现一次
                continue;
            }
            swap(nums,index,i);
            dfs(index + 1,nums,lists);
            swap(nums,index,i);  //还原
        }
    }

    private boolean isRept(int[] nums, int index, int i) {
        for(int j = index;j < i;j++){
            if(nums[j] == nums[i]){
                return true;
            }
        }
        return false;
    }


    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

22. 括号生成

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _22_括号生成 {

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if(n < 0){
            return list;
        }
        /*
            什么时候可以选择左括号
                只要左括号的数量 > 0
            什么时候可以选择右括号
                右括号的数量 > 0 && 左括号的数量 != 右括号的数量
            当左括号、右括号的数量一样时，只能选择左括号
         */
        char[] chars = new char[n << 1];  //存放中间结果
        dfs(0,chars,n,n,list);

        return list;
    }

    //leftRemain: 左括号剩余的数量 rightRemain: 右括号剩余的数量
    private void dfs(int index,char[] chars,int leftRemain,int rightRemain,List<String> list){
        if(index == chars.length){
            list.add(new String(chars));
            return;
        }
        //枚举这一层所有可能的选择
        if(leftRemain > 0){  //选择左括号，进入下一层
            chars[index] = '(';
            dfs(index + 1,chars,leftRemain - 1,rightRemain,list);
        }
        if(rightRemain > 0 && (leftRemain != rightRemain)){
            chars[index] = ')';
            dfs(index + 1,chars,leftRemain,rightRemain - 1,list);
        }
    }

}

设计

剑指offer

3. 数组中重复的数字

public int findRepeatNumber1(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int res = -1;
    for(int num : nums){
        if(!set.add(num)){  //如果添加失败，返回false，则说明找到了重复的那个数字
            res = num;
            break;
        }
    }

    return res;
}

public int findRepeatNumber2(int[] nums) {
    int res = -1;
    int n = nums.length;
    if(nums == null || n <= 0){
        return res;
    }
    //判断元素是否在0~n-1之间
    for(int i = 0;i < n;i++){
        if(nums[i] < 0 || nums[i] > n - 1){
            return res;
        }
    }
    for(int i = 0;i < n;i++){
        while(nums[i] != i){
            if(nums[i] == nums[nums[i]]){
                //找到了
                return nums[i];
            }
            //交换
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
        }
    }
    return res;
}

4. 二维数组中的查找

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

 * 示例:
 *
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 *
 * 给定 target = 20，返回 false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _4_二维数组中的查找 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if((matrix == null || matrix.length == 0) || (matrix.length == 1 && matrix[0].length == 0)){
            return false;
        }
        int i = 0;
        int j = matrix[0].length - 1;  //i j对应右上角坐标
        while(i <= matrix.length - 1 && j >= 0){
            if(target == matrix[i][j]){
                return true;
            }
            if(target < matrix[i][j]){
                j--;
            }else{
                i++;
            }
        }

        return false;
    }

}

5.替换空格

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

 * 示例 1：
 *
 * 输入：s = "We are happy."
 * 输出："We%20are%20happy."
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _5_替换空格 {

    public String replaceSpace(String s) {
        int n = s.length();
        int size = 0;
        char[] chars = new char[n * 3];  //空格换成%20,增长了3倍
        for(int i = 0;i < n;i++){
            char c = s.charAt(i);
            if(c == ' '){
                chars[size++] = '%';
                chars[size++] = '2';
                chars[size++] = '0';
            }else{
                chars[size++] = c;
            }
        }
        s = new String(chars,0,size);
        return s;
    }

}

6. 从尾到头打印链表

//栈
public int[] reversePrint1(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    ListNode node = head;
    while(node != null){
        //压栈
        stack.push(node);
        node = node.next;
    }
    int[] arr = new int[stack.size()];
    //弹栈
    int n = stack.size();
    for(int i = 0;i < n;i++){
        arr[i] = stack.pop().val;
    }

    return arr;
}

public int[] reversePrint2(ListNode head){
    int size = 0;
    ListNode node = head;
    while(node != null){
        size++;
        node = node.next;
    }
    int[] arr = new int[size];
    node = head;
    for(int i = size - 1;i >= 0;i--){
        arr[i] = node.val;  //反向赋值
        node = node.next;
    }
    return arr;
}

7. 重建二叉树

8. 二叉树的下一个节点

9. 用两个栈实现队列

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

 * 示例 1：
 * 输入：
 * ["CQueue","appendTail","deleteHead","deleteHead"]
 * [[],[3],[],[]]
 * 输出：[null,null,3,-1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _9_用两个栈实现队列 {

    private Stack<Integer> stack1;

    private Stack<Integer> stack2;

    private int size;

    public _9_用两个栈实现队列() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    //添加元素
    public void appendTail(int value) {
        //只要stack1不为Null,就把stack1中的剩余元素全部放入stack2中
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        stack1.push(value);  //再把当前值压入stack1
        //然后再把stack2中的元素全部压入stack1中
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        size++;
    }

    //删除元素
    public int deleteHead() {
        if(size == 0){
            return -1;
        }
        int res = stack1.pop();
        size--;
        return res;
    }

}

10. 斐波那契数列 + 青蛙跳台阶

/**
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _10_斐波那契数列 {

    public int fib(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int first = 0;
        int second = 1;
        int res = 0;
        for(int i = 2;i <= n;i++){
            res = (first + second) % 1000000007;
            first = second % 1000000007;
            second = res % 1000000007;
        }
        return res % 1000000007;
    }

}



/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _10_青蛙跳台阶问题 {

    public int numWays(int n) {
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return 1;
        }
        int first = 1;
        int second = 1;
        int res = 0;
        for(int i = 2;i <= n;i++){
            res = (first + second) % 1000000007;
            first = second % 1000000007;
            second = res % 1000000007;
        }
        return res % 1000000007;
    }

}

11. 旋转数组中的最小数字

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，
 * 输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
 *
 * 示例 1：
 *
 * 输入：[3,4,5,1,2]
 * 输出：1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _11_旋转数组的最小数字 {

    public int minArray(int[] numbers) {
        int n = numbers.length;
        int res = -1;
        for(int i = 0;i < n;i++){
            //将数组中的所有元素依次和最后一个元素进行比较，如果比最后一个元素小，那就是最小元素
            //最坏的情况就是最后一个元素就是最小的
            if(numbers[n - 1] > numbers[i]){
                res = numbers[i];
                break;
            }
            res = numbers[n - 1];
        }
        return res;
    }

}

12. 矩阵中的路径

13. 机器人的运动范围

14. 剪绳子

15. 二进制中1的个数

16. 数值的整数次方

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

/**
 * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
 *
 * 示例 1:
 *
 * 输入: n = 1
 * 输出: [1,2,3,4,5,6,7,8,9]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _17_打印从1到最大的n位数 {

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

}

18. 删除链表的结点

/**
 * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
 * 返回删除后的链表的头节点。
 * 注意：此题对比原题有改动
 * 示例 1:
 *
 * 输入: head = [4,5,1,9], val = 5
 * 输出: [4,1,9]
 * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _18_删除链表的结点 {

    public ListNode deleteNode1(ListNode head, int val) {
        if(head == null){
            return head;
        }
        //删除第一个结点
        if(head.val == val){
            return head.next;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur.val != val && cur != null){
            //后移
            pre = cur;
            cur = cur.next;
        }
        //要么找到了，要么找到头了还没有找到
        if(cur != null){
            pre.next = cur.next;
        }
        return head;
    }

    public ListNode deleteNode2(ListNode head, int val) {
        if(head == null){
            return head;
        }
        ListNode virtualHead = new ListNode(-1);   //创建一个虚拟头结点
        virtualHead.next = head;  //虚拟头结点指向真正的第一个结点
        ListNode pre = virtualHead;
        ListNode cur = virtualHead.next;
        while(cur.val != val && cur != null){
            //后移
            pre = cur;
            cur = cur.next;
        }
        //要么找到了，要么找到头了还没有找到
        if(cur != null){
            pre.next = cur.next;
        }
        return virtualHead.next;
    }

}

19. 正则表达式匹配

20. 表示数值的字符串

21. 调整数组顺序，使奇数位于偶数前面

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

 * 示例：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：[1,3,2,4]
 * 注：[3,1,2,4] 也是正确的答案之一。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _21_调整数组位置奇数位于偶数前面 {

    public int[] exchange(int[] nums) {
        //类似快排
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left < right && nums[left] % 2 == 1){  //说明是奇数
                left++;
            }
            while(left < right && nums[right] % 2 == 0){  //说明是偶数
                right--;
            }
            //交换
            if(left < right){
                int tmep = nums[left];
                nums[left] = nums[right];
                nums[right] = tmep;
            }
        }
        return nums;
    }

}

22. 链表中倒数第k个结点

/**
 *输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，
 * 即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，
 * 它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
 *
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 *
 * 返回链表 4->5.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _22_链表中倒数第k个结点 {

    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode node = head;
        int size = 0;
        //先遍历一遍，得到链表的长度
        while(node != null){
            size++;
            node = node.next;
        }
        node = head;
        //从链表的第一个结点开始，遍历(size - k)个，就可以得到
        for(int i = 0;i < size - k;i++){
            node = node.next;
        }
        return node;
    }

}

23. 链表中环的入口结点

24. 反转链表

/**
 *定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _24_反转链表 {

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = null;
        ListNode temp = null;
        while(head != null){
            temp = head.next;   //先让teno指向head的下一个结点
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

}

25. 合并两个排序的链表

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 *
 * 示例1：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _25_合并两个排序的链表 {

    //归并排序思想
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode(-1);  //虚拟头结点
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        //此时l1 l2肯定有一个还没结束
        if(l1 != null){  //如果l1还有元素
            cur.next = l1;  //直接指向l1
        }
        if(l2 != null){
            cur.next = l2;
        }
        return dummy.next;
    }

}

26. 树的子结构

27. 二叉树的镜像

28. 对称的二叉树

29. 顺时针打印矩阵

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.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _30_包含min函数的栈 {

    /*
        数据栈 A ： 栈A用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
        辅助栈 B ： 栈B中存储栈A中所有 非严格降序 的元素，则栈A中的最小元素始终对应栈B的栈顶元素，即 min() 函数只需返回栈B的栈顶元素即可
*/

    private Stack<Integer> A;  //A是正常的栈

    private Stack<Integer> B; //B是用来记录最小元素的栈

    public _30_包含min函数的栈() {
        A = new Stack<>();
        B = new Stack<>();
    }

    //比对当前元素和栈内最小的元素
    public void push(int x) {
        A.add(x);
        if(B.isEmpty() || B.peek() >= x){  //如果此时B为空，或者B的栈顶元素比x大，那么此时x就是最小元素
            B.add(x);
        }
    }

    public void pop() {
        //如果A中pop()出的元素和B的栈顶元素相同，则B也要弹出栈顶元素,否则不弹出
        if(A.pop().equals(B.peek())){
            B.pop();
        }
    }

    //返回A的栈顶
    public int top() {
        return A.peek();
    }

    //直接返回B的栈顶
    public int min() {
        return B.peek();
    }

}

31.栈的压入、弹出队列

32. 从上到下打印二叉树Ⅰ

32. 从上到下打印二叉树Ⅱ

32. 从上到下打印二叉树Ⅲ

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

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

35. 复杂链表的复制

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

37. 序列化二叉树

38. 字符串的排列

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _38_字符串的排列 {

    private Set<String> set = new HashSet<>();  //用来保存结果

    public String[] permutation(String s) {
        if(s == null){
            return new String[]{};
        }
        //boolean[] visited = new boolean[s.length()];  //判断某个字符是否被访问过
        //dfs(s,"",visited);

        char[] arr = s.toCharArray();
        f(arr,0,set);

        return set.toArray(new String[set.size()]);  //转换为String数组
    }

    //递归 + 回溯
    private void dfs(String s1,String s2,boolean[] visited){
        if(s2.length() == s1.length()){
            //说明已经完成了一次排列
            set.add(s2);
            return;
        }
        //排列
        for(int i = 0;i < s1.length();i++){
            char temp = s1.charAt(i);
            if(visited[i]){  //如果被访问过，就不再访问
                continue;
            }
            visited[i] = true;
            //递归
            dfs(s1,s2 + String.valueOf(temp),visited);
            //回溯
            visited[i] = false;
        }
    }

    //全排列
    private void f(char[] array,int k,Set<String> res){
        //边界，说明已经完成了一次全排列
        if(k == array.length){
            res.add(String.valueOf(array));
            return;
        }

        for (int i = k; i < array.length; i++) {
            swap(array,k,i);

            f(array,k + 1,res); //递归后面的数进行全排列

            //每进行一次新的排列之前，要将之前的换回来
            swap(array,k,i);
        }
    }

    private void swap(char[] array,int k,int i){
        char t = array[k];
        array[k] = array[i];
        array[i] = t;
    }

}

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

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例 1:
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _39_数组中出现次数超过一半的数字 {

    //数组排序
    public int majorityElement1(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    //哈希表
    public int majorityElement2(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int half = nums.length >> 1;
        HashMap<Integer,Integer> map = new HashMap<>();
        int count = 0;
        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i]) + 1);
            }else{
                map.put(nums[i], 1);
            }
            if(i >= half && map.get(nums[i]) > half)
                return nums[i];
        }
        return -1;
    }

    //摩尔投票法: 一换一，不同的两者一旦遇见就同归于尽，最后活下来的值都是相同的
    public int majorityElement3(int[] nums) {
        int res = -1;
        if(nums == null || nums.length == 0){
            return res;
        }
        int vote = 0;  //票数
        for(int i = 0;i < nums.length;i++){
            if(vote == 0){
                res = nums[i];
                vote++;
            }else{
                vote += res == nums[i] ? 1 : -1;
            }
        }

        return res;
    }

}

40. 最小的k个数

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，
 * 则最小的4个数字是1、2、3、4。
 *
 * 示例 1：
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _40_最小的k个数 {

    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0){
            return new int[]{};
        }
        Arrays.sort(arr);
        int[] newArr = new int[k];
        for(int i = 0;i < k;i++){
            newArr[i] = arr[i];
        }
        return newArr;
    }

}

41. 数据流中的中位数

42. 连续子数组的最大和

43. 1~n个整数中1出现的次数

44. 数字序列中某一位的数字

45. 把数组排成最小的数

46. 把数字翻译成字符串

47. 礼物的最大价值

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

示例 1:
输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

public class _47_礼物的最大价值 {

    public int maxValue(int[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        //初始化第一行和第一列
        dp[0][0] = grid[0][0];
        for(int i = 1;i < m;i++){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int j = 1;j < n;j++){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    //优化
    public int maxValue2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                dp[j] = Math.max(dp[j],dp[j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[n];
    }

}

48. 最长不含重复字符的子字符串

49. 丑数

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

 * 示例:
 *
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/chou-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _49_丑数 {

    public int nthUglyNumber(int n) {
        if(n < 0){
            return 0;
        }
        int[] arr = new int[n];  //存放从1~n的所有丑数
        arr[0] = 1;   //第一个丑数是1
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for(int i = 1;i < n;i++){
            int maxVal = arr[i - 1];    //假设此时最大丑数是1
            //将此时的最大丑数乘以2 3 5之后，是否大于当前丑数
            while(maxVal >= arr[p2] * 2){
                p2++;
            }
            while(maxVal >= arr[p3] * 3){
                p3++;
            }
            while(maxVal >= arr[p5] * 5){
                p5++;
            }
            //最后找出三个中的最小值
            arr[i] = Math.min(Math.min(arr[p2] * 2,arr[p3] * 3),arr[p5] * 5);
        }
        return arr[n - 1];
    }

}

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

/**
 * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
 *
 * 示例:
 *
 * s = "abaccdeff"
 * 返回 "b"
 *
 * s = ""
 * 返回 " "
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _50_第一个只出现一次的字符 {

    public char firstUniqChar(String s) {
        char ch = ' ';
        if(s == null || s.length() == 0){
            return ch;
        }
        char[] chars = s.toCharArray();
        HashMap<Character, Boolean> map = new HashMap<>();
        for(char c : chars){
            map.put(c,!map.containsKey(c));  //第一次为true,如果重复了就变为false
        }
        for(char c : chars){
            if(map.get(c)){  //如果为true，代表没有重复
                return c;
            }
        }
        return ch;
    }

}

51. 数组中的逆序对

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

53. 在排序数组中查找数字

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

 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 *
 * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 */
public class _53_在排序数组中查找数字 {

    public int search(int[] nums, int target) {
        //二分法
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
                right = mid;
            }
            if(nums[mid] < target){
                left = mid + 1;
            }
        }
        //统计
        while(left < nums.length && nums[left++] == target){
            count++;
        }
        return count;
    }

}

53. 0~n-1中缺失的数字

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 * 示例 1:
 * 输入: [0,1,3]
 * 输出: 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _53_缺失的数字 {

    public int missingNumber(int[] nums) {
        //二分法
        if(nums == null || nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] != mid){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        if(nums[left] == left){  //此时递归到了最后一个还没找到
            return left + 1;
        }
        //否则返回前一个值
        return nums[left] - 1;
    }

}

54. 二叉搜索树的第k大结点

55. 二叉树的深度

55. 平衡二叉树

56. 数组中数字出现的次数Ⅰ

56. 数组中数字出现的次数Ⅱ

57. 和为s的两个数字

57. 和为s的连续正数序列

58. 翻转单词顺序

58. 左旋转字符串

59. 滑动窗口的最大值

59. 队列的最大值

60. n个骰子的点数

61. 扑克牌中的顺子

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
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _62_圆圈中最后剩下的数字 {

    //递归
    //约瑟夫环问题计算公式: f(n,m) = (f(n - 1,m) + m) % n
    public int lastRemaining(int n, int m) {
        if(n == 1){  //结束条件
            return 0;
        }
        return (lastRemaining(n - 1,m) + m) % n;
    }

    //非递归
    public int lastRemaining2(int n, int m) {
        int res = 0;
        for(int i = 2;i <= n;i++){    // i是数据规模，代表有多少个人
            res = (res + m) % i;
        }
        return res;
    }
}

63. 股票的最大利润

64. 求1+2+3+…+n

65. 不用加减乘除做加法

66. 构建乘积数组

67. 把字符串转换为整数

68. 二叉搜索树的最近公共祖先Ⅰ

68.二叉搜索树的最近公共祖先Ⅱ

程序员面试金典

01_09. 字符串轮转

/**
 * 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
 *
 * 示例1:
 *  输入：s1 = "waterbottle", s2 = "erbottlewat"
 *  输出：True
 *
 * 示例2:
 *  输入：s1 = "aa", s2 = "aba"
 *  输出：False
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/string-rotation-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _01_09_字符串轮转 {

    public boolean isFlipedString(String s1, String s2) {
        if(s1 == null || s2 == null){
            return false;
        }
        if(s1.length() != s2.length()){
            return false;
        }
        return (s1 + s1).contains(s2);
    }

}

16_16. 部分排序

/**
 * 给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。
 * 注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，
 * 若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
 *
 * 示例：
 * 输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
 * 输出： [3,9]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sub-sort-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _16_16_部分排序 {

    public int[] subSort(int[] array) {
        if(array == null || array.length == 0){
            return new int[]{-1,-1};
        }
        //从左到右依次扫描，寻找逆序对
        int max = array[0];
        int r = -1;  //记录最右边的那个逆序对的位置
        for(int i = 1;i < array.length;i++){
            if(array[i] >= max){
                max = array[i];
            }else{
                //记录位置
                r = i;
            }
        }
        int l = -1;  //记录最左边的那个逆序对的位置
        int min = array[array.length - 1];
        for(int i = array.length - 2;i >= 0;i--){
            if(array[i] <= min){
                min = array[i];
            }else{
                //记录位置
                l = i;
            }
        }

        return new int[]{l,r};
    }

}