Problem 1 1656. Design ordered flow

We can open an array of strings to hold strings, use an extra variable PTR to hold the position of the PTR, and when inserting new strings, check to see if there is a sequence of consecutive increments by ID from the PTR.

The code is as follows:

class OrderedStream { public: int n; int ptr; vector<string> stream; OrderedStream(int _n) { n = _n; ptr = 1; stream = vector<string>(n + 1, ""); // all strings in the string array are initially empty} vector<string> insert(int id, string value) {stream[id] = value; If (stream[PTR] == "") {// If (stream[PTR] == "") {// If a new string is inserted, but id= PTR string is empty, return an empty string array {}; } vector<string> res; int last = ptr; For (int I = PTR; i <= n; ++i) { if(stream[i] ! = "") { res.push_back(stream[i]); } else {last last = I; break; } } if(stream[last] ! = "") { ptr = last + 1; } else { ptr = last; } return res; }}; /** * Your OrderedStream object will be instantiated and called as such: * OrderedStream* obj = new OrderedStream(n); * vector<string> param_1 = obj->insert(id,value); * /Copy the code

Problem 2:5603. Determine if two strings are close

If two strings are close, these conditions are met :(1) the two strings have the same number of different letters; (2) If the number of occurrences of all letters is counted, then if there are y letters with x occurrences in one string, then there must also be y letters with X occurrences in another string; (3) All letters in the first string appear in the second word, and vice versa.

For points (1) and (3) we can use two unorderd_sets. (2) we can count the frequency of each letter in the two strings with two unordered_map<char, int> cnt1, cnT2, and then concatenate all the frequencies in the hash table into one string using two strings (or arrays). If the original words word1 and word2 are “close” strings, then the two sorted strings must be equal by concatenating their letter frequencies. If they are not equal, then they are not close. This point is easy to understand, for example, if there are several words in word1 with the frequency of occurrence: 2, 1, 3, 4, and word2 with the frequency of occurrence: 1, 2, 4, 3, then their occurrence is 1234, so the two words are close to each other.

The code is as follows:

class Solution { public: unordered_set<char> hash1, hash2; Unordered_map <char, int> cnt1, cnt2; Bool closeStrings(string word1, string word2) {if(word1. Size ()! Word2.size ()) {// If two words are of different lengths, then they are not close to return false; } for(auto &c : word1) { hash1.insert(c); ++cnt1[c]; } for(auto &c : word2) { hash2.insert(c); ++cnt2[c]; } for(auto &c: hash1) {if(hash2.count(c) == 0) {// If the first word has letters that do not appear in the second word, they do not approach return false; }} for(auto &c: hash2) {if(hash1.count(c) == 0) {// If the second word has letters that do not appear in the first word, they do not approach return false; } } string fre1, fre2; For (auto & CNT: cnt1) {fre1 += to_string(cnt.second); fre1 += to_string(cnt.second); } for(auto &cnt : cnt2) { fre2 += to_string(cnt.second); } sort(fre1.begin(), fre1.end()); sort(fre2.begin(), fre2.end()); if(fre1 ! = fre2) { return false; } return true; }};Copy the code

Problem 3:5602. The minimum operand to reduce x to 0

Both ends of the array are continuously deleted, so that the sum of the deleted elements is x. The longest interval in the array is sum-x, where sum is the sum of all elements in the array.

The sum of intervals in an array can be evaluated using the prefix sum, but the start and end times of the enumeration interval are still O(n^2), which is unacceptable for an interval length of 10^5.

So we can consider using a hash table unordered_map

mp to record the subscripts of a prefix sum, mp[I] = j, nums[0] + nums[1] + nums… PreSum [I] = preSum[I] = preSum[I] = preSum[I] = target [I] We have a sum that satisfies the question, and then we can update the answer with the number of elements in the array – the length of the range. Using a hash table to record the subscripts of the prefixes and, we can find the sum of intervals and the length of intervals satisfying the condition in the time complexity of O(n).
,>

The code is as follows:

class Solution { public: vector<int> preSum; unordered_map<int, int> mp; Int minOperations(vector<int> &nums, int x) {if(nums[0] > x &&nums.back () > x) {// If the first and last elements of the array are greater than x, Return -1 return -1; } int n = nums.size(); preSum = vector<int>(n + 1, 0); int res = n + 1; mp[0] = 0; For (int I = 1; i <= n; ++i) { preSum[i] = preSum[i - 1] + nums[i - 1]; mp[preSum[i]] = i; PreSum [I]} int sum = preSum[n]; If (x > sum) {return -1; } if(sum == x) {return n; } int target = sum - x; Sum -x for(int I = 1; i <= n; ++ I) {if(mp[preSum[I] -target] == 0) {if(preSum[I] == target) {// If preSum[I] is target, the sum of the elements after I is x res = min(res, n-i); [left ~ I] int left = mp[preSum[I] -target]; [left ~ I] int left = mp[I] -target]; res = min(res, n - (i - left)); }} return sum () {return sum () {return sum () {return sum () {return sum (); }};Copy the code

Problem 4 1659. Maximizing grid happiness

State compression DP, here reference pit god video problem solving

We use dp[r][I][e][S] to represent the maximum grid happiness of s in front r line grid (1<= R <= N), with I introverted people (0<= I <=introvertsCount), e extroverted people (0<= E <=extrovertsCount), and the distribution status of residents in r line is. The ternary representation of s is the distribution of row r. If the JTH grid of row r (0<=j<m) has no inhabitant, then the JTH bit of S is 0. If you live with an introvert, the JTH bit of s is 1; If you live with an extrovert, the JTH place of s is 2. Then, the maximum happiness of the entire grid is the maximum happiness of the grid with the distribution state of S (0<= S <3^m), which processes the first n rows and has a maximum of introvertsCount and extroverts living in introvertsCount.

With state representation, we have to think about state transitions.

First, since we are enumerating in rows, we need to consider the effect of the previous row on each row (impact: change in the number of introverts, change in the number of extroverts, change in happiness). In addition, because this line personnel distribution may also affect happiness on the line (such as a line of the person, will affect on a line of introverted and outgoing people happiness), so we are enumerated a line on a line state and state, want to consider the influence of each other, the concrete analysis to write in the comments below.

The code is as follows:

int dp[7][7][7][250]; // dp[r][I][e][s] : the former r line uses the maximum grid happiness of I introverts and E extroverts, and the distribution state is S. Since there are at most 5 cells in a row, 3^5=243, the distribution state s ranges from 0 to 242 int base[6]; // Base indicates how many powers of 3 each column is. Base [0] = 3^0 = 1, base[1] = 3^1 = 3, base[2] = 3^2 = 9, base[3] = 3^3 = 27, Column 4 base[4] = 81 and column 5 base[5] = 243. Int movIn[250][250], movEx[250][250], mov[250][250]; / / movIn [I] [j] said ways from a personnel distribution state I move to the next line state j inhibited the change of the number of personnel distribution, movEx [I] [j] said outgoing changes, the number of mov [I] [j] said happiness change class Solution {public: Int get(int s, int I) {// Calculate the ith bit of state s. Return value =0: Nobody =1: introvert =2: extrovert s = s % base[I + 1]; return s / base[i]; } int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { memset(dp, -1, sizeof dp); dp[0][0][0][0] = 0; base[0] = 1; for(int i = 1; i <= 5; ++i) { base[i] = base[i - 1] * 3; } int lim = base[m]; MovIn, movEx, mov for(int s = 0; int s = 0; s < lim; ++s) {// enumerate the state of the previous row s for(int cur = 0; cur < lim; + + cur) {/ / enumerated the current state of the cur movIn [s] [cur] = movEx [s] [cur] = mov [s] [cur] = 0; For (int I = 0; for(int I = 0; i < m; If (get(cur, I) == 0) {// If (get(cur, I) == 0) {continue; Else {if(get(s, I) == 1) {// If (get(s, I) == 1) {// If (get(s, I) == 1) {-30 mov[s][cur] -= 30; } else if(get(s, I) == 2) {// Happiness +20 mov[s][cur] += 20; // Happiness +20 mov[s][cur] += 20; MovIn [s][cur] += 1; movIn[s][cur] += 1; Mov [s][cur] += 120; mov[s][cur] += 120; If (get(s, I) > 0) {// If (get(s, I) > 0) {-30 mov[s][cur] -= 30; } if(I > 0 && get(cur, I - 1) > 0) {// If (I > 0 && get(cur, I - 1) > 0) {// If (I > 0 && get(cur, I - 1) > 0) { } if(I + 1 < m && get(cur, I + 1) > 0) {// If (I + 1 < m && get(cur, I + 1) > 0) { }} if(get(cur, I) == 2) {// If (get(cur, I) == 2) { Mov [s][cur] += 40; Mov [s][cur] += 20; if(get(s, I) > 0) {mov[s][cur] += 20; If (I > 0 && get(cur, I - 1) > 0) {// If (I > 0 && get(cur, I - 1) > 0) {// If (I > 0 && get(cur, I - 1) > 0) {// If (I > 0 && get(cur, I - 1) > 0) { } if(I + 1 < m && get(cur, I + 1) > 0) {// If (I + 1 < m && get(cur, I + 1) > 0) { }}}}} // Dynamic programming for(int r = 1; r <= n; ++r) {// enumerate 1 to n lines for(int I = 0; i <= introvertsCount; ++ I) {// enumerate the number of introverts for(int e = 0; e <= extrovertsCount; ++e) {// enumerate the number of extroverts for(int s = 0; s < lim; + + s) {/ / enumerated on a line (state) line r - 1 s the if (dp (r - 1] [I] [e] [s] = = 1) {continue; } for(int cur = 0; cur < lim; ++cur) {cur int deltaIn = movIn[s][cur], deltaEx = movEx[s][cur], delta = mov[s][cur]; // deltaIn, deltaEx, Delta represents the change in the number of introverts, extroverts, and well-being from the previous line s to the line cur. If (I + deltaIn <= introvertsCount && e + deltaEx <= extrovertsCount) {// If the number of introverts and extroverts doesn't exceed introvertsCount and extrovertsCount, respectively, Dp [r][I + deltaIn][E + deltaEx][cur] = Max (DP [r][I + deltaIn][E + deltaEx][cur], DP [r-1][I][E][s] + delta); } } } } } } int ans = 0; For (int I = 0; for(int I = 0; i <= introvertsCount; For (int e = 0; // int e = 0; // int e = 0; e <= extrovertsCount; ++e) { for(int s = 0; s < lim; ++s) { ans = max(ans, dp[n][i][e][s]); } } } return ans; }};Copy the code