1.最长回文子串

class Solution {
public:
    string isPalindrome(string& s, int left, int right) {
        while (left >= 0 && right <= s.length() - 1 && s[left] == s[right]) {
            left --;
            right ++;
        }
        return s.substr(left+1, right-left-1);
    }
    
    string longestPalindrome(string s) {
        if (s.empty()) return s;
        int left = 0,  right = 0;
        string longestpld = "";
        for (int start = 0; start < s.length(); start ++) {
            string str = isPalindrome (s, start,start);
            if (longestpld.length() < str.length()) longestpld = str;
            str = isPalindrome (s, start,start + 1);
            if (longestpld.length() < str.length()) longestpld = str;
        }
        return longestpld;
    }
};

 2. 快速排序

void quicksort(int *a, int start, int end) {
    if (start >= end) {
        return;
    }
    int right = end;
    int left = start;
    int middle = a[(right+left)/2];
    while (left <= right) {
        while (left <= right && a[left] < middle) 
            left++;
        while (left <= right && a[right] > middle) 
            right--;
        if (left <= right) {
            int temp = a[left];
            a[left] = a[right];
            a[right]   = temp;
            left++;
            right--;
        }
    }
    quicksort (a, start, right);
    quicksort (a, left, end);
}

3. 归并排序

#include <iostream>
using namespace std;


void merge(int *a, int start, int end, int *temp) {
    int middle = (start +  end)/2;
    int left = start;
    int right = middle +1;
    int index = left;
    while(left <= middle && right <= end) {
        if (a[left] <= a[right]){
            temp[index++] = a[left++];
        }
        else {
            temp[index++] = a[right++];
        }
    }
    while (left <= middle) {
        temp[index++] = a[left++];
    }
    while (right <= end) {
        temp[index++] = a[right++];
    }
    for ( int i = start; i<= end; i++){
        a[i] = temp[i];
    }
}

void mergesort(int *a, int start, int end, int *temp) {
    if (start >= end) {
        return;
    }
    mergesort(a, start, (start+end)/2, temp);
    mergesort(a, (start+end)/2 + 1, end, temp);
    merge(a, start, end, temp);
}

int main(int argc, char* argv[]){
    int a[] = {2,8,4,10,3,5,7,9};
    const int num = sizeof(a)/sizeof(a[0]);
    int b[num];
    mergesort(a, 0, num - 1, b);
    for (int i = 0; i< sizeof(a)/sizeof(a[0]); i++){
        cout << a[i] <<endl;
    }
}

 4. 快速选择排序

#include <iostream>
using namespace std;

int quickselect(int *a, int start, int end, int k) {
    if (start >= end) {
        return a[start];
    }
    int left = start;
    int right = end;
    int middle = a[(start+end)/2];
    while (left <= right) {
        while (left <= right && a[left] > middle)
            left++;
        while (left <= right && middle > a[right])
            right--;
        if (left <= right) {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            left++;
            right--;
        }
    }
    if ( start +k -1 <= right) {
        return quickselect (a, start, right, k);
    }
    else if(start +k -1 >= left) {
        return quickselect (a, left, end, k - (left - start)) ;
    }
    return a[right+1];
}

int main(int argc, char* argv[]){
    int a[] = {2,8,4,10,3,5,7,9};
    const int num = sizeof(a)/sizeof(a[0]);
    int k = 3;
    int n = quickselect(a, 0, num - 1, k);
    cout << n << endl;
}

5.二分法

 三数之和

class Solution {
public:
    void towsum (vector<int>& nums, int index, vector<vector<int>>& results) {
        int start = index + 1;
        int end = nums.size()-1;
        int target = -nums[index];
        while(start < end) {
            if (nums[start] + nums[end] > target) {
                end--;
            }
            else if (nums[start] + nums[end] < target) {
                start++;
            }
            else {
                results.push_back(vector<int>{-target, nums[start],nums[end]});
                start++;
                end--;
                while (start < end && nums[start] == nums[start-1]){
                    start++;
                }
            }
        }
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> results;
        if (nums.size()<3){
            return results;
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i<nums.size()-2; i++){
            if (i!=0 && nums[i] == nums[i-1]) 
                continue;
            towsum(nums, i, results);
        }
        return results;
    }
};

三角形个数

class Solution {
public:
    /**
     * @param s: A list of integers
     * @return: An integer
     */
    int getnum(vector<int> &s, int index){
        int left = 0;
        int right = index-1;
        int ans = 0;
        while (left < right){
            if (s[left] + s[right] > s[index]) {
                ans += right - left;
                right--;
            }
            else {
                left++;
            }
        }
        return ans;
    }

    int triangleCount(vector<int> &s) {
        if (s.size()<3) {
            return 0;
        }
        sort(s.begin(), s.end());
        int ans = 0;
        for (int i = 2; i<s.size(); i++) {
            ans += getnum(s, i);
        }
        return ans;
    }
};

四数之和

class Solution {
public:
    /**
     * @param numbers: Give an array
     * @param target: An integer
     * @return: Find all unique quadruplets in the array which gives the sum of zero
     *          we will sort your return value in output
     */
    void twosum (vector<int> &numbers, int index1, int index2, long target, vector<vector<int>>& res) {
        int left = index2 + 1;
        int right = numbers.size() - 1;
        while(left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            }    
            else if (numbers[left] + numbers[right] < target) {
                left++;
            }
            else {
                res.push_back(vector<int> {numbers[index1], numbers[index2], numbers[left], numbers[right]});
                left++;
                right--;
                while (left < right && numbers[left] == numbers[left-1]){
                    left++;
                }
            }
        }
    }
    vector<vector<int>> fourSum(vector<int> &numbers, int target) {
        vector<vector<int>> res;
        if (numbers.size()<4){
            return res;
        }
        sort (numbers.begin(), numbers.end());
        for (int i = 0; i<numbers.size()-3; i++){
            if (i != 0 && numbers[i] == numbers[i-1])
                continue;
            for (int j = i+1; j<numbers.size()-2; j++){
                if (j != i+1 && numbers[j] == numbers[j-1])
                    continue;
                twosum(numbers, i, j, (long)target-(numbers[i] + numbers[j]), res);
            }
        }
        return res;
    }
};

四数组的四数之和

class Solution {
public:
    /**
     * @param a: a list
     * @param b: a list
     * @param c: a list
     * @param d: a list
     * @return: how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero
     */
    int fourSumCount(vector<int> &a, vector<int> &b, vector<int> &c, vector<int> &d) {
        if (!a.size() || !b.size() || !c.size() || !d.size()){
            return 0;
        }
        unordered_map <int, int> hashTable;
        int res = 0;
        for (int i = 0; i < a.size(); i++){
            for (int j = 0; j < b.size(); j++){
                hashTable[a[i]+b[j]]++;
            }
        }
        for (int p = 0; p < c.size(); p++){
            for (int q = 0; q < d.size(); q++){
                int num = c[p] + d[q];
                if (hashTable.find(-num) != hashTable.end()){
                    res += hashTable[-num];
                }
            }
        }
        return res;
    }
};