[编程题]找到字符串的最长无重复字符子串
用LinkedList的removeFirst()调整list的长度并记录
例如:{2,3,4,3}遇到重复元素，remove之后是{4,3}
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
LinkedList<Integer> list = new LinkedList<>();
int p=0, ans=0;
for(int i=0;i<arr.length;i++){
if(list.contains(arr[i])){
int j=list.indexOf(arr[i]);
while (j-->=0){
list.removeFirst();
}
}
list.add(arr[i]);
ans=Math.max(ans,list.size());
}
return ans;
}
}
发表于 2020-09-14 14:57:48
回复(5)
这个题的双指针用起来简单而优雅。可以用哈希集或哈希表来去重：
哈希集的实现稍微慢一点，因为哈希集没有计数功能，所以碰到重复元素后去重时需要左指针一步步前进：
public int lengthOfLongestSubstring(String s) {
char[] a = s.toCharArray();
int n = a.length;
if(n < 2) return n;
int res = 0;
HashSet set = new HashSet();
int i = 0, j = 0;
while (j < n) {
if (!set.contains(a[j])) {
set.add(a[j]);
j++;
} else {
set.remove(a[i]);
i++;
}
res = Math.max(res, set.size());
}
return res;
} 用哈希表实现更快，因为哈希表可以用键来存储数组元素，用值来存储数组元素的位置，这样碰到重复元素后左指针的移动可以一步到位，不需要一步步走。
public int lengthOfLongestSubstring(String s) {
char[] a = s.toCharArray();
int n = a.length;
if(n < 2) return n;
int res = 0;
HashMap<Character,Integer> map= new HashMap<>();
int i = 0, j = 0;
while (j < n) {
if (!map.containsKey(a[j])) {
map.put(a[j], j);
} else {
i = Math.max(i, map.get(a[j])+1);
map.put(a[j], j);
}
res = Math.max(res, j - i + 1);
j++;
}
return res;
}
发表于 2020-09-09 17:17:57
回复(6)
//之前创建了set 显示超时，改用位子标记 部分查找 不增加变量的存储
int maxLength(vector<int>& arr) {
int res(0);int counter(0);
for(auto i = arr.begin(); i != arr.end(); i++)
{
counter = 0;
for(auto t = i; t != arr.end(); t++)
{
if(find(i,t,*t) != t)
{
res = max(res, counter);
break;
}
else
{
counter++;
}
}
res = max(res, counter);
}
return res;
}
发表于 2020-12-21 10:21:48
回复(0)
PYTHON solution:
class Solution: def maxLength(self , arr ): # write code here res=[] length=0 for i in arr: if i not in res: res+=[i] else: res = res[res.index(i)+1:] + [i] if length<len(res): length= len(res) return length
发表于 2020-11-29 23:29:03
回复(4)
滑动窗口
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
int len = arr.length;
int left = 0;
int right = 0;
int res = 0;
boolean valid = false; // 表示窗口是否满足无重复元素
HashMap<Integer, Integer> map = new HashMap<>(); // 窗口中各个数字出现的情况，key：数字，value：该数出现的次数
while (right < len) {
int add = arr[right];
right++;
map.put(add, map.getOrDefault(add, 0) + 1);
if (map.get(add) == 1) { // 判断该数是否只出现一次
valid = true;
} else {
valid = false;
}
// 缩小窗口
while (!valid) {
int remove = arr[left];
map.put(remove, map.get(remove) - 1);
if (map.get(remove) == 1){ // 如果该数出现的次数减为1则窗口满足条件
valid = true;
}
left++;
}
// 更新结果
res = Math.max(res, right - left);
}
return res;
}
}
发表于 2021-02-22 23:17:30
回复(0)
/**
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*/
int maxLength(int* arr, int arrLen ) {
int n[100000] = {0};
int left = 0;
int right = 0;
int res = 0;
while (right < arrLen) {
if (n[arr[right]] > 0) {
n[arr[left]] = 0;
left++;
} else {
n[arr[right]] = 1;
res = res > right - left + 1 ? res : right - left + 1;
right++;
}
}
return res;
}
发表于 2021-02-21 15:36:32
回复(0)
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
std::map<int, int> tmp;
int result = 0;
for (int i = 0; i < arr.size();) {
auto iter = tmp.find(arr[i]);
if (iter != tmp.end()) {
i = iter->second + 1;
if (tmp.size() > result) {
result = tmp.size();
}
tmp.clear();
} else {
tmp.insert(std::make_pair(arr[i], i));
++i;
}
}
return result;
}
};
面试小米的时候，面试官出的题目。
朴素的方法，就是拿个临时的空间去记录串，向后遍历arr，查看值是否在串中出现。
出现了就比较最大值和临时空间里的数据谁大，然后清空临时空间，下标跑回去；没有出现就把值扔到临时空间里。
我考虑优化的点，就是不想让下标往回跑太多，跑太多实际上是无意义的，正好跑到重复值的后一个下标就好。所以这里很蛋疼的用了个map来记录值和下标。
注：STL可能会影响性能，主要是写的省事，习惯用STL了，又没有什么打比赛的需求。（逃
发表于 2021-01-15 20:24:16
回复(2)
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
map<int, int> num_index; //检查是否越界了的map工具
map<int, int>::iterator iter; //迭代器
int before = 0;
int after = 1;
int max_len = 1;
int arr_len = arr.size();
num_index[arr[0]] = 0;
int temp_len = 1;
int next_before = 0;
//下面开始在线的动态测量过程
for (after = 1; after < arr_len; after++)
{
if (before > arr_len - max_len) //设置一个判断是否可以直接终止的情况，为了节省时间
break;
iter = num_index.find(arr[after]); //判断是否在当前的map中
if (iter == num_index.end()) //当前集合没有该键值对
{
num_index[arr[after]] = after; //匹配该值和所在的位置索引值
temp_len++;
}
else //当前集合存在该键值对，重复了
{
next_before = iter->second;
if (temp_len > max_len) //更新最大长度值
{
max_len = temp_len;
}
temp_len = after - next_before;
if (next_before - before < after - next_before) //map删除前面的，保留后面的，最后再加上一个after
{
for (int i = before; i <= next_before; i++) //一个一个删除前面的部分
{
num_index.erase(arr[i]);
}
num_index[arr[after]] = after;
}
else //直接清空map，从next_before往后一个一个加进来，加到after
{
num_index.clear();
for (int i = next_before + 1; i <= after; i++)
{
num_index[arr[i]] = i;
}
}
before = next_before + 1;
}
}
if (temp_len > max_len)
max_len = temp_len;
return max_len;
}
};
发表于 2020-12-16 21:10:44
回复(0)
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
if(arr.length<2) return arr.length;
// write code here
Stack<Integer> stack = new Stack<>();
int res_lat = 0;
for(int i=0;i<arr.length;i++){
int pre =stack.search(arr[i]);
int lat =stack.size()-stack.search(arr[i])+1;
if(pre==-1){
stack.push(arr[i]);
res_lat=res_lat>stack.size()?res_lat:stack.size();
}else{
res_lat=res_lat>stack.size()?res_lat:stack.size();
for(int j=0;j<lat;j++){
stack.remove(0);
}
stack.push(arr[i]);
}
}
return res_lat;
}
}
发表于 2020-09-23 16:01:34
回复(0)
import java.util.*;
public class Solution {
/**
* 有点类似滑动窗口，从左到右遍历，遇到重复的，找到重复的索引，左指针++
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
// write code here
int start = 0;
int end = -1;
int maxLen = 0;
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i]) && map.get(arr[i]) >= start) {
start = map.get(arr[i]) + 1;
}
map.put(arr[i],i);
end++;
if (end-start+1>maxLen){
maxLen = end-start+1;
}
}
return maxLen;
}
}
发表于 2020-09-19 15:11:00
回复(0)
可以使用 c 语言的 hashtable 进行解题。hashtable的初始值是 0 ， 所以我们在坐标计算时 让i多加 1.
思路是这样的，由于hashtable可以轻松的查找到 对应key的值的大小，我们把目标数组的成员作为hashtable的key存入 hashtable，并将 数组成员在数组的位置 +1 作为key值存入。当遇到hashtable中已存在的 数组中的数，则令 start 角标 位 这个数 之前 在 hashtable 中的key值。用 i+1 - start 来判断不重复子串的长度。流程如下图：
代码段：
/**
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*/
int maxLength(int* arr, int arrLen ) {
// write code here
int hashTable[100000] = {0};
int maxlen = 1;
int start = 0;
for(int i = 0; i < arrLen; i ++)
{
if(hashTable[arr[i]] > start)
{
//printf("%d\n",len);
start = hashTable[arr[i]];
}
hashTable[arr[i]] = i+1;
if(maxlen < i - start +1)
{
maxlen = i-start+1;
//printf("max %d\n",maxlen)
}
}
return maxlen;
}
发表于 2020-09-22 10:52:11
回复(0)
class Solution {
public:
int maxLength(vector<int>& arr) {
// write code here
int m[40000] = {0};//用map更好
unsigned int ans = 1, l = 0;//l记录重复位置
arr.push_back(arr[arr.size() - 1]);//尾部添加一个重复数据使其必然触发(3)条件
for(int i = 0; i < arr.size(); ++i){
if(m[arr[i]]){// （3）
if(ans < i - l)
ans = i - l;
if(m[arr[i]] > l)//只需在重复时记录下重复数据的位置
l = m[arr[i]];
}
m[arr[i]] = i + 1;
}
return ans;
}
};
发表于 2020-09-17 11:36:42
回复(3)
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
int l = 0, r = 0, ans = 0;;
set<int> s;
while (r < arr.size()) {
if (!s.count(arr[r])) {
s.insert(arr[r++]);
} else{
s.erase(arr[l++]);
}
ans = ans > s.size() ? ans : s.size();
}
return ans;
}
};
发表于 2020-09-15 22:05:59
回复(1)
import java.util.*;
import java.lang.*;
//从0开始遍历，将遍历的结果放入hashmap，当发生hash冲突时，将遍历的位置向前移动
//到相同数字的地方，并且把当前map的size和maxSize比较
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
// write code here
//定义一个hashmap，key为第i位数字，value为i
Map<Integer,Integer> map=new LinkedHashMap<>();
int maxSize=0;
int i=0;
while(i<arr.length){
//发生hash冲突说明前面已经有相同的数了，那个将i移动到前面那个数的位置
if(map.containsKey(arr[i])){
maxSize=map.size()<maxSize?maxSize:map.size();
i=map.get(arr[i]);
map.clear();
}else{
map.put(arr[i],i);
}
i++;
}
maxSize=map.size()<maxSize?maxSize:map.size();
return maxSize;
}
}
发表于 2020-09-13 21:11:24
回复(1)
# 滑动窗口
class Solution:
def maxLength(self , arr ):
# write code here
ans, j = 0, 0
dst = {}
for i, num in enumerate(arr):
if num in dst:
j = max(j, dst[num])
ans = max(ans, i+1-j)
dst[num] = i+1
return ans
# 堆栈
class Solution:
def maxLength(self , arr ):
# write code here
stack = []
ans = 0
for num in arr:
while num in stack:
stack.pop(0)
stack.append(num)
ans = max(ans, len(stack))
return ans
编辑于 2021-03-01 19:56:32
回复(0)
Python双指针，利用in语法代替map
class Solution:
def maxLength(self , arr ):
if len(arr) <= 1:
return len(arr)
# write code here
fast,slow = 1,0
maxLen = 0
while fast < len(arr):
if arr[fast] not in arr[slow:fast]:
fast += 1
else:
slow += 1
maxLen = max(maxLen,fast-slow)
return maxLen
def maxLength(self , arr ):
if len(arr) <= 1:
return len(arr)
# write code here
fast,slow = 1,0
maxLen = 0
while fast < len(arr):
if arr[fast] not in arr[slow:fast]:
fast += 1
else:
slow += 1
maxLen = max(maxLen,fast-slow)
return maxLen
发表于 2021-02-28 23:48:27
回复(0)
代码采用双指针思路，c语言正常运行，python运行超时？
/** C语言版本
*
* @param arr int整型一维数组 the array
* @param arrLen int arr数组长度
* @return int整型
*/
int maxLength(int* arr, int arrLen ) {
int first = 0;
int end = 1;
int max_len = 0;
int prt = first;
if(arrLen <= 1)
{
return arrLen;
}
while(end < arrLen)
{
for(prt = first;prt<end;prt++)
{
if(arr[end] == arr[prt])
{
if(end - first > max_len)
{
max_len = end - first;
}
first = prt + 1;
break;
}
}
end += 1;
}
if(end - first > max_len)
{
max_len = end - first;
}
return max_len;
// write code here
} # python版本，运行超时 # # @param arr int整型一维数组 the array # @return int整型 # class Solution: def maxLength(self , arr ): if len(arr) <= 1: return len(arr) first = 0 end = 1 max_len = 0 while end < len(arr): prt = first for temp in arr[first:end]: if arr[end] == temp: if end - first > max_len: max_len = end - first first = prt + 1 break prt += 1 end += 1 if end - first > max_len: max_len = end - first return max_len # write code hereC语言版本只用了64ms ，python版本虽然慢但为啥效率差别这么大，无法通过？
发表于 2021-02-23 10:19:13
回复(0)
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
set<int> unique;
int l=0,r=0;
// int i=0;
int res=0;
while(r<arr.size())
{
if(!unique.count(arr[r]))
{
unique.insert(arr[r]);
r++;
}
else
{
unique.erase(arr[l]); //这里注意一下，当上面的if首次判断不通过时，这下面的else很可能会被多次执行
l++; //直到将与当前arr[r]相同的值删除为止
}
res=res>unique.size()?res:unique.size();
}
return res;
}
};
编辑于 2021-02-11 15:39:51
回复(0)
问题信息
难度：
96条回答
218收藏
4869浏览
通过挑战的用户
查看代码-
2021-03-05 00:57:08 -
2021-03-05 00:56:11
-
2021-03-05 00:54:08 -
2021-03-05 00:42:19 -
2021-03-05 00:33:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
