Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

19. Remove Nth Node From End of List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* target = head;
        int size = 0;
        ListNode* iterator = head;
        while (iterator != nullptr)
        {
            ++size;
            iterator = iterator->next;
        }

        for (int i = 0; i < size - n - 1; ++i)
        {
            target = target->next;
        }
        if (size - n - 1 == -1)
        {
            head = head->next;
        }
        if (target->next != nullptr)
            target->next = target->next->next;
        return head;
    }
};
discussion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *start = new ListNode();
        ListNode *fast = start, *slow = start;
        start->next = head;
        for (int i = 0; i < n + 1; ++i)
        {
            fast = fast->next;
        }
        while(fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return start->next;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode ret;
        ret.next = head;
        ListNode* runner = &ret, *walker = &ret;
        while(n--)
            runner = runner->next;
        while(runner->next)
        {
            walker = walker->next;
            runner = runner->next;
        }
        walker->next = walker->next->next;
        return ret.next;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

15. 3Sum

自己的**方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        if(nums.size() < 3) return ret;
        sort(nums.begin(),nums.end());
        if(nums[0] > 0) return ret;
        int bias = 0;
        unordered_set<int> nummm;
        for(auto& num : nums)
        {
            if(nummm.find(num) != nummm.end())
            {
                ++bias;
                continue;
            }else
            {
                nummm.insert(num);
            }
            unordered_set<int> set;
            int target = -num;
            for(size_t i = ++bias; i < nums.size(); ++i)
            {
                if(set.find(target - nums[i]) != set.end())
                {
                    ret.push_back({-target, target - nums[i], nums[i]});
                    set.insert(nums[i]);
                    while(i + 1 < nums.size() && nums[i] == nums[i + 1]) ++i;
                    continue;
                }
                set.insert(nums[i]);
            }
        }
        return ret;
    }
};
改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ret;
        if (nums.size() < 3)
            return ret;
        sort(nums.begin(), nums.end());
        if (nums[0] > 0)
            return ret;
        int bias = 0;
        for (size_t i = 0; i < nums.size(); ++i)
        {
            while (i != 0 && nums[i] == nums[i - 1] && i + 1 < nums.size())
            {
                ++i;
                ++bias;
            }
            unordered_set<int> set;
            int target = -nums[i];
            for (size_t i = ++bias; i < nums.size(); ++i)
            {
                if (set.find(target - nums[i]) != set.end())
                {
                    ret.push_back({-target, target - nums[i], nums[i]});
                    set.insert(nums[i]);
                    while (i + 1 < nums.size() && nums[i] == nums[i + 1])
                        ++i;
                    continue;
                }
                set.insert(nums[i]);
            }
        }
        return ret;
    }
};
discussion里的O(n^2)方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n < 3 || nums.front() > 0)
            return {};
        for (size_t i = 0; i < n; ++i)
        {
            if(i > 0 && nums[i] == nums[i - 1]) 
                continue;
            int low = i + 1, high = n - 1;
            int num = -nums[i];
            while (low < high)
            {
                if (nums[low] + nums[high] == num)
                {
                    ret.push_back({nums[i], nums[low], nums[high]});
                    while (low < high && nums[low] == nums[low + 1])
                        ++low;
                    while (low < high && nums[high] == nums[high - 1])
                        --high;
                    ++low;
                    --high;
                }else if(nums[low] + nums[high] < num)
                {
                    ++low;
                }else
                {
                    --high;
                }
            }
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

17. Letter Combinations of a Phone Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size())
        {
            backtrack("", digits);
        }else
        {
            return {};
        }
    }

private:
    vector<string> ret;
    unordered_map<char, vector<char>> phone{{'2', {'a', 'b', 'c'}}, {'3', {'d', 'e', 'f'}}, {'4', {'g', 'h', 'i'}}, {'5', {'j', 'k', 'l'}}, {'6', {'m', 'n', 'o'}}, {'7', {'p', 'q', 'r', 's'}}, {'8', {'t', 'u', 'v'}}, {'9', {'w', 'x', 'y', 'z'}}};
    void backtrack(string comb, string digit)
    {
        if(!digit.size())
        {
            ret.push_back(comb);
        }

        for(auto& ch : phone[digit[0]])
        {
            backtrack(comb + ch, digit.substr(1));
        }
    }
};

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
            return {};
        vector<string> ret;
        string tmp;
        backTrack(ret, tmp, digits, 0);
        return ret;
    }
private:
    unordered_map<int, vector<char>> map{
        {2, {'a', 'b', 'c'}},
        {3, {'d', 'e', 'f'}},
        {4, {'g', 'h', 'i'}},
        {5, {'j', 'k', 'l'}},
        {6, {'m', 'n', 'o'}},
        {7, {'p', 'q', 'r', 's'}},
        {8, {'t', 'u', 'v'}},
        {9, {'w', 'x', 'y', 'z'}}
        };
    void backTrack(vector<string>& ret, string& tmp, string& digits, int i)
    {
        if(i == digits.size())
        {
            ret.push_back(tmp);
            return;
        }
        for(auto& ch : map[digits[i] - '0'])
        {
            tmp += ch;
            backTrack(ret, tmp, digits, i + 1);
            tmp.pop_back();
        }
    }
};

还有一种

先把一个字母依次添加，然后再依次网上衔接各种情况

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

6. ZigZag Conversion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution
{
public:
    string convert(string s, int numRows)
    {
        int size = s.size();
        if (numRows == 1)
        {
            return s;
        }
        int col = size / (numRows + numRows - 2);
        int addon = size - col * (numRows + numRows - 2);
        string result = "";
        int location = 0;
        for (size_t i = 0; i < numRows; ++i)
        {
            int bias;
            if (i == numRows - 1)
            {
                int temp = col + (addon >= numRows ? 1 : 0);
                for (int i = 0; i < temp; ++i)
                {
                    result += string(1, s[location + i*(numRows+numRows-2)]);
                }
                ++location;
                continue;
            }
            else if (i == 0)
            {
                int temp = col + (addon ? 1 : 0);
                for (int i = 0; i < temp; ++i)
                {
                    result += string(1, s[location + i * (numRows + numRows - 2)]);
                }
                ++location;
                continue;
            }
            else if (addon >= 2 * numRows - 2 - (i - 1))
            {
                bias = 2;
            }
            else if (addon >= i + 1)
            {
                bias = 1;
            }
            else
            {
                bias = 0;
            }
            int temp = col + col + bias;
            for (int i = 0; i < temp; ++i)
            {
                if(i%2==0)
                    result += string(1, s[location + (i/2) * (numRows + numRows - 2)]);
                else
                    result += string(1, s[location + (i/2) * (numRows + numRows - 2)+2*numRows-4-2*(location-1)]);
            }   
            ++location;
        }
        return result;
    }
};
Solution中的两种方法
按行排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1)
            return s;
        vector<string> r(min(numRows, (int)(s.size())));
        int curRow = 0;
        bool goDown = true;
        for(auto ch : s)
        {
            r[curRow] += ch;
            curRow += goDown ? 1 : -1;
            if(curRow == 0 || curRow == numRows - 1)
                goDown = !goDown;
        }
        string ret;
        for(auto& str : r)
            ret += str;
        return ret;
    }
};
按行访问

找到每行的字母在s中字母位置和他行数之间的关系

Posted on Edited on In Disqus:
Symbols count in article: 641 Reading time ≈ 1 mins.

14. Longest Common Prefix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        if (strs.empty())
        {
            return "";
        }
        int minSize = strs[0].size();
        int minSizeStrIndex = 0;
        for (std::size_t i = 0; i < strs.size(); ++i)
        {
            if (strs[i].size() < minSize)
            {
                minSize = strs[i].size();
                minSizeStrIndex = i;
            }
        }
        string chs = "";
        int bias = 0;
        for (const auto &ch : strs[minSizeStrIndex])
        {
            for (std::size_t i = 0;i < strs.size();++i)
            {
                if (i == minSizeStrIndex)
                    continue;
                if (ch != strs[i][bias])
                    return chs;
            }
            chs += ch;
            ++bias;
        }
        return chs;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

13. Roman to Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution
{
public:
    int romanToInt(string s)
    {
        unordered_map<string, int> map{{"I", 1}, {"IV", 4}, {"V", 5}, {"IX", 9}, {"X", 10}, {"XL", 40}, {"L", 50}, {"XC", 90}, {"C", 100}, {"CD", 400}, {"D", 500}, {"CM", 900}, {"M", 1000}};
        int size = s.size();
        int num = 0;

        for (int i = size - 1; i >= 0; --i)
        {
            string now(1, s[i]);
            if (i == 0)
            {
                return num + map[now];
            }
            string before(1, s[i - 1]);
            string sub = before + now;
            if (map.find(sub) != map.end())
            {
                num += map[sub];
                --i;
            }
            else
            {
                num += map[now];
            }
        }
        return num;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int romanToInt(string s) {
        string roman[]{"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int nums[]{1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int ret = 0;
        int index = 12, length = s.size();
        for(int i = 0; i < length; ++i)
        {
            string si = s.substr(i, 1);
            string d = i < length - 1 ? s.substr(i, 2) : "";
            while(index >= 0)
            {
                if(roman[index] == d)
                {
                    ret += nums[index];
                    ++i;
                    break;
                }else if(roman[index] == si)
                {
                    ret += nums[index];
                    break;
                }else
                    --index;
            }
        }
        return ret;
    }
};
solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int romanToInt(string s) {
        int ret = 0;
        for(int i = 0, sz = s.size(); i < sz; ++i)
        {
            int num = symbolValues[s[i]];
            if(i < sz - 1 && num < symbolValues[s[i + 1]])
                ret -= num;
            else
                ret += num;
        }
        return ret;
    }
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

4. Median of Two Sorted Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        // 有必要保证在短的上面遍历，如果在长的上的话
        // j = (m + n + 1) / 2 - i中 i可能>n，则j可能<0
        if(m > n)
        {
            nums1.swap(nums2);
            swap(m, n);
        }
        if(m == 0)
            return (n & 1) ? (nums2[n / 2]) : (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
        int lo = 0, hi = m; // 为了让结果可以靠向m，这里的hi需要定义为m
        while(lo <= hi)  // 相等后进入最后计算一次，然后得出解
        {
            int i = lo + (hi - lo) / 2, j = (m + n + 1) / 2 - i; // 推导过程中假设是奇数的情况让左边多一个，则i + j = m + n - i - j，如果是偶数那就相同，此时由于这个除法是向下取整的，所以偶数和奇数情况可以合并
            if(i > 0 && nums1[i - 1] > nums2[j]) // 本来是需要i>0 && j < n，但是由于满足n >= m，当i > 0时，j = (m + n + 1) / 2 - i <= (m + n + 1) / 2 <= (m + n + 1) / 2 <= m + 1/2 < m
                hi = i - 1;
            else if(i < m && nums2[j - 1] > nums1[i]) // j > 0 && i < m, 同上证明
                lo = i + 1;
            else
            {
                // 几种边缘情况处理
                int left, right;

                if(i == 0)
                    left = nums2[j - 1];
                else if(j == 0)
                    left = nums1[i - 1];
                else
                    left = max(nums1[i - 1], nums2[j - 1]);

                if((m + n) & 1) // 假设的是左半边多一个
                    return left;

                if(i == m)
                    right = nums2[j];
                else if(j == n)
                    right = nums1[i];
                else
                    right = min(nums1[i], nums2[j]);

                return (left + right) / 2.0;
            }
        }
        return 0;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 542 Reading time ≈ 1 mins.

12. Integer to Roman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string intToRoman(int num) {
        string roman[]{"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int nums[]{1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        string result = "";
        int i = size(nums) - 1;
        while ( num > 0 )
        {
            while ( num >= nums[i] )
            {
                num -= nums[i];
                result += roman[i];
            }
            --i;
        }
        return result;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 512 Reading time ≈ 1 mins.

9. Palindrome Number

第一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
public:
    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
        else
        {
            if(reverse(x) == x)
            {
                return true;
            }else
            {
                return false;
            }
        }
    }

    int reverse(int x)
    {
        int rev = 0;
        while (x != 0)
        {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10) && (pop > INT_MAX % 10))
                return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10) && (pop < INT_MIN % 10))
                return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 338 Reading time ≈ 1 mins.

7. Reverse Integer

第一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
public:
    int reverse(int x)
    {
        int rev = 0;
        while (x != 0)
        {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10) && (pop > INT_MAX % 10))
                return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10) && (pop < INT_MIN % 10))
                return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};