268 篇文章 含有標籤「leetcode」

class Solution {
public:
    void rotate(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        for(int i = 0; i < n; ++i)
        {
            for(int j = i; j < n; ++j)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i = 0; i < n; i++)
        {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int start)
    {
        if (start == nums.size())
        {
            res.push_back(nums); return;
        }

        for (int i = start; i < nums.size(); ++i)
        {
            swap(nums[i], nums[start]);
            backtracking(nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
};

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;
    }
};

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;
    }
};

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;
    }
};

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]);
        }
    }
};

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();
        }
    }
};

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;
    }
};

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;
    }
};

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;
    }
};

/*
 * @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