Tag Archives: 双指针

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。
小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。
以下 T 行每行一个正整数N。
对于30%的数据,1 ≤ N ≤ 1000
对于80%的数据,1 ≤ N ≤ 100000
对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。
要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		} else {
			ll i = 1, j = 2;
			ll sum = i + j, ans = 0;
			while (true) {
				while (j <= n && sum < n) {
					++j;
					sum += j;
				}
				if (j > n)break;
				while (i < j && sum > n) {
					sum -= i;
					++i;
				}
				if (sum == n) {
					//printf("%d\n", j - i + 1);
					ans = max(ans, j - i + 1);
					break;
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

无奈,提交后TLE,只过了80%的数据。
实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。
后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。
举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。
所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		}
		else {
			ll ans = 1;
			for (ll i = 1; i < n; ++i) {
				ll sum = (1 + i)*i / 2;
				if (sum > n)break;
				ll left = sum - n;
				if (left%i == 0) {
					ans = max(ans, i);
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

本代码提交AC,用时10MS。

LeetCode Smallest Range

LeetCode Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a,b] is smaller than range if b-a < d-c or a < c if b-a == d-c.
Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -105 <= value of elements <= 105.
  4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

给定k个升序数组,求一个整数区间,该区间能至少包括所有数组的一个元素,且该区间最小。最小的定义是区间长度最小,如果区间长度相同,则区间起始点小则小。
参考Find smallest range containing elements from k lists这篇博客,突然发现GeeksforGeeks网站上的题比Leetcode上的多好多,而且都有详细题解和代码,好棒。
要求区间最小,则区间只包括每个数组的一个元素最好,所以我们要找k个数组中的k个数,使得这k个数的最大值和最小值的差最小,那么这个区间的两个端点就是这个最大值和最小值。
所以我们对k个数组维护k个指针,初始时都指向每个数组的首元素,然后找到这k个数的最大值和最小值,得到一个区间及其长度。然后我们不断循环:向前移动k个指针中的最小者,在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束,则返回得到的最小区间。
以样例为例。

  1. i,j,k分别指向三个数组的开头,即i=j=k=0,相当于在[4,0,5]中找最大值和最小值,构成区间[0,5],长度为5。
  2. 最小值为j所在数组,所以++j,在新的数组[4,9,5]中找最大值和最小值,构成区间[4,9],长度为5。
  3. 最小值为i所在数组,所以++i,在新的数组[10,9,5]中找最大值和最小值,构成区间[5,10],长度为5。
  4. ++k,新数组[10,9,18],区间[9,18],长度为9。
  5. ++j,新数组[10,12,18],区间[10,18],长度为8。
  6. ++i,新数组[15,12,18],区间[12,18],长度为6。
  7. ++j,新数组[15,20,18],区间[15,20],长度为5。
  8. ++i,新数组[24,20,18],区间[18,24],长度为6。
  9. ++k,新数组[24,20,22],区间[20,24],长度为4。
  10. ++j,第二个数组遍历完毕,结束,遍历过程中,得到的长度最短的区间是[20,24]。

完整代码如下:

class Solution {
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();
		vector<int> ptr(k, 0);
		while (true) {
			bool done = false;
			int curmin = INT_MAX, curmax = INT_MIN, minid = 0;
			for (int i = 0; i < k; ++i) {
				if (ptr[i] >= nums[i].size()) {
					done = true;
					break;
				}
				if (nums[i][ptr[i]] < curmin) {
					curmin = nums[i][ptr[i]];
					minid = i;
				}
				if (nums[i][ptr[i]] > curmax) {
					curmax = nums[i][ptr[i]];
				}
			}
			if (done)break;
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			++ptr[minid];
		}
		return{ ansmin,ansmax };
	}
};

本代码提交AC,用时1016MS。
因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。
求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下:

class Solution {
private:
	struct Node {
		int value;
		int idx;
		int nxt;
		Node(int v, int i, int n) :value(v), idx(i), nxt(n) {};
		bool operator<(const Node& nd) const {
			return value > nd.value;
		}
		bool operator>(const Node& nd) const {
			return value < nd.value;
		}
	};
public:
	vector<int> smallestRange(vector<vector<int>>& nums) {
		int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size();
		priority_queue<Node> pq;
		for (int i = 0; i < k; ++i) {
			pq.push(Node(nums[i][0], i, 1));
			if (nums[i][0] < ansmin) {
				ansmin = nums[i][0];
			}
			ansmax = max(ansmax, nums[i][0]);
		}
		int curmax = ansmax;
		while (true) {
			int curmin = pq.top().value;
			int minidx = pq.top().idx;
			int minnxt = pq.top().nxt;
			pq.pop();
			if (curmax - curmin < ansrange) {
				ansrange = curmax - curmin;
				ansmin = curmin;
				ansmax = curmax;
			}
			if (minnxt < nums[minidx].size()) {
				curmax = max(curmax, nums[minidx][minnxt]);
				pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1));
			}
			else break;
		}
		return{ ansmin,ansmax };
	}
};

本代码提交AC,用时56MS。
 

LeetCode Minimum Size Subarray Sum

LeetCode 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.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

给定一个正整数数组和一个数s,要求从数组中找出最短的子串,使得子串的和大于等于s。
解法1,双指针法,O(n)。维护两个指针left和right,初始时都为0,我们的目标就是使[left,right)的和大于等于s。所以先right右移,直到和大于等于s,此时尝试缩小区间,即left也右移,在右移的过程中,更新最短子串长度,且累加和要减去left指向的数。这样不断的先移right,后移left,并更新最短长度。
代码如下,非常简洁易懂。

class Solution {
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
		while(right < n) {
			while (right < n&&sum < s)sum += nums[right++];
			while (left <= right&&sum >= s) {
				ans = min(ans, right - left);
				sum -= nums[left++];
			}
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时13MS。
解法2,二分查找,O(nlgn)。我们先想想暴力方法,枚举每个left,从left开始枚举right,直到累加和第一次超过sum,更新最短长度。这样两层循环,时间复杂度是O(n^2)的。有没有办法把内层查找right的时间复杂度降低呢?
遇到子数组和的问题,马上要想到借助累加和数组。所以我们先求到原数组的累加和数组accuSum[n+1],其中accuSum[i]等于原数组中前i-1个数之和。我们利用accuSum来循环right,对于每个left,它要找一个right,使得left和right之间的和大于等于s,也就相当于在accuSum中找一个right,使得accuSum[right]>=accuSum[left]+s,等价于accuSum[right]-accuSum[left]>=s,即left到right的累加和大于等于s。因为原数组是正整数数组,所以accuSum是递增有序的,所以我们可以在accuSum中二分查找。即查找right的复杂度降为了O(lgn),所以总的复杂度就是O(nlgn)了。
完整代码如下:

class Solution {
private:
	int searchRight(vector<int>& accuSum, int l, int r, int target) {
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (accuSum[m] == target)return m;
			else if (accuSum[m] > target)r = m - 1;
			else l = m + 1;
		}
		return l;
	}
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), ans = INT_MAX;
		vector<int> accuSum(n + 1, 0);
		for (int i = 1; i <= n; ++i)accuSum[i] = accuSum[i - 1] + nums[i - 1];
		for (int left = 0; left < n; ++left) {
			int right = searchRight(accuSum, left, accuSum.size() - 1, accuSum[left] + s);
			if (right == n + 1)break;
			ans = min(ans, right - left);
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时16MS。

LeetCode Longest Word in Dictionary through Deleting

LeetCode Longest Word in Dictionary through Deleting
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

Note:

  1. All the strings in the input will only contain lower-case letters.
  2. The size of the dictionary won't exceed 1,000.
  3. The length of all the strings in the input won't exceed 1,000.

给定一个字典d和字符串s,问d中哪些字符串可以通过s删除若干个字符得到,要求输出满足条件的最长字符串,如果有多个,则输出字典序最小的。
本题有两个考点,一是判断t是否能通过删除s中的若干个字符得到。使用两个指向s,t的指针i,j,j不断后移找t[i],找到之后i,j都后移。最终如果找到t中所有字符,则成功,否则失败。
另一个考点是,找出所有满足条件的字符串之后,怎样找到长度最长且字典序最小的字符串。这可以通过自定义string的比较函数,然后sort得到。具体看代码:

bool comp(const string& s1, const string& s2) {
	return s1.size() > s2.size() || (s1.size() == s2.size() && s1 < s2);
}
class Solution {
private:
	bool convert(const string& src, const string& dest){
		int m = src.size(), n = dest.size();
		if (m < n)return false;
		int i = 0, j = 0;
		while (i < m) {
			while (i < m && src[i] != dest[j])++i;
			if (i >= m)break;
			++i;
			++j;
			if (j == n)break;
		}
		return j == n;
	}
public:
	string findLongestWord(string s, vector<string>& d) {
		vector<string> cand;
		for (int i = 0; i < d.size(); ++i) {
			if (convert(s, d[i]))cand.push_back(d[i]);
		}
		sort(cand.begin(), cand.end(), comp);
		if (cand.size() > 0)return cand[0];
		else return "";
	}
};

本代码提交AC,用时135MS。