# Weekly Contest 407 日期 2024/07/21 這次做滿第三題,第三題似曾相識,好像在與 LeetCode 某題內容相同。 第四題來不及看,難度約為 Medium+ - [Number of Bit Changes to Make Two Integers Equal](https://leetcode.com/problems/number-of-bit-changes-to-make-two-integers-equal/) - [Vowels Game in a String](https://leetcode.com/problems/vowels-game-in-a-string/) - [Maximum Number of Operations to Move Ones to the End](https://leetcode.com/problems/maximum-number-of-operations-to-move-ones-to-the-end/) - [Minimum Operations to Make Array Equal to Target](https://leetcode.com/problems/minimum-operations-to-make-array-equal-to-target/) ### 第一題 ```cpp int minChanges(int n, int k) { int ret = 0; for(int i = 0; i < 32; i++) { int x = n & (1 << i); x = !!x; int y = k & (1 << i); y = !!y; if(x == 0 && y == 1) return -1; if(x == 1 && y == 0) ret++; } return ret; } ``` ### 第二題 這題卡我太久,實際上 Alice 只要有任意一個母音就能贏。 ```cpp bool doesAliceWin(string s) { stack<int> ss; int count = 0; for (int i = 0; i < s.size(); i++) { bool is_v = s[i] == 'i' || s[i] == 'a' || s[i] == 'e' || s[i] == 'o' || s[i] == 'u'; count += is_v; if (count & 1) ss.push(i); } if (count == 0) return false; return true; } ``` ### 第三題 ```cpp int maxOperations(string s) { const int n = s.size(); int ret = 0; int i = 0; int count_one = 0; while (i < n) { if (s[i] == '1') { int j = i; for(; j < n; j++) { if(s[j] == '0') break; count_one++; } for(; j < n; j++) { if(s[j] == '1') break; } if(j != n || s[j - 1] == '0') ret += count_one; i = j; }else i++; } return ret; } ``` ### 第四題 參考[討論區解答](https://leetcode.com/problems/minimum-operations-to-make-array-equal-to-target/solutions/5508919/o-n-keep-track-of-how-many-increments-decrements-are-done-till-now) ```cpp long long minimumOperations(vector<int>& nums, vector<int>& target) { const int n = nums.size(); using ll = long long; ll incr = 0; ll decr = 0; ll ret = 0; for(int i = 0; i < n; i++) { ll diff = target[i] - nums[i]; if(diff > 0) { if(incr < diff) ret += diff - incr; incr = diff; decr = 0; }else if(diff < 0) { ll abs_diff = abs(diff); if(decr < abs_diff) ret += abs_diff - decr; decr = abs_diff; incr = 0; }else{ incr = 0; decr = 0; } } return ret; } ``` 後來有更簡易的寫法,其中這題跟 [LeetCode 1526 類似](https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/754674/JavaC++Python-Comparison-of-Consecutive-Elements/) ```cpp long long minimumOperations(vector<int>& nums, vector<int>& target) { const int n = target.size(); using ll = long long; ll pre = 0; ll ret = 0; for(int i = 0; i < n; i++) { ll diff = target[i] - nums[i] - pre; ret += max(diff, 0LL); pre = target[i] - nums[i]; } return ret + max(-pre, 0LL); } ```
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up