- 27.移除元素
- 26.删除排序数组中的重复项
- 283.移动零
- 844.比较含退格的字符串
- 977.有序数组的平方
- 344.反转字符串
- 剑指Offer05.替换空格
- 151.翻转字符串里的单词
- 206.反转链表
- 19.删除链表的倒数第N个节点
- 07.链表相交
- 142.环形链表II
- 15.三数之和
- 18.四数之和
- 5186区间内查询数字的频率
- 986区间列表的交集
- 11盛最多水的容器
class Solution {
public:
// 双指针求解
int removeElement(vector<int>& nums, int val) {
int slowIndex{},fastIndex{};
int n = nums.size();
int count{};
for(;fastIndex < n;++fastIndex){
// 当快指针数据不是val时进行数据交换、慢指针右移
if(nums[fastIndex] != val){
count++;
swap(nums[slowIndex++],nums[fastIndex]);
}
}
return count;
}
};
class Solution {
public:
// 双指针求解
int removeDuplicates(vector<int>& nums) {
int slowIndex{},fastIndex{1},count{};
for(;fastIndex < nums.size();++fastIndex){
// 当遇到非重复项时，直接赋值，慢指针右移
if(nums[fastIndex] != nums[slowIndex]){
nums[slowIndex+1] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex+1;
}
};
class Solution {
public:
// 双指针求解
void moveZeroes(vector<int>& nums) {
int slowIndex{},fastIndex{};
int n = nums.size();
for(;fastIndex < n;++fastIndex){
// 遇到非0值，数据交换、慢指针右移
if(nums[fastIndex]){
swap(nums[slowIndex++],nums[fastIndex]);
}
}
}
};
class Solution {
public:
bool backspaceCompare(string s, string t) {
int nS = s.size();
int nT = t.size();
int indexS = nS -1;
int indexT = nT -1;
// 从后往前判断
while(indexS >= 0 || indexT >= 0){
int countS{};
int countT{};
// 遇到非#字符直接退出、否则处理#字符
while(indexS >= 0){
if(s[indexS] == '#'){
countS++;
indexS--;
}else if(countS > 0){
indexS--;
countS--;
}else{
break;
}
}
// 遇到非#字符直接退出、否则处理#字符
while(indexT >= 0){
if(t[indexT] == '#'){
countT++;
indexT--;
}else if(countT > 0){
indexT--;
countT--;
}else{
break;
}
}
// 当两个下标都大于0，判断当前字符是否相等
if(indexS >= 0 && indexT >=0){
if(s[indexS] != t[indexT]) return false;
}
// 如果有一个下标大于0，直接返回false（说明字符长度不同了）
else if(indexS >= 0 || indexT >=0) return false;
// 下标前移，接续判断下一个字符
--indexS;
--indexT;
}
return true;
}
};
class Solution {
public:
// 双指针求解
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
int slowIndex{};
int fastIndex = n-1;
vector<int> ans(n);
int index = n-1;
while(slowIndex <= fastIndex){
// 判断取大值、从后向前赋值
if(abs(nums[slowIndex]) >= abs(nums[fastIndex])){
ans[index--] = nums[slowIndex]*nums[slowIndex];
slowIndex++;
}else{
ans[index--] = nums[fastIndex]*nums[fastIndex];
fastIndex--;
}
}
return ans;
}
};
class Solution {
public:
// 通过双指针交换字符
void reverseString(vector<char>& s) {
int n = s.size();
for(int i{},j = n-1;i<n/2;i++,j--){
swap(s[i],s[j]);
}
}
};
class Solution {
public:
string replaceSpace(string s) {
int spaceCount{};
// 先计算空格数量
for(char c : s){
if(c == ' ') spaceCount++;
}
// 从新分配替换后的字符串长度
int n = s.size();
s.resize(n+spaceCount*2);
// 然后从后向前赋值，遇到空格替换为“%20”
for(int i = s.size() -1,j = n-1;i>=0;--i){
if(s[j] != ' '){
s[i] = s[j--];
continue;
}else{
s[i--] = '0';
s[i--] = '2';
s[i] = '%';
j--;
}
}
return s;
}
};
class Solution {
public:
// 清空字符串,双指针清空
void emptySpace(string &s){
int n = s.size();
int slowIndex{},fastIndex = 0;
// 清空前面的空格
while(fastIndex < n && s[fastIndex] == ' ') fastIndex++;
// 清空中间的空格
for(;fastIndex < n;++fastIndex){
if(fastIndex-1 > 0 && s[fastIndex] == s[fastIndex-1] && s[fastIndex] == ' '){
continue;
}else{
s[slowIndex++] = s[fastIndex];
}
}
// 清空尾部的空格
if(slowIndex - 1 >0 && s[slowIndex-1] == ' '){
s.resize(slowIndex-1);
}else{
s.resize(slowIndex);
}
}
// 翻转字符串，双指针翻转
void reverse(string &s,int start,int end){
for(int i = start,j = end; i<j;++i,--j){
swap(s[i],s[j]);
}
}
string reverseWords(string s) {
// 清空字符串空格
emptySpace(s);
// 翻转整体字符串
reverse(s,0,s.size()-1);
// 单个翻转字符串
for(int i{};i<s.size();++i){
int j = i;
while(j < s.size() && s[j] != ' ') j++;
reverse(s,i,j-1);
i = j;
}
return s;
}
};
class Solution {
public:
// 递归求解
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == nullptr) return pre;
ListNode* temp = cur->next;
cur->next = pre;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 双指针求解
// ListNode* cur = head;
// ListNode* pre = nullptr;
// while(cur){
// ListNode* temp = cur->next;
// cur->next = pre;
// pre = cur;
// cur = temp;
// }
// return pre;
return reverse(nullptr,head);
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 应用双指针
ListNode* dummpyNode = new ListNode(0);
dummpyNode->next = head;
ListNode* slowNode = dummpyNode;
ListNode* fastNode = dummpyNode;
// 先移动n个节点
while(n-- && fastNode != nullptr) fastNode = fastNode->next;
// 双指针寻找倒数第n个节点
fastNode = fastNode->next;
while(fastNode != nullptr){
slowNode = slowNode->next;
fastNode = fastNode->next;
}
// 删除节点
slowNode->next = slowNode->next->next;
return dummpyNode->next;
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 计算两个链表的长度
int lenA{},lenB{};
ListNode* curA = headA;
ListNode* curB = headB;
while(curA!=nullptr){
lenA++;
curA = curA->next;
}
while(curB != nullptr){
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// lenA表示为最长的链表长度，curA为最长的链表头节点
if(lenB > lenA){
swap(lenA,lenB);
swap(curA,curB);
}
// 最长节点先移动长度差个节点
int delta = lenA - lenB;
while(delta--){
curA = curA->next;
}
// 判断链表是否会相交
while(curA!=nullptr){
if(curB == curA) return curB;
curB = curB->next;
curA = curA->next;
}
return {};
}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 应用双指针
if(!head) return{};
ListNode* slow = head;
ListNode* fast = head;
while(fast->next!=nullptr && fast->next->next!=nullptr){
slow = slow->next;
fast = fast->next->next;
// 如果快慢指针相遇，说明有环
if(slow == fast){
slow = head;
// 公式推导查看具体题解
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return {};
}
};
class Solution {
public:
// 使用关联式容器并配合双指针求解
vector<vector<int>> threeSum(vector<int>& nums) {
int n =nums.size();
int left{},right{};
vector<vector<int>> ans;
sort(nums.begin(),nums.end()); // 先排序，然后使用双指针
for(int i{};i<n;++i){
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
left = i+1;
right = n-1;
// 双指针求解
while(left < right){
int sumNum = nums[i] + nums[left] + nums[right];
if(sumNum > 0){
right--;
}else if(sumNum < 0){
left++;
}else{
ans.push_back({nums[i],nums[left],nums[right]});
while(left < right && nums[right] == nums[right-1]) right--;
while(left < right && nums[left] == nums[left+1]) left++;
right--;
left++;
}
}
}
return ans;
}
};
class Solution {
public:
// 与三数之和一致：关联式容器+双指针求解，只是多嵌套了一层循环
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
int left{},right{};
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i{};i<n;++i){
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
for(int j = i+1;j<n;++j){
if(j > i+1 && nums[j] == nums[j-1]){
continue;
}
left = j+1;
right = n-1;
while(left <right){
if(nums[i] + nums[j] > target - (nums[left] + nums[right])){
right--;
}else if(nums[i] + nums[j] < target - (nums[left] + nums[right])){
left++;
}else{
ans.push_back({nums[i], nums[j], nums[left] ,nums[right]});
while(left < right && nums[right] == nums[right-1]) right--;
while(left < right && nums[left] == nums[left+1]) left++;
left++;
right--;
}
}
}
}
return ans;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）