NC719 牛牛与字符串3（视频讲解+4种语言代码）

- 题目描述：

- 题目链接：

https://www.nowcoder.com/practice/ff33127a91934d2da054f75c7047f6e5?tpId=196&&tqId=37707&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking
- 设计思想：

-视频讲解链接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
};