leetcode

 //45. 跳跃游戏 II
public int jump(int[] nums) {
    int index = 0; //记录跳跃前当前下标
    int len = nums.length - 1; //目标终点
    int next = 0; //记录下一跳应该往哪跳
    int count = 0; //跳跃次数
    int max = 0; //每次寻找时，能跳到最远的位置
    while (index < len) {
        for (int i = 1; i <= nums[index]; i++) {
            if (index + i >= len) return ++count; //如果已经出界返回
            if (nums[index + i] + i >= max) { //能比之前找的跳的更远更新next,max
                max = nums[index + i] + i;
                next = index + i;
            }
        }
        index = next; //更新位置为下一跳
        count++;
        max = 0;  //max清0不干扰下次比较
    }
    return count;
}
//300. 最长递增子序列
public int lengthOfLIS(int[] nums) {
    if(nums==null || nums.length<1) return 0;
    if(nums.length == 1) return 1;
    //end中的元素表示长度为index+1的递增子序列的最右边的值，因此end是递增数组
    int[] end = new int[nums.length];
    end[0]=nums[0];
    int last = 0; //表示end的有效长度
    for(int i = 1; i < nums.length;i++){
        if(nums[i]>end[last]){
            end[++last] = nums[i]; //比最大的递增子序列还大，end有效长度+1
        }else if(nums[i]==end[last]){
            continue;  //刚好一样 跳过继续循环
        }else{
            int index = serach(end,last,nums[i]);  //end找到大于最右的，或者等于的
            end[index] = nums[i];
        }
    }
    return last+1;

}
private int serach(int[] array,int lastIndex,int target){
    int R = lastIndex;
    int L = 0;
    int mid = 0;
    while(L<=R){
        mid = (R-L)/2+L;
        if(array[mid]>target) {
            R = mid - 1;
        }else if(array[mid]==target){
            return mid;
        }
        else{
            L = mid +1;
        }
    }
    return L;
}
//96. 不同的二叉搜索树
public int numTrees(int n) {
    //思考成以1,2,3,4……n为根节点时左子树的可能性*右子树
    if(n<2) return 1;
    int[] dp = new int[n+1]; //dp[n]表示n个节点有几种
    dp[0] = 1;
    dp[1] = 1;
    //动态转移dp[n] = dp[0]*dp[n-1]+dp[1]*dp[n-2]+dp[2]*dp[n-3]+dp[3]*dp[n-4]+...dp[n-1]*dp[0]
    for(int i =2;i<=n;i++){
        for(int j = 0;j-1||j>-1){
        int a = i>-1 ? ch1[i]-'0' : 0;
        int b = j>-1 ? ch2[j]-'0' : 0;
        int sum = a+b+up;
        up=sum/10;
        sum =sum%10;
        builder.append(sum);
        i--;
        j--;
    }
    if(up>0) builder.append(up);
    return builder.reverse().toString();
}
//101. 对称二叉树
public boolean isSymmetric(TreeNode root) {
    //一个往左一个往右移动看是否相等
    return cheak(root, root);
}
private boolean cheak(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) return true;
    if (root1 == null || root2 == null) return false;
    if (root1.val != root2.val) return false;
    return cheak(root1.left, root2.right) && cheak(root1.right, root2.left);

}

//226. 翻转二叉树
public TreeNode invertTree(TreeNode root) {
    //翻转节点的左右节点，并向左右儿子节点递归。
    reverse(root);
    return root;
}
private void reverse(TreeNode node) {
    if (node == null) return;
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
    reverse(node.left);
    reverse(node.right);
}
//438. 找到字符串中所有字母异位词 滑动窗口
public List findAnagrams(String s, String p) {
    List list = new ArrayList();//结果集
    int plen = p.length(); //s长度
    int slen = s.length();//p长度
    int count = 0;//遍历窗口时匹配上p所需要的字符的个数
    if (slen < plen) return list;
    //记录p需要的字符个数0表示不需要，-1表示刚好满足要求，-2表示多一个.... 1表示差1个
    int[] pchar = new int[26];
    //统计需要的词频
    for (int i = 0; i < plen; i++) {
        pchar[p.charAt(i) - 'a']++;
    }
    //初始化窗口
    for (int i = 0; i < plen; i++) {
        int x = s.charAt(i) - 'a';
        if (pchar[x] > 1) {
            count++;
            pchar[x]--;
        } else if (pchar[x] == 1) {
            count++;
            pchar[x] = -1;
        } else if (pchar[x] < 0) {
            pchar[x]--;
        }
    }
    if (count == plen) list.add(0); //如果初始化即可满足加入0
    int right = plen;  //窗口右指针，表示要加入窗口的下一个字母
    int left = 0;  //窗口左指针，表示要退出窗口的下一个字母
    while (right < slen) { //不越界
        int x2 = s.charAt(left) - 'a'; //左右对应的词频表的位置
        int x1 = s.charAt(right) - 'a';
        if (pchar[x1] > 1) {
            count++;   //加入了需要的 count++
            pchar[x1]--;
        } else if (pchar[x1] == 1) {
            count++;    //加入了需要的并且刚好够了 修改为-1 count++
            pchar[x1] = -1;
        } else if (pchar[x1] < 0) {
            pchar[x1]--; //加入了重复需要的count不变 词频继续减
        }
        if (pchar[x2] > 0) {
            count--;    //退出了还需要的 count--
            pchar[x2]++;
        } else if (pchar[x2] == -1) {
            count--;     //退出了刚好满足的 count-- ，还需要1个修改为1
            pchar[x2] = 1;
        } else if (pchar[x2] < -1) {
            pchar[x2]++;  //退出了窗口中重复多的 count不变 词频++
        }
        if (count == plen) list.add(left + 1);  //刚好满足 加入结果
        right++;
        left++;
    }
    return list;
}