Tag Archives: 首尾指针

LeetCode Sum of Square Numbers

LeetCode Sum of Square Numbers
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

给定一个非负整数c,问是否存在两个整数a和b,使得a2 + b2 = c。
简单题,首尾指针法,首尾指针分别指向[0,c],根据a2 + b2 和 c的大小,首指针++或者尾指针--。
但是这样性能太差,过不了大数据,其实尾指针只需要到sqrt(c)即可,因为如果b大于sqrt(c)的话,a2 + b2 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)],性能大幅提升。
代码如下:

class Solution {
public:
	bool judgeSquareSum(int c) {
		long long i = 0, j = sqrt(c) + 1;
		while (i <= j) {
			long long cur = i*i + j*j;
			if (cur == c)return true;
			else if (cur < c)++i;
			else --j;
		}
		return false;
	}
};

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

LeetCode 4Sum

LeetCode Teemo Attacking
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

本题问一个数组中哪四个数加起来的和等于target,相当于LeetCode 3Sum的升级版,但是方法和3Sum是一样的,先枚举前两个数,对于后两个数,用首尾指针来求和。
一开始我的代码完全按照LeetCode 3Sum来写,先求最大最小值,然后用桶来hash,最后三层循环,代码如下:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    	int min_v = INT_MAX, max_v = INT_MIN;
    	for(int i = 0; i < nums.size(); ++i) {
    		if(nums[i] < min_v)min_v = nums[i];
    		if(nums[i] > max_v)max_v = nums[i];
    	}
    	vector<int> hash(max_v - min_v + 1, 0);
    	for(int i = 0; i < nums.size(); ++i){
    		++hash[nums[i] - min_v];
    	}
    	vector<vector<int>> ans;
    	for(int i = 0; i < hash.size(); ++i){
    		if(hash[i] == 0)continue;
    		--hash[i];
    		for(int j = i; j < hash.size(); ++j){
    			if(hash[j] == 0) continue;
    			--hash[j];
    			int u = j, v = hash.size() - 1;
    			while(u <= v){
    				while(u <= v && hash[u] == 0) ++u;
    				if(u > v) break;
    				--hash[u];
    				while(u <= v && hash[v] == 0) --v;
    				if(u > v){
    					++hash[u];
    					break;
    				}
    				--hash[v];
    				int sum = i + j + u + v + 4 * min_v;
    				++hash[u];
    				++hash[v];
    				if(sum == target){
    					ans.push_back({i + min_v, j + min_v, u + min_v, v + min_v});
    					++u;
    					--v;
    				} else if(sum < target) ++u;
    				else --v;
    			}
    			++hash[j];
    		}
    		++hash[i];
    	}
    	return ans;
    }
};

但是本代码提交TLE,看了一下,最后一个样例中,最小值有-236727523之小,最大值有91277418之大,导致hash数组太大了,从而无效的空for循环太多,最终TLE。
后来改用排序代替hash,需要注意为了防止重复结果,对四个数都要有去重的操作。代码如下:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    	sort(nums.begin(), nums.end());
    	vector<vector<int>> ans;
    	int n = nums.size();
    	for(int i = 0; i < n - 3; ++i){
    		if(i > 0 && nums[i] == nums[i-1])continue; // 防止nums[i]重复
    		for(int j = i + 1; j < n - 2; ++j){
    			if(j > i + 1 && nums[j] == nums[j-1])continue; // 防止nums[j]重复
    			int u = j + 1, v = n - 1;
    			while(u < v){
    				int sum = nums[i] + nums[j] + nums[u] + nums[v];
    				if(sum == target){
    					ans.push_back({nums[i], nums[j], nums[u], nums[v]});
    					int k = u + 1;
    					while(k < v && nums[k] == nums[u]) ++k; // 防止nums[u]重复
    					u = k;
    					k = v - 1;
    					while(k > u && nums[k] == nums[v]) --k; // 防止nums[v]重复
    					v = k;
    				}
    				else if(sum < target) ++u;
    				else --v;
    			}
    		}
    	}
    	return ans;
    }
};

本代码提交AC,用时39MS。
还有一种思路是,先对数组中两数之和Hash,然后枚举两个两数之和,转换为类似Two Sum的方法,时间复杂度为O(n^2)

LeetCode Reverse Words in a String

LeetCode Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

对一个字符串,以单词为单位进行逆序。注意字符串中可能会有多个连续的空格,还可能在首尾有空格。
如果允许使用额外的空间,那就好办,先把字符串分词,然后逆序拼接。代码如下:

class Solution {
public:
	void reverseWords(string &s) {
		string ans = "";
		int start = 0, end = 0, n = s.size();
		while (true) {
			while (start < n&&s[start] == ' ')++start;
			if (start >= n)break;
			end = start + 1;
			while (end < n&&s[end] != ' ')++end;
			if (end >= n)break;
			ans = s.substr(start, end - start) + " " + ans;
			start = end + 1;
		}
		if (end > start)ans = s.substr(start, end - start) + " " + ans;
		s = ans.substr(0, ans.size() - 1);
	}
};

本代码提交AC,用时9MS。
如果不借助额外空间,则只能在原字符串上进行逆序了,有意思。我们可以进行两次翻转,第一次对整个字符串翻转,然后遍历新字符串,对每个单词进行翻转。比如原字符串是"the sky is blue",第一次翻转之后就是"eulb si yks eht",再依次对每个单词翻转,就变成了"blue is sky the"。
我们知道对一个字符串进行翻转可以使用首尾指针的方法in-place实现,代码中为了可读性,直接调用了STL的reverse函数。

class Solution {
public:
	void reverseWords(string &s) {
		reverse(s.begin(), s.end());
		//i,j为新字符串每个单词的首尾位置,u,v为旧字符串每个单词的首尾位置
		int i = 0, j = 0, u = 0, v = 0, n = s.size();
		while (true) {
			while (u < n&&s[u] == ' ')++u;
			if (u >= n)break;
			v = u;
			while (v < n&&s[v] != ' ')s[j++] = s[v++];
			reverse(s.begin() + i, s.begin() + j);
			if (v >= n)break;
			s[j++] = ' ';
			i = j;
			u = v;
		}
		if (j == 0)s = "";
		else if (s[j - 1] == ' ')s.resize(j - 1);
		else s.resize(j);
	}
};

本代码提交AC,用时6MS。虽然第二种方法更快,也更省空间,但是有很多边界条件很容易出错,我还是觉得第一种方法安全。
参考:http://www.cnblogs.com/grandyang/p/4606676.html

LeetCode Reverse Vowels of a String

LeetCode Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".


把字符串中的所有元音字母逆序。简单题,使用首尾两个指针i,j,找到元音后交换,直到i>j。
完整代码如下:

class Solution {
public:
	string reverseVowels(string s) {
		unordered_set<char> vowels = { 'a','e','i','o','u','A','E','I','O','U' };
		int i = 0, j = s.size() - 1;
		while (i < j) {
			while (i < j&&vowels.find(s[i]) == vowels.end())++i;
			if (i >= j)break;
			while (i < j&&vowels.find(s[j]) == vowels.end())--j;
			if (i >= j)break;
			swap(s[i++], s[j--]);
		}
		return s;
	}
};

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

LeetCode Two Sum II - Input array is sorted

LeetCode Two Sum II - Input array is sorted
Given 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. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2


本题要在一个已排序数组中找两个数,使得这两个数的和等于一个目标target。这应该是LeetCode Two Sum的简化版吧,因为之前那个题有一种解法就是先对数组排序,然后首尾指针夹逼,现在这个题都排好序了,那还有什么好说的呢,直接借用之前的方法。
完整代码如下:

class Solution {
public:
	vector<int> twoSum(vector<int>& numbers, int target) {
		int i = 0, j = numbers.size() - 1;
		while (numbers[i] + numbers[j] != target) {
			if (numbers[i] + numbers[j] > target)--j;
			else ++i;
		}
		return vector<int>({ i + 1,j + 1 });
	}
};

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

LeetCode Reverse String

LeetCode Reverse String
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".


本题要把一个字符串逆序一下。最简单的题了,两种方法,一种是直接调用STL的reverse函数;另一种方法是用首尾指针不断swap。
方法1代码如下:

class Solution {
public:
	string reverseString(string s) {
		reverse(s.begin(), s.end());
		return s;
	}
};

本代码提交AC,用时9MS。
方法2代码如下:

class Solution {
public:
	string reverseString(string s) {
		int i = 0, j = s.size() - 1;
		while (i < j) {
			swap(s[i], s[j]);
			++i;
			--j;
		}
		return s;
	}
};

本代码提交AC,用时也是9MS。

LeetCode Valid Palindrome

LeetCode Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.


本题要判断一个字符串是否是回文串,回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时,只考虑数字和字母,并且忽略字母的大小写。
思路很简单,两个指针i,j,分别指向字符串的头尾,各自跳过所有非数字和字母的字符,然后把大写字母转换为小写字母,如果出现头尾字符不一样的情况,则不是回文,立即返回false。如果比完整个字符串都相等,则是回文,返回true。
完整代码如下:

bool isAlphaNum(char c) {
	return (c >= 'A'&&c <= 'Z') || (c >= 'a'&&c <= 'z') || (c >= '0'&&c <= '9');
}
char upper2lower(char c) {
	if (c >= 'A'&&c <= 'Z')return c + 32;
	return c;
}
class Solution {
public:
	bool isPalindrome(string s) {
		int i = 0, j = s.size() - 1;
		while (i < s.size() && j >= 0) {
			while (!isAlphaNum(s[i]) && i < s.size())i++;
			if (i >= s.size())break;
			char c1 = upper2lower(s[i]);
			while (!isAlphaNum(s[j]) && j >= 0)j--;
			if (j < 0)break;
			char c2 = upper2lower(s[j]);
			if (c1 != c2)return false;
			i++;
			j--;
		}
		return true;
	}
};

本代码提交AC,用时12MS。
二刷。其实i,j不用走完全程,只需要走到他们交错之后就可以了,也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码,其实就是把while循环和if条件判断改一下,如下:

bool isAlphaNum(char c) {
    return (c >= 'A'&&c <= 'Z') || (c >= 'a'&&c <= 'z') || (c >= '0'&&c <= '9');
}
char upper2lower(char c) {
    if (c >= 'A'&&c <= 'Z')return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)i++;
            if (i > j)break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)j--;
            if (i > j)break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)return false;
            i++;
            j--;
        }
        return true;
    }
};

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

LeetCode Merge Sorted Array

LeetCode Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.


把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间,所以用两个指针i,j指向两个数组,然后每次从nums2中找第一个小于nums1[i]的数,然后交换nums1[i]和nums2[j],再调整nums2使有序。如此下去,nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = 0;
		while (i < m) {
			int j = 0;
			while (nums1[i] <= nums2[j] && i < m)i++;
			if (i >= m)break;
			swap(nums1[i], nums2[j]);
			while (j<n - 1 && nums2[j]>nums2[j + 1]) {
				swap(nums2[j], nums2[j + 1]);
				j++;
			}
			i++;
		}
		for (int j = 0; j < n; j++) {
			nums1[i++] = nums2[j];
		}
	}
};

本代码提交AC,用时6MS。
但是只击败了15%的人,仔细看看算法实现,最坏复杂度是O(n*m),因为如果nums1={6,7,8,9,10},nums2={1,2,3,4,5},则nums1[i]每和nums2[0]交换一次,nums2调整时都要交换n-1次,所以最坏复杂度是O(n*m)。所以应该还有更好的算法。
看题解,发现我没有很好利用nums1的数组大小至少是n+m这个信息,这说明合并之后的整个数组,最大下标只能是n+m-1,所以我们可以对nums1和nums2从后往前比较,把更大的元素依次在nums1[n+m-1]往前放,这样共3个指针,他们之间不会有overlap。此算法的复杂度只有O(max(n,m))
完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = m - 1, j = n - 1, k = m + n - 1;
		while (i >= 0 || j >= 0) {
			int a = i >= 0 ? nums1[i] : INT_MIN;
			int b = j >= 0 ? nums2[j] : INT_MIN;
			if (a > b) {
				nums1[k--] = a;
				i--;
			}
			else {
				nums1[k--] = b;
				j--;
			}
		}
	}
};

本代码提交AC,用时3MS,果然快多了。

LeetCode Sort Colors

LeetCode Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?


这道题有意思。实质是要把由0,1,2组成的数组从小到大排序,本来用计数排序,分别统计一下0,1,2这3个数字各有多少个,然后重新构造一个排好序的数组即可,但是Follow up里提到不能使用two-pass算法,并且只能使用常数空间复杂度。
我稍加思考,想到一个可行的算法。因为数组中只有3个数字,那么排好序的数组开头肯定是0(如果有0的话),结尾肯定是2(如果有2的话)。所以我们只需一遍遍历,遇到0则放到开头,遇到2则放到结尾,遇到1的话,就先统计一下1的数目。最后把1重新赋值到所有0的后面,1的个数在前面已经统计过了,所以正好。
完整代码如下:

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int p0 = 0, p2 = nums.size() - 1; // p0和p2分别代表下一个0和2应该填入的位置
		int n1 = 0; // 1的数量
		for (int i = 0; i <= p2; i++) {
			if (nums[i] == 0)nums[p0++] = nums[i];
			else if (nums[i] == 1)n1++;
			else {
				swap(nums[i], nums[p2]);
				p2--;
				i--;
			}
		}
		for (int i = 0; i < n1; i++)
			nums[p0++] = 1;
	}
};

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

LeetCode Remove Element

LeetCode Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.


要求我们把数组中等于某个数的元素全部“移除”,移除并不是真正的移除,可以把它们移到数组的末尾。
我的思路是,i指针从前往后扫,遇到一个等于val的(需要移除的)元素时,j从i+1开始找一个不等于val的,交换i,j指向的元素,i继续前进。
思路还是很简单,结果也正确,但是在计算新数组的长度时需要考虑较多cases,太麻烦,我就直接从末尾再往前找,直到找到一个不等于val的下标位置。ugly代码:

class Solution {
public:
	int removeElement(vector<int>& nums, int val) {
		if (nums.size() == 0)return 0;
		if (nums.size() == 1)return (nums[0] != val) ? 1 : 0;
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == val) {
				for (int j = i + 1; j < nums.size(); j++) {
					if (nums[j] != val) {
						nums[i] = nums[j];
						nums[j] = val;
						break;
					}
				}
			}
		}
		if (nums[0] == val)
			return 0;
		else
		{
			int i;
			for (i = nums.size() - 1; i >= 0; i--)
				if (nums[i] != val)
					break;
			return i + 1;
		}
	}
};

本代码提交AC,用时4MS,排名倒数也是在我的预料之中的。看过题解之后,不得不感慨自己还是太笨,过段时间再来刷一遍。