题解 | #牛牛的协作#
牛牛的协作
https://www.nowcoder.com/practice/ae483ed148b34e14bec1451b3317984d
考察知识点:数组,遍历
解题分析: 1、这道题的解法可以是遍历出当前字符串中没有出现重复字符的最长子串,那么可以通过遍历每个字符s[i]和当前字符往前的所有的所有字符s[j]做对比,当发现出现一样的字符,那么从第一个字符,到字符s[i-1]是一个没有重复字符的子串,记录到max_len中
2、但是这种情况找到的子串未必一定是最长子串,所有我们还需要再次往下找,所有在第1点的基础上,我首先便利s[j]的时候,需要倒序便利,拿到一个离s[i]最近的且和s[i]相同元素的位置index,我们标记的和当前s[i]一样的字符s[j]的下一个元素s[j+1]到index中,因为从s[j+1]到当前的s[i]是新的子串,没重复字符的。之后我们便利s[j]时,index就是s[j]的最小位置,,s[i]是最大位置,再次寻找新的子串。
3、当第2点中再次发现新的子串时,从index到s[i]就是我们找到的新的子串的长度,将这个长度和我们记录的max_len做比较,如果max_len小于,就将更新max_len的值
4、但是有一种情况是,便利完整个字符串,都发现不了相同的字符,这个时候退出的遍历,max_len是0,这个时候就需要判断字符串的长度距离最近一个更新的index的位置,和当前的max_len谁更大了
编程语言:C
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ int lengthOfLongestContinuousTasks(char* s ) { int len_s = strlen(s); int index = 0, max_len = 0; for (int i = 0; i < len_s; i++) { // 获取一个需要被判断的元素s[i] for (int j = index; j < i; j++) { // 倒序的方法遍历s[j]和s[i]比较 if (s[i] == s[j]) { // 相同的话,就是寻找到了距离s[i]距离最近的相同元素 if ((i - index) > max_len) max_len = i - index; // 将最长的字符串长度赋值给max_len index = j+1; // 更新index的位置,标记新子串的开始位置 break; } } } if ((len_s - index) > max_len) // 处理遍历完字符串之后,没有来得及刷新max_len的情况 max_len = len_s - index; return max_len; }
面试高频TOP202解析 文章被收录于专栏
采用Java,C,Python等方法去解答面试高频TOP202题目,