Welcome to MDGSF's Blog!

This is my github blog

[算法学习][leetcode] 387 First Unique Character in a String

2017-09-02

mdgsf

Art

Leetcode

https://leetcode.com/problems/first-unique-character-in-a-string/description/

题目

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

题目翻译

题目解析

参考答案

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int firstUniqChar(string s) {

        int aiANSI[128] = { 0 };

        for (char c : s)
        {
            aiANSI[c]++;
        }

        for (int i = 0; i < s.size(); i++)
        {
            if (aiANSI[s[i]] == 1)
            {
                return i;
            }
        }

        return -1;
    }
};

int main()
{
    Solution o;
    cout << o.firstUniqChar("loveleetcode") << endl;
    return 0;
}

Read All

[算法学习][leetcode] 383 Ransom Note

2017-09-02

mdgsf

Art

Leetcode

https://leetcode.com/problems/ransom-note/description/

题目

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

题目翻译

题目解析

参考答案

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {

        int aiANSI[128] = { 0 };
        for (char c : magazine)
        {
            aiANSI[c]++;
        }

        for (char c : ransomNote)
        {
            if (aiANSI[c] <= 0)
            {
                return false;
            }
            else
            {
                aiANSI[c]--;
            }
        }
        return true;
    }
};

int main()
{
    Solution o;
    cout << o.canConstruct("a", "b") << endl;
    cout << o.canConstruct("aa", "aab") << endl;
    return 0;
}

Read All

[算法学习][leetcode] 350 Intersection of Two Arrays II

2017-09-02

mdgsf

Art

Leetcode

https://leetcode.com/problems/intersection-of-two-arrays-ii/description/

题目

Given two arrays, write a function to compute their intersection.

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目翻译

题目解析

参考答案

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

        vector<int> result;

        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int i = 0;
        int j = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] == nums2[j])
            {
                result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if (nums1[i] < nums2[j])
            {
                i++;
            }
            else
            {
                j++;
            }
        }

        return result;
    }
};

int main()
{
    return 0;
}

Read All

[算法学习][leetcode] 401 Binary Watch

2017-09-01

mdgsf

Art

Leetcode

https://leetcode.com/problems/binary-watch/description/

题目

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

题目翻译

题目解析

参考答案

排列组合

#include <iostream>
#include <string>
using namespace std;


void func(const string & strSource, const int iMaxNum, const int iSelectNum,
    int iCurIndex, int iCurLeftNum, string & strCurResult)
{
    if (iCurLeftNum == 0)
    {
        cout << strCurResult << endl;
        return;
    }

    for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
    {
        strCurResult.push_back(strSource[i]);
        func(strSource, iMaxNum, iSelectNum, i + 1, iCurLeftNum - 1, strCurResult);
        strCurResult.pop_back();
    }
}


int main()
{
    string strResult;
    func("abcdef", 6, 2, 0, 2, strResult);
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;


class Solution {
public:
    Solution()
        : hour(4, vector<string>()),
        minute(6, vector<string>())
    {
        int i;

        for (i = 0; i < 4; i++)
        {
            int iCurResult = 0;
            func(4, 0, i, iCurResult, hour[i]);
        }

        for (i = 0; i < 6; i++)
        {
            int iCurResult = 0;
            func(6, 0, i, iCurResult, minute[i]);
        }

        vPrint();
    }

    void vPrint()
    {
        for (int i = 0; i < 4; i++)
        {
            vector<string>::iterator iter = hour[i].begin();
            while (iter != hour[i].end())
            {
                cout << *iter << " ";
                ++iter;
            }
            cout << endl;
        }
        cout << endl;

        for (int i = 0; i < 6; i++)
        {
            vector<string>::iterator iter = minute[i].begin();
            while (iter != minute[i].end())
            {
                cout << *iter << " ";
                ++iter;
            }
            cout << endl;
        }
    }

    vector<string> readBinaryWatch(int num)
    {

    }

private:

    void func(const int iMaxNum, int iCurIndex, int iCurLeftNum, int iCurResult, vector<string> & vecResult)
    {
        if (iCurLeftNum == 0)
        {
            char acResult[10] = { 0 };
            sprintf(acResult, "%d", iCurResult);
            vecResult.push_back(acResult);
            return;
        }

        for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
        {
            iCurResult += pow(2, i);
            func(iMaxNum, i + 1, iCurLeftNum - 1, iCurResult, vecResult);
            iCurResult -= pow(2, i);
        }
    }

    vector<vector<string>> hour;
    vector<vector<string>> minute;
};

int main()
{
    Solution o;
    return 0;
}

最终

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;


class Solution {
public:
    Solution()
        : hour(4, vector<string>()),
        minute(6, vector<string>())
    {
        int i;

        for (i = 0; i < 4; i++)
        {
            int iCurResult = 0;
            func(4, 0, i, iCurResult, hour[i], 12, false);
        }

        for (i = 0; i < 6; i++)
        {
            int iCurResult = 0;
            func(6, 0, i, iCurResult, minute[i], 60, true);
        }

        vPrint();
    }

    void vPrint()
    {
        for (int i = 0; i < 4; i++)
        {
            vector<string>::iterator iter = hour[i].begin();
            while (iter != hour[i].end())
            {
                cout << *iter << " ";
                ++iter;
            }
            cout << endl;
        }
        cout << endl;

        for (int i = 0; i < 6; i++)
        {
            vector<string>::iterator iter = minute[i].begin();
            while (iter != minute[i].end())
            {
                cout << *iter << " ";
                ++iter;
            }
            cout << endl;
        }
        cout << endl;
    }

    vector<string> readBinaryWatch(int num)
    {
        vector<string> vecResult;

        for (int i = 0; i <= num; i++)
        {
            if (i <= 3)
            {
                int j = num - i;
                if (0 <= j && j <= 5)
                {
                    vector<string>::iterator iterHour = hour[i].begin();
                    while (iterHour != hour[i].end())
                    {

                        vector<string>::iterator iterMinute = minute[j].begin();
                        while (iterMinute != minute[j].end())
                        {
                            vecResult.push_back(*iterHour + ":" + *iterMinute);
                            ++iterMinute;
                        }

                        ++iterHour;
                    }
                }
            }
        }
        return vecResult;
    }

private:

    void func(const int iMaxNum, int iCurIndex, int iCurLeftNum, int iCurResult, vector<string> & vecResult, const int iMaxValue, bool bFormatZero)
    {
        if (iMaxValue <= iCurResult)
        {
            return;
        }

        if (iCurLeftNum == 0)
        {
            char acResult[10] = { 0 };
            sprintf(acResult, bFormatZero ? "%02d" : "%d", iCurResult);
            vecResult.push_back(acResult);
            return;
        }

        for (int i = iCurIndex; i + iCurLeftNum <= iMaxNum; i++)
        {
            iCurResult += pow(2, i);
            func(iMaxNum, i + 1, iCurLeftNum - 1, iCurResult, vecResult, iMaxValue, bFormatZero);
            iCurResult -= pow(2, i);
        }
    }

    vector<vector<string>> hour;
    vector<vector<string>> minute;
};

int main()
{
    Solution o;
    vector<string> vecResult = o.readBinaryWatch(2);
    vector<string>::iterator iter = vecResult.begin();
    while (iter != vecResult.end())
    {
        cout << *iter << endl;
        ++iter;
    }
    return 0;
}

Read All

[算法学习][leetcode] 415 Add Strings

2017-08-31

mdgsf

Art

Leetcode

https://leetcode.com/problems/add-strings/description/

题目

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目翻译

题目解析

参考答案

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string addStrings(string num1, string num2) {

        string strResult;
        int iFlag = 0;

        int iIdx1 = num1.size() - 1;
        int iIdx2 = num2.size() - 1;
        while (iIdx1 >= 0 && iIdx2 >= 0)
        {
            int iSum = (num1[iIdx1] - '0') + (num2[iIdx2] - '0') + iFlag;
            if (iSum >= 10)
            {
                iFlag = 1;
                iSum -= 10;
            }
            else
            {
                iFlag = 0;
            }

            strResult.append(1, iSum + '0');

            iIdx1--;
            iIdx2--;
        }

        while (iIdx1 >= 0)
        {
            int iSum = (num1[iIdx1] - '0') + iFlag;
            if (iSum >= 10)
            {
                iFlag = 1;
                iSum -= 10;
            }
            else
            {
                iFlag = 0;
            }

            strResult.append(1, iSum + '0');

            iIdx1--;
        }

        while (iIdx2 >= 0)
        {
            int iSum = (num2[iIdx2] - '0') + iFlag;
            if (iSum >= 10)
            {
                iFlag = 1;
                iSum -= 10;
            }
            else
            {
                iFlag = 0;
            }

            strResult.append(1, iSum + '0');

            iIdx2--;
        }

        if (iFlag > 0)
        {
            strResult.append(1, '1');
        }

        int i = 0;
        int j = strResult.size() - 1;
        while (i < j)
        {
            int temp = strResult[i];
            strResult[i] = strResult[j];
            strResult[j] = temp;
            i++;
            j--;
        }

        return strResult;
    }
};

int main()
{
    string num1 = "1";
    string num2 = "9";
    Solution o;
    string strResult = o.addStrings(num1, num2);
    cout << strResult << endl;
    return 0;
}

Read All

[算法学习][leetcode] 414 Third Maximum Number

2017-08-31

mdgsf

Art

Leetcode

https://leetcode.com/problems/third-maximum-number/description/

题目

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

题目翻译

题目解析

参考答案

set 遍历的时候，会从小到大。

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> setThirdMax;
        vector<int>::iterator iter = nums.begin();
        while (iter != nums.end())
        {
            setThirdMax.insert(*iter);
            if (setThirdMax.size() > 3)
            {
                setThirdMax.erase(setThirdMax.begin());
            }
            ++iter;
        }

        return setThirdMax.size() == 3 ? *setThirdMax.begin() : *setThirdMax.rbegin();
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(4);

    Solution o;
    int iResult = o.thirdMax(nums);
    cout << iResult << endl;
    return 0;
}

Read All

46/97