Re: [閒聊] LeetCode Weekly Contest 409

看板Marginalman作者eden6197 (:))時間1年前 (2024/08/04 13:45)推噓8(8推 0噓 2→)

留言10則, 9人參與討論串2/2 (看更多)

我這次3000多名感覺可以+個10分 https://i.imgur.com/9kYi4ea.png

附圖為證第一題: 要找目標旁邊或是斜角的元素和思路: 照做 ```cpp class neighborSum { public: vector<vector<int>> paper; neighborSum(vector<vector<int>>& grid) { paper = grid; } int adjacentSum(int value) { for(int i = 0 ; i < paper.size(); i ++) { for(int j = 0 ; j < paper[0].size() ; j ++) { if(paper[i][j] == value) { int res = 0; if(i>0)res += paper[i-1][j]; if(i+1<paper.size())res += paper[i+1][j]; if(j>0)res +=paper[i][j-1]; if(j+1<paper[0].size())res += paper[i][j+1]; return res; } } } return 0; } int diagonalSum(int value) { for(int i = 0 ; i < paper.size(); i ++) { for(int j = 0 ; j < paper[0].size() ; j ++) { if(paper[i][j] == value) { int res = 0; if(i>0 && j>0)res += paper[i-1][j-1]; if(i+1<paper.size() && j+1<paper[0].size())res += paper[i+ 1] [j+1]; if(j>0 && i+1<paper.size())res +=paper[i+1][j-1]; if(j+1<paper[0].size() && i>0)res += paper[i-1][j+1]; return res; } } } return 0; } }; /** * Your neighborSum object will be instantiated and called as such: * neighborSum* obj = new neighborSum(grid); * int param_1 = obj->adjacentSum(value); * int param_2 = obj->diagonalSum(value); */ ``` 第二題: 有n個城市編號0 ~ n-1 他們i跟i-1之間的距離都是1 給你很多個queries 每個queries會有一條新的道路同樣距離都會是1 請問每加進一個新的道路之後最短的路徑是什麼思路: 因為資料比較少所以直接用個圖來模擬一下就好了 ```cpp class Solution { public: vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queri es ) { int len = queries.size(); vector<int> paper(n,0); for(int i = 0 ; i < n ; i ++) { paper[i] = i; } vector<int> res(len,0); unordered_map<int,vector<int>> save; for(int i = 0 ; i < n-1 ; i ++) { save[i].push_back(i+1); } for(int i = 0 ; i < len ; i ++) { save[queries[i][0]].push_back(queries[i][1]); for(int j = 0 ; j < n ; j ++) { for(int k : save[j] ) { paper[k] = min(paper[k] , paper[j]+1); } } res[i] = paper[n-1]; } return res; } }; ``` 第三題: 圖不會交疊思路: 模擬然後TLE 這應該有其他解法放棄 -- https://i.imgur.com/tBVdL1R.jpeg