当前位置：首页 > java >正文

【力扣】3403. 从盒子中找出字典序最大的字符串 I

java 2025/6/29 1:41:35

在这里插入图片描述

解法一：

class Solution {public String answerString(String word, int numFriends) {//对字符的划分，word长度为n，共有n+1个位置可以插入，但是要求被分为非空字符串，所以插入的位置最多为n-1。int n = word.length();//字符串长度//字符数组存储分解下的字符串//分解个数等于长度，每个一个字母if (numFriends == 1){return word;}String max = "";//可以取出来的时候直接比较！，不必浪费空间去存储！//而这道题的思路并不是让我直接全部取出来比较//而是考虑一个问题：以某个位置i为起点可以截取的的字符串，其长度越大，字典序也就越大//根据n和numfriends,可以得到这个字符串在这个情况下可以截取的最大长度，直接将该长度拿出来即可！！！！！//而这个最大长度应该是min(n-numfriends+1,n-i)for (int i = 0; i < n; i++) {String str = word.substring(i,Math.min(n+i-numFriends+1,n));max = max.compareTo(str) >=0 ? max : str ;}return max;}
}

总结：在这里我犯了一个错误，关于最大长度min(n-numfriends+1,n-i)，确实是最大长度，但是从第i个位置开始的最大长度，那么我还应该加上i,所以代码中是min(n+i-numFriends+1,n)，n-i:当前长度到字符串末尾还剩的长度，有可能不足可以取的最大长度
反思：善于从题目中提取信息后转化为数学问题（而这道题的思路并不是让我直接全部取出来比较，而是考虑一个问题：以某个位置i为起点可以截取的的字符串，其长度越大，字典序也就越大，所以仅需将从某个位置开始的可以取的最大长度取出来比较即可）

解法二：双指针

在这里插入图片描述

class Solution {public String lastSubstring(String s) {int i = 0, j = 1, n = s.length();while (j < n) {int k = 0;while (j + k < n && s.charAt(i + k) == s.charAt(j + k)) {k++;}if (j + k < n && s.charAt(i + k) < s.charAt(j + k)) {int t = i;i = j;j = Math.max(j + 1, t + k + 1);} else {j = j + k + 1;}}return s.substring(i);}public String answerString(String word, int numFriends) {if (numFriends == 1) {return word;}String last = lastSubstring(word);int n = word.length(), m = last.length();return last.substring(0, Math.min(m, n - numFriends + 1));}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-lexicographically-largest-string-from-the-box-i/solutions/3685906/cong-he-zi-zhong-zhao-chu-zi-dian-xu-zui-eg0v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。