Yitao's Blog

5841. Find the Longest Valid Obstacle Course at Each Position tag: monotone-stack, greedy, Maximum Increasing Subsequence Description Solution Use monotone-stack to find the longest subsequence end with obstacles[i] Greedily replace the very obstacles[j], j < i that exactly greater than obstacles[i], other elements in the stack just remain 12341 3 5 7 4stack : 1 3 5 7after : 1 3 4 7 Just be careful about the same number should also be inclueded, so just binary search for (obstacle[i] ...

233. Number of Digit One Description Solution We can calculate the number of one on each digit, for example 123To count one's number on 1234567we can count one on 1, 10, 100...If we need to count one on 100, we can have 1234 * 100 + 100 So we can have 12k's digit count = [n/10^(k+1)] * 10 ^ k + min(max(n mod 10^(k+1) - 100, 0), 10^k) Code 123456789101112131415class Solution {public: int countDigitOne(int n) { // mulk 表示 10^k // 在下面的代码中，可以发现 k ...

1671. Minimum Number of Removals to Make Mountain Array Tag: monotone-stack, DP, No AC first time Description Solution For each index, we can calculate its preceding minimum delete number and its succeeding delete number. Then search for the minimum sum. So how to calculate deleting number? -> calculate longest monotonous sequence A naive way, use DP to calculate: Find the very nums[j] that lower than nums[i], then inherit its by length + 1 1dp[i] = max(dp[j] + 1) for all nums[j] < ...

5840. Minimum Number of Swaps to Make the String Balanced tag: stack, greedy Description Solution In each switch, brackets are reduced mostly 2, at least 1. 123//Just swap the first dismatched ] with second dismatched [2 for: ]]] [[[ -> []] [][. 1 for just 1 pair left, switch them then all done Code 12345678910111213141516171819class Solution {public: int minSwaps(string s) { //只要[的右边有对应个数个]即可 stack<int> stk; int res = 0; for(int i = 0; ...

5832. Array With Elements Not Equal to Average of Neighbors Description Solution To generate the array in the requirement, my strategy is pickthe smallest the largest the second smallest …, because we have the largest * 2 > the sum of the smallest numbers, it should always work. Or we can keep looping the swap the mismatched pair till we get the correct array. Code 123456789101112131415class Solution {public: vector<int> rearrangeArray(vector<int>& nums) { ...

576. Out of Boundary Paths Description Solution DP for each stage. Code 123456789101112131415161718192021222324252627282930313233class Solution {public: static constexpr int MOD = 1'000'000'007; int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int outCounts = 0; vector<vector<vec ...

399. Evaluate Division Description Solution Record each equations’ string name and its corresponding index, used later. Then do a floyd search to all strings, find their division. Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { vector<string ...

1583. Count Unhappy Friends Description Solution Iterate all potential pair(i,j) to see if they are ranked higher in each preference Code 12345678910111213141516171819202122232425262728293031class Solution {public: int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) { vector<unordered_map<int,int>> perfers(n); unordered_map<int,int> Map; int res = 0; for(int j = ...

516. Longest Palindromic Subsequence Description Solution Use DP to find the longest palindromic subsequence in one interval 12//dp[i][j] = (i > j) from j to i, longest palinidromic subsequence//dp[i][j] = dp[i-1][j+1] + 2 (if s[i] == s[j]), else dp[i][j] = dp[i][j+1] Code 123456789101112131415161718192021class Solution {public: int longestPalindromeSubseq(string s) { //dp[i][j] = (i > j) from j to i, longest palinidromic subsequence //dp[i][j] = dp[i-1 ...

446. Arithmetic Slices II - Subsequence Description Solution DP to check out the previous subsequence number satisfied requirement. 1dp[i][d] = In position i, the number satisfied requirement that difference is d Code 123456789101112131415161718typedef long long LL;class Solution { // int res = 0;public: int numberOfArithmeticSlices(vector<int>& nums) { vector<unordered_map<LL,int>> dp(nums.size()+1); int res = 0; for(int i = 1; ...

679. 24 Game Description Solution Recursively check all the potential combination of the 4 numbers. In each round, we iteratively select 2 out of N numbers, calculate the result of +, -, *, / then put back the result into next round. Don’t forget the function return condition is if N == 1, nums[0] == 24 . And for float number, we should do this in abs() < 1e-6 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { int op[4] = {1 ...

491.Increasing Subsequences Description Solution Two solutions: DP, use set<vector<int>> to deduplicate Back Tracking, don’t forget deduplicating Code 12345678910111213141516171819202122232425class Solution {public: vector<vector<int>> findSubsequences(vector<int>& nums) { vector<vector<vector<int>>> dp(nums.size()); set<vector<int>> Set; for(int i = 0; i < nums.size(); i ++){ ...

133. Clone Graph Description Solution I uses two map to store the visited and waiting nodes, then BFS for the next node be copied. Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859/*// Definition for a Node.class Node {public: int val; vector<Node*> neighbors; Node() { val = 0; neighbors = vector<Node*>(); } Node(int _val) { val = _val; neighbors = ve ...

413. Arithmetic Slices Description Solution Iteration to find start & end of each Arithmetic Code 12345678910111213141516171819202122class Solution {public: int numberOfArithmeticSlices(vector<int>& nums) { if(nums.size() < 3) return 0; vector<int> diff(nums.size()-1); for(int i = 1; i < nums.size(); i++){ diff[i-1] = nums[i] - nums[i-1]; } int prev = diff[0], count = 0, res = 0; ...

1353. Maximum Number of Events That Can Be Attended Description Solution Use priority_queue to find the closed DDL’s event and handle it in the day. There is are tricky programming point that we can directly iterate the whole [earliest start time, latest finish time] to find each day’s best strategy or we can also iterate every sorted event. Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class Solution { static bool cmp(vector<int&g ...