跳至主要内容

268 篇文章 含有標籤「leetcode」

檢視所有標籤

994. Rotting Oranges

· 閱讀時間約 2 分鐘

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

image

Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();

        // 用來存花了多少分鐘
        int minutes = 0;

        // 用來存剩下多少橘子
        int fresh = 0;
        queue<pair<int, int>> q;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // 如果遇到 1，新鮮橘子 + 1
                if(grid[i][j] == 1) fresh++;
                // 如果遇到 2，壞橘子推到 queue
                else if(grid[i][j] == 2) q.push({i, j});
            }
        }

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while(!q.empty() && fresh > 0) {
            int qSize = q.size();
            for(int i = 0; i < qSize; i++) {
                auto node = q.front(); q.pop();
                for(auto& dir : directions) {
                    int new_r = node.first + dir[0];
                    int new_c = node.second + dir[1];
                    // 遇到超出邊界的、不是好橘子的都略過
                    if(new_r < 0 || new_c < 0 || new_r >= rows || new_c >= cols || grid[new_r][new_c] != 1)
                        continue;

                    // 標記新的格子已經是壞橘子
                    grid[new_r][new_c] = 2;
                    q.push({new_r, new_c});
                    fresh--;
                }
            }
            // queue 搜索完一輪，minutes++
            minutes++;
        }
        // 判斷最後還有新鮮橘子，return -1
        return fresh == 0 ? minutes : -1;
    }
};
  • T: $O(M \cdot N)$
  • S: $O(M \cdot N)$

983. Minimum Cost For Tickets

· 閱讀時間約 3 分鐘
/*
 * @lc app=leetcode id=983 lang=cpp
 *
 * [983] Minimum Cost For Tickets
 *
 * https://leetcode.com/problems/minimum-cost-for-tickets/description/
 *
 * algorithms
 * Medium (65.25%)
 * Likes:    8510
 * Dislikes: 180
 * Total Accepted:    418.4K
 * Total Submissions: 620.7K
 * Testcase Example:  '[1,4,6,7,8,20]\n[2,7,15]'
 *
 * You have planned some train traveling one year in advance. The days of the
 * year in which you will travel are given as an integer array days. Each day
 * is an integer from 1 to 365.
 *
 * Train tickets are sold in three different ways:
 *
 *
 * a 1-day pass is sold for costs[0] dollars,
 * a 7-day pass is sold for costs[1] dollars, and
 * a 30-day pass is sold for costs[2] dollars.
 *
 *
 * The passes allow that many days of consecutive travel.
 *
 *
 * For example, if we get a 7-day pass on day 2, then we can travel for 7 days:
 * 2, 3, 4, 5, 6, 7, and 8.
 *
 *
 * Return the minimum number of dollars you need to travel every day in the
 * given list of days.
 *
 *
 * Example 1:
 *
 *
 * Input: days = [1,4,6,7,8,20], costs = [2,7,15]
 * Output: 11
 * Explanation: For example, here is one way to buy passes that lets you travel
 * your travel plan:
 * On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
 * On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3,
 * 4, ..., 9.
 * On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
 * In total, you spent $11 and covered all the days of your travel.
 *
 *
 * Example 2:
 *
 *
 * Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
 * Output: 17
 * Explanation: For example, here is one way to buy passes that lets you travel
 * your travel plan:
 * On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1,
 * 2, ..., 30.
 * On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
 * In total, you spent $17 and covered all the days of your travel.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= days.length <= 365
 * 1 <= days[i] <= 365
 * days is in strictly increasing order.
 * costs.length == 3
 * 1 <= costs[i] <= 1000
 *
 *
 */

// @lc code=start
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int lastDay = days.back();
        vector<int> dp(lastDay + 1, 0);

        int i = 0;

        for (int day = 1; day < lastDay + 1; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;

                dp[day] = min({
                    dp[day - 1] + costs[0],
                    dp[max(0, day - 7)] + costs[1],
                    dp[max(0, day - 30)] + costs[2]});
            }
        }
        return dp[lastDay];
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(N)$

974. Subarray Sums Divisible by K

· 閱讀時間約 1 分鐘

子數列 [0, i] 的和子數列 [0, j] 的和，除以 k 的餘數相同的話，代表 [i + 1, j] 的和也可以被 k 整除。

舉個例子：nums = [1, 2, 3, 4]，k = 5

  • 1 除以 5 餘 1
  • [1, 2, 3] 除以 5，也餘 1

按照規律，[2, 3] 的和一定可以整除 5

也就是說，子數列能被 k 整除的關鍵是在餘數相不相同。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        // 計算子數列能不能被 k 整除
        // sum[i : j] 能被 k 整除的條件就是
        // prefixSum[i] 和 prefixSum[j - 1] 除以 k 的餘數相同

     int res = 0, sum = 0;

        // 保存 prefixSum 除以 k 的餘數出現多少次
        unordered_map<int, int> m{{0, 1}};

        for (int num : nums)
        {
            // 累加 sum
            // 加上 k 的原因是確保結果為正整數
            // 沒有加上 k，有可能出現負數的情況
         sum = (sum + num % k + k) % k;

            // 加上相同餘數對應的頻率
         res += m[sum];

            // 餘數出現的頻率 + 1
         ++m[sum];
        }
        return res;
    }
};
  • T: $O(n + k)$
  • S: $O(n)$

945. Minimum Increment to Make Array Unique

· 閱讀時間約 1 分鐘
  • 加最少的步數讓數列的元素都不重複。
  • 排序
  • 數字差多少：increment = nums[i - 1] - nums[i] + 1
class Solution {
public:
    int minIncrementForUnique(vector<int>& nums)
    {
        int moves = 0;

        int n = nums.size();

        sort(nums.begin(), nums.end());

        // nums = [1, 1, 2, 2, 3, 7]
        for (int i = 1; i < n; ++i)
        {
            // 如果發現目前的數字小於等於前一個數字
            if (nums[i - 1] >= nums[i])
            {

                // 要加的數字等於兩者之差 + 1
                int increment = nums[i - 1] - nums[i] + 1;
                moves += increment;
                // 更新目前的數字
                nums[i] = nums[i - 1] + 1;
            }
        }
        return moves;
    }
};
  • T: $O(n \cdot \log n)$
  • S: $O(1)$

944. Delete Columns to Make Sorted

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=944 lang=cpp
 *
 * [944] Delete Columns to Make Sorted
 *
 * https://leetcode.com/problems/delete-columns-to-make-sorted/description/
 *
 * algorithms
 * Easy (74.65%)
 * Likes:    1740
 * Dislikes: 2898
 * Total Accepted:    205.4K
 * Total Submissions: 274.8K
 * Testcase Example:  '["cba","daf","ghi"]'
 *
 * You are given an array of n strings strs, all of the same length.
 *
 * The strings can be arranged such that there is one on each line, making a
 * grid.
 *
 *
 * For example, strs = ["abc", "bce", "cae"] can be arranged as follows:
 *
 *
 *
 * abc
 * bce
 * cae
 *
 *
 * You want to delete the columns that are not sorted lexicographically. In the
 * above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e')
 * are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete
 * column 1.
 *
 * Return the number of columns that you will delete.
 *
 *
 * Example 1:
 *
 *
 * Input: strs = ["cba","daf","ghi"]
 * Output: 1
 * Explanation: The grid looks as follows:
 * ⁠ cba
 * ⁠ daf
 * ⁠ ghi
 * Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete
 * 1 column.
 *
 *
 * Example 2:
 *
 *
 * Input: strs = ["a","b"]
 * Output: 0
 * Explanation: The grid looks as follows:
 * ⁠ a
 * ⁠ b
 * Column 0 is the only column and is sorted, so you will not delete any
 * columns.
 *
 *
 * Example 3:
 *
 *
 * Input: strs = ["zyx","wvu","tsr"]
 * Output: 3
 * Explanation: The grid looks as follows:
 * ⁠ zyx
 * ⁠ wvu
 * ⁠ tsr
 * All 3 columns are not sorted, so you will delete all 3.
 *
 *
 *
 * Constraints:
 *
 *
 * n == strs.length
 * 1 <= n <= 100
 * 1 <= strs[i].length <= 1000
 * strs[i] consists of lowercase English letters.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int m = strs.size(), n = strs[0].size();
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    cnt++; break;
                }
            }
        }
        return cnt;
    }
};
// @lc code=end

931. Minimum Falling Path Sum

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=931 lang=cpp
 *
 * [931] Minimum Falling Path Sum
 *
 * https://leetcode.com/problems/minimum-falling-path-sum/description/
 *
 * algorithms
 * Medium (62.52%)
 * Likes:    6578
 * Dislikes: 165
 * Total Accepted:    521.8K
 * Total Submissions: 841.4K
 * Testcase Example:  '[[2,1,3],[6,5,4],[7,8,9]]'
 *
 * Given an n x n array of integers matrix, return the minimum sum of any
 * falling path through matrix.
 *
 * A falling path starts at any element in the first row and chooses the
 * element in the next row that is either directly below or diagonally
 * left/right. Specifically, the next element from position (row, col) will be
 * (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
 *
 *
 * Example 1:
 *
 *
 * Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
 * Output: 13
 * Explanation: There are two falling paths with a minimum sum as shown.
 *
 *
 * Example 2:
 *
 *
 * Input: matrix = [[-19,57],[-40,-5]]
 * Output: -59
 * Explanation: The falling path with a minimum sum is shown.
 *
 *
 *
 * Constraints:
 *
 *
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 100
 * -100 <= matrix[i][j] <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        if (n == 1) return matrix[0][0];

        int res = INT_MAX;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int previous = matrix[i - 1][j];
                if (j > 0)
                {
                    previous = min(previous, matrix[i - 1][j - 1]);
                }
                if (j < n - 1)
                {
                    previous = min(previous, matrix[i - 1][j + 1]);
                }
                matrix[i][j] += previous;
                if (i == n - 1)
                {
                    res = min(res, matrix[i][j]);
                }
            }
        }
        return res;
    }
};
// @lc code=end
  • T: $O(N^2)$
  • S: $O(1)$

918. Maximum Sum Circular Subarray

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=918 lang=cpp
 *
 * [918] Maximum Sum Circular Subarray
 *
 * https://leetcode.com/problems/maximum-sum-circular-subarray/description/
 *
 * algorithms
 * Medium (46.01%)
 * Likes:    6878
 * Dislikes: 320
 * Total Accepted:    319.7K
 * Total Submissions: 682K
 * Testcase Example:  '[1,-2,3,-2]'
 *
 * Given a circular integer array nums of length n, return the maximum possible
 * sum of a non-empty subarray of nums.
 *
 * A circular array means the end of the array connects to the beginning of the
 * array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the
 * previous element of nums[i] is nums[(i - 1 + n) % n].
 *
 * A subarray may only include each element of the fixed buffer nums at most
 * once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there
 * does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,-2,3,-2]
 * Output: 3
 * Explanation: Subarray [3] has maximum sum 3.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [5,-3,5]
 * Output: 10
 * Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [-3,-2,-3]
 * Output: -2
 * Explanation: Subarray [-2] has maximum sum -2.
 *
 *
 *
 * Constraints:
 *
 *
 * n == nums.length
 * 1 <= n <= 3 * 10^4
 * -3 * 10^4 <= nums[i] <= 3 * 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int curMax = 0, curMin = 0;
        int maxSum = nums[0], minSum = nums[0];
        int totalSum = 0;

        for(int num : nums) {
            curMax = max(curMax + num, num);
            maxSum = max(maxSum, curMax);

            curMin = min(curMin + num, num);
            minSum = min(minSum, curMin);

            totalSum += num;
        }
        if(totalSum == minSum) {
            return maxSum;
        }
        return max(maxSum, totalSum - minSum);
    }
};
// @lc code=end
  • T: $O(N)$
  • S: $O(1)$

912. Sort an Array

· 閱讀時間約 2 分鐘
  • Merge Sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void merge(vector<int> &nums, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> l1(n1), l2(n2);
        for (int i = 0; i < n1; ++i) l1[i] = nums[left + i];

        for (int i = 0; i < n2; ++i) l2[i] = nums[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (l1[i] <= l2[j])
            {
                nums[k] = l1[i++];
            }
            else
            {
                nums[k] = l2[j++];
            }
            ++k;
        }

        while (i < n1)
        {
            nums[k] = l1[i];
            ++i; ++k;
        }

        while (j < n2)
        {
            nums[k] = l2[j];
            ++j; ++k;
        }
    }

    void mergeSort(vector<int> &nums, int left, int right)
    {
     if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
};

  • T: $O(n \log n)$

  • S: $O(1)$

  • Quick Sort (TLE)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return

        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int pointer = left;
        for (int i = left; i < right; ++i)
        {
            if (nums[i] <= pivot)
            {
                swap(nums[pointer++], nums[i]);
            }
        }
        swap(nums[pointer], nums[right]);
        return pointer;
    }
};
  • T: $O(n \log n)$
  • S: $O(1)$

909. Snakes and Ladders

· 閱讀時間約 3 分鐘

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
    • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
  • If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
  • The game ends when you reach the square n2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

  • For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return-1.

Example 1:

image

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4 Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]] Output: 1

Constraints:

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n2].
  • The squares labeled 1 and n2 do not have any ladders or snakes.
  • T: $O()$
  • S: $O()$