Cinte's Leetcode Record
0%

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

剑指 Offer 58 - II. 左旋转字符串

和189. Rotate Array一样

转转转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s, 0, s.size() - 1);
        reverse(s, 0, s.size() - n - 1);
        reverse(s, s.size() - n, s.size() - 1);
        return s;
    }
private:
    void reverse(string& s, int start, int end)
    {
        while(start < end)
            swap(s[start++], s[end--]);
    }
};

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

剑指 Offer 53 - I. 在排序数组中查找数字 I

参考34. Find First and Last Position of Element in Sorted Array

直接遍历
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ret = 0;
        for(auto& num : nums)
            ret += num == target ? 1 : 0;
        return ret;
    }
};

O(n)

二分
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 search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size(), mid;
        int ret = 0;
        while(lo < hi)
        {
            mid = lo + ((hi - lo) >> 1);
            if(nums[mid] == target)
            {
                ++ret;
                break;
            }
            else if(nums[mid] > target)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        int i = mid - 1;
        while(i >= 0 && nums[i--] == target)
            ++ret;
        i = mid + 1;
        while(i <= nums.size() - 1 && nums[i++] == target)
            ++ret;
        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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        int left = hi; // 最后保留一个等于目标的左边界
        if(nums[lo] != target)
            return 0;
        hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = ((lo + hi) >> 1) + 1; // 偏向右边
            if(nums[mid] <= target)
                lo = mid;
            else
                hi = mid - 1;
        }
        // 保留一个等于左边的左边界
        return lo - left + 1;
    }
};
v.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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size() - 1;
        while(lo <= hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        // 当他们相等时候，进入会出现hi在lo的前面一位，即hi是左边界而lo是左边界右边一个，hi!=target而lo==target
        int left = hi;
        if(lo <= nums.size() - 1 && nums[lo] != target) // lo如果不等于的话，那就直接跳出
            return 0;
        hi = nums.size() - 1;
        while(lo <= hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] <= target)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        // lo是右边界
        return lo - left - 1;
    }
};

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

剑指 Offer 58 - I. 翻转单词顺序

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
class Solution {
public:
    string reverseWords(string s) {
        if(s.empty())
            return "";
        string ret = "";
        int end = s.size() - 1;
        while(end >= 0 && s[end] == ' ')
            --end;
        if(end < 0)
            return "";
        for(int i = end; i >= -1; --i)
        {
            if(i == -1 || s[i] == ' ')
            {
                ret.append(s.substr(i + 1, end - i));
                while(i >= 0 && s[i] == ' ')
                    --i;
                end = i;
                if(end < 0)
                    break;
                ret.append(" ");
            }
        }
        return ret;
    }
};

T(n) : O(n)

S(n) : O(n)

review

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int end = s.size();
        for(int i = s.size() - 1; i >= -1; --i) {
            if(i == -1 || s[i] == ' ') {
                if(i != end - 1)
                    ret += s.substr(i + 1, end - i - 1) + " ";
                end = i;
            }
        }
        ret.pop_back();
        return ret;
    }
};

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

剑指 Offer 47. 礼物的最大价值

最简单的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        for(int i = 1; i < grid.size(); ++i)
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < grid[0].size(); ++i)
            grid[0][i] += grid[0][i - 1];
        for(int i = 1; i < grid.size(); ++i)
            for(int j = 1; j < grid[0].size(); ++j)
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]); 
        return grid.back().back();
    }
};

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

剑指 Offer 46. 把数字翻译成字符串

BackTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int translateNum(int num) {
        string strs = to_string(num);
        backTrack(strs, 0);
        return ret;
    }
private:
    int ret = 0;
    void backTrack(string& nums, int cur)
    {
        if(cur >= nums.size() - 1)
        {
            ++ret;
            return;
        }
        backTrack(nums, cur + 1);
        auto sum = (nums[cur] - '0') * 10 + nums[cur + 1] - '0';
        if(nums[cur] != '0' && sum < 26 && sum > 0)
            backTrack(nums, cur + 2);
    }
};
dp

version.1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int translateNum(int num) {
        string str = to_string(num);
        vector<int> dp(str.size());
        dp[0] = 1;
        for(int i = 1; i < str.size(); ++i)
        {
            dp[i] += dp[i - 1];
            auto num = (str[i - 1] - '0') * 10 + str[i] - '0';
            if(num >= 10 && num < 26)
                dp[i] += (i >= 2 ? dp[i - 2] : 1);
        }
        return dp.back();
    }
};
version.2

优化dp的空间，但字符串还是占O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int translateNum(int num) {
        string str = to_string(num);
        int a = 1, b = 1;
        for(int i = 1; i < str.size(); ++i)
        {
            auto num = (str[i - 1] - '0') * 10 + str[i] - '0';
            a = (num >= 10 && num < 26) ? a + b : b;
            swap(a, b);
        }
        return b;
    }
};
version.3

直接使用取余计算数位 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int translateNum(int num) {
        int a = 1, b = 1;
        int lastNum = num % 10;
        num /= 10;
        while(num)
        {
            auto curNum = num % 10;
            auto sum = curNum * 10 + lastNum;
            a = (sum >= 10 && sum < 26) ? a + b : b;
            num /= 10;
            lastNum = curNum;
            swap(a, b);
        }
        return b;
    }
};
递归 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int translateNum(int num) {
        if(num < 10)
            return 1;
        int ret = 0;
        int a = num % 10;
        num /= 10;
        int b = num % 10;
        if(b != 0 && b * 10 + a < 26)
            ret += translateNum(num / 10);
        ret += translateNum(num);
        return ret;
    }
};

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

剑指 Offer 45. 把数组排成最小的数

类似179. 最大数

我可太太太太太菜了

本质上转换为一个排序问题，对于两个数字a1,b1。当str(a1) + str(b1) < str(b1) + str(a1)时，表示a1因当刚在b1左边，反之则表示a1应当放在b1右边。以此为判断条件对数组进行排序，排序后重新组合成字符串就是所需

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:
    string minNumber(vector<int>& nums) {
        sort(nums, 0, nums.size() - 1);
        string ret = "";
        for(auto& num : nums)
            ret += to_string(num);
        return ret;
    }
private:
    int partition(vector<int>& nums, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        string c = to_string(nums[lo]);
        while(i < j)
        {
            while(i < hi && to_string(nums[++i]) + c < c + to_string(nums[i])) {}
            while(j > lo && to_string(nums[--j]) + c > c + to_string(nums[j])) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[j], nums[lo]);
        return j;
    }
    void sort(vector<int>& nums, int lo, int hi)
    {
        if(lo > hi)
            return;
        auto j = partition(nums, lo, hi);
        sort(nums, lo, j - 1);
        sort(nums, j + 1, hi);
    }
};

v2 

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:
    string minNumber(vector<int>& nums) {
        string ret = "";
        vector<string> strs;
        for(auto& num : nums)
            strs.push_back(to_string(num));
        sort(strs, 0, nums.size() - 1);
        for(auto& str : strs)
            ret += str;
        return ret;
    }
private:
    int partition(vector<string>& nums, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        string c = nums[lo];
        while(i < j)
        {
            while(i < hi && nums[++i] + c < c + nums[i]) {}
            while(j > lo && nums[--j] + c > c + nums[j]) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[j], nums[lo]);
        return j;
    }
    void sort(vector<string>& nums, int lo, int hi)
    {
        if(lo > hi)
            return;
        auto j = partition(nums, lo, hi);
        sort(nums, lo, j - 1);
        sort(nums, j + 1, hi);
    }
};
v3 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        for(auto& num : nums)
            strs.push_back(to_string(num));
        sort(strs.begin(), strs.end(), [](string& str1, string str2){ return str1 + str2 < str2 + str1; });
        string ret = "";
        for(auto& str : strs)
            ret.append(str);
        return ret;
    }
};
v4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string minNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b)
        {
            long sa = 10;
            long sb = 10;
            while(sa <= a)
                sa *= 10;
            while(sb <= b)
                sb *= 10;
            return sb * a + b < sa * b + a;
        });
        string ret;
        for(auto& num : nums)
            ret += to_string(num);
        return ret;
    }
};

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

剑指 Offer 57 - II. 和为s的连续正数序列

暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ret;
        for(int i = 1; i <= target >> 1; ++i)
        {
            int sum = i;
            vector<int> tmp;
            tmp.push_back(i);
            for(int j = i + 1; j < target; ++j)
            {
                tmp.push_back(j);
                sum += j;
                if(sum > target)
                    break;
                else if(sum == target)
                    ret.push_back(tmp);
            }
        }
        return ret;
    }
};

T(n) : O(n^2)

sliding window
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:
    vector<vector<int>> findContinuousSequence(int target) {
        int begin = 1, end = 1, sum = 0;
        vector<vector<int>> ret;
        while(begin < (target >> 1))
        {
            sum += end;
            while(sum >= target)
            {
                if(sum == target)
                {
                    vector<int> tmp;
                    for(int i = begin; i <= end; ++i)
                        tmp.push_back(i);
                    ret.push_back(tmp);
                }
                sum -= begin;
                ++begin;
            }
            ++end;
        }
        return ret;
    }
};

T(n) : O(n)

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

剑指 Offer 57. 和为s的两个数字

借助two sum的思路
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_set<int> set;
        for(auto& num : nums)
        {
            if(set.find(target - num) != set.end())
                return {num, target - num};
            else
                set.insert(num);
        }  
        return {};
    }
};

T(n) : O(n)

S(n) : O(n)

利用好递增顺序，双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            if(nums[lo] + nums[hi] > target)
                --hi;
            else if(nums[lo] + nums[hi] < target)
                ++lo;
            else
                return {nums[lo], nums[hi]};
        }
        return {};
    }
};

T(n) : O(n)

S(n) : O(1)

1
提醒一下，判断条件最好不要用相加后的结果，应该用target - nums[i] 跟 nums[j]比较，这样保证不会溢出。虽然这题中不会出错。同样的例子还有二分查找，(left + right) / 2 可以用left + ((rigth - left) >> 1))代替

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

剑指 Offer 56 - II. 数组中数字出现的次数 II

hashmap
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> map;
        for(auto& num : nums)
            map[num] += 1;
        for(auto& it : map)
            if(it.second == 1)
                return it.first;
        return 0;
    }
};

T(n) : O(n)

S(n) : O(n)

位运算

因为其他数都出现三次，只有一个数出现一次，所以将所有数的每一位加起来后对3取余剩下的就是那个只出现一次的数字

对于每一位构建状态转换图，有三个状态0,1,2 1625471528006.png 其中三个状态为0,1,2表示除以3后的余数

求出来后的结果必然是00或01两个状态，因为所有出现三次的数都加完了取余完了，所以只剩下了这2种情况表示那个只出现一次的数的位为0或1，所以最后只需要返回one即可

对于每一位都是相同的方法，所以可以直接放到一起来用位运算

根据状态转换图，构建卡诺图，化简
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for(auto& num : nums)
        {
            auto tmp = one;
            one = (one & ~num) | (~two & ~one & num);
            two = (two & ~num) | (tmp & num);
        }
        return one;
    }
};
根据图观察获得
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for(auto& num : nums)
        {
            one = ~two & (one ^ num);
            two = ~one & (two ^ num); // 注意此处的两个运算并不是同时进行的，所以这里的two需要根据变化后的one的结果来运算。根据计算后的one的结果，见下图（还是卡诺图来的直观）
        }
        return one;
    }
};
1625471719640.png

T(n) : O(n)

S(n) : O(1)