线型结构算法 | Automannn的学习园地

# 数组类算法

# 二分查找

问题描述：给定一个n个元素的（升序）整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在则返回下标，否则返回-1;(从一个有序数组中查找目标值的位置)
力扣位置 (opens new window)
题解

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while (left<=right){
            int middle = (left+right)>>1;
            if (nums[middle]>target){
                right= middle-1;
            }else if (nums[middle]<target){
                left = middle+1;
            }else{
                return middle;
            }
        }
        return -1;
    }
};

关键点
- 两自然数的中点的计算方式

# 移除元素

问题描述: 不使用额外数组的情况下，从一个数组中删除指定值的元素，返回数组长度
力扣位置 (opens new window)
题解

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex=0,fastIndex=0;
        for(;fastIndex<nums.size();fastIndex++){
            if(nums[fastIndex]!=val){
                int tmp = nums[slowIndex];
                nums[slowIndex] = nums[fastIndex];
                nums[fastIndex] = tmp;
                slowIndex++;
            }
        }
        return slowIndex;
    }
};

关键点
- 表面上重点是删除，实则是获取数组长度，换言之，求最后一个有效字符的位置
- 另一个角度，不借助辅助空间删除元素，本质上是移动元素位置

# 有序数组的平方

问题描述：求递增数列的平方，组成的数组,返回数组;
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left=0; 
        int right = nums.size()-1;
        int pos = nums.size()-1;
        vector<int> result(pos+1);
        while(left<=right){
            if(nums[left]*nums[left]>=nums[right]*nums[right]){
                result[pos--]=nums[left]*nums[left];
                left++;
            }else{
                result[pos--]=nums[right]*nums[right];
                right--;
            }
        }
        return result;
    }
};

关键点
- 从常规思维，递增数列可分为：全正数，全负数，以及有正有负；相应衍生出很多情况的探讨
- 思维角度转换，可以将全正，全负，或有正有负，规范化为以首位逐步推进，建立平方数组

# 长度最小的子数组

问题描述: 在一个正整数数组中，求满足和>=target的最小长度的连续子数组，返回该子数组的长度，不存在则返回0；
力扣位置 (opens new window)
题解

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum=0;
        int slowIndex=0;
        int minLen=nums.size();
        for(int fastIndex=0;fastIndex<nums.size();fastIndex++){
            sum+=nums[fastIndex];
            while(sum>=target){
                minLen=minLen>(fastIndex-slowIndex+1)?(fastIndex-slowIndex+1):minLen;
                slowIndex++;
                sum -=nums[slowIndex-1];
            }
        }
        if(slowIndex==0){
            if(sum>=target){
                return nums.size();
            }else{
                return 0;
            }
        }
        return minLen;
    }
};

关键点
- 常规思维是通过双重迭代便利，逻辑上类似于计算窗口的向右单向递增
- 本算法在于计算窗口的整体动态移动，复用计算过程
- 临界点的处理，分情况

# 顺时针螺旋矩阵

题目描述：求1到n平方的顺时针螺旋矩阵
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n,vector<int>(n,0));
        int value =1;
        int offset=1;
        int mid = n/2;
        int cycle=n/2;
        int startx=0,starty=0;
        while(cycle>0){
            int x=startx,y=starty;
            for(;x<startx+n-offset;x++){
                result[y][x]=value++;
            }
            for(;y<starty+n-offset;y++){
                result[y][x]=value++;
            }
            for(;x>startx;x--){
                result[y][x]=value++;
            }
            for(;y>starty;y--){
                result[y][x]=value++;
            }
            offset+=2;
            cycle--;
            startx++;
            starty++;
        }

        if(n%2){
            result[mid][mid]=value++;
        }

        return result;
    }
};

关键点
- 将行为轨迹量化，找到关键代换量

# 链表类算法

# 移除链表元素

题目描述：从一个链表中，移除指定元素,返回新链表的头节点;
力扣位置 (opens new window)
题解

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(!head){
            return head;
        }
        ListNode* newNode=new ListNode();
        ListNode* newHead=newNode;
        newNode->next=head;
        while(newNode){
            ListNode* nextNode = newNode->next;
            if(nextNode&&nextNode->val==val){
                newNode->next = nextNode->next;
                delete nextNode;
            }else{
                newNode = newNode->next;
            }
        }
        return newHead->next;
    }
};

关键点
- 乍一看，该问题挺简单。
- 关键点在于临界值的处理：如头节点要删除时的处理，处理方式是将其泛化
- 为其新增一个头节点

# 设计链表

问题描述: 设计链表的实现。实现addAtHead(val),addAtTail(val),addAtIndex(index,val),deleteAtIndex(index),get(index)
力扣位置 (opens new window)
题解

class MyLinkedList {

public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode* prev;
        ListNode():val(0),next(NULL),prev(NULL){}
        ListNode(int x):val(x),next(NULL),prev(NULL){}
    };

    MyLinkedList() {
        size=0;
        head=NULL;
        tail=NULL;
    }
    
    int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        if(size/2>=index){
            ListNode* result=head;
            while(index>0){
                result=result->next;
                index--;
            }
          return  result->val;
        }else{
            ListNode* result;
            result=tail;
            int len= size-1-index;
                while(len>0){
                    result=result->prev;
                    len--;
                }
          return  result->val;
        }
    }
    
    void addAtHead(int val) {
        if(!head){
            head = new ListNode(val);
            head->prev=NULL;
            head->next=NULL;
            tail=head;
        }else{
            ListNode* newNode = new ListNode(val);
            newNode->next = head;
            head->prev = newNode;
            head=newNode;
        }
        size++;
    }
    
    void addAtTail(int val) {
        if(!tail){
            ListNode* tmpNode = head;
            while(tmpNode&&tmpNode->next){
                tmpNode=tmpNode->next;
            }
            tail=tmpNode;
        }
        if(tail){
            ListNode* newNode = new ListNode(val);
            newNode->prev=tail;
            tail->next= newNode;
            tail=tail->next;
        }else{
            tail= new ListNode(val);
            head=tail;
        }
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<=0){
            addAtHead(val);
        }else if(index==size){
        	addAtTail(val);
		}else{
            if(size/2>=index){
                ListNode* result;
                result=head;
                while(index>0){
                    result=result->next;
                    index--;
                }
                ListNode* newNode= new ListNode(val);
                newNode->next = result;
                newNode->prev = result->prev;
                result->prev->next=newNode;
                result->prev = newNode;
                size++;
            }else{
                ListNode* result;
                result=tail;
                int len= size-1-index;
                while(len>0){
                    result=result->prev;
                    len--;
                }
                ListNode* newNode= new ListNode(val);
                newNode->next = result;
                newNode->prev = result->prev;
                result->prev->next=newNode;
                result->prev = newNode;
                size++;
            }
        }
    }
    
    void deleteAtIndex(int index) {
        if(index>=0&&index<=size-1){
            if(index==0){
                ListNode* prevNode=head;
                head = head->next;
                if(head){
                	head->prev=NULL;
				}
                size--;
                delete prevNode;
            }else if(index==size-1){
                ListNode* oldNode = tail;
                tail=tail->prev;
                if(tail){
                    tail->next=NULL;
                }
                
                delete oldNode;
                size--;
            }else if (size/2>=index){
                ListNode* result;
                result=head;
                while(index>0){
                    result=result->next;
                    index--;
                }
                result->prev->next=result->next;
                result->next->prev = result->prev;
                delete result;
                size--;
            }else{
                ListNode* result;
                result=tail;
                int len= size-1-index;
                while(len>0){
                    result=result->prev;
                    len--;
                }
                result->prev->next=result->next;
                result->next->prev = result->prev;
                delete result;
                size--;
            }
        }
    }
private:
    int size;
    ListNode* head;
    ListNode* tail;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

关键点
- 链表临界点的处理：头节点，尾节点;
- 链表也可结合size，二分提高查询效率;

# 翻转链表

问题描述: 将一个单链表进行反转，返回该链表。
力扣位置 (opens new window)
题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head){
            return head;
        }
        ListNode* newHead=head;
        head=head->next;
        newHead->next=NULL;
        while(head){
            ListNode* newNode=head;
            head=head->next;
            newNode->next=newHead;
            newHead=newNode;
            
        }
        return newHead;
    }
};

# 两两交换链表节点

题目描述: 两两交换链表中的节点，返回交换后链表的头节点
力扣位置 (opens new window)
题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head){
            return head;
        }
        ListNode* left=NULL;
        ListNode* right=NULL;
        ListNode* cur=head;
        ListNode* newHead = new ListNode(0);
        left = cur;
        right=cur->next;
        if(right){
            newHead->next = right;
        }else{
            newHead->next=left;
        }
        while(left&&right){
            cur = cur->next->next;
            left->next=cur;
            if(cur&&cur->next){
                left->next = cur->next;
            }
            right->next=left;
            left = cur;
            if(left){
                right = cur->next;
            }else{
                right=NULL;
            }
        }
        ListNode* tmp = newHead;
        newHead = newHead->next;
        delete tmp;
        return newHead;
    }
};

关键点
- 借助多个指针实现相对位置的移动
- 新增头节点，使问题泛化,简化操作

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

问题描述: 删除给定链表的倒数第n个节点，返回该链表的头节点
力扣位置 (opens new window)
题解

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head){
            return head;
        }
        ListNode* slow=head;
        ListNode* fast=head;
        n++;
        while(fast&&n>0){
            fast=fast->next;
            n--;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        ListNode* tmpNode = slow->next;
        if(!slow->next){
            delete head;
            return NULL;
        }
        if(n>0){
            ListNode* tmp = head;
            head=head->next;
            delete tmp;
            return head;
        }
        slow->next = slow->next->next;
        delete tmpNode;
        return head;
    }
};

关键点
- 由于链表只有单向遍历，因此需要将该逆向的问题转化正向问题
- 临界点泛化的问题

# 链表相交

问题描述: 求两个链表相交的起始节点，没有相交则返空
力扣位置 (opens new window)
题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int m =0,n=0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA){
            m++;
            curA=curA->next;
        }
        while(curB){
            n++;
            curB=curB->next;
        }
        curA = headA;
        curB = headB;
        if(m<n){
            while(curB !=curA&&m<n){
                curB=curB->next;
                n--;
            }
        }else if(m>n){
            while(curA!=curB&&m>n){
                curA = curA->next;
                m--;
            }
        }
        if(curA==curB){
            return curA;
        }else{
            while(curA){
                curA = curA->next;
                curB = curB->next;
                if(curA==curB){
                    return curA;
                }
            }
            return NULL;
        }
    }
};

关键点
- 抓住问题的本质，并将其具象化
- 勤训练，拓宽思路

# 环型链表

问题描述: 求给定链表的第一个入环节点，如无环，则返回null.
力扣位置 (opens new window)
题解

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head){
            return NULL;
        }
        ListNode* slow=head;
        ListNode* fast=head;
        while(slow&&fast){
            slow=slow->next;
            fast=fast->next;
            if(fast){
                fast=fast->next;
            }
            if(slow==fast){
                break;
            }
        }
        if(!slow||!fast){
            return NULL;
        }
        ListNode* index2 = slow;
        ListNode* index1 = head;
        while(index1!=index2){
            index1 = index1->next;
            index2 = index2->next;
        }
        return index1;
    }
};

关键点
- 快慢指针，快指针二倍速追赶慢指针，慢指针一定可以在一圈之内被追上
- 通过数学计算，可以计算出相遇节点与头节点到入环节点的距离相等，具体可参考代码随想录内容

# 哈希表类算法

# 有效的字母异位词

问题描述：判断两个字符串，设为s,t是否有字母异位词。(字母异位词指:s和t中每个字符出现的次数都相同，字符串中仅包含小写字母)
力扣位置 (opens new window)
题解

class Solution {
public:
    bool isAnagram(string s, string t) {
        int results[26] = {0};
        for(int i=0;i<s.length();i++){
            results[s[i]%26]++;
        }
        for(int i=0;i<t.length();i++){
            results[t[i]%26]--;
        }
        for(int i=0;i<26;i++){
            if(results[i]!=0){
                return false;
            }
        }
        return true;
    }
};

关键点
- 用于多个元素比较，使用加减可以直指问题核心，而不用考虑其它有的没的
- 模长对于hash表的建立很重要

# 两个数组的交集

问题描述：给定两个数组nums1和nums2，返回它们的交集;输出结果中的每个元素一定是唯一的。0<=nums1[i],nums2[i]<=1000;
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> results;
        unordered_set<int> nums1_set(nums1.begin(),nums1.end());
        for(int num:nums2){
            if(nums1_set.find(num)!=nums1_set.end()){
                results.insert(num);
            }
        }
        return vector<int>(results.begin(),results.end());
    }
};

关键点
- 用set可以很好的解决重复的问题

# 快乐数

问题描述：一个正整数，用它每个位置的平方和，重复该流程，最终得到结果为1，则是快乐数。判断某数是否为快乐数
力扣位置 (opens new window)
题解

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> sums;
        while(1){
            int sum = getSum(n);
            if(sum==1){
                return true;
            }else{
                if(sums.find(sum)!=sums.end()){
                    return false;
                }else{
                    sums.insert(sum);
                    n=sum;
                }
            }
        }
    }

    int getSum(int n){
        int sum = 0;
        while(n){
            sum+=(n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
};

关键点
- 数学问题，似乎相比较其它问题问题，更难。。
- 迭代，各位数相加的计算方法
- 递归出口：各位数之和，最终一定会重复(应该算是数学的某个定理，性质之类的，束手无策)。
- 无限循环=====>求和的过程中，sum会重复出现? 这里有点不理解，感觉不是充分条件，最终依然是数学问题

# 赎金信

问题描述：两个数组，判断第一个数组的元素是否能被第二个数组覆盖.(第二个数组中的每个元素只使用一次)
力扣位置 (opens new window)
题解

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int,int> hash;
        for(int i=0;i<ransomNote.length();i++){
            hash[ransomNote[i]]++;
        }
        for(int i=0;i<magazine.length();i++){
            hash[magazine[i]]--;
        }
        for(auto& item:hash){
            if(item.second>0){
                return false;
            }
        }
        return true;
    }
};

关键点
- 元素个数比较天然适合hash插槽;

# 两数之和

问题描述：从一个number数组中，找出两数和为target的两数下标.(假设只有一对符合情况)
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>results;
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++){
            if(hash[target-nums[i]]>0){
                results.push_back(i);
                results.push_back(hash[target-nums[i]]-1);
                break;
            }
            hash[nums[i]]=i+1;
        }
        return results;
    }
};

关键点
- 比较，可以通过 hash结构辅助实现
- 利用下标辅助实现循环出口，类似于将下标与业务相结合

# 三数之和

问题描述: 从一个整数数组中，找出和为零的三元组。三元素各不相等
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> results;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0){
                return results;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }else{
                    vector<int> result;
                    result.push_back(nums[i]);
                    result.push_back(nums[left]);
                    result.push_back(nums[right]);
                    results.push_back(result);

                    while(left<right&&nums[right]==nums[right-1])right--;
                    while(left<right&&nums[left]==nums[left+1])left++;
                    right--;
                    left++;
                }
            }
        }
       return results;
    }
};

关键点
- 可直接使用排序函数，sort(begin,end),位于#include库函数中
- 将问题简化，借助数学原理，降低复杂度
- 三指针，两指针为浮动窗口
- 互不重复的临界表示

# 四数之和

问题描述: 从一个整数数组中，找出和为 target的四元组。该元组内的元素互不重复。
力扣地址 (opens new window)
题解

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> results;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }

            for(int j=i+1;j<nums.size();j++){

                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }

                int left =j+1;
                int right = nums.size()-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{
                        vector<int> result;
                        result.push_back(nums[i]);
                        result.push_back(nums[j]);
                        result.push_back(nums[left]);
                        result.push_back(nums[right]);
                        results.push_back(result);

                        while(left<right&&nums[right]==nums[right-1])right--;
                        while(left<right&&nums[left]==nums[left+1])left++;

                        left++;
                        right--;
                    }

                } 
            }
        }
        return results;
    }
};

关键点
- 三数之和的泛化，理论上更多元组的和也能求出来

# 四数相加

问题描述: 求四个长度一致的整数数组的元素相加为0的结果有几种。
力扣位置 (opens new window)
题解

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
       unordered_map<int,int> sums_hash;
       int count=0;

       for(int i=0;i<nums1.size();i++){
           for(int j=0;j<nums2.size();j++){
               int sum = nums1[i]+nums2[j];
               sums_hash[sum]++;
           }
       }
       for(int i=0;i<nums3.size();i++){
           for(int j=0;j<nums4.size();j++){
               int sum = nums3[i]+nums4[j];
               count += sums_hash[-sum];
           }
       }

       return count;
       
    }
};

关键点
- 正负数关于零对称，可简化该题

# 字符串类算法

# 反转字符串

问题描述：原地反转字符串。要求空间复杂度为O(1)
力扣位置 (opens new window)
题解

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left =0,right=s.size()-1;
        while(left<right){
            char tmp = s[right];
            s[right] = s[left];
            s[left]=tmp;
            left++;
            right--;
        }
    }
};

# 反转字符串2

问题描述：部分翻转字符串
力扣位置 (opens new window)
题解

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i=0;i<s.length();i+=2*k){
            if(i+k<=s.length()){
                reverse(s.begin()+i,s.begin()+i+k);
                continue;
            }else{
                reverse(s.begin()+i,s.end());
            }
        }
        return s;
    }
};

关键点
- 可直接使用字符串翻转函数reverse(begin,end),左闭右开，需要使用库函数：#include
- 函数可视为分段，将问题拆分，可以使复杂问题简化

# 替换空格

问题描述: 将字符串的空格转化为 %20.
力扣位置 (opens new window)
题解

class Solution {
public:
    string replaceSpace(string s) {
        int whiteSpaceNum = 0;
        int oldSize = s.size()-1; 
        for(int i=0;i<s.size();i++){
            if(s[i]==' '){
                whiteSpaceNum++;
            }
        }
        s.resize(s.size()+whiteSpaceNum*2);
        int right = s.size()-1;
        for(int left = oldSize;left>=0;left--){
            if(s[left]!=' '){
                s[right--]=s[left];
            }else{
                s[right--]='0';
                s[right--]='2';
                s[right--]='%';
            }
        }
        return s;
    }
};

关键点
- 字符串api： 变更容量resize()
- 扩容之后，从后往前移动，可简化操作;

# 翻转字符串里面的单词

问题描述：将整个字符串，以单词为单位进行翻转(以空格为分隔，可能存在多个空格，翻转后只能存在一个空格,前置与后置也可能存在多个空格)。
力扣位置 (opens new window)
题解

class Solution {
public:
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s,0,s.size()-1);
        int start=0;
        int end =0;
        bool entry = false;
        for(int i=0;i<s.size();i++){
            if(!entry){
                start =i;
                entry = true;
            }
            if(entry && s[i]== ' '){
                end =i -1;
                entry =false;
                reverse(s,start,end);
            }
            if(entry && (i == (s.size()-1)) ){
                end = i;
                entry = false;
                reverse(s,start,end);
            }
        }
        return s;
    }

    void reverse(string& s,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }

    void removeExtraSpaces(string& s){
        int slowIndex=0,fastIndex=0;
        while(s.size()>0 && fastIndex<s.size() &&s[fastIndex]==' '){
            fastIndex++;
        }
        for(;fastIndex<s.size();fastIndex++){
            if(fastIndex-1>0&&s[fastIndex-1]==s[fastIndex]
            && s[fastIndex]==' '){
                continue;
            }else{
                s[slowIndex++]= s[fastIndex];
            }
        }
        if(slowIndex-1>0 && s[slowIndex-1] == ' '){
            s.resize(slowIndex-1);
        }else{
            s.resize(slowIndex);
        }
    }
};

关键点
- 首先将问题规范化，去除多余的空格，并重置字符串大小，即将所有的空格移除到末尾。
- 交换元素api:swap(a,b)，位于命名空间:std下
- 偶数次翻转可以达到奇妙的效果

# 左旋转字符串

问题描述：以字符串以左部分的字符，转移到尾部。
力扣位置 (opens new window)
题解

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s,0,n-1);
        reverse(s,n,s.size()-1);
        reverse(s,0,s.size()-1);
        return s;

    }

    void reverse(string& s, int left,int right){
        while(left<right){
            char tmp = s[left];
            s[left++]=s[right];
            s[right--]=tmp;
        }
    }
};

关键点
- 偶数次旋转，有奇效

# 字符串匹配

为题描述: 求模式串在目标字符串的第一个匹配位置
力扣位置 (opens new window)
题解

class Solution {
public:

    void getNext(int* next,const string& s){
        int j=-1;
        next[0]= j;
        for(int i=1;i<s.size();i++){
            while(j>=0 && s[i]!=s[j+1]){
                j = next[j];
            }
            if(s[i]== s[j+1]){
                j++;
            }
            next[i] =j;
        }
    }

    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }

        int next[needle.size()];
        getNext(next,needle);

        int j=-1;
        for(int i=0;i<haystack.size();i++){
            while(j>=0 && haystack[i]!=needle[j+1]){
                j = next[j];
            }
            if(haystack[i] == needle[j+1]){
                j++;
            }
            if(j==(needle.size()-1)){
                return (i-needle.size()+1);
            }

        }
        return -1;
    }
};

关键点
- KMP算法
- 计算模式串next数组的方法，理论需要先理解
- KMP的比较过程的理解：目标串一直向前，模式串回溯到恰当的位置。
- 模式串匹配成功与next数组的关系：下一次匹配的时候模式串回溯地址为最后一个元素的位置，则匹配成功

# 重复的子字符串

问题描述：非空字符串是否能够由某个模式串重复构成。
力扣位置 (opens new window)
题解

class Solution {
public:

    void getNext(int* next,const string& s){
        next[0] =0;
        int j =0;
        for(int i=1;i<s.size();i++){
            while(j>0&&s[i]!=s[j]){
                j = next[j-1];
            }
            if(s[i]==s[j]){
                j++;
            }
            next[i] =j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        if(s.size()==0){
            return false;
        }
        int next[s.size()];
        getNext(next,s);

        int len = s.size();
        if(next[len-1]!=0 && len %(len -(next[len-1]))==0){
            return true;
        }
        return false;
    }
};

关键点
- kmp理解起来还是比较难，看carl的解释;

# 栈与队列

# 队列实现栈

问题描述：用两个队列实现栈操作(包含栈的四种基本操作:push,pop,peek,empty)；
力扣位置 (opens new window)
题解

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stIn.empty()&& stOut.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

关键点
- 队列操作api: push,pop,top,empty,stack需要引入头文件#include
- 核心点在于操作顺序重排组合

# 队列实现栈

问题描述： 使用队列实现栈，包含栈的基本操作:push,pop,top,empty
力扣位置 (opens new window)
题解

class MyStack {
public:
    queue<int> que;
    MyStack() {
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        size--;
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

关键点
- 本质上是通过自环改变顺序，中间有一个位置的间隔;
- 灵活使用队列的api: back;
- 使用队列需要引入**#include **

# 有效的括号

问题描述: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效(前后配对)
力扣位置 (opens new window)
题解

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        int small_left ='(',small_right=')';
        int big_left = '{',big_right='}';
        int middle_left ='[',middle_right=']';
        for(int i=0;i<s.size();i++){
            int flag = s[i];
            if(flag==small_left||flag==big_left||flag==middle_left){
                st.push(flag);
            }else{
                if(st.empty()){
                    return false;
                }
                if(small_right==flag){
                    if(st.top()!=small_left){
                        return false;
                    }else{
                        st.pop();
                    }
                }
                if(big_right==flag){
                    if(st.top()!=big_left){
                        return false;
                    }else{
                        st.pop();
                    }
                }
                if(middle_right==flag){
                    if(st.top()!=middle_left){
                        return false;
                    }else{
                        st.pop();
                    }
                }
            }
        }
        return st.empty();
    }
};

关键点
- 处理字符的字面值与标识符的关系;
- 边界值的处理(栈为空，右边的符号一个不匹配，即表明匹配失败)

# 消除相邻重复项

问题描述：删除字符串(由小写字符组成)中的相邻重复项
力扣位置 (opens new window)
题解

class Solution {
public:
    string removeDuplicates(string s) {
        stack<int> st;
        for(int i=0;i<s.size();i++){
            if(st.empty()){
                st.push(s[i]);
            }else{
                if(st.top()==s[i]){
                    st.pop();
                }else{
                    st.push(s[i]);
                }
            }
        }
        s.resize(st.size());
        for(int i=s.size()-1;i>=0;i--){
            s[i]=st.top();
            st.pop();
        } 
        return s;
    }
};

关键点
- 需要足够熟悉c++的参数传递
- 删除相邻重复项存在着迭代行为，类似祖玛游戏

# 逆波兰表达式求职

问题描述：求四则运算(逆波兰表达式,假设除法始终合法，保留整数)
力扣位置 (opens new window)
题解

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0;i<tokens.size();i++){
            string flag = tokens[i];
            if(flag=="+"||flag=="-"||flag=="*"||flag=="/"){
                int param1 = st.top();
                st.pop();
                int param2 = st.top();
                st.pop();
                int result = compute(param2,param1,flag);
                st.push(result);
            }else{
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }

    int compute(int param1,int param2,string flag){
        if(flag=="+"){
            return param1+param2;
        }
        else if(flag =="-"){
            return param1-param2;
        }
        else if(flag=="*"){
            return param1*param2;
        }
        else{
            return param1/param2;
        }
    }
};

关键点
- 题目描述结合例子能够更好理解

# 滑动窗口最大值

问题描述: 整数数组nums，给一个大小为k的窗口，从数组最左侧滑动到最右侧，求滑动窗口经过时组成的最大值数组;
力扣位置 (opens new window)
题解

class Solution {
private:
    class MyQueue{
        public:
            deque<int> que;

            void pop(int value){
                if(!que.empty() && value == que.front()){
                    que.pop_front();
                }
            }

            void push(int value){
                while(!que.empty() && value>que.back()){
                    que.pop_back();
                }
                que.push_back(value);
            }

            int front(){
                return que.front();
            }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        if(nums.size()<k){
            return result;
        }
        MyQueue windowQueue;
        for(int i=0;i<k;i++){
            windowQueue.push(nums[i]);
        }
        result.push_back(windowQueue.front());

        for(int i=k;i<nums.size();i++){
            windowQueue.pop(nums[i-k]);
            windowQueue.push(nums[i]);
            result.push_back(windowQueue.front());
        }
        return result;
    }
};

关键点
- 将移动这个动作转化为结果,并不是直接去执行移动这个动作
- 借助队列操作，使得队列既满足size<k,又满足元素递减的特性
- 通过重载队列的pop()操作为pop(val)，当队首与要出队的值相等时，执行出队操作
- 本质上是一个双端队列

← c++api概览树型结构算法 →