动态规划

17.09 面试题 第k个数

Tags: hashtable, 动态规划, 堆

题目

https://leetcode.cn/problems/get-kth-magic-number-lcci/

Solution1

使用小顶堆，每次取出堆顶元素x，将3x，5x，7x放入堆中，第k次取出的为目标数。这里需要注意我们存入堆中的数可能大于INT_MAX，需要使用long

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
class Solution {
public:
    int getKthMagicNumber(int k) {
        // 小顶堆
        priority_queue<long, vector<long>, greater<long>> my_heap;
        // 去重hash表
        unordered_set<long> my_hash;
        vector<int> factors = {3, 5, 7};

        int ugly = 0;

        // 初始化
        my_heap.push(1);
        my_hash.insert(1);

        while (k > 0) {
            long cur_element = my_heap.top();
            my_heap.pop();
            ugly = (int) cur_element;

            for (auto factor: factors) {
                long next = factor * cur_element;
                if (my_hash.count(next) == 0) {
                    my_hash.insert(next);
                    my_heap.push(next);
                }
            }
            k--;
        }

        return ugly;
    }
};

  • 缺点：维护堆和hash表时，存储了较多不需要的数，时间复杂度也很高

Solution2

Solution1的性能上还有很多不足，主要可优化的点在于堆和hash表的维护过程有很多不必要的步骤。主要的冗余步骤在于我们每次循环都将3x，5x和7x三个值都存了进去，如果我们每次只存一个正确的值，就可以优化掉这个性能。

通过观察我们可以发现，一个丑数一定是在他之前的某个丑数与’3,5,7’中的一个数之积。

假设有一个数组ugly[n]，其中从头存放了一段丑数，那么包含所有丑数数组的数组一定是以下三个数组合并的结果

1
2
3
1. [ugly[0] * 3, ugly[1] * 3, ..., ugly[n] * 3]
2. [ugly[0] * 5, ugly[1] * 5, ..., ugly[n] * 5]
3. [ugly[0] * 7, ugly[1] * 7, ..., ugly[n] * 7]

这道题就变成了合并有序数组的题目，我们使用三个指针分别指向三个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> ugly(k);
        // 三个指针
        int p3 = 0, p5 = 0, p7 = 0;

        ugly[0] = 1;
        for (int i = 1; i < k; i++) {
            int tmp_min = min(min(ugly[p3] * 3, ugly[p5] * 5), ugly[p7] * 7);
            ugly[i] = tmp_min;

            if (ugly[i] == ugly[p3] * 3)
                p3++;
            if (ugly[i] == ugly[p5] * 5)
                p5++;
            if (ugly[i] == ugly[p7] * 7)
                p7++;
        }

        return ugly[k - 1];
    }
};

  • 优点：优化了性能

53.最大子数组和

经典的动态规划问题，详解动态规划

题目

https://leetcode.cn/problems/maximum-subarray/

Solution1

nums = [-2,1,-3,4,-1,2,1,-5,4]

  1. -2 最大子数组 [-2]

  2. 1 最大子数组 [1]

  3. -3 最大子数组 [1]

  4. 4 最大子数组 [4]

  5. -1 最大子数组 [4]

  6. 2 最大子数组 [4, -1, 2]

  7. 1 最大子数组 [4, -1, 2, 1]

  8. -5 最大子数组 [4, -1, 2, 1]

  9. 4 最大子数组 [4, -1, 2, 1]

观察得到结论，即对于前n个数的最大子数组和f(n)，有f(n) = max(f(n-1) + nums[n], nums[n])，所以我们可以使用动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int pre_array = 0;
        for (const auto x: nums) {
            pre_array = max(pre_array + x, x);
            sum = max(sum, pre_array);
        }
        return sum;
    }
};

55.跳跃游戏

题目

https://leetcode.cn/problems/jump-game/

Solution2

nums = [2,3,1,1,4]

我们设f(i)为前i-1个点能到达的最远距离，那么就有f(n) = max(f(n-1), i + nums[i])，当f(i) > nums.size()时，能够跳到

f(n)可以优化为一个变量max_distance表示当前能到达的最远距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    // 这里用到的是动态规划的空间优化方法，同时包含贪心算法的思想
    bool canJump(vector<int>& nums) {
        // 前i - 1个点能到达的最远距离
        int max_distance = 0;
        // 遍历，max_distance是能到达的最远距离
        // 如果i > max_distance，说明最远距离不再改变，且没有到末尾元素
        // 这是我们无法跳到终点
        for (int i = 0; i <= max_distance; i++) {
            int tmp = i + nums[i];
            // 与第i个点能到达的最远距离比较
            max_distance = max(tmp, max_distance);

            if (max_distance >= nums.size() - 1)
                return true;
        }
        return false;
    }
};

45.跳跃游戏 II

题目

https://leetcode.cn/problems/jump-game-ii/

Solution2

二分查找

二分查找题目

35. 搜索插入位置

题目

Tags: 二分查找

https://leetcode.cn/problems/search-insert-position/

Solution1

二分查找标准模板

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 searchInsert(vector<int>& nums, int target) {
        int size = nums.size();

        if (size == 0)
            return 0;

        if (target > nums[size - 1])
            return size;

        int lo = 0, hi = nums.size() - 1;
        int mid = 0;

        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            // 下面可能会整型溢出
            // mid = (hi + lo) / 2;
            if (nums[mid] < target)
                lo = mid + 1;
            else if (nums[mid] > target)
                hi = mid - 1;
            else
                return mid;
        }

        return lo;
    }
};

33.搜索旋转排序数组

Tags: 数组，二分查找

题目

https://leetcode.cn/problems/search-in-rotated-sorted-array/

Solution1

  1. 将数组一分为二，一定有一部分是有序的，对有序部分进行二分查找

  2. 如果没有找到目标值，重复步骤1

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:
    int search(vector<int>& nums, int target) {
        int left  = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            // obvious values check
            if (nums[left] == target)
                return left;
            if (nums[right] == target)
                return right;
            if (nums[mid] == target)
                return mid;

            // 对有序部分进行二分查找
            if (nums[mid] > nums[left]) {
                if (nums[mid] > target && nums[left] < target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else {
                if (nums[mid] < target && nums[right] > target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
};

34.排序数组查找元素的第一个和最后一个位置

题目

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

Solution1

找到数组中第一个等于target的下标lo和第一个大于target的下标hi, ans = {lo, hi}

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
class Solution {
public:
    // lower: true 寻找大于等于target的下标, false 寻找第一个大于target的下标
    int BinarySearch(vector<int> &nums, int target, bool lower){
        int lo = 0, hi = nums.size() - 1, mid = 0;
        int ans = nums.size();

        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                hi = mid - 1;
                ans = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans = {-1, -1};

        if (nums.size() == 0)
            return ans;

        // 第一个等于target的下标
        int lo = BinarySearch(nums, target, true);
        // 第一个大于target的下标 - 1
        int hi = BinarySearch(nums, target, false) - 1;

        if (lo <= hi &&
            hi <= nums.size() - 1 &&
            nums[lo] == target &&
            nums[hi] == target) {
                ans[0] = lo;
                ans[1] = hi;
            }

        return ans;
    }
};

74.搜索二维矩阵

题目

https://leetcode.cn/problems/search-a-2d-matrix/

Solution1

先对每行第一个值做二分查找，确定target可能在哪一行，在对这行做二分查找

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
class Solution {
public:
    // 两次二分法
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        // 边界值
        if (target < matrix[0][0])
            return false;

        // 确定target可能在哪一行
        int lo = 0, hi = m - 1, mid = 0;
        while (lo <= hi && m > 1) {
            mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] > target)
                hi = mid - 1;
            else if (matrix[mid][0] <  target)
                lo = mid + 1;
            else
                return true;
        }

        // 在目标行内做而二分查找
        int row = (m == 1 ? 0 : lo - 1);
        lo = 0, hi = n - 1, mid = 0;
        while (lo <= hi && n > 1) {
            mid = lo + (hi - lo) / 2;
            if (matrix[row][mid] > target)
                hi = mid - 1;
            else if (matrix[row][mid] <  target)
                lo = mid + 1;
            else
                return true;
        }

        // 边界值
        if (n == 1 && matrix[row][0] == target)
            return true;

        return false;
    }
};

Solution2

优化Solution1的写法，使用lambda函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    // 两次二分法
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // lambda 函数比较出在哪一行
        auto row = upper_bound(matrix.begin(), matrix.end(), target,
            [](const int b, const vector<int> &a) {
                return b < a[0];
            });

        // 边界值
        if (row == matrix.begin())
            return false;

        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};

Solution3

将矩阵的坐标映射为一维数组的下标，只做一次二分查找

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:
    // 一次二分法，将矩阵坐标映射为一维数组下标
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int lo = 0, hi = m * n - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int num = matrix[mid / n][mid % n];

            if (num > target) {
                hi = mid - 1;
            }
            else if (num < target) {
                lo = mid + 1;
            }
            else
                return true;
        }

        return false;
    }
};

自动机

8.字符串转换整数

Tags: 字符串，自动机

题目

https://leetcode.cn/problems/string-to-integer-atoi

Solution1

最直观的遍历字符串方法，根据题目规则判断字符串中的每一个字符。

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
class Solution {
public:
    int myAtoi(string s) {
        int sign = 1;  // sign flag
        long long int sum = 0;
        bool in_digit_range = false;  // we are in digital range

        for (auto element: s)
        {
            // skip space
            if (element == ' ') {
                if (in_digit_range)
                    break;
                else
                    continue;
            }

            if (element == '-') {
                if (in_digit_range)
                    break;

                sign = -1;
                in_digit_range = true;
                continue;
            }

            if (element == '+') {
                if (in_digit_range)
                    break;
                else
                {
                    in_digit_range = true;
                    continue;
                }
            }

            if (element >= '0' && element <= '9') {
                in_digit_range = true;

                if (sum > INT_MAX / 10 || (sum == INT_MAX / 10 && element > '7'))
                    return sign > 0 ? INT_MAX : INT_MIN;

                sum = sum * 10 + (element - '0');
            }
            else {
                break;
            }
        }

        return sign * sum;
    }
};

  • 优点：直观易懂

  • 缺点：代码臃肿

  • 结论：正常思路

Solution2

来自LeetCode官方的思路：自动机

我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

自动机状态表格：

’ ’ +/- number other
start start signed in_number end
signed end end in_number end
in_number end end in_number end
end end end end end 
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
// Automaton class
class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c))
            return 0;
        if (c == '+' || c == '-')
            return 1;
        if (isdigit(c))
            return 2;
        return 3;
    }

  public:
    int sign = 1;
    long long int sum = 0;

    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            sum = sum * 10 + (c - '0');
            sum = sign == 1 ? min(sum, (long long)INT_MAX) : min(sum, -(long long)INT_MIN);
        }
        else if (state == "signed") {
            sign = c == '+' ? 1 : -1;
        }
    }
};

class Solution {
  public:
    int myAtoi(string str) {
        Automaton automaton;
        for (auto c: str) {
            automaton.get(c);
        }
        return automaton.sign * automaton.sum;
    }
};

  • 优点：能简单练习下自动机，代码更好看一点

  • 缺点：逻辑更复杂，性能更慢，内存占用更大

  • 结论：如果是生产代码，我肯定不会这么写。但是练习算法时还是可以试试的