In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1 Output: 2 Explanation: Flip A[0], then flip A[2]. Example 2:

Input: A = [1,1,0], K = 2 Output: -1 Explanation: No matter how we flip subarrays of size 2, we can’t make the array become [1,1,1]. Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3 Output: 3 Explanation: Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0] Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0] Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“babca”,”bbazb”] and deletion indices {0, 1, 4}, then the final array after deletions is [“bc”,”az”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= … <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= … <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: [“babca”,”bbazb”] Output: 3 Explanation: After deleting columns 0, 1, and 4, the final array is A = [“bc”, “az”]. Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]). Note that A[0] > A[1] - the array A isn’t necessarily in lexicographic order. Example 2:

Input: [“edcba”] Output: 4 Explanation: If we delete less than 4 columns, the only row won’t be lexicographically sorted. Example 3:

Input: [“ghi”,”def”,”abc”] Output: 0 Explanation: All rows are already lexicographically sorted.

classSolution { public: intminDeletionSize(vector<string>& A){ int row = A.size(), col = A[0].size(); int max_len = 0; vector<int> dp(col); dp[0] = 1; for (int c = 1; c < col; c++) { dp[c] = 1; for (int k = 0; k < c; k++) { if (greater(A, c, k)) dp[c] = max(dp[c], dp[k] + 1); } max_len = max(max_len, dp[c]); } return col - max_len; } boolgreater(vector<string>& A, int c1, int c2){ int row = A.size(); for (int r = 0; r < row; r++) { if (A[r][c1] < A[r][c2]) returnfalse; } returntrue; } };

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”,”vyz”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] … <= A[A.length - 1]).

Return the minimum possible value of D.length.

Example 1:

Input: [“ca”,”bb”,”ac”] Output: 1 Explanation: After deleting the first column, A = [“a”, “b”, “c”]. Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]). We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1. Example 2:

Input: [“xc”,”yb”,”za”] Output: 0 Explanation: A is already in lexicographic order, so we don’t need to delete anything. Note that the rows of A are not necessarily in lexicographic order: ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= …) Example 3:

Input: [“zyx”,”wvu”,”tsr”] Output: 3 Explanation: We have to delete every column.

classSolution { public: boolvalidMountainArray(vector<int>& arr){ int size = arr.size(); int i = 0; while (i < size) { if (i > 0 && arr[i] <= arr[i - 1]) break; i++; } if (i == 1 || i == size) returnfalse; while (i < size) { if (arr[i] >= arr[i-1]) break; i++; } return i == size; } };

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1: Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4. Note: You may assume all numbers in the input are non-negative integers. The length of Profits array and Capital array will not exceed 50,000. The answer is guaranteed to fit in a 32-bit signed integer.

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6 Output: 1 Explanation: Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch. Example 2:

Input: nums = [1,5,10], n = 20 Output: 2 Explanation: The two patches can be [2, 4]. Example 3:

classSolution { public: intminPatches(vector<int>& nums, int n){ long miss = 1; int add = 0; int i = 0; int size = nums.size(); while (miss <= n) { if (i < size && nums[i] <= miss) miss += nums[i++]; else { miss += miss; add++; } } return add; } };

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3] Output: 1 Explanation: We only need to swap the second (row[1]) and third (row[2]) person. Example 2:

Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples are already seated side by side. Note:

len(row) is even and in the range of [4, 60]. row is guaranteed to be a permutation of 0…len(row)-1.

bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. Follow up: Could you implement the functions of the class with each function works in average O(1) time?

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-2^31 <= val <= 2^31 - 1 At most 105 calls will be made to insert, remove, and getRandom. There will be at least one element in the data structure when getRandom is called.

classRandomizedSet { public: /** Initialize your data structure here. */ RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ boolinsert(int val){ if (maps.count(val) > 0) returnfalse; data.push_back(val); maps[val] = data.size() - 1; returntrue; } /** Removes a value from the set. Returns true if the set contained the specified element. */ boolremove(int val){ if (maps.count(val) > 0) { int idx = maps[val]; maps.erase(val); if (idx != data.size() - 1) { data[idx] = data.back(); maps[data.back()] = idx; } data.pop_back(); returntrue; } returnfalse; } /** Get a random element from the set. */ intgetRandom(){ int size = data.size(); int idx = rand() % size; return data[idx]; } private: unordered_map<int, int> maps; //val -> pos vector<int> data; };

/** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */