- 题目描述:
- 题目链接:
-视频讲解链接B站视频讲解
- 复杂度分析:
- 代码:
c++版本:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回与该字符串循环同构所有字符串中字典序最小的起始位置 * @param s string字符串 代表题意中的s * @return int整型 */ int solve(string s) { // write code here int len = s.size(); int i = 0, j = 1, k = 0, t; while(i < len && j < len && k < len) { //如果前后两个字符相同,那么k++; t = s[(i + k) >= len ? i + k - len : i + k] - s[(j + k) >= len ? j + k - len : j + k]; if(!t) k++; else{ if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀 else j = j + k + 1; //后段较大 那么后段就往后 推一下 if(i == j) ++ j; //同一位置的话j移动 k = 0; //每次更新位置要k要从0开始控制 } } return (i < j ? i : j)+1; } };
Java版本:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回与该字符串循环同构所有字符串中字典序最小的起始位置 * @param s string字符串 代表题意中的s * @return int整型 */ public int solve (String s) { // write code here //i指向最小表示的位置,j作为比较指针 int len = s.length(); int i = 0, j = 1, k = 0, t; while(i < len && j < len && k < len) { //如果前后两个字符相同,那么k++; t = s.charAt((i + k) >= len ? i + k - len : i + k) - s.charAt((j + k) >= len ? j + k - len : j + k); if(t == 0) k++; else{ if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀 else j = j + k + 1; //后段较大 那么后段就往后 推一下 if(i == j) ++ j; //同一位置的话j移动 k = 0; //每次更新位置要k要从0开始控制 } } return (i < j ? i : j)+1; } }
Python版本:
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 返回与该字符串循环同构所有字符串中字典序最小的起始位置 # @param s string字符串 代表题意中的s # @return int整型 # class Solution: def solve(self , s ): # write code here #i指向最小表示的位置,j作为比较指针 n = len(s); i,j,k,t = 0,1,0,0 while(i < n and j < n and k < n): #如果前后两个字符相同,那么k++; t = ord(s[(i + k - n) if (i + k) >= n else i + k]) - ord(s[j + k - n if (j + k) >= n else j + k]) if(t == 0): k += 1 else: if(t > 0): i = i + k + 1#表明前段比后段大 那么前段肯定不能作为前缀 else: j = j + k + 1#后段较大 那么后段就往后 推一下 if(i == j): j += 1#同一位置的话j移动 k = 0#每次更新位置要k要从0开始控制 return (i if i < j else j) + 1
JavaScript版本:
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回与该字符串循环同构所有字符串中字典序最小的起始位置 * @param s string字符串 代表题意中的s * @return int整型 */ function solve( s ) { // write code here //i指向最小表示的位置,j作为比较指针 let len = s.length; let i = 0, j = 1, k = 0, t; while(i < len && j < len && k < len) { //如果前后两个字符相同,那么k++; t = s[(i + k) >= len ? i + k - len : i + k].charCodeAt() - s[(j + k) >= len ? j + k - len : j + k].charCodeAt(); if(!t) k++; else{ if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀 else j = j + k + 1; //后段较大 那么后段就往后 推一下 if(i == j) ++ j; //同一位置的话j移动 k = 0; //每次更新位置要k要从0开始控制 } } return (i < j ? i : j)+1; } module.exports = { solve : solve };