Two Pointer问题总结 #14
Comments
167. Two Sum II - Input array is sortedGiven an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based.
var twoSum = function(numbers, target) {
var left = 0, right = numbers.length-1;
while(left < right){
if(numbers[left] + numbers[right] == target){
return [left+1, right+1]
}else if(numbers[left] + numbers[right] > target){
right --
}else{
left++
}
}
return []
}; |
763. Partition LabelsA string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Note: S will have length in range [1, 500]. function partitionLabels( s) {
var ans = []
if (!s.length){
return ans;
}
// 依次对数组进行遍历, 先找到相应的数据的最后一个位置, 构成区间, 然后查看区间内的元素, 随时扩充区间.
// 若找到了 就保存下来, 然后继续从下一个上一个区间的最后一个+1的位置继续进行
for (var i = 0; i < s.length;) {
// 最开始确定的区间 [start, end] 这个end可以扩充
var start = i;
// 没有判断这个end是否存在
var end = s.lastIndexOf(s[start]);
if (end == -1) {
end = start;
}
// 当end不存在的时候, 会返回一个很大的数字.
// 在子区间内继续进行扩充
for (var j = start + 1; j <= end; j++) {
var lastPos = s.lastIndexOf(s[j]);
// 如果能找到这个字母的最后一个位置
if (lastPos != -1 && lastPos > end) {
// 这个是最终的end
end = lastPos;
}
}
// 要记录被扩大的区间
console.log(s.slice(start, end+1))
ans.push(end - start + 1);
// 对i进行更新
i = end + 1;
}
return ans
}
console.log( partitionLabels('ababcbacadefegdehijhklij') )
console.log( partitionLabels('abbcdbyyuiu') ) |
|
这道题给了我们一个字符串S，然我们将其尽可能多的分割为子字符串，条件是每种字符最多只能出现在一个子串中。比如题目汇总的例子，字符串S中有多个a，这些a必须只能在第一个子串中，再比如所有的字母e值出现在了第二个子串中。那么这道题的难点就是如何找到字符串的断点，即拆分成为子串的位置。我们仔细观察题目中的例子，可以发现一旦某个字母多次出现了，那么其最后一个出现位置必须要在当前子串中，字母a，e，和j，分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置，我们可以使用一个 HashMap 来建立字母和其最后出现位置之间的映射，那么对于题目中的例子来说，我们可以得到如下映射： a -> 8 建立好映射之后，就需要开始遍历字符串S了，我们维护一个 start 变量，是当前子串的起始位置，还有一个 last 变量，是当前子串的结束位置，每当我们遍历到一个字母，我们需要在 HashMap 中提取出其最后一个位置，因为一旦当前子串包含了一个字母，其必须包含所有的相同字母，所以我们要不停的用当前字母的最后一个位置来更新 last 变量，只有当i和 last 相同了，即当 i = 8 时，当前子串包含了所有已出现过的字母的最后一个位置，即之后的字符串里不会有之前出现过的字母了，此时就应该是断开的位置，我们将长度9加入结果 res 中，同理类推，我们可以找出之后的断开的位置，参见代码如下： function partitionLabels( s) {
var res = [], n = s.length
if (!n){
return res;
}
var hash = {}
for(var i = 0; i< n; i++){
hash[s[i]] = i
}
var last = 0, start = 0
for (var i = 0; i < n; ++i) {
last = Math.max(last, hash[s[i]]);
if (i == last) {
res.push(i - start + 1);
start = i + 1;
}
}
return res;
}
console.log( partitionLabels('ababcbacadefegdehijhklij') )
console.log( partitionLabels('abbcdbyyuiu') ) |
https://blog.csdn.net/excellentlizhensbfhw/article/details/82597006 function numSubarrayProductLessThanK(nums, k) {
var n = nums.length
if (n < 1 || k <= 1){
return 0;
}
var count = 0, left = 0, multiResult = 1
for (var right = 0; right < n; right++) {
multiResult *= nums[right];
while( multiResult >= k){
multiResult /= nums[left]
left+=1 //用于确定滑动窗口的最左边界
}
count += right - left +1 //累加子数组个数
}
return count;
}
console.log( numSubarrayProductLessThanK([10,5,2,6], 100) ) |
424. Longest Repeating Character ReplacementGiven a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations. Note:
Explanation: 定义一段区间内出现次数最多的字符为“优势字符” var characterReplacement = function(nums, k) {
var n = nums.length
var hash = {}, left = 0, right = 0, maxCount = 0,res = 0
for ( ; right < n; right++) {
var c = nums[right];
hash[c] = !hash[c] ? 1 : hash[c]+1;
maxCount = Math.max(maxCount, hash[c]) //得到当前优势的字符
if(right - left + 1 - maxCount > k){
hash[nums[left]] --;
left++
}
res = Math.max(res, right - left+1)
}
return res;
}; |
567. Permutation in StringGiven two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string. Example 1:
Note: The input strings only contain lower case letters. function checkInclusion(s1, s2) {
var hash1 = new Array(26).fill(0);
var hash2 = new Array(26).fill(0);
for (var i = 0; i < s1.length; i++) {
hash1[s1.charCodeAt(i) - 97]++;
}
var left = 0, right = 0
while (right < s2.length) {
hash2[s2.charCodeAt(right) - 97]++
if (hash1 + '' === hash2 + '') {
return true;
}
right++
if (right - left + 1 > s1.length) {
hash2[s2.charCodeAt(left) - 97]--;
left++
}
}
return false
}
console.log(checkInclusion('aa', "aa"))
console.log(checkInclusion('ab', "eidbaooo"))
console.log(checkInclusion('bdi', "eidboaoo"))
console.log(checkInclusion('abb', "eidbgaooo")) |
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example:
If there is no such window in S that covers all characters in T, return the empty string "". function minWindow(s, t) {
if (!s || !t) {
return ''
}
var tmap = new Array(128 - 65).fill(0)
function getIndex(a, i) {
return a.charCodeAt(i) - 65
}
for (var i = 0; i < t.length; i++) {
var c = getIndex(t, i)
++tmap[c]
}
var res = "", counts = 0, minwin = Infinity, left = 0;
for (var right = 0; right < s.length; right++) {
var r = getIndex(s, right)
--tmap[r]; //碰到重复的减去
if (tmap[r] >= 0) {
++counts;//如果只有一个就相加
}
//刚好相等
while (counts >= t.length) {
if (minwin > right - left + 1) {
minwin = right - left + 1;
res = s.substr(left, minwin);
}
var l = getIndex(s, left)
if (tmap[l] >= 0) { //太长了
--counts;
}
++tmap[l];
++left;
}
}
return res;
}
minWindow("adobecodebanc", "abc") |
209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
简化判定条件
还有这样的骚操作
The text was updated successfully, but these errors were encountered: