Skip to content

leetcode_OJ WC97 解題心得

  • Contest time: Aug 12, 2018

888. Uncommon Words from Two Sentences Map的運用

  • 題意:找只在自己的句子中出現過一次而對方未出現的詞彙
  • 思路:水題,map計數跑兩次即可。
  • 分析:Time complexity O(N), Space complexity O(N)
    class Solution
    {
    public:
        vector<string> uncommonFromSentences(string A, string B)
        {
            map<string, int>mymap;
            map<string, int>mymap2;
            stringstream ss(A);
            stringstream ss2(B);
    
            vector<string> stra;
            vector<string> strb;
            vector<string> res;
            string tmp;
    
            while(ss >> tmp)
            {
                stra.push_back(tmp);
            }
    
            while(ss2 >> tmp)
            {
                strb.push_back(tmp);
            }
    
            for(int i = 0; i < stra.size(); i++)
            {
                mymap[stra[i]]++;
            }
            for(int i = 0; i < strb.size(); i++)
            {
                mymap2[strb[i]]++;
            }
    
            for(map<string, int>::iterator it = mymap.begin(); it != mymap.end(); it++)
            {
                if(it->second == 1)
                {
                    if(mymap2[it->first] == 0)
                    {
                        res.push_back(it->first);
                    }
                }
            }
    
            for(map<string, int>::iterator it = mymap2.begin(); it != mymap2.end(); it++)
            {
                if(it->second == 1)
                {
    
                    if(mymap[it->first] == 0)
                    {
                        res.push_back(it->first);
                    }
                }
            }
            return res;
        }
    };
    

889. Spiral Matrix III 模擬

  • 題意:矩陣中逆時針旋轉,問界內的座標有哪些
  • 思路:模擬,先從題目給的圖片可看出行走的距離是一個1 1 2 2 3 3 4 4 5 5 6 6每兩組遞增一次一,一樣用for loop + dx dy (或說drow dcolumn)代表要走的方向,每次走一點看看是否在界內即可。 不用想太難,想說還要自己建一個grid在看是否界內,這樣太麻煩,只要想像成有 無限大的地圖持續走訪,看看是否在邊界即可
  • 分析:Time complexity O(max(ROW, COL) ^ 2), Space complexity O(ROW * COL)
    class Solution
    {
    public:
        vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0)
        {
            //1 1 2 2 3 3 4 4 5 5 6 6
            //0 1 2 3 4 5 6 8 7 8 9 10* increase if it is in the odd number
            int rpos = r0, cpos = c0, dir = 0, go = 1;
            int cnt = 0, ans_cnt = 0;
            int dr[4] = {0, 1, 0, -1};
            int dc[4] = {1, 0, -1, 0};
            vector<vector<int>> res;
    
            //push back the start position
            res.push_back({rpos, cpos});
            ans_cnt++;
            while(ans_cnt < R * C)
            {
                for(int i = 1; i <= go; i++)
                {
                    rpos += dr[dir];
                    cpos += dc[dir];
                    if(rpos >= 0 && rpos < R && cpos >=0 && cpos < C) //push back th eanswer if it is in the grid
                    {
                        res.push_back({rpos, cpos});
                        ans_cnt++;
                    }
                }
    
                if(cnt & 1) //to make  1 1 2 2 3 3 4 4 5 5 sequence
                {
                    go++;
                }
                cnt++;
    
                dir++;
                dir %= 4; //change direction
            }
            return res;
        }
    };
    

890. Possible Bipartition 二分圖檢測

  • 題意:每一個人都討厭自己以外的某人(edge),問如何分成兩組(bipartie graph)使每一組裡面的所有人不會互相討厭
  • 思路:題意如同二分圖檢測問題,解題流程如下
    • 首先初始化一些必要的資料結構,例如visited[N + 1]這個array用以紀錄走訪過的點避免重複走訪,其中dislikes就是adjecent list中的edges。
    • DFS,沒走過的點標記為-1,走過的點分兩種,一種放0色、另一種1色,查找adjacent list看接下來要走訪點,並且依據當前顏色選擇另一個顏色為相鄰頂點上色(異色)。
    • 查找的途中發現相鄰點已經上過色並且是相同色,代表無法切割成二分圖,將結果標示為false
  • 分析:Time complexity O(V + E)(vector of dislikes acts as an adjacent list method for graph), Space complexity O(V + E) (adjacent list plus the visited array to mark the traversed vertices) 想知道使用相鄰list 時間複雜度分析後是O(V + E)而非O(V*E)可以看這篇
  • 心得,本以為很難,想到是二分圖檢測居然一次過了,完全出乎意料呢:D,以前圖論問題頗卡,算是罩門,光是一個深度優先搜索寫了半天還是無窮遞迴解不下去,算是為自己的圖論算法打下信心囉 :D
class Solution
{
public:
    bool is_bipartie;
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) //dislike act as adjacent matrix
    {
        int visited[N + 1] , visit_cnt; //visited matrix. -1 as unvisited, 0 as color1, 1 as color2
        memset(visited, -1, sizeof(visited));

        is_bipartie = true;
        dfs(1, 0, visited, dislikes);
        return is_bipartie;
    }
    void dfs(int cur_vertex,int cur_color, int* visited, vector<vector<int>>& dislikes)
    {
        visited[cur_vertex] = cur_color;
        for(int i = 0; i < dislikes.size(); i++)
        {
            if(dislikes[i][0] == cur_vertex) //check if unvisited and is the path of current vertex
            {
                if(visited[dislikes[i][1]] == -1) //unvisited
                {
                    dfs(dislikes[i][1], cur_color == 1 ? 0 : 1 /*change the color for adjacent vertices*/, visited, dislikes);
                }
                else if(visited[dislikes[i][1]] == cur_color) //visited, same color, not bipartie graph
                {
                    is_bipartie = false;
                }
            }
        }
    }

};

891. Super Egg Drop DP難題,尚未完成,之後有空寫,還望包涵