LeetCode每日一题：1713得到子序列的最少操作次数

今天的每日一题有些难度，一开始没看数据范围直接用的最长公共子序列不行，仔细一看，A串不重复，想到了用最长上升子序列，树状数组太久没写有点生疏，顺便复习了一下树状数组

class Solution {

    private int T[];
    private int L;

    void update(int i, int x) { 
        for (; i <= L; i += i & -i)
            T[i] = Math.max(T[i], x);
    }   
    int query(int i) {
        int ans = 0;
        for (; i != 0; i -= i & -i)
            ans = Math.max(ans, T[i]);
        return ans;
    }

    public int minOperations(int[] target, int[] arr) {
        L = target.length;
        T = new int[target.length+1];
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<target.length;i++){
            map.put(target[i],i+1);
        }
        int a[] = new int[arr.length];
        int tot = 0;
        for(int i=0;i<arr.length;i++){
            if(map.get(arr[i]) == null) continue;
            else{
                a[tot] = map.get(arr[i]);
                tot++;
            }
        }
        int maxx = 0;
        for(int i=0;i<tot;i++){
            int aa = query(a[i] - 1) + 1;
            maxx = Math.max(maxx,aa);
            update(a[i],aa);
        }
        return target.length-maxx;

    }
}

树状数组复习

C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]; //k为i的二进制中从最低位到高位连续零的长度

这个怎么实现求和呢，比如我们要找前7项和，那么应该是SUM = C[7] + C[6] + C[4];而根据上面的式子，容易的出SUMi = C[i] + C[i-2^k1] + C[(i - 2^k1) - 2^k2] + .....；

实现更新同理，如要更新位置3，则应该把所有带3的都更新，即C[3],C[4],C[8]

int lowbit(int x){
 5     return x&(-x);
 6 }
 7 
 8 void updata(int i,int k){    //在i位置加上k
 9     while(i <= n){
10         c[i] += k;
11         i += lowbit(i);
12     }
13 }
14 
15 int getsum(int i){        //求A[1 - i]的和
16     int res = 0;
17     while(i > 0){
18         res += c[i];
19         i -= lowbit(i);
20     }
21     return res;
22 }