Cpp LeetCode

//逐个冒出当前最大值
template <class T>
void bubble_sort(T arr[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-i-1;j++)
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
    }
}
//设置flag，如果存在一轮冒泡没有进行交换，则排序完成

//从序列中选出该位置上应该出现的元素
template <class T>
void selection_sort(T arr[],int len){
    for(int i=0;i<len-1;i++){
        int index=i;
        for(int j=i+1;j<len;j++){
            if(arr[j]<arr[index]){
                index=j;
            }
        }
        swap(arr[i],arr[index]);
    }

//向前遍历有序序列，寻找当前元素的合适位置插入
template <class T>
void  direct_insertion_sort(T arr[],int len){
    for(int i=1;i<len;i++){
        T key=arr[i];
        int j=i;
        while(j-1>=0&&arr[j-1]>key){
            arr[j]=arr[j-1];
            j--;
        }
        arr[j]=key;
    }//位置j的元素要么是j-1(挪),要么是key(插)
}
//二分法加快插入位置的搜索

//宏观性优先调控，减少插排比较和交换次数
template <class T>
void shell_sort(T arr[],int len){
    int h=1;
    while(h<len/3) h=3*h+1;
    while(h>=1){
        for(int i=h;i<len;i++){
            T key=arr[i];
            int j=i;
            while(j-h>=0&&key<arr[j-h]){
                arr[j]=arr[j-h];
                j-=h;
            }
            arr[j]=key;
        }
        h/=3;
    }
}
//对于增量以除以2递减的排序，时间代价：$\theta$(n^2^);选取的增量之间并不互质，上一轮排序中某些子序列已经排过了导致处理效率不高
//对于增量不以除以2递减的排序，时间代价：$\theta$(n^3/2^)

/*1.选择轴值

2.划分两个子序列L和R

- 使得L中所有记录都小于或者等于轴值
- R中记录大于轴值
*/

//采用双指针排列小序列，也可以使用夹逼的方式
int partitioner(int arr[],int low,int high){
    int pivot=arr[high];
    int i=low;
    for(int j=low;j<high;j++)//处理low~high-1的元素pivot分离
        if(arr[j]<pivot)
            swap(arr[i++],arr[j]);
    swap(arr[i],arr[high]); //对小于pivot的最后一个元素的后一位置与pivot交换（包括边界）
    return i;
}

void qsort(int arr[],int low,int high){
    if(low<high){
        int mid=partitioner(arr,low,high);
        qsort(arr,low,mid-1);
        qsort(arr,mid+1,high);
    }
}

inline int findpivot(int* arr,int i ,int j){
    return (i+j)/2;
}

inline int Partition(int* arr,int left,int right,int pivotindex){
    swap(arr[pivotindex],arr[right]);
    int pivot = arr[right];
    int i = left-1, j=right;
    do{
        while(arr[++i] < pivot);       
        while((i < j) && (pivot < arr[--j]));    
        swap(arr[i], arr[j]);
    }while(i<j);
    swap(A[i],A[right]);
    return i;
}

inline int Partition(int* arr,int left,int right,int pivotindex){
    swap(arr[pivotindex],arr[left]);
    int pivot = arr[left];
    int i = left,j=right+1;
    while(ture){
        while(arr[++i]<=pivot && i<right);
        while(arr[--j]>=pivot && j>left+1);
        if(i<j) swap(arr[i],arr[j]);
        else break;
    }
    swap(arr[j],arr[left]);
    return j;
}

//交换循环中要求对i,j索引有边界限制和qsort交换限制
//交换要求i<j
//mid与pivot位置有关，pivot放在右边，则为i（第一个大于pivot的index）；否则为j

void qsort(int *arr,int left,int right){
    if(left<right){
        int pivotindex = findpivot(arr,left,right);
        int mid=Partition(A,left,right,pivotindex);
        qsort(A,left,mid-1);
        qsort(A,mid+1,right);
    }
}

void merger(int arr[],int temparr[],int left,int mid,int right){
    int l_pos=left;
    int r_pos=mid+1;
    int pos=left;
    while(l_pos<=mid&&r_pos<=right)
    {
        if(arr[l_pos]<arr[r_pos])
            temparr[pos++]=arr[l_pos++];
        else
            temparr[pos++]=arr[r_pos++];
    }
    while(l_pos<=mid)
    {
        temparr[pos++]=arr[l_pos++];
    }
    while(r_pos<=right)
    {
        temparr[pos++]=arr[r_pos++];
    }
    while(left<=right)
    {
        arr[left]=temparr[left];
        left++;
    }
}

void merge_sort(int arr[],int temparr[],int left,int right)
{
    if(left<right){
        int mid=(left+right)/2;
        merge_sort(arr,temparr,left,mid);
        merge_sort(arr,temparr,mid+1,right);
        merger(arr,temparr,left,mid,right);
    }
}

int binarySearch(vector<int>& nums, int target) {
    int middle,left=0,right=nums.size()-1;
    while(left<=right){
        middle = left+(right-left)/2;
        if(nums[middle]<target) left=middle+1 ;   
        else if(nums[middle]>target) right=middle-1;
        else return middle;
    }
    return left/return right+1;
}

int findLeft(vector<int>& nums, int target) {
    int middle, left=0, right=nums.size()-1, ans=-1;
    while(left<=right) {
        int middle=left+(right-left)/2;
        if(nums[middle]<target) left=middle+1;
        else if(nums[middle]>target) right=middle-1;
        else {
            right=middle-1;
            ans=middle;
        }
    }
    return ans;
}

int findRight(vector<int>& nums, int target) {
    int middle, left=0, right=nums.size()-1, ans=-1;
    while(left<=right) {
        int middle=left+(right-left)/2;
        if(nums[middle]<target) left=middle+1;
        else if(nums[middle]>target) right=middle-1;
        else {
            left=middle+1;
            ans=middle;
        }
    }
    return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
    return {findLeft(nums, target), findRight(nums, target)};
}

bool search(vector<int>& nums, int target) {
    int mid, size=nums.size(), left=0, right=size-1;
    while(left<=right) {
        mid=left+(right-left)/2;
        if(nums[mid]==target) return true;
        if(nums[mid]==nums[left] && nums[mid]==nums[right]) {
            left++;
            right--;
        }
        else if(nums[mid]>=nums[left]) {
            if(target>=nums[left] && target<nums[mid])
                right=mid-1;
            else left=mid+1;
        }
        else {
            if(target<=nums[right] && target>nums[mid])
                left=mid+1;
            else right=mid-1;
        }
    }
    return false;
}

int slowFast(vector<int>& nums, int val) {
    int slow=0;
    for(int fast=0;fast<nums.size();fast++){
        if(condition(nums[fast]))
            action(slow++,fast);
    }
    return slow;
}

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = 0, p2 = 0;
    int sorted[m + n];
    while (p1 < m || p2 < n) {
        if(p1==m) sorted[p1+p2-1]=nums2[p2++];
        else if(p2==n) sorted[p1+p2-1]=nums1[p1++];
        else if(nums1[p1]<nums2[p2]) sorted[p1+p2-1]=nums1[p1++];
        else sorted[p1+p2-1]=nums2[p2++];
    }
}

int leftRight(vector<int>& nums){
    int left=0,right=nums.size()-1;
    while(left<=right){
        if(compare(left,right)) 
            res.push_back(nums[left++]||nums[right--]);
    }
}

int startEnd(int target, vector<int>& nums) {
    int start=0;
    for(int end=0;end<nums.size();end++){
        push(nums[end]);
        while(checkLegal([start,end],target)) {
            	deal(res, [start,end]);
            	start++;
        }
    }
    return res;
}

//需要排序，返回值不可是索引，可去重
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());      		
    vector<vector<int>> res;
    for(int i=0; i<nums.size(); i++) {
        if(i>0 && nums[i]==nums[i-1]) continue;		//a去重
        for(int j=i+1; j<nums.size(); j++) {
            if(j>i+1 && nums[j]==nums[j-1]) continue;		//b去重
            int left=j+1,right=nums.size()-1;
            while(left<right) {
                long val = (long)nums[i]+nums[j]+nums[left]+nums[right];
                if(val>target) right--;
                else if(val<target) left++;
                else {
                    while(right-1>left && nums[right]==nums[right-1]) right--;
                    while(right>left+1 && nums[left]==nums[left+1]) left++;			//c、d去重
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                    right--;left++;
                }
            }
        } 
    }
    return res;
}

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n,vector<int>(n,0));
    int x1=0,y1=0,x2=n-1,y2=n-1;					//不变量：螺旋角标
    int num=1;
    while(x1<x2&&y1<y2){
        for(int i=y1;i<y2;i++) res[x1][i]=num++;
        for(int i=x1;i<x2;i++) res[i][y2]=num++;
        for(int i=y2;i>y1;i--) res[x2][i]=num++;
        for(int i=x2;i>x1;i--) res[i][y1]=num++;
        x1++;y1++;x2--;y2--;
    }
    if(x1==x2)										//奇偶性补充
        for(int i=y1;i<=y2;i++) res[x1][i]=num++;
    else if(y1==y2)
        for(int i=x1;i<=x2;i++) res[i][y1]=num++;
    return res;
}

//不作排序，返回索引，无需去重
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D, int target) {
    unordered_map<int, int> umap; 								//a+b:count(a+b)
    for (int a : A) 
        for (int b : B) 
            umap[a + b]++;
    
    int count = 0;
    for (int c : C) {
        for (int d : D) {
            if (umap.find(target-(c+d))!=umap.end()) {
                count+=umap[target-(c+d)];
            }
        }
    }
    return count;
}

//需要排序，返回数值，可去重
vector<vector<int>> threeSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for(int i=0; i<nums.size(); i++) {
        if(i>0 && nums[i]==nums[i-1]) continue;		//a去重
        unordered_set<int> s;
        for(int j=i+1; j<nums.size(); j++) {
            if(j>i+2 && nums[j]==nums[j-1]  && nums[j-1]==nums[j-2]) continue;		//b去重
            //if(j>i+1 && nums[j]==nums[j-1]) continue会导致跳过b、c共用同一元素的情况
            int c=target-(nums[i]+nums[j]);
            if(s.find(c)!=s.end()) {
                res.push_back({nums[i],nums[j],c});
                s.erase(c);		//c去重
            }
            else s.insert(nums[j]);
        }
    }
    return res;
}

void setZeroes(vector<vector<int>>& matrix) {
    int m=matrix.size(), n=matrix[0].size();
    vector<bool> row(m, false);
    vector<bool> col(n, false);
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(matrix[i][j]==0) {
                row[i]=col[j]=true;
            }
        }
    } 
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(row[i] || col[j]) {
                matrix[i][j]=0;
            }
        }
    }

    return;
}

int rangeSum(vector<int>& vec, int i, int j) {
    for(int i=1; i<vec.size(); i++) vec[i]+=vec[i-1];
    if(i==0) return vec[j];
    else return vec[j]-vec[i-1];
}

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) {}
};
ListNode* _dummyHead= new ListNode(0,head);
ListNode* head = _dummyHead->next;

vector<ListNode*> equalList(ListNode* head) {
    if(head==NULL || head->next==NULL) return {head,NULL};
    ListNode* slow=head;
    ListNode* fast=head;
    ListNode* pre=head;
    while(fast!=NULL && fast->next!=NULL) {
        pre=slow;
        slow=slow->next;
        fast=fast->next->next;
    }
    pre->next=NULL;
    if(fast==NULL) return {head, slow};			//偶数，自然平分
    else return {head, slow->next};   			//奇数，删除中间节点
}

ListNode* reverseList(ListNode* head) {
    ListNode *tmp;
    ListNode *cur=head;
    ListNode *pre=NULL;
    while(cur!=NULL){							//逐个操作链表节点
        tmp=cur->next;
        cur->next=pre;
        pre=curr;
        cur=tmp;
    }
    return pre;
}
------------------------------------------------------------------------------
ListNode* reverseList(ListNode* head) {
    if(head==NULL || head->next==NULL) return head;
    ListNode *last=reverseList(head->next);
    head->next->next=head;
    head->next=NULL;
    return last;
}

ListNode *detectCycle(ListNode *head) {			//slow:x+y   fast:x+y+n*(y+z)  -->   x=n(y+z)+z
    ListNode* slow=head;
    ListNode* fast=head;
    while(fast!=NULL && fast->next!=NULL) {		//间隔操作链表节点
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast) {
            ListNode* meet=slow;
            ListNode* entry=head;
            while(meet!=entry) {
                meet=meet->next;
                entry=entry->next;
            }
            return entry;
        }
    }
    return NULL;
}

void reverse(vector<char>& s,int start,int end){
    for(int i=start;i<=(start+end)/2;i++){
        swap(s[i],s[end+start-i]);
    }
}
----------------swap--------------------------------
int temp = s[i];
s[i] = s[j];
s[j] = temp;

a[i] = a[i] ^ a[j]; 
a[j] = a[i] ^ a[j]; // a[j] = a[i] ^ a[j] ^ a[j] = a[i]
a[i] = a[i] ^ a[j]; // a[i] = a[i] ^ a[j] ^ a[i] = a[j]

a[i] = a[i] + a[j];
a[j] = a[i] - a[j]; // a[j] = a[i] + a[j] - a[j]
a[i] = a[i] - a[j]; // a[i] = a[i] + a[j] - a[i]

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty()) {
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int res=stOut.top();
        stOut.pop();
        return res;
    }
    
    int peek() {
        int res=this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
private:
    stack<int> stIn;
    stack<int> stOut;
};

int precedence(char op) {
    if((op=='(') return 0;
    else if(op=='+' || op=='-') return 1;
    else if(op=='*' || op=='/') return 2;
    else if (op=='^') return 3;
    else return -1;
}

//中缀 --> 后缀：将中缀按运算顺序加上括号，再将操作符移动到对应括号后，最后删除括号
string infixToPostfix(const string& expression) {
    string postfix="";
    stack<char> st;

    for (int i=0; i<expression.size(); i++) {
        if(expression[i]==' ') continue;
        else if(isalnum(expression[i])) postfix+=expression[i];
        else if(expression[i]=='(') st.push(expression[i]);
        else if (expression[i]==')') {
            while (!st.empty() && st.top()!='(') {
                postfix+=st.top();
                st.pop();
            }
            if(!st.empty()) st.pop();
        }
        else {
            while(!st.empty() && precedence(st.top())>=precedence(expression[i])) {	
                postfix+=st.top();				//当新操作符优先级较低时，处理好前面优先级低的算式
                st.pop();
            }
            st.push(expression[i]);
        }
    }
    while(!st.empty()) {
        postfix+=st.top();
        st.pop();
    }
    return postfix;
}

//中缀 --> 前缀：将中缀按运算顺序加上括号，再将操作符移动到对应括号前，最后删除括号
string infixToPrefix(const string& expression) {
    string prefix="";
    stack<char> st;

    for (int i=expression.size()-1; i>=0; i--) {
        if(expression[i]==' ') continue;
        else if(isalnum(expression[i])) prefix+=expression[i];
        else if(expression[i]==')') st.push(expression[i]);
        else if (expression[i]=='(') {
            while (!st.empty() && st.top()!=')') {
                prefix+=st.top();
                st.pop();
            }
            if(!st.empty()) st.pop();
        }
        else {
            while(!st.empty() && precedence(st.top())>precedence(expression[i])) {
                prefix+=st.top();
                st.pop();
            }
            st.push(expression[i]);
        }
    }
    while(!st.empty()) {
        prefix+=st.top();
        st.pop();
    }
    reverse(prefix.begin(), prefix.end());
    return prefix;
}

// 后缀 --> 中缀：顺序遍历，遇到操作数直接压入栈中，遇到操作符弹出两操作数组成新的表达式并压入栈
string postfixToInfix(string expression) {
    stack<string> st;
    for(int i=0; i<expression.size(); i++) {
        if(!isalnum(expression[i])) { 
            string op2=st.top(); st.pop();
            string op1=st.top(); st.pop();
            string temp="("+op1+expression[i]+op2+")";
            st.push(temp);
        } 
        else st.push(string(1, expression[i]));
    }
    return st.top();
}

// 前缀 --> 中缀：逆序遍历，遇到操作数直接压入栈中，遇到操作符弹出两操作数组成新的表达式并压入栈
string prefixToInfix(string expression) {
    stack<string> st;
    for (int i=expression.size()-1; i>=0; i--) {
        if(!isalnum(expression[i])) {
            string op1=st.top(); st.pop();
            string op2=st.top(); st.pop();
            string temp="("+op1+expression[i]+op2+")";
            st.push(temp);
        } 
        else st.push(string(1, expression[i]));
    }
    return st.top();
}

// 后缀表达式计算：思路类似  后缀 --> 中缀
int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for(int i=0; i<tokens.size(); i++) {
        if(isNum(tokens[i])) st.push(atoi(tokens[i].data()));
        else {
            int num2=st.top(); st.pop();
            int num1=st.top(); st.pop();
            switch (tokens[i][0]) {
                case '+':
                    st.push(num1+num2);
                    break;
                case '-':
                    st.push(num1-num2);
                    break;
                case '*':
                    st.push(num1*num2);
                    break;
                case '/':
                    st.push(num1/num2);
                    break;
            }
        }
    }
    return st.top();
}

// 前缀表达式计算：思路类似  前缀 --> 中缀
int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for(int i=tokens.size()-1; i>=0; i--) {
        if(isNum(tokens[i])) st.push(atoi(tokens[i].data()));
        else {
            int num1=st.top(); st.pop();
            int num2=st.top(); st.pop();
            switch (tokens[i][0]) {
                case '+':
                    st.push(num1+num2);
                    break;
                case '-':
                    st.push(num1-num2);
                    break;
                case '*':
                    st.push(num1*num2);
                    break;
                case '/':
                    st.push(num1/num2);
                    break;
            }
        }
    }
    return st.top();
}
       
// 中缀表达式计算：中缀 --> 前缀（以vector<string>收集postfix）,再计算逆波兰式

// ctype.h：isalpha isdigit isalnum isspace
bool isNum(char it) {return it>='0' && it<='9';}
bool isLetter(char it) {return it>='a' && it<='z';}
bool isSign(char it) {return it=='+' || it=='-' || it=='*' || it=='/';}

// 数字字符串转数字
int AscToInt(const string& s, int& i) {
    int j=i+1;
    while(j<s.size() && isNum(s[j])) j++;
    int len=j-i;
    i=j;
    return atoi(s.substr(i,len).data());
}

// 正负性定义表达式，压缩乘除式
void posORneg(char preSign, int num) {
    switch (preSign) {
        case '+':
            vec.push_back(num);
            break;
        case '-':
            vec.push_back(-num);
            break;
        case '*':
            vec.back()*=num;
            break;
        case '/':
            vec.back()/=num;
            break;
    }
}

// 表达式预处理
void expSpaceDeal(string& s) {
    string tmp;
    for(char ch : s) {
        if(ch!=' ') tmp+=ch;
    }
    s=tmp;
}

void expOneDimDeal(string& s) {
    string tmp;
    for(int i=0; i<s.size(); i++) {
        if(s[i]=='-' && (i==0 || s[i-1]=='(')) tmp+="0-";
        else if(s[i]=='+' && (i==0 || s[i-1]=='(')) tmp+="0+";
        else tmp+=s[i];
    }
    s=tmp;
}

void expSignDeal(string& s) {
    stack<char> st;
    int flag=0;
    string tmp;
    for(int i=0; i<s.size(); i++) {
        if(s[i]=='(') {
        	if(i==0) st.push('+');
            else st.push(s[i-1]);
            if(st.top()=='-') flag=!flag;
        }
        else if(s[i]==')') {
            if(st.top()=='-') flag=!flag;
            st.pop();
        }
        else if(isSign(s[i]) && flag){
            if(s[i]=='+') tmp+='-';
            else tmp+='+';
        }
        else tmp+=s[i];
    }
    s=tmp;
}