兼具大小写的最好英文字母（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的整数之和
解题思路：
- 当
num == 0时，很显然返回0。 - 当
k > num时，因为多重集中的数个位数只能是k，只看个位数都不满足条件，所以这样的多重集一定不存在。 - 进行完以上两种特殊情况判断之后，就来到这道题的核心部分。假设存在这样的多重集使得多重集中的整数之和等于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的最长二进制子序列
解题思路：
- 将所有的0选上一定符合题意的，并且选0一定优于选1。
原因：将一个二进制数中任意一个0换成1只会让该二进制数变得更大。 - 我们可以将所有0选上之后利用贪心，将1插入，插入时应该从后往前插入，因为前面的1对二进制数大小的影响大于后面的数。
例：s = “1001010”, k = 5
- 将0全部选上，“0000”。
- 从后往前将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]; } }
优化
- 在切割木块时，由于对称性，我们可以减少一半循环。
- 因为我们是从小到大的计算数组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]; } }
