链接:https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
解题思路
最小表示法
关于最小表示法详细介绍可看链接 最小表示法详解
暴力求解
暴力枚举字符串每一个元素,判断元素大小
这里有个小技巧,当每次都判断之后字符字典序大小时,很显然会超时,但是限制一下每次判断之后字符的长度就不会了,限制长度这里设为20
最小表示法
- char * lastSubstring(char * s){
- int n = strlen(s);
-
- //最小表示法
- int k = 0, i = 0, j = 1;
- while (k < n && i+k < n && j+k < n) {
- if (s[i + k] == s[j + k]) {
- k++;
- } else {
- if(s[i + k] >= s[j + k])
- {
- j = j + k + 1;
- }else
- {
- i = i + k + 1;
- }
- if (i == j) i++;
- k = 0;
- }
- }
- i = fmin(i, j);
-
- return s+i;
- }
-
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
暴力求解
- char * lastSubstring(char * s){
- int len = strlen(s);
- int des = 0;
- char maxCh = s[0];
- for (int i = 1; i < len; i++) {//枚举每一个元素
- if (s[i] > maxCh) {//保存最大值
- maxCh = s[i];
- des = i;
- } else if (s[i] == maxCh) {//当元素等于最大元素时,判断之后字符字典序大小,保存字典序大的下标
- des = (strncmp(s+des, s+i, 20) >= 0) ? des : i;
- }
- }
-
- return s+des;
- }
-
-
- 作者:xun-ge-v
- 链接:https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。