1
public class PosArrayToBST {
2
    public static class Node{
3
        public int value;
4
        public Node left;
5
        public Node right;
6
        public Node(int v){
7
            value = v;
8
        }
9
    }
10

11
    public static Node startPosArrayToBST(int[] posArr){
12
       return process(posArr, 0, posArr.length-1);
13
    }
14
    // 使用posArr[L....R]这些数字，来建树，返回建好的树的头节点
15
    // 递归
16
    public static Node process(int[] posArr, int L, int R){
17
        if (L>R){
18
            return null;
19
        }
20
        // 头节点的数为R的数，即posArr最后的数为头节点
21
        Node head = new Node(posArr[R]);
22
        if (L == R){   // 说明该树只有一个节点
23
            return head;
24
        }
25
        int  M = L -1;
26
        int left = L;
27
        int right = R;
28
        while (left <= right){
29
            // 等同于 mid = (L+R)/2,之所以用位移，是因为位移更快，除法底层更复杂
30
            // int 范围 -21亿~21亿，L+R过大时有溢出风险， 所以用 L + （R - L）
31
            int mid = left + ((right - left) >> 1);
32
            if (posArr[mid] < posArr[R]){
33
                M = mid;
34
                left = mid +1;
35
            }else {
36
                right = mid - 1;
37
            }
38
        }
39
        head.left = process(posArr, L, M);
40
        head.right = process(posArr, M+1, R-1);
41
        return head;
42
    }
43
}

1
head.right = process(posArr, M+1, R-1);
2
// M = R -1 ;上面的结构就变为：
3
head.right = process(posArr, R, R-1); // 无效head.right = null;

1
if(M == -1){
2
    head.right = process(posArr, L, R-1);
3
}else if(M == R-1){
4
    head.left = process(posArr, L, R-1);
5
}else{
6
    head.left = process(posArr, L, M);
7
    head.right = process(posArr, M+1, R-1);
8
}

1
public class containExactly {
2
    // 时间复杂度 O（N^3 * logN） 不行
3
    public static int wayOne(String s, String a){
4
        if(s == null || a == null || s.length() < a.length()){
5
            return -1;
6
        }
7
        char[] aim = a.toCharArray();
8
        System.out.println("aim 的值为" + aim);
9
        Arrays.sort(aim);
10
        // aim 排完序
11
        String aimSort = String.valueOf(aim);
12
        for(int L = 0; L< s.length(); L++){
13
            for(int R = L; R < s.length(); R++){
14
                // substring 获取的范围是 [ )
15
                char[] cur = s.substring(L, R+1).toCharArray();
16
                Arrays.sort(cur);
17
                System.out.println(cur);
18
                String curSort = String.valueOf(cur);
19
                if (curSort.equals(aimSort)){
20
                    return L;
21
                }
22
            }
23
        }
24
        return -1;
25
    }
26
    // 下面这个复杂度低
27
    public static int wayTwo(String s, String a){
28
        if(s == null || a == null || s.length() < a.length()){
29
            return -1;
30
        }
31
        char[] aim = a.toCharArray();
32
        int[] count = new int[256];
33
        int M = aim.length;
34
        char[] str = s.toCharArray();
35
        for (int i = 0; i < M; i++) {
36
            count[aim[i]] ++;
37
        }
38
        int inValidTimes = 0, R = 0;
39
        // 先让窗口拥有M个字符
40
        for (; R< M; R++){
41
            if(count[str[R]]-- <=0){
42
                inValidTimes++;
43
            }
44
        }
45
        System.out.println(inValidTimes);
46
        // R==M  [0...M-1]
47
        // 第一次形成长度为M 的窗口
48
        for(; R < str.length; R++){
49
            if (inValidTimes == 0){
50
                return R-M;
51
            }
52
            if (count[str[R]]-- <= 0){
53
                inValidTimes++;
54
            }
55
            if (count[str[R - M]]++ < 0){
56
                inValidTimes--;
57
            }
58
        }
59
        return inValidTimes == 0 ? R - M : -1;
60
    }
61
    public static void main(String[] args) {
62
        String string = "abcdabcdsfcas";
63
        String a = "abc";
64
        int result = wayTwo(string, a);
65
        System.out.println(result);
66
    }
67
}