My Leetcode

作者: 寂静之进 | 来源:发表于2022-02-06 14:23 被阅读0次

我的code

1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int a = target - nums[i];//7
            if (!map.containsKey(nums[i])) {//2
                map.put(a, i);//7,0
            } else {
                return new int[]{map.get(nums[i]), i};
            }
        }
        return new int[]{0, 0};
    }
}

2.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例:

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int sum = 0;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }
        if (carry>0){
            current.next = new ListNode(carry);
        }
        return dummy.next;

    }
}

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     
输入: s = ""
输出: 0

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int j = 0;
        int length = 0;
        //abcbe
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
                length = Math.max(length, set.size());
            } else {
                //逐个移除，直到无重复字符
                while (set.contains(c)) {
                    set.remove(s.charAt(j));
                    j++;
                }
                set.add(c);
            }
        }
        return length;
    }
}

5.最长回文字符串

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"
输入：s = "a"
输出："a"
输入：s = "ac"
输出："a"

// 双指针 中心扩散法
class Solution {
    public String longestPalindrome(String s) {
        String s1 = "";
        String s2 = "";
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 分两种情况：即一个元素作为中心点，两个元素作为中心点
            s1 = extend(s, i, i);  // 情况1
            res = s1.length() > res.length() ? s1 : res;
            s2 = extend(s, i, i + 1);  // 情况2
            res = s2.length() > res.length() ? s2 : res;
        }
        return res;  // 返回最长的
    }
    public String extend(String s, int start, int end){
        String tmp = "";
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            tmp = s.substring(start, end + 1);  // Java中substring是左闭右开的，所以要+1
            // 向两边扩散
            start--;
            end++;
        }
        return tmp;
    }
}

7.整数翻转（des）

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

示例:

输入：x = 123
输出：321
输入：x = -123
输出：-321
输入：x = 120
输出：21
输入：x = 0
输出：0

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

17.电话号码的字母排列

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

class Solution {
    private String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private StringBuilder sb = new StringBuilder();
    private List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        backTrack(digits, 0);
        return result;
    }

    /**
     * @param digits 原始字符
     * @param i      位数
     */
    private void backTrack(String digits, int i) {
        if (i == digits.length()) {
            result.add(sb.toString());
            return;
        }
        String s = numString[digits.charAt(i) - '0'];
        for (int j = 0; j < s.length(); j++) {
            sb.append(s.charAt(j));
            backTrack(digits, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode dummy = new ListNode(-1);
//        dummy.next = head;
//        ListNode t1 = dummy;
//        ListNode t2 = dummy;//后
//        while (n-- > 0) {
//            t2 = t2.next;
//        }
//        ListNode tmp = null;//删除节点前一位
//        while (t2 != null) {
//            tmp = t1;
//            t1 = t1.next;
//            t2 = t2.next;
//        }
//        tmp.next = t1.next;
//        t1.next = null;
//        return dummy.next;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int count = 0;
        ListNode t1 = dummy.next;
        while (t1 != null) {
            t1 = t1.next;
            count++;
        }
        if (count < n){
            return null;
        }
        ListNode tmp = dummy;
        for (int i = 0; i < count - n; i++) {
            tmp = tmp.next;
        }
        tmp.next = tmp.next.next;
        return dummy.next;
    }
}

26.删除有序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        //输入：nums = [0,0,1,1,1,2,2,3,3,4]
        //输出：5, nums = [0,1,2,3,4]
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int j = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[j] != nums[i]) {
                nums[++j] = nums[i];
            }
        }
        return j + 1;
    }
}

27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 $O(1)$ 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //输入：nums = [0,1,2,2,3,0,4,2], val = 2
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                //交换双指令的int值
                int tmp = nums[j];
                nums[j++] = nums[i];
                nums[i] = tmp;
            }
        }
        return j;
    }
}

36.有效的数独

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 记录某行，某位数字是否已经被摆放
        boolean[][] row = new boolean[9][9];
        // 记录某列，某位数字是否已经被摆放
        boolean[][] col = new boolean[9][9];
        // 记录某 3x3 宫格内，某位数字是否已经被摆放
        boolean[][] block = new boolean[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int blockIndex = i / 3 * 3 + j / 3;
                    if (row[i][num] || col[j][num] || block[blockIndex][num]) {
                        return false;
                    } else {
                        row[i][num] = true;
                        col[j][num] = true;
                        block[blockIndex][num] = true;
                    }
                }
            }
        }
        return true;

    }
}

37.解数独（难）

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }
    private boolean solveSudokuHelper(char[][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int idx) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
        }
        for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, i);//可以重复
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

40.组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    private int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        used = new boolean[candidates.length];
        combinationSum2Help(candidates, target, 0);
        return result;
    }

    public void combinationSum2Help(int[] candidates, int target, int index) {
        //结束
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length && sum + candidates[i] <= target; i++) {
            //同树层剪枝
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            if (!used[i]) {
                used[i] = true;
                path.add(candidates[i]);
                sum += candidates[i];
                combinationSum2Help(candidates, target, i + 1);
                sum -= candidates[i];
                path.removeLast();
                used[i] = false;
            }
        }
    }
}

46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }

}

47.全排列II

给定一个可包含重复数字的序列 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]]

class Solution {

    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        permuteUniqueHelper(nums);
        return result;
    }

    public void permuteUniqueHelper(int[] nums) {
        if (nums.length == path.size()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //同树层剪枝
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                permuteUniqueHelper(nums);
                path.removeLast();
                used[i] = false;
            }
        }
    }


}

53.最大子数组合

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];//dp[i]是以下标i元素结尾的最大和
        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            if(max < dp[i]){
                max = dp[i];
            }
        }
        return max;
    }
}

55.跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

class Solution {
    public boolean canJump(int[] nums) {
//        if (nums.length == 1) {
//            return true;
//        }
//        int most = 0;
//
//        for (int i = 0; i <= most; i++) {
//            most = Math.max(most, i + nums[i]);
//            if (most >= nums.length - 1) {
//                return true;
//            }
//        }
//        return false;

        int most = 0;//累计步数
        for (int i = 0; i < nums.length; i++) {
            if (i <= most) {
                most = Math.max(most, i + nums[i]);
                if (most >= nums.length - 1){
                    return true;
                }
            }else {
                return false;
            }
        }
        return false;
    }
}

62.不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

// 示例 1： 
//
// 
//输入：m = 3, n = 7
//输出：28 
//
// 示例 2： 
//
// 
//输入：m = 3, n = 2
//输出：3
//解释：
//从左上角开始，总共有 3 条路径可以到达右下角。
//1. 向右 -> 向下 -> 向下
//2. 向下 -> 向下 -> 向右
//3. 向下 -> 向右 -> 向下

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //初始化
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

63.不同路径II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

示例 2：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];

        for (int i = 0; i < m; i++) {
            if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍，后续都到不了
            dp[0][i] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[i][0] == 1) break; ////一旦遇到障碍，后续都到不了
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][m - 1];
    }
}

69.X的平方根(des)

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶

示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶

class Solution {
    public int climbStairs(int n) {
//        // 跟斐波那契数列一样
        if (n <= 2) return n;
        int a = 1, b = 2, sum = 0;

        for (int i = 3; i <= n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
//        int[] dp = new int[n + 1];
//        dp[0] = 1;
//        dp[1] = 1;
//        for (int i = 2; i <= n; i++) {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//        int a = 0, b = 1, c = 0; // 默认需要1次
//        for (int i = 1; i <= n; i++) {
//            c = a + b;          // f(i - 1) + f(n - 2)
//            a = b;              // 记录上一轮的值
//            b = c;              // 向后步进1个数
//        }
//        return c;
    }
}

75.颜色分类（des）

class Solution {
    public void sortColors(int[] nums) {
        //输入：nums = [2,0,2,1,1,0]
        //输出：[0,0,1,1,2,2]
//        int a = 0, b = 0, c = 0;
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] == 0) {
//                a++;
//            }
//            if (nums[i] == 1) {
//                b++;
//            }
//            if (nums[i] == 2) {
//                c++;
//            }
//        }
//        for (int i = 0; i < a; i++) {
//            nums[i] = 0;
//        }
//        for (int i = a; i < a + b; i++) {
//            nums[i] = 1;
//        }
//        for (int i = a+b; i < a+b+c; i++) {
//            nums[i] = 2;
//        }
//        int count[] = {0, 0, 0};
//        for (int i = 0; i < nums.length; i++) {
//            assert nums[i] >= 0 && nums[i] <= 2;
//            count[nums[i]]++;
//        }
//        int index = 0;
//        for (int i = 0; i < count[0]; i++) {
//            nums[index++] = 0;
//        }
//        for (int i = 0; i < count[1]; i++) {
//            nums[index++] = 1;
//        }
//        for (int i = 0; i < count[2]; i++) {
//            nums[index++] = 2;
//        }
        //输入：nums = [2,0,2,1,1,0]
        //输出：[0,0,1,1,2,2]
        int k = -1;
        int e = nums.length;//逐渐缩小
        for (int i = 0; i < e; ) {
            if (nums[i] == 0) {
                k++;
                int tmp = nums[k];
                nums[k] = nums[i];
                nums[i] = tmp;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                assert nums[i] == 2;
                e--;
                int tmp = nums[e];
                nums[e] = nums[i];
                nums[i] = tmp;
            }
        }
    }
}

77.组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution {


    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果

    public List<List<Integer>> combine(int n, int k) {
        if (n == 0) {
            return result;
        }
        combineHelper(n, k, 0);
        return result;
    }

    private void combineHelper(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < n; i++) {
//        for (int i = startIndex; i < n - (k - path.size()) + 1; i++) {
            path.add(i + 1);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

80.删除有序数组中的重复项II

//给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
// 示例 1： 
//
// 
//输入：nums = [1,1,1,2,2,3]
//输出：5, nums = [1,1,2,2,3]
//解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,1,1,1,1,2,3,3]
//输出：7, nums = [0,0,1,1,2,3,3]
//解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的
//元素。

class Solution {
    public int removeDuplicates(int[] nums) {
        //输入：nums = [0,0,0,1,1,1,2,3,3]
        //输出：7, nums = [0,0,1,1,2,3,3]
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int j = 0;//指针
        int c = 1;//计数器
        for (int i = 1; i < nums.length; i++) {
            if (nums[j] != nums[i]) {
                c = 1;
                nums[++j] = nums[i];

            } else if (c >= 2) {
                continue;
            } else {
                nums[++j] = nums[i];
                c++;
            }
        }
        return j + 1;
//
//        int i = 0;
//        for (int n : nums)
//            if (i < 2 || n > nums[i-2])
//                nums[i++] = n;
//        return i;
    }
}

91.解码方法

//一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： 
//
// 
//'A' -> 1
//'B' -> 2
//...
//'Z' -> 26
// 
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为： 
//
// 
// "AAJF" ，将消息分组为 (1 1 10 6) 
// "KJF" ，将消息分组为 (11 10 6) 
// 示例 1： 
//
// 
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

class Solution {
    public int numDecodings(String s) {
        final int length = s.length();
        if(length == 0) return 0;
        if(s.charAt(0) == '0') return 0;

        int[] dp = new int[length+1];
        dp[0] = 1;

        for(int i=0;i<length;i++){
            dp[i+1] = s.charAt(i)=='0'?0:dp[i];
            if(i > 0 && (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))){
                dp[i+1] += dp[i-1];
            }
        }

        return dp[length];
    }
}

95.不同的二叉搜索树II

//给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 3
//输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[[1]]

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return buildTree(1, n);
    }

    /**
     * @param start 左边界
     * @param end   右边界
     * @return
     */
    public List<TreeNode> buildTree(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        //终止条件
        if (start > end) {
            result.add(null);
            return result;
        }
        //递归根节点
        for (int i = start; i <= end; i++) {
            //左右子树元素合集
            List<TreeNode> leftTreeNodes = buildTree(start, i - 1);
            List<TreeNode> rightTreeNodes = buildTree(i + 1, end);
            //连接
            for (TreeNode leftNode : leftTreeNodes) {
                for (TreeNode rightNode : rightTreeNodes) {
                    TreeNode cur = new TreeNode(i);
                    cur.left = leftNode;
                    cur.right = rightNode;
                    result.add(cur);
                }
            }
        }
        return result;
    }

}

96.不同的二叉搜索树

//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

98.验证二叉搜索树

class Solution {

    private Long val = Long.MIN_VALUE;//左边值，遍历至今的最大值

    /**
     * 中序遍历判断是否按顺序递增
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        if (!left) {
            return false;
        }
        if (root.val <= val) {
            return false;
        }
        //更新最大值
        val = Long.valueOf(root.val);
        boolean right = isValidBST(root.right);
        return right;
    }
}

99.恢复二叉搜索树

class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        dfs(root, list);
        TreeNode x = null;
        TreeNode y = null;
        //扫面遍历的结果，找出可能存在错误交换的节点x和y
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i).val > list.get(i + 1).val) {
                y = list.get(i + 1);
                if (x == null) {//相邻节点取值
                    x = list.get(i);
                }
            }
        }
        //如果x和y不为空，则交换这两个节点值，恢复二叉搜索树
        if (x != null && y != null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    //中序遍历二叉树，并将遍历的结果保存到list中
    private void dfs(TreeNode node, List<TreeNode> list) {
        if (node == null) {
            return;
        }
        dfs(node.left, list);
        list.add(node);
        dfs(node.right, list);
    }
}

122.买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        //贪心
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
//        //动态规划
//        // [天数][是否持有股票]
//        int[][] dp = new int[prices.length][2];
//
//        // base case
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//
//        for (int i = 1; i < prices.length; i++) {
//            // dp公式
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//        }
//
//        return dp[prices.length - 1][0];
    }
}

139.单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (wordDict.contains(s.substring(j,i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }
}

141.环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        //快慢指针
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

167.两数之和II-输入有序数组

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //输入：numbers = [2,7,11,15], target = 9
        //双指针
        int low = 0, high = numbers.length - 1;
        while (low <= high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum > target) {
                high--;
            } else {
                low++;
            }
        }
        return new int[]{0, 0};
    }
}

198.打家劫舍

class Solution {
    public int rob(int[] nums) {
        //d[i] = Max(d[i-1],d[i-2]+num[i])
        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(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

206.反转链表

class Solution {
//    public ListNode reverseList(ListNode head) {
//        //从后往前递归
//        if (head == null) {
//            return null;
//        }
//        if (head.next == null) {
//            return head;
//        }
//        ListNode last = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return last;
//    }

    //    public ListNode reverse(ListNode pre,ListNode head){
//        if(head == null) return pre;
//        ListNode temp = head.next;
//        head.next = pre;
//        return reverse(head,temp);
//    }
//    public ListNode reverseList(ListNode head) {
//        return reverse(null, head);
//    }
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;//qian
        ListNode cur = head;//hou
        ListNode tmp;//临时
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

213.打家劫舍II

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        if (nums.length == 3) return Math.max(Math.max(nums[0], nums[1]), nums[2]);
        int i1 = robHelper(nums, 0, nums.length - 1);
        int i2 = robHelper(nums, 1, nums.length);
        Arrays.copyOfRange(nums,1,3);
        return Math.max(i1, i2);
    }

    private int robHelper(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];

        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);

//        dp[0] = nums[start];
//        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2; i < end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end - 1];
    }
}

215.数组中的第K个最大元素(des)

class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
//        int len = nums.length;
//        Arrays.sort(nums);
//        return nums[len - k];
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            int index = partition(nums, left, right);
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
    }

    // 在区间 nums[left..right] 区间执行 partition 操作
    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

279.完全平方数

class Solution {
    // 版本一，先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        //当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

//class Solution {
//    // 版本二， 先遍历背包, 再遍历物品
//    public int numSquares(int n) {
//        int max = Integer.MAX_VALUE;
//        int[] dp = new int[n + 1];
//        // 初始化
//        for (int j = 0; j <= n; j++) {
//            dp[j] = max;
//        }
//        // 当和为0时，组合的个数为0
//        dp[0] = 0;
//        // 遍历背包
//        for (int j = 1; j <= n; j++) {
//            // 遍历物品
//            for (int i = 1; i * i <= j; i++) {
//                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
//            }
//        }
//        return dp[n];
//    }
//}

283.移动零

class Solution {
    public void moveZeroes(int[] nums) {
        //前置条件
        if (nums == null || nums.length <= 1) {
            return;
        }
        //双指针，一个指针遍历，一个指针标记当前非零位置
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i == j) {            //防止全部非0,自身交换
                    j++;
                } else {
                    //交换数据
                    int temp = nums[j];
                    nums[j++] = nums[i];
                    nums[i] = temp;
                }
            }
        }
    }
}

300.最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

309.最佳买卖股票时间含冷冻期

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];

        // bad case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
        dp[1][1] = Math.max(dp[0][1], -prices[1]);

        for (int i = 2; i < prices.length; i++) {
            // dp公式
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }

        return dp[prices.length - 1][0];
    }
}

322.零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

337.打家劫舍III

class Solution {
    public int rob(TreeNode root) {
//        Map<TreeNode, Integer> memo = new HashMap<>();
//        return robAction(root, memo);
        int[] res = robAction1(root);
        return Math.max(res[0], res[1]);
    }
//    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
//        if (root == null)
//            return 0;
//        if (memo.containsKey(root))
//            return memo.get(root);
//        int money = root.val;
//        if (root.left != null) {
//            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
//        }
//        if (root.right != null) {
//            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
//        }
//        int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo));
//        memo.put(root, res);
//        return res;
//    }

    int[] robAction1(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

343.整数拆分

class Solution {
    public int integerBreak(int n) {
        //dp[i]为正整数i拆分结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i - 1; ++j) {
                //j*(i-j)代表把i拆分为j和i-j两个数相乘
                //j*dp[i-j]代表把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

377.组合总和IV

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

392.判断子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }
    }
}

435.无重复区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
//        if (intervals.length < 2) return 0;
//
//        Arrays.sort(intervals, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                if (o1[1] != o2[1]) {
//                    return Integer.compare(o1[1],o2[1]);
//                } else {
//                    return Integer.compare(o1[0],o2[0]);
//                }
//            }
//        });
//
//        int count = 1;
//        int edge = intervals[0][1];
//        for (int i = 1; i < intervals.length; i++) {
//            if (edge <= intervals[i][0]){
//                count ++; //non overlap + 1
//                edge = intervals[i][1];
//            }
//        }
//        return intervals.length - count;

        Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });
        int remove = 0;
        int pre = intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            if(pre>intervals[i][0]) {
                remove++;
                pre = Math.min(pre,intervals[i][1]);
            }
            else pre = intervals[i][1];
        }
        return remove;
    }
}

474.一和零

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

494.目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}

509.斐波那契数

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

1115.交替打印FooBar

class FooBar {
    private int n;
    private CountDownLatch countDownLatch1 = new CountDownLatch(1);
    private CountDownLatch countDownLatch2 = new CountDownLatch(0);
    private AtomicBoolean atomicBoolean = new AtomicBoolean(true);

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        for (int i = 0; i < n; i++) {
//            while (!atomicBoolean.get()){
                Thread.currentThread().yield();
//            }
            // printFoo.run() outputs "foo". Do not change or remove this line.
            countDownLatch2.await();
            printFoo.run();
//            atomicBoolean.set(false);
            countDownLatch1.countDown();
            countDownLatch2 = new CountDownLatch(1);
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {

        for (int i = 0; i < n; i++) {
            countDownLatch1.await();
            // printBar.run() outputs "bar". Do not change or remove this line.
//            while (atomicBoolean.get()){
//                Thread.currentThread().yield();
//            }
            printBar.run();
//            atomicBoolean.set(true);
            countDownLatch1 = new CountDownLatch(1);
            countDownLatch2.countDown();
        }
    }
}

1114.按序打印

class Foo {
    //    private Semaphore semaphore1 = new Semaphore(0);
//    private Semaphore semaphore2 = new Semaphore(0);
//    private AtomicInteger atomicInteger1 = new AtomicInteger(0);
//    private AtomicInteger atomicInteger2 = new AtomicInteger(0);
    private CountDownLatch second = new CountDownLatch(1);
    private CountDownLatch third = new CountDownLatch(1);
//    private volatile int condition = 1;

    public Foo() {
    }

    public void first(Runnable printFirst) throws InterruptedException {

        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
//        condition = 2;
        second.countDown();
//        atomicInteger1.incrementAndGet();
//        semaphore1.release();
    }

    public void second(Runnable printSecond) throws InterruptedException {

        // printSecond.run() outputs "second". Do not change or remove this line.
//        semaphore1.acquire();
//        while (atomicInteger1.get() != 1) {
//
//        }
//        while (condition != 2) {
//
//        }
        second.await();
        printSecond.run();
//        condition = 3;
        third.countDown();
//        atomicInteger2.incrementAndGet();
//        semaphore2.release();
    }

    public void third(Runnable printThird) throws InterruptedException {

        // printThird.run() outputs "third". Do not change or remove this line.
//        semaphore2.acquire();
//        while (atomicInteger2.get() != 1) {
//
//        }
//        while (condition != 3) {
//
//        }
        third.await();
        printThird.run();
    }
}

My Leetcode

我的code

1.两数之和

2.两数相加

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

5.最长回文字符串

7.整数翻转（des）

17.电话号码的字母排列

19.删除链表的倒数第N个节点

26.删除有序数组中的重复项

27.移除元素

36.有效的数独

37.解数独（难）

39.组合总和

40.组合总和II

46.全排列

47.全排列II

53.最大子数组合

55.跳跃游戏

62.不同路径

63.不同路径II

69.X的平方根(des)

70.爬楼梯

75.颜色分类（des）

77.组合

80.删除有序数组中的重复项II

91.解码方法

95.不同的二叉搜索树II

96.不同的二叉搜索树

98.验证二叉搜索树

99.恢复二叉搜索树

122.买卖股票的最佳时机II

139.单词拆分

141.环形链表

167.两数之和II-输入有序数组

198.打家劫舍

206.反转链表

213.打家劫舍II

215.数组中的第K个最大元素(des)

279.完全平方数

283.移动零

300.最长递增子序列

309.最佳买卖股票时间含冷冻期

322.零钱兑换

337.打家劫舍III

343.整数拆分

377.组合总和IV

392.判断子序列

435.无重复区间

474.一和零

494.目标和

509.斐波那契数

1115.交替打印FooBar

1114.按序打印

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读