跳至主要内容

45. Jump Game II

· 閱讀時間約 1 分鐘

Hint

class Solution {
public:
    int jump(vector<int>& nums)
    {
        // This will store the farthest index we can reach so far
        // This will count the number of jumps needed
        // This will store the current goal index we aim to reach with the next jump

        // Loop through the array up to the second-to-last element
        for ()
        {
            // Update maxReach with the farthest we can reach from the current index

            // If we have reached the current goal
                // Increment the jump count
                // Update the goal to the farthest we can reach
            }
        }
        // Return the number of jumps needed to reach the last index
    }
};
class Solution {
public:
    int jump(vector<int>& nums)
    {
        int maxReach = 0;
        int cnt = 0;
        int goal = 0;;
        for (int i = 0; i < nums.size() - 1; ++i)
        {
            maxReach = max(maxReach, i + nums[i]);
            if (i == goal)
            {
                ++cnt;
                goal = maxReach;
            }
        }
        return cnt;
    }
};
  • T: $O(N)$
  • S: $O(1)$

42. Trapping Rain Water

· 閱讀時間約 1 分鐘

Hint

class Solution {
public:
    int trap(vector<int>& height)
    {
        // Pointer to the left end of the array
        // Pointer to the right end of the array
        // Maximum height seen from the left side
        // Maximum height seen from the right side
        // Variable to store the total amount of trapped water

        // Traverse the array until the left and right pointers meet
        while()
        {
            if()
            {
                // Move the left pointer one step to the right
                // Update leftMax if the new height is greater
                // Add the trapped water at the current position
            }
            else
            {
                // Move the right pointer one step to the left
                // Update rightMax if the new height is greater
                // Add the trapped water at the current position
            }
        }
        // Return the total amount of trapped water
    }
};
class Solution {
public:
    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int leftMax = height[left], rightMax = height[right];
        int res = 0;

        while(left < right)
        {
            if(leftMax < rightMax)
            {
                leftMax = max(leftMax, height[++left]);
                res += leftMax - height[left];
            }
            else
            {
                rightMax = max(rightMax, height[--right]);
                res += rightMax - height[right];
            }
        }
        return res;
    }
};
  • T: $O(N)$
  • S: $O(1)$

41. First Missing Positive

· 閱讀時間約 1 分鐘

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0] Output: 3 Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest positive integer 1 is missing.

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            // 若數字大於 0 且小於等於 n，且該位置上的數字不等於當前數字，則進行交換
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
};
  • T: $O(N)$
  • S: $O(1)$

40. Combination Sum II

· 閱讀時間約 1 分鐘
class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0);
        return res;
    }
    void backtracking(vector<int>& candidates, int target, int start)
    {
        if (target == 0) res.push_back(comb);
        if (target < 0) return;

        unordered_set<int> seen;

        for (int i = start; i < candidates.size(); i++)
        {
            if (seen.count(candidates[i])) continue;
            comb.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            comb.pop_back();
            seen.insert(candidates[i]);
        }
    }
};
  • T: $O(2^N)$
  • S: $O(N)$

39. Combination Sum

· 閱讀時間約 1 分鐘
class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        backtracking(candidates, target, 0);
        return res;
    }
    void backtracking(vector<int>& candidates, int target, int start)
    {
        if (target == 0) res.push_back(comb);
        if (target < 0) return;

        for (int i = start; i < candidates.size(); i++)
        {
            comb.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i);
            comb.pop_back();
        }
    }
};
  • T: O(N^(T/M+1))
  • S: O(T/M)

36. Valid Sudoku

· 閱讀時間約 2 分鐘
  • Use Three Vectors
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        int n = 9;
        vector<vector<int>> rows_seen(n, vector<int>(n));
        vector<vector<int>> cols_seen(n, vector<int>(n));
        vector<vector<int>> boxes_seen(n, vector<int>(n));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == '.') continue;

                int c = board[i][j] - '1';

                int boxIndex = 3 * (i / 3) + j / 3;

                if (rows_seen[i][c] || cols_seen[c][j] || boxes_seen[boxIndex][c])
                    return false;

                rows_seen[i][c] = 1;
                cols_seen[c][j] = 1;
                boxes_seen[boxIndex][c] = 1;
            }
        }
        return true;
    }
};

  • T: $O(N^2)$

  • S: $O(N^2)$

  • Use Three HashSet

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        unordered_set<int> rowSet[9], colSet[9], boxSet[9];
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                char val = board[i][j];

                if (val == '.') continue;

                if (rowSet[i].count(val)) return false;
                rowSet[i].insert(val);

                if (colSet[j].count(val)) return false;
                colSet[j].insert(val);

                int boxIndex = (i / 3) * 3 + j / 3;
                if (boxSet[boxIndex].count(val)) return false;
                boxSet[boxIndex].insert(val);
            }
        }
        return true;
    }
};

  • T: $O(N^2)$

  • S: $O(N^2)$

  • Use One HashSet

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        int n = 9;
        unordered_set<string> st;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (board[i][j] == '.') continue;
                string t = "(" + to_string(board[i][j] - '0') + ")";
                string row = to_string(i) + t;
                string col = t + to_string(j);
                string cell = to_string(i / 3) + t + to_string(j / 3);
                if (st.count(row) || st.count(col) || st.count(cell)) return false;
                st.insert(row);
                st.insert(col);
                st.insert(cell);
            }
        }
        return true;
    }
};
  • T: $O(N^2)$
  • S: $O(N)$

35. Search Insert Position

· 閱讀時間約 1 分鐘
/*
 * @lc app=leetcode id=35 lang=cpp
 *
 * [35] Search Insert Position
 *
 * https://leetcode.com/problems/search-insert-position/description/
 *
 * algorithms
 * Easy (47.55%)
 * Likes:    17368
 * Dislikes: 815
 * Total Accepted:    3.8M
 * Total Submissions: 7.7M
 * Testcase Example:  '[1,3,5,6]\n5'
 *
 * Given a sorted array of distinct integers and a target value, return the
 * index if the target is found. If not, return the index where it would be if
 * it were inserted in order.
 *
 * You must write an algorithm with O(log n) runtime complexity.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,3,5,6], target = 5
 * Output: 2
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,3,5,6], target = 2
 * Output: 1
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [1,3,5,6], target = 7
 * Output: 4
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 10^4
 * -10^4 <= nums[i] <= 10^4
 * nums contains distinct values sorted in ascending order.
 * -10^4 <= target <= 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};
// @lc code=end
  • T: $O(\log N)$
  • S: $O(1)$

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

· 閱讀時間約 2 分鐘
/*
 * @lc app=leetcode id=34 lang=cpp
 *
 * [34] Find First and Last Position of Element in Sorted Array
 *
 * https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 *
 * algorithms
 * Medium (45.48%)
 * Likes:    21764
 * Dislikes: 573
 * Total Accepted:    2.6M
 * Total Submissions: 5.7M
 * Testcase Example:  '[5,7,7,8,8,10]\n8'
 *
 * Given an array of integers nums sorted in non-decreasing order, find the
 * starting and ending position of a given target value.
 *
 * If target is not found in the array, return [-1, -1].
 *
 * You must write an algorithm with O(log n) runtime complexity.
 *
 *
 * Example 1:
 * Input: nums = [5,7,7,8,8,10], target = 8
 * Output: [3,4]
 * Example 2:
 * Input: nums = [5,7,7,8,8,10], target = 6
 * Output: [-1,-1]
 * Example 3:
 * Input: nums = [], target = 0
 * Output: [-1,-1]
 *
 *
 * Constraints:
 *
 *
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums is a non-decreasing array.
 * -10^9 <= target <= 10^9
 *
 *
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<int> res(2, -1);

        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (right == n || nums[right] != target) {
            return res;
        }
        res[0] = right;
        right = n;

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

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        res[1] = right - 1;

        return res;
    }
};
// @lc code=end
  • T: $O(\log n)$
  • S: $O(1)$

31. Next Permutation

· 閱讀時間約 2 分鐘

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3] Output: [1,3,2]

Example 2:

Input: nums = [3,2,1] Output: [1,2,3]

Example 3:

Input: nums = [1,1,5] Output: [1,5,1]

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int left = n - 2, right = n - 1;
        while(left >= 0 && nums[left] >= nums[left + 1]) {
            --left;
        }
        if(left >= 0) {
            while(nums[left] >= nums[right]) {
                --right;
            }
            swap(nums[left], nums[right]);
        }
        reverse(nums.begin() + left + 1, nums.end());
    }
};
  • T: $O(N)$
  • S: $O(1)$