Collating string
You are given a string s composed of upper and lower case English letters.
In a collated string, two adjacent characters s[I] and s[I + 1] do not satisfy both of the following conditions:
0 <= i <= s.length – 2
S [I] is a lowercase character, but s[I + 1] is the same uppercase character; And vice versa.
Please tidy up the string. Each time you can select two adjacent characters from the string that meet the above conditions and delete them until the string is clean.
Return the collated string. They guarantee that the answer to the test sample is unique given the constraints given.
Note: Empty strings are also collated strings, even though there are no characters in them.
Example:
Enter: s = ‘leEeetcode’
Output: ‘leetcode’
Explanation: whether you choose I = 1 or I = 2, s is reduced to ‘leetcode’
In this case, the following two points are mainly investigated:
-
Data structure — stack
-
Use the difference of charCode to determine whether two adjacent characters are uppercase characters
Time complexity O(n), space complexity O(n).
const makeGood = function(s) {
const stack = [];
let startIndex = 0;
while (startIndex < s.length) {
const currentItem = s[startIndex];
if (stack.length && Math.abs(currentItem.charCodeAt(0) - stack[stack.length - 1].charCodeAt(0= = =))32) {
stack.pop();
} else {
stack.push(currentItem);
}
startIndex++;
}
return stack.join(' ');
};
Copy the code
Find the KTH bit in the NTH string
Given two positive integers n and k, the binary string Sn is formed as follows:
S1 = ‘0’
When I > 1, Si + ‘1’ = Si – 1 + reverse (invert (Si – 1))
Where + represents concatenation, reverse(x) returns the string inverted x, and invert(x) reverses every bit of x (0 becomes 1, and 1 becomes 0)
Title data guarantees a winner in the game.
For example, the first four strings in a sequence that matches the above description are, in order:
S1 = ‘0’
S2 = ‘011’
S3 = ‘0111001’
S4 = ‘011100110110001’
Please return the KTH character of Sn. The data in the question guarantees that K must be within the length range of Sn.
Example:
Input: n = 3, k = 1
Output: ‘0’
Explanation: s3 is ‘0111001’ and its first digit is ‘0’.
After reading the question, you should notice the following rules:
-
Each line of string is 2^n – 1 in length
-
The next line is a recursive relation to the previous line
-
The left and right parts of each line are flipped
According to the above rules, we can calculate how many flips the KTH character goes through during the evolution from the first line to the NTH line to get the final result.
Time complexity O(n), space complexity O(1).
const findKthBit = function(n, k) {
let current = n;
let reverseCount = 0;
if (n === 1) {
return '0'
}
while (current > 1) {
const total = 2 ** current - 1;
const mid = Math.ceil(total / 2);
if (k === mid) {
if (reverseCount % 2= = =0) {
return '1';
}
return '0';
}
if (k > mid) {
reverseCount++;
k = mid * 2 - k;
}
current--;
}
if (reverseCount % 2= = =0) {
return '0';
}
return '1';
};
Copy the code
Maximum number of nonoverlapping nonempty subarrays
Give you the array NUMs and an integer target.
Return the maximum number of non-empty non-overlapping subarrays, and the sum of the elements of each subarray is target.
Example:
Enter: nums = [1,1,1,1], target = 2
Output: 2
Explanation: there are two non-overlapping subarrays [1,1] and [1,1].
To solve this problem, consider the following two questions:
-
Subarray targets and values
-
Subarrays do not overlap
The simplest way to evaluate subarray targets and values is to loop twice. Using prefixes and sums reduces complexity to O(n) by swapping space for time.
However, to ensure that the subarrays do not overlap, some modification needs to be performed on the basis of prefix and: after finding the subarrays that meet the conditions, reset the current prefix and state.
Time complexity O(n), space complexity O(n).
const maxNonOverlapping = function(nums, target) {
let record = new Set(a);
record.add(0);
let ans = 0;
let currentSum = 0;
for (let i = 0; i < nums.length; i++) {
currentSum += nums[i];
if (record.has(currentSum - target)) {
ans++;
record.clear();
record.add(0);
currentSum = 0;
} else {
record.add(currentSum);
}
}
return ans;
};
Copy the code
Minimum cost of cutting sticks
There is a stick of n units, marked with positions from 0 to n.
You can cut in order or change the order of cutting as needed.
The cost of each cut is the current length of the stick to be cut, and the total cost of cutting the stick is the sum of all the previous cuts. Cutting the stick will divide the stick into two smaller sticks (the sum of the two sticks is the length of the stick before cutting). See the first example for a more intuitive explanation.
Returns the minimum total cost of cutting a stick.
Example:
Input: n = 7, cuts = [1, 3, 4, 5]
Output: 16
This is a problem type to find the optimal solution, and it’s easy to think of the idea is to go through all the solutions to get the optimal solution.
For this problem, we can try the segmentation points between [0, n], and the minimum cost of each segmentation is composed of the following three parts:
-
The length of the current stick
-
Cost of subsequent cutting of the left half of the stick after segmentation
-
Cost of subsequent cutting of the right half of the stick after segmentation
It is easy to see that this is a recursive relationship, and do not forget to use memorization to reduce the calculation of repeating subproblems in the recursive enumeration process.
const minCost = function(n, cuts) {
const cache = new Map(a);
return help(0, n, cuts, cache);
};
function help(left, right, cuts, cache) {
const cacheKey = `${left}-${right}`;
if (cache.has(cacheKey)) {
return cache.get(cacheKey);
}
let min = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < cuts.length; i++) {
if (cuts[i] > left && cuts[i] < right) {
let cost = help(left, cuts[i], cuts, cache) + help(cuts[i], right, cuts, cache);
min = Math.min(min, cost);
}
}
if (min === Number.MAX_SAFE_INTEGER) {
min = 0
} else {
min += right - left;
}
cache.set(cacheKey, min);
return min;
}
Copy the codeIn the prompt condition of this problem, the length of the cuts array is far less than N, so there is room for optimization of the above solution.
In the optimized solution, enumeration subscripts can be obtained from the cuts array, but the cuts array given in the question needs to be modified as follows:
-
The cuts array is disordered, which makes it difficult to judge whether the current cutting point is within the legal range during traversal.
-
Cuts does not contain head and tail subscripts, resulting in no starting and ending boundary during recursion.
The optimized code looks like this:
const minCost = function(n, cuts) {
const record = new Map(a);
cuts.sort((a, b) = > a - b);
cuts.unshift(0);
cuts.push(n);
const maxIndex = cuts.length - 1;
return help(0, maxIndex, cuts, record);
};
function help(leftIndex, rightIndex, cuts, record) {
const cacheKey = `${leftIndex}-${rightIndex}`
if (record.has(cacheKey)) {
return record.get(cacheKey);
}
const left = cuts[leftIndex];
const right = cuts[rightIndex];
let min = Number.MAX_SAFE_INTEGER;
for (let i = leftIndex + 1; i < rightIndex; i++) {
const cost = help(leftIndex, i, cuts, record) + help(i, rightIndex, cuts, record);
min = Math.min(cost, min);
}
if (min === Number.MAX_SAFE_INTEGER) {
min = 0;
} else {
min += right - left;
}
record.set(cacheKey, min);
return min;
}
Copy the code
Highlights from the past
-
LeetCode Tour for Front End Engineers – Weekly Race 200
-
LeetCode Tour for front End Engineers – Week 185
-
Front End Engineer’s LeetCode Journey — Week 184
-
LeetCode Tour for front End Engineers – Week 183
-
JavaScript AC solutions to problems on LeetCode
