C++ 算法题解

1、leetcode #28 implement strStr()

题目地址：https://leetcode.com/problems/implement-strstr/

分析：实现寻找字符串的功能，即实现类似于substr()函数

如果未找到字串，返回-1，找到返回匹配模式串的第一个字符的下标

如果输入的匹配字符串为空，返回0

方法：KMP匹配算法

注意：当主串haystack为空时应输出-1而不是0

int strStr(string haystack, string needle) {
    if(needle == "")   
        return 0;

    //generate next[]
    int next[needle.length()] = {0};
    next[0] = 0;
    int temp = 0;
    for(int i = 1; i < needle.length(); i++){
        temp = next[i-1];
        while(needle[i] != needle[temp] && temp > 0){
            temp = next[temp-1];
        }
        if(needle[i] == needle[temp])
            next[i] = temp + 1;
        else next[i] = 0;
    }

    //KMP search
    int hp = 0,np = 0;
    for(;hp < haystack.length() ; hp++){
        while(haystack[hp] != needle[np] && np) 
            np = next[np - 1];
        if(haystack[hp] == needle[np]) np++;
        if(np == needle.length()){
            return hp - np + 1;
        }
    }
    
    //didn't find
    return -1;
}

2. leetcode #38 count_and_say

题目地址：https://leetcode.com/problems/count-and-say/

递归

string countAndSay(int n){
    if(n == 1) return "1";
    else{
        string str = countAndSay(n-1);
        string result = "";
        char c;
        int counter = 0 , i = 0;
        while(i < str.length()){
            c = str[i];
            counter ++;
            while(str[++i] == c){
                counter++;
            }
            result +=  to_string(counter) + c;
            counter = 0;
        }
        return result;
    }
}

3. 题目如下图

分析：首先需要将字符串分为一个一个的单词，将分离得到的单词压入栈中

工具：#include<sstream>  #include<stack>

#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

void reverse_word_by_word(string str);

int main(){
    
    string str;
    getline(cin,str);
    reverse_word_by_word(str);    
}

void reverse_word_by_word(string str){
    stringstream ss;
    string temp_word;
    stack<string>result;
    ss.str(str);

    //split words and push then in a stack
    while((ss >> temp_word) && !ss.fail()){
        result.push(temp_word);
    }

    //pop these words
    cout << result.top();
    result.pop();
    while(!result.empty()){
        cout << " " << result.top() ;
        result.pop();
    }
    cout << endl;
}

4.题目如下图

分析：实现字符串数字的模拟加法，考虑到一个数字字符串可能很长，比如10000个 “1”，c++中最大变量为long long int，如果单纯的将字符串转换为数字，可能会有溢出问题，故舍弃这种方法而采取模拟加法运算法----设置进位...

注意：本算法只考虑了整数的运算，未考虑到实数

#include <iostream>
#include <sstream>
#include <stack>
#include <cstring>

using namespace std;
/*
## analysis
    #1 length not match, eg. "12345" + "456" = "12801"
    #2 all 0's, "000" + "0" = "0"
    #3 one of them is empty, eg. "" + "123" = "123"
    #4 the final overflow, eg. "9999" + "1" = "100000"
    #5 invalid input
## note
    # the Hex conting method is ot implemented
*/

int sum_of_two_strings(string str1, string str2, int counting_method = 10){

    if(str1 == "" && str2 == ""){
        cout << "Invalid input!" << endl;
        return -1;
    }

    //####chose counting method
    char S ,E;
    switch(counting_method){
        case 10: S='0';E='9';break;
        case 8: S='0';E='7';break;
        case 2: S='0';E='1';break;
        default:cout << "Not supported counting method!"<<endl;return -1;
    }


    stack<char>result;
    bool overflow = 0;
    int temp_add;
    int i = str1.length()-1 , j = str2.length()-1;

    //right alignment, calculate till the short one consumed
    for(; i >= 0 && j >= 0; i-- , j--){
        if(str1[i] < S || str1[i] > E || str2[j] < S || str2[j] > E){
            printf("%s\n", "Invalid input!");
            return -1;
        }else{
            if(overflow){
                temp_add = (str1[i] - S) + (str2[j] - S) + 1;
                if(temp_add > counting_method-1){
                    overflow = 1;
                    result.push(temp_add % counting_method );
                }else{
                    overflow = 0;
                    result.push(temp_add);
                }
            }else{
                temp_add = (str1[i] - S) + (str2[j] - S);
                if(temp_add > counting_method-1){
                    overflow = 1;
                    result.push(temp_add % counting_method );
                }else{
                    overflow = 0;
                    result.push(temp_add);
                }
            }
        }
    }

    //if str1 bigger then str2, calculate the rest of it
    while(i>= 0){
        if(!(S < str1[i] <= E)){
            printf("%s\n", "Invalid input!");
            return -1;
        }else{
            if (overflow)
            {
                int temp_add = (str1[i] - S) + 1;
                if (temp_add > counting_method-1)
                {
                    overflow = 1;
                    result.push(temp_add % counting_method);
                }else{
                    overflow = 0;
                    result.push(temp_add);
                }
            }else{
                result.push((str1[i])-S);
            }
            i--;
        } 
    }
    //if str2 bigger then str1, calculate the rest of it
    while(j >= 0){
        if(!(S < str2[j] <= E)){
            printf("%s\n", "Invalid input!");
            return -1;
        }else{
            if (overflow)
            {
                int temp_add = (str2[j] - S) + 1;
                if (temp_add > counting_method-1)
                {
                    overflow = 1;
                    result.push(temp_add % counting_method );
                }else{
                    overflow = 0;
                    result.push(temp_add);
                }
            }else{
                result.push((str2[j])- S);
            }
            j--;
        }
    }
    //consider the final overflow 
    //eg.99999 + 1 = 1000000(D), the overflow exits throughout the calculation period
    if(overflow){
        result.push(1);
    }

    //get the naive answer, it may include 000018 which the prefix of 0's we don't want
    char result_str[result.size()];
    int index = result.size()-1;
    while(!result.empty()){
        result_str[index--] = (char)(result.top() + S);
        result.pop();
    }
    
    index = sizeof(result_str) / sizeof(char);
    //consume the prefix of 0's
    while((--index >= 0) && result_str[index] == S){;}
    //consider 000 + 0 , we can not consume all the 0's but stay ont 0
    if(index == -1)
        cout << S;
    else{
        //after correct consumed 0's, put the final answer
        while(index >= 0){
            cout << result_str[index--];
        }
    }
    cout << endl;
    return 1;
}

int main(){
    string str1, str2;
    int counting_method, times = 10;

    for(int i = 1; i <= times ; i++){
        cout << "##########  test:" << i << "  ###########" << endl;
        cout << "Chose counting method(2,8,10,16):";
        cin >> counting_method;
        getchar();
        cout << "str1:";
        getline(cin, str1);
        cout << "str2:";
        getline(cin, str2);
        sum_of_two_strings(str1, str2,counting_method);
        cout << endl;
    }

}

5 leetcode #75 sort colors

题目链接：https://leetcode.com/problems/sort-colors/

方法：三路快速 排序 法

void sortColors(vector<int>& nums) {
    int len = nums.size();
    int one_index = 0, two_index = len;
    int pointer = 0;
    while(pointer < two_index){
        if(nums[pointer] == 0){
            swap(nums[pointer++], nums[one_index++]);
        }else if(nums[pointer] == 2){
            swap(nums[pointer],nums[--two_index]);
        }else{pointer++;}
    }
        
}

6. leetcode #167 two sum(2)

题目地址：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int i = 0;
        int j = numbers.size() - 1;
        //int mid = j - ( j - i ) / 2;
        while(i < j){
            if(numbers[i] + numbers[j] == target){
                result.push_back(i+1);
                result.push_back(j+1);
                return result;
            }else if(numbers[i] + numbers[j] < target){
                i ++ ;
            }else{
                j --;
            }
        }

        return result; 
    }

7. leetcode #283 move_zeroes

题目地址：https://leetcode.com/problems/move-zeroes/

void moveZeroes(vector<int>& nums) {
        int pointer = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != 0){
                nums[pointer++] = nums[i];
            }
        } 
        while(pointer < nums.size()){
            nums[pointer++] = 0;
        } 
    }

8. leetcode #51 N-Queens

题目链接：https://leetcode.com/problems/n-queens/

算法分析：以4皇后为例

void N_Queens(std::vector<std::vector<string>> &result, std::vector<string> &NQueen, std::vector<int> &flag, int row , int &n ){
            if(row == n){
                result.push_back(NQueen);
                return;
            }else{
                for(int col = 0; col != n; col ++){
                    if(flag[col] && flag[n + col + row] && flag[n + (2 * n -1) + (n - 1 + col - row)]){
                        flag[col] = flag[n + col + row] = flag[4 * n - 2 + col - row] = 0;
                        NQueen[row][col] = 'Q';
                        N_Queens(result, NQueen, flag, row + 1, n);
                        NQueen[row][col] = '.';
                        flag[col] = flag[n + col + row] = flag[4 * n - 2 + col - row] = 1;
                    }
                }
            }
        }

        std::vector<std::vector<string>> solveNQueens(int n){
            std::vector<string> NQueen(n, string(n, '.'));
            std::vector<int> flag(5 * n - 2, 1);
            std::vector<std::vector<string>> result;
            N_Queens(result, NQueen, flag , 0, n);
            return result;
        }

9 leetcode #2 add two numbers

题目链接：https://leetcode.com/problems/add-two-numbers/

算法分析：

Method1

if l1 and l2 are in the same size, no attention

if l1 is longer than  l2, attention the overflow, eg. [9,9] + [1] = [0,0,1] not [0,10].

if l2 is longer than l1,put the result of l2 to the tail of result list

Method2

recursion

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    //nullptr judgement
    if(l1 == nullptr){
        return l2?l2:NULL;
    }
    if(l2 == nullptr)
        return l1?l1:NULL;

    //teh head and tail of result number list 
    ListNode* head = l1 ,*tail = l1;
    while(l1 && l2 ){
        int temp_add = l1->val + l2->val;
        if(temp_add > 9){   //avoid using >= 10, that needs more time to execute
            temp_add %= 10;
            if(l1->next)
                l1->next->val++;
            else
                l1->next = new ListNode(1);
        }
        l1->val = temp_add;
        tail = l1;
        l1 = l1->next;
        l2 = l2->next;
    }

    //l1 is the longer one, if current val greater than 9, execute this block
    while(l1 && l1->val > 9){
        if(l1->next)
            l1->next->val++;
        else
            l1->next = new ListNode(1);
        l1->val = l1->val % 10;
        l1 = l1->next;
    }

    // l2 is the longer one
    if(l2){
        tail->next = l2;
    }
    
    return head;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2?l2:NULL;
        }
        if(l2 == nullptr)
            return l1?l1:NULL;
        int sum = l1->val + l2->val;
        if(sum > 9){
            sum = sum % 10;
            if( l1->next ){
                l1->next->val++;
            }else{
                l1->next = new ListNode(1);
            }
            if(l2->next == nullptr)
                l2->next = new ListNode(0);
        }
        ListNode*  cur_node = new ListNode(sum);
        cur_node->next = addTwoNumbers(l1->next, l2->next);
        return cur_node;
    }

10 leetcode # 4 median of two sorted array

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/

算法分析：采用归并排序和堆排序。下图时采用归并排序的过程。堆排序采用一个大顶堆和小顶堆，中间值记录median。

//using merge sort 
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums;
        nums.resize(nums1.size() + nums2.size());
        merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),nums.begin() );
        int half_size = nums.size() / 2;
        if(nums.size() % 2){
            return nums[half_size] * 1.0;
        }else{
            return (nums[half_size - 1] + nums[half_size]) / 2.0;
        }
    }



//using heap sort
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       if(nums1.empty()){
            if(nums2.size() % 2 == 0)
                return (nums2[nums2.size() / 2 -1] + nums2[nums2.size() / 2]) / 2.0;
            else 
                return nums2[nums2.size() / 2] * 1.0;
        }
        if(nums2.empty()){
            if(nums1.size() % 2 == 0)
                return (nums1[nums1.size() / 2 -1] + nums1[nums1.size() / 2]) / 2.0;
            else 
                return nums1[nums1.size() / 2] * 1.0;
        }  
        multiset<int> left;  //min heap
        multiset<int> right; //max heap
        vector<int> temp;    //make sure nums1 is the longest vector, so that we can create two heap faster
        if(nums1.size() < nums2.size()){
            temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int index = 0;
        int median;
        int nums1_half = nums1.size() / 2;
        if(nums1.size() % 2){
            index = 0;
            median = nums1[nums1_half];
            while(index < nums1_half)
                left.insert(nums1[index++]);
            while(++index < nums1.size())
                right.insert(nums1[index]);
        }else{
            index = 0;
            median = nums1[nums1_half - 1];
            while(index < nums1_half - 1)
                left.insert(nums1[index++]);
            while(++index < nums1.size())
                right.insert(nums1[index]);
        }
        
        index = 0;
        while(index < nums2.size()){
            if(right.size() > left.size() && right.size() - left.size() > 1){
                left.insert(median);
                median = *right.begin();
                right.erase(right.begin());
            }
            if(left.size() > right.size() && left.size() - right.size() > 1){
                right.insert(median);
                multiset<int>::iterator iter = --left.end();
                median = *iter;
                left.erase(iter);      
            }
            if(nums2[index] >= median){
                right.insert(nums2[index]);
            }else{
                left.insert(nums2[index]);
            }
            index ++ ;   
        }
        
        if(right.size() > left.size() && right.size() - left.size() > 1){
            left.insert(median);
            median = *right.begin();
            right.erase(right.begin());
        }
        if(left.size() > right.size() && left.size() - right.size() > 1){
            right.insert(median);
            multiset<int>::iterator iter = --left.end();
            median = *iter;
            left.erase(iter);      
        }
        
        if(right.size() == left.size()){
            return median;
        }else if(right.size() > left.size()){
            return (median + *(right.begin())) / 2.0;
        }else{
            return (median + *(--left.end())) /2.0;
        }
}

11 leetcode # 3 longest-substring-without-repeating-characters

题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/

算法分析：

int lengthOfLongestSubstring(string s) {
        if(s.length() == 0)
            return 0;
        int result = 0;
        vector<char> temp_chars;
        temp_chars.push_back(s[0]);
        for(int i = 1; i < (int)s.length(); i++){
            vector<char>::iterator iter = find(temp_chars.begin(),temp_chars.end(),s[i]);
            if(iter != temp_chars.end()){
                if(result < temp_chars.size())
                    result = temp_chars.size();
                while(temp_chars[0] != s[i]){
                    temp_chars.erase(temp_chars.begin());
                } 
                temp_chars.erase(temp_chars.begin());
            }
            temp_chars.push_back(s[i]);
            //showchars(temp_chars);
        }
        if(result < temp_chars.size())
            result = temp_chars.size();
        return result;
    }

Linux公社的RSS地址 ： https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址： https://www.linuxidc.com/Linux/2019-06/158952.htm