当前位置：首页 > news >正文

9.5LeetCode

news 2025/7/14 14:58:33

80.删除有序数组重复项II

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

思路:和删除有序数组的重复项1很相似，1是不允许有两个一样的元素，而2是不允许有三个一样的元素，这就需要额外定义一个len来管理长度问题了，如果出现两个以上相等的元素，便不会进入if语句中，不会更改nums数组。

class Solution {
public:int work(vector<int>& nums){int len=0;for(int i=0;i<nums.size();i++){if(len<2||nums[len-2]!=nums[i]){nums[len++]=nums[i];}}return len;}int removeDuplicates(vector<int>& nums) {int res=work(nums);return res;}
};

189.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

这个是LeetCode的官方解答，是通过额外的数组来进行轮转的，首先定义一个额外数组，然后将遍历原数组将元素放到正确的位置上，最后用vector中的assign函数，将额外数组的元素赋值到nums中。

class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size();vector<int> newArr(n);for(int i=0;i<n;i++){newArr[(i+k)%n]=nums[i];    //这是通过额外数组将每个元素放到正确位置}nums.assign(newArr.begin(),newArr.end());}
};

二、小米笔试

1.堆排序的最好，最坏，平均复杂度排序

最好==最坏==平均复杂度

2.HTTP的持久化连接

HTTP 的持久化连接（也称为 HTTP keep-alive）是一种在单个 TCP 连接上发送和接收多个 HTTP 请求和响应的技术。

一、作用与优势减少连接建立的开销：在没有持久化连接的情况下，每次 HTTP 请求都需要建立一个新的 TCP 连接，而建立连接的过程包括三次握手等操作，会消耗一定的时间和资源。使用持久化连接可以避免频繁地建立和关闭连接，从而减少了连接建立的时间开销。提高性能：由于减少了连接建立的次数，整体的传输效率得到提高。特别是对于需要发送多个请求的场景，如加载一个包含多个图片、脚本和样式表的网页，持久化连接可以显著提高页面加载速度。降低服务器负载：服务器不需要为每个请求都进行连接的建立和关闭操作，减少了服务器的资源消耗和处理负担，能够更好地处理大量并发请求。

二、工作原理连接建立：当客户端发起第一个 HTTP 请求时，会在请求头中包含一个支持持久化连接的标识，例如 “Connection: keep-alive”。如果服务器也支持持久化连接，它会在响应头中同样设置这个标识，表示同意建立持久化连接。此时，TCP 连接在完成第一个请求和响应后不会立即关闭，而是保持打开状态，以便后续的请求和响应可以复用这个连接。请求和响应复用连接：客户端可以在同一个连接上连续发送多个 HTTP 请求，每个请求之间不需要等待连接的建立。服务器接收到请求后，依次处理并返回响应，同样通过这个连接进行传输。连接关闭：持久化连接不会一直保持打开状态，有以下几种情况会导致连接关闭：客户端或服务器主动关闭连接：客户端可以在请求头中设置 “Connection: close” 来表明本次请求后关闭连接；服务器也可以在响应头中设置这个标识来通知客户端关闭连接。超时：如果在一定时间内没有任何请求或响应通过连接传输，连接可能会因为超时而被关闭。这个超时时间可以由服务器或客户端配置。错误情况：如果在连接上发生了网络错误或其他异常情况，连接可能会被关闭。

3.在首尾添加数据频繁的应用场景下，可以使用带有尾指针的单链表来实现

4.aaababcaabbc 这个字符串的next数组？

459.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

对于如何构建的前缀表要注意

class Solution {
public:void getNext(vector<int>& next,string& s){//前缀表int j=0;next[0]=0;for(int i=1;i<s.size();i++){while(j>0&&s[j]!=s[i]){j=next[j-1];}if(s[i]==s[j]){j++;}next[i]=j;}}bool repeatedSubstringPattern(string s) {vector<int> next(s.size()+1);getNext(next,s);int num=s.size();if(next[num-1]!=0&&num%(num-next[num-1])==0){return true;}return false;}
};