今天的題單：

• Rotting Oranges

• Search in Rotated Sorted Array

994. Rotting Oranges

思路：先找出所有的壞掉的橘子，用 BFS 找出下一輪哪些橘子會壞掉，並用 queue 追蹤每輪壞掉的橘子和時間。最後再看看地圖上有沒有橘子沒壞掉。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<pair<int, int>, int > > rotten; // {loc, minute}
        int minutes = 0;

        // find the all the rotten oranges fisrt
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 2)
                    rotten.push({{i, j}, 0});
            }
        }

        // rotting
        while (!rotten.empty()) {
            pair<pair<int, int>, int > orange = rotten.front();
            pair<int,int> loc = orange.first;
            int t = orange.second;

            push_adjcent(loc.first + 1, loc.second, grid, rotten, t + 1);
            push_adjcent(loc.first - 1, loc.second, grid, rotten, t + 1);
            push_adjcent(loc.first, loc.second + 1, grid, rotten, t + 1);
            push_adjcent(loc.first, loc.second - 1, grid, rotten, t + 1);
            minutes = max(minutes, t);
            rotten.pop();
        }

        // check if any fresh orange left
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1)
                    return -1;
            }
        }
        return minutes;
    }

    void push_adjcent(int i, int j, vector<vector<int>>& grid, queue<pair<pair<int, int>, int > >& q, int minute) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size())
            return;
        
        if (grid[i][j] == 1) {
            q.push({{i, j}, minute});
            grid[i][j] = 2;
        }
    }
};

33. Search in Rotated Sorted Array

思路：題目要求 O(log n) time 解法。不過因爲 array 不一定是遞增排序好的所以不能直接用 binary search，需要做一點變形：要想怎麼去框出 target 在內的遞增數列。

Rotated Sorted Array 的特性是它會有兩段遞增數列，所以在縮短搜尋範圍時要先確定 mid 和 left/right 框出來的數列是不是遞增的並且 target 落在區間內，如果是才能採用 binary search。

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 - left) / 2;
            if (nums[mid] == target) return mid;
            
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            } else {
                if (nums[right] >= target && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }

        return -1;
    }
};