leetcode_OJ WC67 解題心得
- Contest time: Jan 14, 2018
- Virtual Contest time: Mar 24, 2018
PA. 762. Prime Number of Set Bits in Binary Representation 位元操作水題
- 思路：位元運算抓一，看看一的個數是否為質數
class Solution { public: int bitcnt(int num) { int cnt = 0; while(num > 0) { if(num & 0x1) { cnt++; } num>>=1; } return cnt; } bool is_prime(int num) { if(num == 1) return false; for(int i=2;i<=(int)sqrt(num);i++) { if(num % i == 0) { return false; } } return true; } int countPrimeSetBits(int left, int right) { int cnt = 0, bit = 0; for (size_t i = left; i <= right; i++) { bit = bitcnt(i); if(is_prime(bit)) { cnt++; } } return cnt; } };
PB. 763. Partition Labels 貪心演算法推理題
- 思路：必須讓所有char開始結束均屬於同一個區塊，故利用struct紀錄每一個char的最早開始位置，與最晚結束位置。若字元x的開始位置x_start介於當前最小開始(min_start)與結束(max_end)之間，並且字元x的結束位置大於當前的max_end 則必須再將max_end延伸，否則無法符合題目需求讓char最小開始與最大結束街位在同一個區塊。 每次都找當前最遠的並檢查是否更新（區域最優解），是屬於貪心算法的一種
class Solution { public: struct stend { char alpha; int start, end; }; bool mycompare(stend s1, stend s2) { return s1.start < s2.start; } vector<int> partitionLabels(string str) { int count = str.size(); vector<stend> vec; vec.resize(26); for(int i = 0; i < 26; i++) { vec[i].start = -1; vec[i].end = 0; vec[i].alpha = 0; } vec[str[0]-'a'].start = 0; for (size_t i = 1; i < count; i++) { vec[str[i]-'a'].alpha = str[i]; if(vec[str[i]-'a'].start == -1) { vec[str[i]-'a'].start = i; } if(i > vec[str[i]-'a'].end) { vec[str[i]-'a'].end = i; } } int min_start = vec[str[0]-'a'].start; int max_end = vec[str[0]-'a'].end; //greedy approach int partition = 0; vector<int>res; for (size_t i = 0; i < count; i++) { if( vec[str[i]-'a'].start > min_start && vec[str[i]-'a'].start < max_end && vec[str[i]-'a'].end > max_end ) { max_end = vec[str[i]-'a'].end; } if(i == max_end || i == count - 1)//last will definitely cut over to match. just in case { if(i != count - 1) { res.push_back(max_end - min_start + 1); min_start = vec[str[i + 1]-'a'].start; max_end = vec[str[i + 1]-'a'].end; } else { res.push_back(max_end - min_start + 1); // a special case } } } return res; } };
PC. 764. Largest Plus Sign 動態規劃
- 由於每一點的+號中心，周圍的四角都必須等長為連續的1(重疊子問題)，若不等長則只能盡量延伸至『四角最短的角』作為本次的order(最優子結構)，因此採用動態規劃
首先把四個方向（朝上 朝下 朝左 朝右 連續的1給記載 例如朝右行進 0110111 → 0120123
朝左行進→ 0210321 的寫法），最後全部走訪過一遍後，對於每一點取min(u,d,l,r)連續一的個數就是當前能組成＋號的order（度數）
最後重新走訪一遍找出對於每一點最大的order。
class Solution { public: int orderOfLargestPlusSign(int MAXN, vector<vector<int>>& mines) { int order = 0, count = mines.size(); vector<vector<int>>dp_up(MAXN, vector<int>(MAXN, 1)), dp_down(MAXN, vector<int>(MAXN, 1)), dp_left(MAXN, vector<int>(MAXN, 1)), dp_right(MAXN, vector<int>(MAXN, 1)), dp_ans(MAXN, vector<int>(MAXN, 0)); for (size_t i = 0; i < count; i++) { dp_up[mines[i][0]][mines[i][1]] = 0; dp_down[mines[i][0]][mines[i][1]] = 0; dp_left[mines[i][0]][mines[i][1]] = 0; dp_right[mines[i][0]][mines[i][1]] = 0; } //main dynamic programming //up continuous (bottom up) for(int i = 0;i < MAXN; i++) { for(int j = MAXN - 2;j >= 0; j--) { if(dp_up[j][i] == 1) { dp_up[j][i] = dp_up[j + 1][i] + 1; } } } //down continuous (top down) for(int i = 0;i < MAXN; i++) { for(int j = 1;j < MAXN; j++) { if(dp_down[j][i] == 1) { dp_down[j][i] = dp_down[j - 1][i] + 1; } } } //left continuous for(int i = 0;i < MAXN; i++) { for(int j = MAXN - 2;j >=0 ;j--) { if(dp_left[i][j] == 1) { dp_left[i][j] = dp_left[i][j + 1] + 1; } } } //right continuous for(int i = 0;i < MAXN; i++) { for(int j = 1;j < MAXN; j++) { if(dp_right[i][j] == 1) { dp_right[i][j] = dp_right[i][j - 1] + 1; } } } //check for direction since the plus sign has to satisfiy all the four direction, if one of the direction fails. it has to decrease to that direction for(int i = 0; i < MAXN; i++) { for(int j = 0; j < MAXN; j++) { dp_ans[i][j] = min(min(dp_up[i][j], dp_down[i][j]), min(dp_left[i][j], dp_right[i][j])); if(dp_ans[i][j] > order) { order = dp_ans[i][j]; } } } return order; } };