[数据结构与算法]第298场力扣周赛个人题解

兼具大小写的最好英文字母（3分）

题目链接：力扣：5242.兼具大小写的最好英文字母

解题思路1：
统计字符串中出现的每一个字符(利用桶排序的思想)，然后按照26个英文字母表从后往前的顺序判断其(大小写)是否都在数组中出现，若都出现直接返回该字母的大写(以字符串的形式)，若26个英文字母都不符合条件，那么返回空字符串。

代码如下：

class Solution {
    public String greatestLetter(String s) {
        int arr[] = new int['z' + 1];
        //统计字符串中出现的每一个字符
        for(int i = 0; i < s.length(); i++){
            arr[s.charAt(i)] = 1;
        }
        //从后往前寻找符合条件的字符
        for(int i = 'Z'; i >= 'A'; i--){
            if(arr[i] == 1 && arr[i + 32] == 1)
            return (char)i + "";
        }
        return "";
    }
}

解题思路2：
上面的方法我们使用一个数组来记录出现的字符，空间复杂度为O(n)。这里讲解一种位运算的方法，将空间复杂度降为O(1)。 下面字母的ASCII码为 A:65 Z:90 a:97 z:122 ，122-65+1=58 因此可以用一个long类型的整形mask来记录有没有出现过某个字母。
代码如下：

class Solution {
    public String greatestLetter(String s) {
        long mask = 0;
        int l = s.length();
        //将字符串中出现过的字符全部标记
        for(int i = 0; i < l; i++){
            mask |= 1L << (s.charAt(i) - 'A');
        }
        //从后往前寻找大写和小写同时出现的字符
        //25对应'Z'，0对应'A'
        for(int i = 25; i >= 0; i--){
            if((mask >> i & 1) == 1 && (mask >> (i + 32) & 1) == 1){
                return (char)(i+65) + "";
            }
        }
        return "";
    }
}

个位数字为K的整数之和（4分）

题目链接：力扣：5218.个位数字为K的整数之和

解题思路：

1. 当num == 0 时，很显然返回0。
2. 当k > num时，因为多重集中的数个位数只能是k，只看个位数都不满足条件，所以这样的多重集一定不存在。
3. 进行完以上两种特殊情况判断之后，就来到这道题的核心部分。假设存在这样的多重集使得多重集中的整数之和等于num，我们可以将num看成 ：10*x + y(y是10以内的数字)，这里的x我们可以不用管(题目只要求多重集中的数个位数必须为k，其它位数都不加限制，10*x加在多重集中任何一个数上都可以)，因此这道题的条件就可以转换为：多重集中整数之和的个位数必须是y(num的个位数)。又因为只有多重集中每一个整数的个位数(只能是k)影响整数之和的个位数，这道题的条件可以再次转换成：(多重集元素个数*k)%10 == num % 10

代码如下：

class Solution {
    public int minimumNumbers(int num, int k) {
       if(num == 0) return 0;
       if(num < k) return -1;
       for(int i = 1; i <= 10; i++){
           if(num % 10 == (k*i)%10 && k*i <= num)
           return i;
       }
        return -1;
    }
}

小于K的最长二进制子序列(5分)

题目链接：力扣：6099.小于K的最长二进制子序列

解题思路：

1. 将所有的0选上一定符合题意的，并且选0一定优于选1。
   原因：将一个二进制数中任意一个0换成1只会让该二进制数变得更大。

2. 我们可以将所有0选上之后利用贪心，将1插入，插入时应该从后往前插入，因为前面的1对二进制数大小的影响大于后面的数。

例：s = “1001010”, k = 5

1. 将0全部选上，“0000”。
2. 从后往前将1插入：
   （1）“00010”，此时该二进制数的值为2 ，仍然小于5，需要继续插入。
   （2）“001010”,此时该二进制数的值为10，大于5，不符合题意。到这里就不在需要插入了，因为插入前面的1只会让该二进制数变得更大。

代码如下：

class Solution {
    public int longestSubsequence(String s, int k) {
        int l = s.length();
        int rnt = 0,tmp = 0,flag = 0;
        long sum = 0;
        char cur;
        for(int i = l - 1; i >=0; i--){
            cur = s.charAt(i);
            if(cur == '0'){
                rnt++;
                tmp++;
            }
            else if(flag == 0){
                if(sum + (1L<<tmp) > k)
                    flag = 1;
                else{
                    sum += (1L<<tmp);
                    rnt++;
                    tmp++;
                }
            }
        }
        return rnt;
    }
}

卖木头块(6分)

题目链接：力扣：5254卖木头块

解题思路：
该题可以使用线性dp的方法。首先我们定义一个数组arr，arr[ i ][ j ]就是高为i宽为j的木块可以卖的价格。一个木块儿切割之后一定是会变小的，那么我们定义一个dp数组，dp[ i ][ j ]就是高为i，宽为j的木块儿最高能卖的价格，我们可以得到以下关系：

dp[i][j] = arr[i][j];
for(int k = 1; k < i; k++) dp[i][j] = Math.max(dp[i][j],dp[i-k][j] + dp[k][j]);//水平切割
for(int k = 1; k < j; k++) dp[i][j] = Math.max(dp[i][j],dp[i][j-k] + dp[i][k]);//垂直切割

此时的dp[ i ][ j ]一定是可以卖到的最高价格。
代码如下：

class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        int [][]arr = new int[m+1][n+1];
        for (int p[] : prices) arr[p[0]][p[1]] = p[2];
        long dp[][] = new long[m + 1][n + 1];
        for(int i = 1; i <= m ; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = arr[i][j];
                for(int k = 1; k < i; k++) dp[i][j] = Math.max(dp[i][j],dp[i-k][j] + dp[k][j]);
                for(int k = 1; k < j; k++) dp[i][j] = Math.max(dp[i][j],dp[i][j-k] + dp[i][k]);
            }
        }
        return dp[m][n];
    }
}

优化

1. 在切割木块时，由于对称性，我们可以减少一半循环。
2. 因为我们是从小到大的计算数组dp的值，我们可以不用定义dp数组，直接使用arr数组就行。

优化后代码如下：

class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        long [][]arr = new long[m+1][n+1];
        for (int p[] : prices) arr[p[0]][p[1]] = p[2];
        for(int i = 1; i <= m ; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= i/2; k++) arr[i][j] = Math.max(arr[i][j],arr[i-k][j] + arr[k][j]);//水平切割
                for(int k = 1; k <= j/2; k++) arr[i][j] = Math.max(arr[i][j],arr[i][j-k] + arr[i][k]);//垂直切割
            }
        }
        return arr[m][n];
    }
}