

leetcode_OJ WC91 解題心得

Contest time: Jul 1,2018

PA. 860. Lemonade Change 水題

思路：水題，用map儲存每一種硬幣與其對應的數量，注意十五元也能用三個五塊找錢即可

Time complexity = O(N), Space complexity (with auxilary map structure) = O(N)

#define FORI(n) for(int i = 0; i < n; ++ i)
class Solution
{
public:
    bool lemonadeChange(vector<int>& bl)
    {
        map<int ,int>mymap;
        FORI(bl.size())
        {
            mymap[bl[i]]++;
            if(bl[i] == 10)
            {
                if(mymap[5] == 0)
                {
                    return 0;
                }
                else
                {
                    mymap[5]--;
                }
            }
            else
            {
                if(mymap[5] > 0 && mymap[10] > 0)
                {
                    mymap[5]--;
                    mymap[10]--;
                }
                else if(mymap[5] >=3 && mymap[10] == 0)
                {
                    mymap[5] -= 3;
                }
                else if(mymap[5] == 0 || mymap[10] == 0)
                {
                    return 0;
                }
            }
        }
        return 1;
    }
};

PB. 863. All Nodes Distance K in Binary Tree 經典樹圖論題，DFS加上set, map 實作應用

找出一個二元樹中，從指定結點出發，給定一距離K，找出所有距離同為K的節點，相當重要又經典！
Geekforgeeks ref
題意：找出一個二元樹中，從一個點出發，找出所有距離該點為K的節點（包含父節點也算）
思路：首先DFS用map儲存每一個child-parent node pair，接著從該點出發，走訪兩種CASE
- 左右子樹（每走過一個點就將K-1，代表一個距離的減少），直到K==0 代表指定的距離到了，便可以停下。
- 父節點，則是將child對應的perent以 parent_ptr = map[current_node]取出，再行走訪，因為方才走訪過的點會被放入set中，因此換到父結點的時候便不會又走回來現在的點，一舉兩得
- 走訪的同時也不忘了使用set 儲存visited path以防重複走訪，也就是標記過已經進行DFS過的節點。
分析: Time complexity = O(N), Space complexity = O(N) where N is # of nodes in that BT.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    map<TreeNode* , TreeNode* > child_par_pair; //[child parent] pair for accessing the relationship b/w the child and parent
    set<int> visited;
    vector<int> res; //store the result

    vector<int> distanceK(TreeNode* root, TreeNode* target, int dist_K)
    {
        if(root == NULL) //return nothing if the
        {
            return vector<int>(1,0);
        }
        dfs_parent(root);
        dfs_relation(target, dist_K);
        return res;
    }
    void dfs_parent(TreeNode* root)
    {
        if(root == NULL)
        {
            return;
        }
        if(root->left)
        {
            child_par_pair[root->left] = root;
            dfs_parent(root->left);
        }
        if(root->right)
        {
            child_par_pair[root->right] = root;
            dfs_parent(root->right);
        }
    }
    void dfs_relation(TreeNode* root, int dist_K)
    {
        if(root == NULL)
        {
            return;
        }

        for(set<int>::iterator it = visited.begin(); it != visited.end(); ++it)
        {
            if(*it == root->val)//the current-visiting node has been traversed before, so we just quit
            {
                return;
            }
        }
        visited.insert(root->val); //push the current visited node for dfs mark what node has been traversed to prevent duplicated traversing

        if(dist_K == 0) //dist_K reached
        {
            res.push_back(root->val);
            return;
        }

        if(root->left) //traverse left child`
        {
            dfs_relation(root->left, dist_K - 1);
        }

        if(root->right) //traverse left child`
        {
            dfs_relation(root->right, dist_K - 1);
        }

        TreeNode* parent_node_to_traverse = child_par_pair[root];
        if(parent_node_to_traverse)
        {
            dfs_relation(parent_node_to_traverse, dist_K - 1);
        }
    }
};

PC.861. Score After Flipping Matrix 貪心算法

同步刊載於leetcode discussion thread
題意：數個二進位數字以矩陣的row表示，每一次我們能toggle整個row或column使得整個row或column的全部元素XOR with 1，問最大的二進位數字是多少（亦即將每個row的二進位數字加總）
思路：基本的貪心演算法題(因為我們希望局部解愈大愈好，每一次都讓該col or row的組合情形能最大)，因此有以下兩種情形
- 對於橫排由於 2^n > sum(2^n-1 + 2^n-2 + ....... + 1)，因此改變最左邊的MSB會將剩餘的都設為一來的好，所以反轉使得MSB = 1是好的
- 對於直排亦即每一個位數（即column而言，把1變得比0多也是好事)，因此對於col我們可以記錄該col有多少個零以及一，倘若零的個數大於一的個數，則反轉整個col使得一的個數比較多。

綜合以上兩點便能得到以下的code，其中迴圈跳出條件為，每一個二進位數字矩陣，每一個col的一的個數均大於零的個數（局部最佳解），每一個row的MSB都是1(源自於方才的數學計算式)
* 分析: Time complexity = O(row * col), Space complexity (with auxiliary vector of pair) = O(col)

/*
Algorithm design:
Greedy algorithm is used in this problem.
Since 2^n > sum(2^n-1 + 2^n-2 + ....... + 1), so the msb(most significant bit) has more power than all the other.
Steps:
1. We may toggle the whole column if cnt_0 is greater than cnt_1 in such row to make # of 1s more than 0s.
2. Than we toggle the whole row if the first
3. For loop termination,  we check 2 flags
    First we check if all of the columns that 1s are greater than 0s.
    Than we check if all of the rows that the msb is all 1 to max the value.
*/
class Solution
{
public:
    int matrixScore(vector<vector<int>>& arr)
    {
        int flag_1 = 0, flag_2 = 0, cnt_0 = 0, cnt_1 = 0;
        vector<pair<int, int>>col_data_pair;
        while(1)
        {
            //data structure
            col_data_pair.clear();
            col_data_pair.resize(arr[0].size());
            flag_1 = 1;
            flag_2 = 1;
            //statistical data of 1 and 0 of each column
            for(int i = 0; i < arr[0].size(); i++)
            {
                cnt_0 = cnt_1 = 0;

                for(int j = 0; j < arr.size(); j++)
                {
                    if(arr[j][i])
                    {
                        cnt_1++;
                    }
                    else
                    {
                        cnt_0++;
                    }
                }
                //check the first flag of 1s and 0s
                if(cnt_0 > cnt_1)
                {
                    flag_1 = 0;
                }

                col_data_pair[i].first = cnt_0;
                col_data_pair[i].second = cnt_1;
            }
            //check the second flag of MSB
            for(int i = 0; i < arr.size(); i++)
            {
                if(arr[i][0] == 0)
                {
                    flag_2 = 0;
                }
            }
            if(flag_1 == 1 && flag_2 == 1)
            {
                break;
            }
            //toggle the column if such column's 0 more than 1

            for(int i = 0; i < col_data_pair.size(); i++)
            {
                if(col_data_pair[i].first > col_data_pair[i].second)
                {
                    for(int j = 0; j < arr.size(); j++)
                    {
                        arr[j][i] ^= 1;
                    }
                }
            }

            //toggle the row if such row's arr[0][col] = 0, if so, toggle the whole row

            for(int i = 0; i < arr.size(); i++)
            {
                if(arr[i][0] == 0)
                {
                    for(int j = 0; j < arr[i].size(); j++)
                    {
                        arr[i][j] ^= 1;
                    }
                }
            }


        }
        return binary_sum(arr);
    }
    int binary_sum(vector<vector<int>>& arr)
    {
        unsigned int sum = 0;
        for(int i = 0; i < arr.size(); i++)
        {
            string str_bin("");
            for(int j = 0; j < arr[i].size(); j++)
            {
                str_bin += arr[i][j] + '0';
            }
            sum += (unsigned int) stoi(str_bin, nullptr, 2);
        }
        return sum;
    }
};

PD 862. Shortest Subarray with Sum at Least K deque應用

TLE VERSION
思路:精簡之後的暴力解，雖然使用了滑動視窗，但是時間並沒有壓在O(N^2)，基本上還是近乎查找每一個所有可能的subarray而已。

分析: Time complexity O(N^2) Space complexity O(1) (only some helper variables)

/*
TLE in very large testcases(vector with length more than 30000), testcases 83/93
the algorithm is implemented in the sliding-window.
need to optimize to O(N)
*/
class Solutio
{
public:
    int shortestSubarray(vector<int>& arr, int target_val)
    {

        if(arr.size() == 1)
        {
            return 1;
        }
        int start_idx = 0, end_idx = 1, cur_sum = 0;
        unsigned int min_len = 9999999;
        while(arr.size() > 1)
        {
            cur_sum = 0;
            for(int i = start_idx; i <= end_idx; i++)
            {
                cur_sum += arr[i];
            }
            if(cur_sum < target_val)
            {
                if(end_idx != arr.size() - 1)//keep adding the elements, extending the right side of the window
                {
                    end_idx++;
                }
                else if(end_idx == arr.size() - 1 && start_idx < end_idx) //shrink the subarray, try to toss away some negative values
                {
                    if(cur_sum - arr[start_idx] >= target_val) //if successfully toss away enough negative value, then the min_len can be updated
                    {
                        min_len = min((unsigned int)end_idx - start_idx, min_len);
                    }
                    start_idx++; //shrink the left side of the window
                }
            }
            else //if the target value is reached, then we can try to shrink the left side of the window to try to make the window narrower
            {
                min_len = min((unsigned int)end_idx - start_idx + 1, min_len);
                if(start_idx < end_idx) //shrink the leftside
                {
                    start_idx++;
                }
                else if(start_idx == end_idx) //moving forward to prevent locked situation
                {
                    start_idx++;
                    end_idx++;
                }
                if(cur_sum - arr[start_idx - 1] >= target_val) //update the min value if the shrinked sliding window still satisfies the criteria
                {
                    min_len = min((unsigned int)end_idx - start_idx + 1, min_len);
                }
            }
            //I think the TLE mainly due to this part since my time complexity is not O(N) but O(N^2)
            if(start_idx == arr.size() - 1 && end_idx == arr.size() - 1 ) //if we reach the end of the vector, pop the last element, to do again for the smaller array.
            {
                arr.pop_back();
                start_idx = 0;
                end_idx = 1;
            }
        }
        return (min_len == 9999999) ? -1 : min_len; //check the return answer
    }
};

AC VERSION
改進: 採用deque(和queue一樣FCFS的資料結構，但是可以頭尾都出去的雙隊列)，採用prefix_sum來找到哪個區間的prefix_sum 是負的，那代表經過那段區間只會變小，可以捨棄他。
思路: 首先將各個array到該點的prefix_sum寫出來，其中prefix_sum[i] = sum(arr[0] + arr[1] + ... arr[i - 1]) (加總到前一項的和)，接著，由於 prefix_sum[j] - prefix_sum[i] 代表從第i項到第j - 1項目的區間和，再以以下程式碼求解(具體更詳細的思路請見程式碼的註解)
分析: Time complexity: O(N) Space complexity O(N) (auxiliary deque)
備註:下面的printf可以自己放測資跑跑看，比較好理解流程唷 :D photo

class Solution {
public:
    int shortestSubarray(vector<int>& arr, int target) {
        int prefix_sum[arr.size() + 1] = {0};

        for(int i = 1; i <= arr.size(); i++)
        {
            prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1];
        }

        int ans = 0x7fffffff;

        deque<int> window_left;

        for(int end = 0; end <= arr.size(); end++)
        {
            printf("end now %d   back ", end);
            while(!window_left.empty() && prefix_sum[end] - prefix_sum[window_left.back()] <= 0)
            {
                printf("%d ", window_left.back());
                window_left.pop_back();
            }
            printf("   front   while loop 2   front ");
            while(!window_left.empty() && prefix_sum[end] - prefix_sum[window_left.front()] >= target) //區間和大於等於木雕哦要愈短愈好，所以從deque的front(比較早進來的<也就是比較左邊的，向右縮減，最後期望縮短到最小又能符合大於等於目標值(亦即，這個區間(prefix_sum[j] - prefix_sum[i] 代表從第i項到第j - 1項目的區間和)能符合 prefix_sum[end] - prefix_sum[window_left.front()] >= target)的長度，每次就向右邊縮短一格(見下方)
            {
                int beg = window_left.front();
                printf("%d ", window_left.front());
                window_left.pop_front();//目前這一格的長度找出後，向右邊縮短一格，接著重新跑這個while迴圈，看看能不能繼續符合他的目標數值要求，可以的話就在繼續縮短，不可以就跳離迴圈
                ans = min(ans, end - beg); //找出比較短的長度
            }
            printf("back \n");
            window_left.push_back(end);
        }

        return ans == 0x7fffffff ? -1 : ans;

    }
};