AQS

题目十一 使字符串平衡的最少删除次数

给你一个字符串 s ，它仅包含字符 ‘a’ 和 ‘b’ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = ‘b’ 的同时 s[j]= ‘a’ ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

class Solution12 {
    public int minimumDeletions(String s) {

        int t = 0;

        int length = s.length();

        //统计a数量
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == 'a'){
                t++;
            }
        }
        int ans = t;

        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == 'a'){
                t--;
            }else {
                t++;
            }
            ans =Math.min(ans,t);
        }
        return ans;
    }
}

使用前后缀分解法，由于结果必然是以a|b为分界线划分为前后缀，第一次遍历统计完s中a的值，当循环开始，单词作为后缀就需要删除所有的a，也就是删除值，划分后移一位，则判断新出现的字母是a还是b，如果是a则作为前缀，减少需要删除的值，如果出现的是b则说明b出现在前缀中，需要增加一次删除次数，直到遍历完字符串，记录过程中最小删除值即可

题目十二 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

class Solution13 {
    public String longestPalindrome(String s) {

        int l = s.length();
        String ans = "";
        int n = 0;

        boolean b = true;

        //中心扩散法
        if (l == 1){
            return s;
        }

        //复杂度为n
        for (int i = 0; i < l; i=(b)?i:++i,b=!b) {

            String ss = ""+s.charAt(i);
            int nn = 1;
            int p1 = i-1,p2 = i+1;

            if (b){
                ss = "";
                nn = 0;
                p1 = i;
                p2 = i+1;
            }

            for (; p1 >=0 && p2 < l ; p1--,p2++) {
                char c1 = s.charAt(p1);
                char c2 = s.charAt(p2);
                if (c1 == c2){
                    ss = c1 + ss + c2;
                    nn+=2;
                }else {
                    break;
                }
            }

            //更新记录
            if (nn > n){
                ans = ss;
                n = nn;
            }

        }

        return ans;
    }
}

使用中心扩散法的思想，回文串可能为奇数串也可能为偶数串，因此有从两个字母之间开始扩散和某个字母两边的字母开始扩散两种，如果是长度为1的字符串则默认回文返回其本身，时间复杂度因为O(n^2)

题目十三 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

class Solution15 {
    public int maxValue(int[][] grid) {

        int m = grid.length;

        int n = grid[0].length;

        int[][] v = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0){
                    v[i][j] = grid[0][0];
                    continue;
                }

                //边界条件只能通过单方向携带价值
                if (i == 0){
                    v[i][j] = grid[i][j] + v[i][j-1];
                    continue;
                }
                if (j == 0){
                    v[i][j] = grid[i][j] + v[i-1][j];
                    continue;
                }

                //选择上一步的携带价值的来源,附加本次携带价值
                v[i][j] = grid[i][j] + Math.max(v[i][j-1],v[i-1][j]);
            }
        }

        return v[m-1][n-1];
    }
}

使用动态规划思想可知，当前价值来源只能是i-1 或者是 j-1，因此我们只需要累计整个表中的价值，通过比较i-1，j-1价值的大小来选择累加到当前价值上，使用一张二位数组表来存放累计价值，通过m*n次循环遍历二位数组，当遍历到末尾时即可得到累计的最大价值的值

题目十四 得到 K 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 ‘W’ 要么是 ‘B’ ，表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

class Solution16 {
    public int minimumRecolors(String blocks, int k) {

        //使用滑块法，滑块为k长度，统计每次滑块中黑色块的数量，要求记录滑块中黑色块数量最多的情况
        int p1 = 0,p2 = k-1;

        int length = blocks.length();

        //k个中黑色块最多数量
        int bN = 0;

        //统计前k个值黑色数量
        for (int i = 0; i < k; i++) {
            char c = blocks.charAt(i);
            if (c == 'B'){
                bN++;
            }
        }

        int t = bN;

        //向后滑动
        for (;p2 < length-1;p1++,p2++){
            //左滑块移动时为黑则数量减少
            if (blocks.charAt(p1) == 'B'){
                t--;
            }

            //右滑块移动后为黑则数量增加
            if (blocks.charAt(p2+1) == 'B'){
                t++;
            }

            if (t > bN){
                bN = t;
            }
        }

        return k - bN;
    }
}

使用滑动窗口法，由于我们需要的结果为k个连续B字符串，因此只需要使用一个长度为k的滑块遍历字符串，当滑块中的B的数量最多时，则表明需要操作的次数越少。因此给出方案，先统计前k个字符串B的数量，左指针指向滑块首，右指针指向滑块右，如果左指针为B则表明下次移动会减少B的数量，如果右指针+1为B则表明会增加B的数量，统计滑块滑动过程中b数量的最大值，返回k-b最大值即为需要操作的最小次数

题目十五 使数组和能被 P 整除

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

class Solution17 {
    public int minSubarray(int[] nums, int p) {

        int p1,p2;

        //先查看总和能否被整除，然后尝试滑块内数的和,长度一个数的和,二个数的和，三个数的和...，当总和减去滑块内的和满足能被p整除即可

        long nSum = 0;

        for (int i = 0; i < nums.length; i++) {
            nSum += nums[i];
        }

        if (nSum < p){
            return -1;
        }

        //长度为0
        if (nSum % p == 0){
            return 0;
        }

        //长度为一
        for (int i = 0; i < nums.length; i++) {
            if ((nSum - nums[i]) % p == 0){
                return 1;
            }
        }

        int ll = nums.length - 1;

        //k为右边界
        for (int k = 0; k < ll; k++) {

            //滑块内和
            long sum = 0;
            //先统计0到k区间滑块内的和
            for (int i = 0; i <= k; i++) {
                sum+=nums[i];
            }
            if ((nSum - sum) % p == 0){
                return k + 1;
            }

            //滑块向后移动
            for(p1 = 1,p2 = 1+k;p2 < nums.length;p1++,p2++){
                //统计相对上一步更新的被删除的和
                sum -= nums[p1 - 1];
                sum += nums[p2];
                if ((nSum - sum) % p == 0){
                    return k + 1;
                }
            }
        }

        return -1;
    }
}

滑块法：先查看总和能否被整除，然后尝试滑块内数的和,长度一个数的和,二个数的和，三个数的和…，当总和减去滑块内的和满足能被p整除即可

题目十六 N 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

class Solution18 {
    public String convert(String s, int numRows) {
        //单个字符或指定为一行则直接返回
        if (s.length() == 1 || numRows == 1){
            return s;
        }

        StringBuffer[] ms = new StringBuffer[numRows];

        //初始化
        for (int i = 0; i < numRows; i++) {
            ms[i] = new StringBuffer();
        }

        int length = s.length();
        int k = 1,up = 1;
        ms[0].append(s.charAt(0));
        for (int i = 1; i < length; i++) {
            char c = s.charAt(i);
            //向下移动填入
            ms[k].append(c);

            //反向索引
            if (k == numRows - 1 || k == 0) {
                up = -up;
            }

            k+=up;
        }

        StringBuffer ss = new StringBuffer();

        for (StringBuffer m : ms) {
            ss.append(m);
        }

        return ss.toString();
    }
}

题目的关键在于使用合理的数据结构，由于变换后的格式符合变长的二维矩阵，因此我们使用StringBuffer来构建答案，找到移动的规律，也就是当遇到0或numRows-1时才进行移动方向变换

题目十七 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
    public int reverse(int x) {
        int ans = 0;

        if (x < 10 && x> -10){
            return x;
        }

        while (x != 0){
            //取末尾数字
            int i = x % 10;
            if (ans > Integer.MAX_VALUE/10 || i > 7 && ans == Integer.MAX_VALUE/10){
                return 0;
            }
            if (ans < Integer.MIN_VALUE/10 || i < -8 && ans == Integer.MIN_VALUE/10){
                return 0;
            }
            ans = ans *10 + i;
            x/=10;
        }

        return ans;
    }
}

本题的算法为：通过mod运算取末尾，添加到ans，ans乘10进位，通过div运算去x最高位，当x为0时结束循环

因为条件限制，还需要在大于2^31-1 和小于 -2^31的答案进行限制，由于int类型存储数量限制，需要进行提前判断

题目十八 赢得比赛需要的最少训练时长

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少 energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

class Solution20 {
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {

        //末状态体力一定为1最节约时间，由1开始逆推即可

        //经验从第一条开始，计算需要附加的值即可

        int tL = 1;

        for (int i = energy.length-1; i >=0 ; i--) {
            tL += energy[i];
        }

        int exp = 0;

        int nowExp = 0;

        for (int i = 0; i < experience.length; i++) {

            if (nowExp > experience[i]){
                //直接加上i的经验
                nowExp += experience[i];
            }else {
                //需要额外携带的经验
                exp += experience[i] + 1 - nowExp;
                //当前经验正好变为比i经验多1再加上i的经验
                nowExp = 2 * experience[i] + 1;
            }

        }

        int ans = 0;

        ans += initialEnergy >= tL ? 0 : tL - initialEnergy;
        ans += initialExperience >= exp ? 0 : exp - initialExperience;
        return ans;
    }
}

本题关键在于从结果逆推即可，体力只需要想到最后一定是正好用完只剩1时，即最后一次恰好大于对手体力值，一开始训练的时间最少。

经验则也从恰好大于1的角度考虑，只需要在不足时才进行累加，也就是计算一开始需要额外附带多少经验

题目十九 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

class Solution {
    public String longestCommonPrefix(String[] strs) {


        String ans = strs[0];

        if(strs.length==1){return ans;}

        int end =strs[0].length();

        for(int i=1;i<strs.length;i++){

            boolean s= true;

            int a =strs[i].length();
            int b=end;

            //依次与后续字符串比较
            for(int j=0;j<a&&j<b;j++){

                if(ans.charAt(j) != strs[i].charAt(j)){
                    s=false;
                    end=j;
                    break;
                }
            }

            if(s){
                if(b>a){ans=strs[i];end=a;}
            }


        }

        ans=ans.substring(0,end);

        return ans;

    }
}

选取第一个字符串为比较字符串，与后面的字符串不断取交即可，每次更新新的公共部分长度，用一个值end来维护即可

题目二十 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

class Solution {
    public int myAtoi(String s) {

        int lZ = -1;
        int k =0;
        int max =Integer.MAX_VALUE;
        int min =Integer.MIN_VALUE;
        int sN=-1;

        //记录前置空格
        for(int i =0;i<s.length();i++){
            char c = s.charAt(i);
            if(c==' '){
                sN++;
            }else{break;}
        }

        for(int i =sN+1;i<s.length();i++){

            char c = s.charAt(i);
            if(c>='0'&&c<='9'){
                if(lZ==-1){
                    lZ=0;
                }
                if(k > max/10 || k == max/10 && c >'7'){
                    k = max;break;
                }
                if(k < min /10 || k== min/10&& c > '8'){
                    k = min;break;
                }
                //1判断为负数，其它默认为正
                if(lZ==1){
                    k*=10;
                    k-=Character.getNumericValue(c);
                }else{
                    k*=10; k+=Character.getNumericValue(c);
                }
            }else if(c == '-'){
                //再次遇到符号位则退出循环
                if(lZ!=-1){
                    break;
                }else{
                    lZ=1;
                }
            }else if(c== '+'){
                //再次遇到符号位则退出循环
                if(lZ!=-1){
                    break;
                }else{
                    lZ=0;
                }
            }else{break;}//其它符号退出循环
        }

        return k;
    }
}

先用一个计数器sN来过滤空格，从sN+1开始判断符号位，如果存在符号位则用一个int值lZ来维护正负(0/1)，如果无符号为则lZ值为-1，每次将数字字符转换为整型值累加到k上并且k进位，判断是否满足取值边界。

如果第一次遇到符号位则更新符号标识lZ，否则退出循环，如果遇到其它非数字符号则也退出循环。

无符号位则检查到数字时则默认符号位为正（0）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com