Cinte's Leetcode Record
0%

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

8. String to Integer (atoi)

第一次
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
class Solution
{
public:
    int myAtoi(string s)
    {
        int sum = 0;
        int positive = 1;
        bool isEntered = false;
        for (const auto &ch : s)
        {
            switch (ch)
            {
            case '+':
                if (!isEntered)
                {
                    positive = 1;
                    isEntered = true;                    
                }
                else
                    return positive * sum;
                break;
            case '-':
                if (!isEntered)
                {
                    positive = -1;
                    isEntered = true;                    
                }
                else
                    return positive * sum;
                break;
            default:
                if (ch >= 48 && ch <= 57)
                {
                    if (!isEntered)
                        isEntered = true;
                    int pop = ch - 48;
                    switch (positive)
                    {
                    case 1:
                        if (sum > INT_MAX / 10 || (sum == INT_MAX / 10 && pop > 7))
                            return INT_MAX;
                        break;
                    case -1:
                        if (-sum < INT_MIN / 10 || (-sum == INT_MIN / 10 && pop >= 8))
                            return INT_MIN;
                        break;
                    }
                    sum = sum * 10 + pop;
                }
                else if (ch != ' ')
                {
                    return positive * sum;
                }else if (ch == ' ' && isEntered)
                {
                    return positive * sum;
                }
            }
        }
        return positive * sum;
    }
};

坑有点多，起初忽视了很多种情况

其中判断是否溢出参考了https://leetcode.com/problems/reverse-integer/solution/

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

3. Longest Substring Without Repeating Characters

第一次
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
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int count = 0;
        int max = 0;
        int index = 0;
        int pre_index = 0;
        unordered_map<char, int> map;
        for (const auto ch : s)
        {
            max = count > max ? count : max;
            if (!map.emplace(ch, index++).second)
            {
                auto t = map[ch];
                map[ch] = index - 1;
                if (t - pre_index < 0)
                {
                    ++count;
                    continue;
                }
                count -= t - pre_index;
                pre_index = t + 1;
            }
            else
            {
                ++count;
            }
        }
        max = count > max ? count : max;
        return max;
    }
};

review

sliding window 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> memo;
        int begin = 0, end = 0, sz = s.size();
        int ret = 0;
        while(end < sz)
        {
            char ch = s[end++];
            ++memo[ch];
            while(memo[ch] > 1)
                --memo[s[begin++]];
            ret = max(ret, end - begin);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> memo;
        int begin = 0, end = 0, sz = s.size();
        int ret = 0;
        while(end < sz)
        {
            char ch = s[end++];
            while(memo.count(ch))
                memo.erase(s[begin++]);
            memo.emplace(ch);
            ret = max(ret, end - begin);
        }
        return ret;
    }
};
但是如果出现重复的字符的话，begin不需要一个一个递增然后判断，只需要移到重复字符的前一个位置即可，于是可以进行优化 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> memo(256, -1);
        int begin = -1, end = 0, ret = 0;
        int sz = s.size();
        for(; end < sz; ++end)
        {
            begin = max(begin, memo[s[end]]); // 如果当前的字符在[begin, end]区域重复了，就把begin移动到前一个s[end]出现的地方，跳跃
            memo[s[end]] = end; // 更新当前字符最后出现的坐标
            ret = max(ret, end - begin);
        }
        return ret;
    }
};
使用hash map 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> memo;
        int begin = 0, end = 0, ret = 0;
        int sz = s.size();
        for(; end < sz; ++end)
        {
            begin = max(begin, memo[s[end]]);
            memo[s[end]] = end + 1; // map中默认初始化为0，所以这里加以改变
            ret = max(ret, end - begin + 1);
        }
        return ret;
    }
};

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

2. Add Two Numbers

第一次
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
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *result = new ListNode();
        ListNode *point = result;
        unsigned int c = 0;
        do
        {
            int sum;
            try
            {
                if (l1 != 0 && l2 != 0)
                {
                    sum = l1->val + l2->val + c;
                    l1 = l1->next;
                    l2 = l2->next;
                    throw "case 1";
                }
                else if (l1 != 0 && l2 == 0)
                {
                    sum = l1->val + c;
                    l1 = l1->next;
                    throw "case 2";
                }
                else if (l1 == 0 && l2 != 0)
                {
                    sum = l2->val + c;
                    l2 = l2->next;
                    throw "case 3";
                }
                else
                {
                    sum = 0;
                }
            }
            catch (...)
            {
                point->val = sum % 10;
                c = sum / 10;
                if (l1 != 0 || l2 != 0)
                {
                    point->next = new ListNode();
                    point = point->next;
                }
                else
                {
                    if (c != 0)
                    {
                        point->next = new ListNode(c);
                    }
                }
            }
        } while (l1 != 0 || l2 != 0);

        return result;
    }
};

第一次结果

Read more »

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

1. 两数之和

hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i = 0, sz = nums.size(); i < sz; ++i)
        {
            if(map.count(target - nums[i]))
                return {map[target - nums[i]], i};
            else
                map.emplace(nums[i], i);
        }
        return {};
    }
};