27.移除元素

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;
    }
};

26.删除排序数组中的重复项

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;
    }
};

283.移动零

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]);
            }
        }
    }
};

844.比较含退格的字符串

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;
}
};

977.有序数组的平方

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;
    }
};

344.反转字符串

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]);
        }
    }
};

剑指Offer05.替换空格

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;
    }
};

151.翻转字符串里的单词

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;
    }
};

206.反转链表

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);
    }
};

19.删除链表的倒数第N个节点

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;
    }
};

07.链表相交

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 {};
    }
};

142.环形链表II

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 {};
    }
};

15.三数之和

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;
    }
};

18.四数之和

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;
    }
};

5186区间内查询数字的频率

986区间列表的交集

11盛最多水的容器