输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        // hold[i] 表示 s 中以 i - 1 结尾的字符串是否可被wordDict拆分
        boolean[] hold = new boolean[n + 1];
        hold[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (hold[j] && wordDict.contains(s.substring(j, i))) {
                    hold[i] = true;
                    break;
                }
            }
        }
        return hold[n];
    }
}

/* String s;
   List<String> list = new ArrayList<String>(); */
   s.contains("hello"); //检验s是否包含字串"hello"
   list.contains("hello"); //检验list（集合）是否包含元素"hello"

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

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode hold = dummyHead;
        if(head==null){
            return head;
        }
        while(hold.next != null){
            if(!list.contains(hold.next.val)){
                list.add(hold.next.val);
                hold = hold.next;
            }
            else{
                hold.next = hold.next.next;
            }
        }
        return dummyHead.next;
    }
}

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

输入: [7,8,9,11,12]
输出: 1

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums.length == 0){
            return 1;
        }
        var list = new ArrayList<Integer>();
        int ans = 0;
        for(int i = 0;i < nums.length;i++){
            list.add(nums[i]);
        }
        //list.size()+2 可应对[1],[0,1,2...]等特殊数组
        for(int i = 1;i<list.size() + 2;i++){
            if(!list.contains(i)){
                ans = i;
                break;
            } 
        }
        return ans;
    }
}

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //调用库函数
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        return nums[nums.length-k];
        
        /* 手写某一种排序算法
        var len = nums.length;
        for (var i = 0; i < len - 1; i++) {
            for (var j = 0; j < len - 1 - i; j++) {
                if (nums[j] > nums[j+1]) {        // 相邻元素两两对比
                    var temp = nums[j+1];        // 元素交换
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums[len-k];
        */
    }
}

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int m = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, left, m - 1);
        root.right = buildTree(nums, m + 1, right);
        return root;
    }
}

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

class Solution {
public int longestValidParentheses(String s) {
	char[] chars = s.toCharArray();
	return Math.max(calc(chars, 0, 1, chars.length, '('), calc(chars, chars.length -1, -1, -1, ')'));
}
private static int calc(char[] chars , int i ,  int flag,int end, char cTem){
	int max = 0, sum = 0, currLen = 0,validLen = 0;
	for (;i != end; i += flag) {
		sum += (chars[i] == cTem ? 1 : -1);
        currLen ++;
		if(sum < 0){
			max = max > validLen ? max : validLen;
			sum = 0;
			currLen = 0;
            validLen = 0;
		}else if(sum == 0){
            validLen = currLen;
        }
	}
	return max > validLen ? max : validLen;
}
}

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

class Solution {
    public static boolean isMatch(String s, String p) {
        int sn = s.length();
        int pn = p.length();
        boolean[][] dp = new boolean[sn + 1][pn + 1];
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        dp[0][0] = true;
        for (int i = 1; i <= pn; ++i) {
            if (pArray[i-1] == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= sn; ++i) {
            for (int j = 1; j <= pn; ++j) {
                if (pArray[j-1] == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (pArray[j-1] == '?' || sArray[i-1] == pArray[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[sn][pn];
    }
}

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

class Solution {
       public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] dp = new int[row][col];
        dp[0][0] = 1;
        
        // base case
        for (int i = 1; i < row; i ++) {
            if (dp[i - 1][0] == 1 && obstacleGrid[i][0] != 1) dp[i][0] = 1;
            else break;
        }
        for (int i = 1; i < col; i ++) {
            if (dp[0][i - 1] == 1 && obstacleGrid[0][i] != 1) dp[0][i] = 1;
            else break;
        }

        for (int i = 1; i < row; i ++) {
            for (int j = 1; j < col; j ++) {
                if (obstacleGrid[i][j] == 1) continue;

                dp[i][j] = (obstacleGrid[i - 1][j] == 1 ? 0 : dp[i - 1][j])
                        + (obstacleGrid[i][j - 1] == 1 ? 0 : dp[i][j - 1]);
            }
        }
        return dp[row - 1][col - 1];
    }
}

给定如下二叉树，以及目标和 sum = 22
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return root.val == sum;
        }
        return hasPathSum(root.left, sum - root.val) 
            || hasPathSum(root.right, sum - root.val);
    }
}

输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        if(k == 0) {
            return new int[]{}; // 表示返回集合 {} 空集
    }
        if (longer == shorter) {
            return new int[]{k * longer}; // 表示返回集合 {value} value为k*longer的值
    }
        int n = longer - shorter;
        int[] ans = new int[k + 1];
        for(int i = 0;i <= k;i++) {
            ans[i] = shorter * k + i * n;
        }
        return ans;
    }
}

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2(K)	-3	    3
-5	    -10	    1
10	    30	   -5(P)
 

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] dp = new int[row][col];
        for(int i = row - 1; i >= 0; i--){
            for(int j = col - 1; j >= 0; j--){
                if(i==row-1&&j==col-1){ //终点的情况
        			dp[i][j]=Math.max(1, 1-dungeon[i][j]);
        		}else if(i==row-1){ //最后一行的情况
        			dp[i][j]=Math.max(1, dp[i][j+1]-dungeon[i][j]);
        		}else if(j==col-1){ //最后一列的情况
        			dp[i][j]=Math.max(1, dp[i+1][j]-dungeon[i][j]);
        		}else{	
        			dp[i][j]=Math.max(1, Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);
        		}
            }
        }
        return dp[0][0];
    }
}

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

class Solution {
    public int[] twoSum(int[] numbers, int target){
        int len = numbers.length;
        int left = 0, right = len - 1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return new int[]{left + 1, right + 1};
            }else if(sum > target){
                right--;
            }else {
                left++;
            }
        }
        return new int[2];
    }
}