B站左程云算法视频中级班9~10

题目1：给定一个整数数组，长度为n，找到[1，n]中所有未出现在A中的数

inplace算法：使得i位置上放i+1

3 2 1 6 2 7 5

0 1 2 3 4 5 6

0位置放1，所以3和2位置的数换，1位置放2，2位置放3，.....

//请保证arr[0..N-1]上的数字都在[1~n]之间
public static void printNumberNoInArray(int[] arr) {
    if (arr == null || arr.length == 0){
        return ;
    }
    for (int value : arr){ // 争取做到，i位置上，放的数是 i + 1
        modify(value,arr);
    }
    for(int i = 0; i < arr.length; i++){
        if (arr[i] != i + 1){// 没做到的位置，就知道缺的数字
            System.out.println(i + 1);
        }
    }
}

public static void modify(int value, int[] arr){
    while(arr[value - 1] != value){
        int tmp = arr[value - 1];
        arr[value - 1] = value;
        value = tmp; 
    }
}

题目2：（主播打赏问题） 初始人气值a（设为偶数），目标人气值b（偶数）  a小于等于b

方案1）点赞，花费x， 人气值+2 

        2）送礼 ，花费Y，人气值*2

        3）私聊，花费Z，人气值-2

使得a = b，至少花费几个币

//想要达到的目标是end
//目前达到的分数是cur
//三种决策
//1) cur + 2
//2) cur * 2
//3) cur - 2
public static int func(int x, int y, int z, int end, int cur){
    if(cur == end){
        return 0;
    }
    int p1 = process(x, y, z, end, cur + 2) + x;
    int p2 = process(x, y, z, end, cur * 2) + y;
    int p3 = process(x, y, z, end, cur - 2) + z;
    return Math.min(p1, Math.min(p2, p3));
}

存在的问题：递归跑不完

缺少限制条件，basecase的量不够

1）求出频繁解，设通过一直点赞得答案，花费x币，所以添加设置，当花费超过x时return（通用）

2）通过存在a>b，再减，例如a*2 - 2 = b，则a不能超过目标的两倍

public static int minCoins1(int add, int times, int del, int start, int end){
    if (start > end){
        return -1;
    }
    return process(0, end, add, times, del, start, end * 2, ((end - start) / 2) * add);
}

//preMoney 之前花了多少币  可变
//aim 目标 
//int add, int times, int del  固定
//start当前来到的人气
//limitAim人气达到什么程度不需要再尝试 固定
//limitCoin已经使用的币大到什么程度不需要再尝试了 固定
//返回最小币数
public static int process(int preMoney, int aim, int add, int times, int del, int start, int limitAim, int limitCoin){
   if (preMoney > limitCoin){
        return Integer.MAX_VALUE;
    }
    if (start < 0){
        return Integer.MAX_VALUE;
    }
    if (start > limitAim){
        return Integer.MAX_VALUE;
    }
    if (aim == start){
        return preMoney;
    }
    int min = Integer.MAX_VALUE;
    //人气+2的方式
    int p1 = process(preMoney + add, aim, add, times, del, start + 2, limtiAim, limitCoin);
    if(p1 != Integer.MAX_VALUE){
        min = p1;
    }
    //人气-2的方式
    int p2 = process(preMoney + add, aim, add, times, del, start - 2, limtiAim, limitCoin);
    if(p2 != Integer.MAX_VALUE){
        min = Math.min(min, p2);
    }
    //人气*2的方式
    int p3 = process(preMoney + add, aim, add, times, del, start * 2, limtiAim, limitCoin);
    if(p3 != Integer.MAX_VALUE){
        min = Math.min(min, p3);
    }
    return min;
}

题目3：每个活动需要花费一定的时间参与，参与活动可以从任意活动开始，但一旦开始，就需要将后续活动参加完毕，活动之间存在依赖，计算在有限时间内能获得的最大奖励和需要的最少时长

思路：建表map（有序表）key总天数，value钱

每个节点里的表天数变大，收益也变大，最后合成一个大表

题目4：给一个只有0（假）、1（真）、&（与）、|（或）和^（异或）五种字符组成的字符串express，给再一个布尔值desired，返回express有多少种组合方式（加小括号），可以达到desired的结果

0        &        1        ^        0        |        0        &        1

0        1        2        3        4        5        6        7        8

1） &         2）^         3 ）|         4）&  做最后结合的符号         

public static int num1(String express, boolean desired){
    if(express == null || express.equals("")){
        return 0;
    }
    char[] exp = express.toCharArray();
    if (!isValid(exp)){
        return 0;
    }
    return p(exp, desired, 0, exp.length - 1);
}

//exp[L..R] 返回期待为desired的组合方法数
//潜台词：L R一定不要压中逻辑符号
public static int p(char[] exp, boolean desired, int L, int R){
    if (L == R){//basecase 1
        if(exp[L] == '1'){
            return desried ? 1 : 0;
        }else {
            return desried ? 0 : 1;
        }
    }
    
    // L..R
    int res = 0;    
    if(desired){
        //i位置尝试L..R范围上的每一个逻辑符号，都是最后结合的
        for (int i = L + 1; i < R; i += 2) {
            switch(exp[i]){
                case '&':
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    break;
                case '|':
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    break;
                case '^':
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    break;
            }
        }
    }else {//期待为false
       for (int i = L + 1; i < R; i += 2) {
            switch(exp[i]){
                case '&':
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, true, L, i - 1) * p(exp, false, i + 1, R);
                    break;
                case '|':
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    break;
                case '^':
                    res += p(exp, true, L, i - 1) * p(exp, true, i + 1, R);
                    res += p(exp, false, L, i - 1) * p(exp, false, i + 1, R);
                    break;
            }
        }
    }
    return res;
}

public static boolean isValid(char[] exp){
    if((exp.length & 1) == 0){
        return false;
    }
    for(int i = 0; i < exp.length; i += 2){
        if((exp[i] != '1') && (exp[i] != '0')){
            return false;
        }
    }
    for(int i = 1; i < exp.length; i += 2){
        if((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '|')){
            return false;
        }
    }
    return true;
}

动态规划：

public static int dpLive(String express, boolean desired){
    char[] str = express.toCharArray();
    int N = str.length;
    int[][] tMap = new int[N][N];
    int[][] fMap = new int[N][N];
    for(int i = 0; i < N; i += 2){
        tMap[i][i] = str[i] == '1' ? 1 : 0;
        fMap[i][i] = str[i] == '0' ? 1 : 0;
    }
    for (int row = N - 3; row >= 0; row -= 2){
        for (int col = row + 2; col < N; col += 2){
            //row...col tMap fMap
            for(int i = row + 1; i < col; i += 2){
                switch(str[i]){
                case '&':
                    tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];
                    break;
                case '|':
                    tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];
                    tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];
                    tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];
                    break;
                case '^':
                    tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];
                    tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];
                    break;
            }
                switch(str[i]){
                case '&':
                    fMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];
                    fMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];
                    fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];
                    break;
                case '|':
                    fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];
                    break;
                case '^':
                    fMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];
                    fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];
                    break;
            }
        }
    }
    return desired ? tMap[0][N - 1] : fMap[0][N - 1];
}

题目5：在一个字符串中找到没有重复字符串中最长的长度

思路：看到子串和子序列就想到以i位置为结尾的情况下最长无重复子序列的情况

两种情况：i位置的数的第一个瓶颈：上次i位置数出现的位置

                i-1结尾的最长无重复子串的长度是多少 ，以i结尾突破不了i-1的瓶颈

       两个瓶颈哪个近，哪个就是答案

public static int maxUnique(String str){
    if(str == null || str.equals("")){
        return 0;
    }
    char[] chas = str.toCharArray();
    //map代替了哈希表 假设字符的码是0~255
    int[] map = new int[256];
    for(int i = 0; i < 256; i++){
        map[i] = -1;
    }
    int len = 0;
    int pre = -1;
    int cur = 0;
    for (int i = 0; i != chas.length; i++){
        pre = Math.max(pre, map[chas[i]]);
        cur = i - pre;
        len = Math.max(len, cur);
        map[chas[i]] = i;
    }
    return len;
}

题目6：编辑距离问题

给定两个字符串str1和str2，再给定三个整数ic、dc和rc代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价

1）1：a1bck   2: abc

将a1bc转成abc，然后删去k  dp[i-1][j]+del

2）1：abcd   2：abcde    

       dp[i][j-1] + add

3）1：abcds   2：abcdt

        dp[i - 1][j -1] + replace

4）abcde   abcde

         dp[i - 1][j -1]

public static int minCost1(String str1, String str2, int ic, int dc, int rc){
    if (str1 == null || str2 == null){
        return 0;
    }
    char[] chs1 = str1.toCharArray();
    char[] chs2 = str2.toCharArray();
    int row = chs1.length + 1;
    int col = chs2.length + 1;
    int[][] dp = new int[row][col];
    for (int i = 1; i < row; i++){
        dp[i][0] = dc * i;
    }
    for (int i = 1; i < row; i++){
        for (int j = 1; i < col; j++){
            if(chs1[i - 1] == chs2[j - 1]){
                dp[i][j] = dp[i -1][j - 1];
            }else{
                dp[i][j] = dp[i - 1][j - 1] + rc;
            }
            dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
        }
    }
    return dp[row - 1][col - 1];
}

题目7：给一个全是小写字母的字符串，删除多余字符，每种字符保留一个，并让字典序最小

建立词频表，选acs码最小的保留

public static String romove(String str){
    if(str == null || str.length() < 2){
        return str;
    }
    int[] map = new int[256];
    for(int i = 0; i < str.length(); i++){
        map[str.charAt(i)]++;
    }
    int minACSIndex = 0;
    for(int i = 0; i < str.length(); i++){
        if(--map[str.charAt(i)] == 0){
            break;
        }else{
            minACSIndex = str.charAt(minACSIndex) > str.charAt(i) ? i : minACSIndex;
        }
    }
    return String.valueOf(str.charAt(minACSIndex)) + remove(str.substring(minACSIndex + 1).replaceAll(String.valueOf(str.charAt(minACSIndex)),""));
}

题目8：a,b,c,d,e,f,……，z

1）{a}

2）{b}

……

26）{z}

27）{ab}

……

{az}

{bc}

给一个子序列，返回第几个

思路：写两个函数f和g

f(N)长度为N的子序列有多少个 g(char,len)以char开头的长度为len的子序列有多少个

//必须以i号字符开头、长度为len的子序列有多少个
public static int g(int i, int len){
    int sum = 0;
    if(len == 1){
        return 1;
    }
    for(int j = i + 1; j <= 26; j++){
        sum += g(j, len - 1);
    }
    return sum;
}

//长度为len的字符串有多少个
public static int f(int len){
    int sum = 0;
    for (int i = 1; i <= 26; i++){
        sum += g(i, len);
    }
    return sum;
}
public static int kth(String s){
    char[] str = s.toCharArray();
    int sum = 0;
    int len = str.length;
    for(int i = 1; i < len; i++){
        sum += f(i);
    }
    int first = str[0] - 'a' + 1;// 第一个字符
    for (int i = 1; i < first; i++){
        sum += g(i, len);
    }
    int pre = first;
    for(int i = 1; i < len; i++){
        int cur = str[i] - 'a' + 1;
        for(int j = pre + 1; j < cur; j++){
            sum += g(j, len - i);
        }
        pre = cur;
    }
    return sum + 1;
}