Tag Archives: 双指针

LeetCode Minimum Window Substring

76. Minimum Window Substring

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:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给两个字符串S和T,问S中是否存在一个子串,包括T中的所有字符,如果存在,输出最短的那个子串。

hard题,用双指针+滑动窗口。核心思想是找到滑动窗口[i,j),首先++j,加入右边界的字符;然后检查[i,j)是否能覆盖t;再然后++i,丢掉左边界的字符。

首先设置一个required数组,存储t中每个字符出现的次数,表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数,如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j,如果s[j]在t中,则++found。然后看看found==n?,如果是,则检查左边界,如果左边界s[i]在t中,则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下:

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

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

今晚字节跳动三面,面试官问了一个此题的变种,即只给定了字符串s,要找s的一个子串,使得该子串能覆盖s中所有特异的字符,且子串越短越好。可以把面试问题转换为这个问题,即先遍历s,把s中的特异字符拼成一个字符串t,然后调用本题的解法。

LeetCode Maximum Number of Vowels in a Substring of Given Length

5417. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:

Input: s = "tryhard", k = 4
Output: 1

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

给定字符串s和长度k,问s中长度为k的子串中,包含最多元音字母的个数。

简单题,直接滑动窗口+双指针计数即可:

class Solution {
public:
	bool IsVol(const char &c) {
		return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
	}
	int maxVowels(string s, int k) {
		int ans = 0;
		int i = 0, j = k - 1, n = s.size();
		for (int k = i; k <= j; ++k) {
			if (IsVol(s[k]))++ans;
		}
		int cur = ans;
		while (j < n - 1) {
			++j;
			if (IsVol(s[j]))++cur;
			if (IsVol(s[i]))--cur;
			++i;
			ans = max(ans, cur);
		}
		return ans;
	}
};

本代码提交AC。

LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

给定一个数组,问数组中一个连续的子数组内的最大值和最小值的差不超过limit的最长连续子数组的长度。

常规解法。使用DP求出任何一个子区间dp[i,j]的最大值和最小值,dp[i,j+1]的最大值和最小值只需要用nums[j]和dp[i,j]的最大值和最小值比较即可。完整代码如下:

class Solution {
public:
	int longestSubarray(vector<int>& nums, int limit) {
		int n = nums.size();
		int ans = 1; // 最小值是1

		for (int i = 0; i < n; ++i) {
			vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
			dp_max[i] = dp_min[i] = nums[i];
			for (int len = 2; len <= n; ++len) {
				int j = i + len - 1;
				if (j >= n)break;
				dp_max[j] = max(dp_max[j - 1], nums[j]);
				dp_min[j] = min(dp_min[j - 1], nums[j]);
				int diff = dp_max[j] - dp_min[j];
				if (diff <= limit) {
					ans = max(ans, j - i + 1);
				}
				else {
					break;
				}
			}
		}
		return ans;
	}
};

很不幸,该代码的时间复杂度达到了O(n^2),在最后两个测试样例上TLE了。

比O(n^2)低的复杂度有O(nlgn)和O(n)。O(nlgn)排序好像无法求解,那么只有O(n)的方法了。此题本质上是一个滑动窗口的问题,可以用两个指针i和j,标记区间的起止位置。那么问题的关键就是如何快速求解到区间[i,j]的最大值和最小值。

我之前的方法是用DP提前算出来,但是DP的过程费时。使用优先队列priority_queue(最大堆、最小堆)可以得到当前区域的最大值和最小值,但是一旦差的绝对值超过limit,需要从优先队列中删除i所指元素时,priority_queue没有提供erase或者remove之类的接口,所以使用priority_queue无法达成目标。

提示使用multiset,我之前知道multiset内部使用红黑树结构,内部存储是有序的,而且提供了erase接口以供删除元素。但是我一直不确定如何获得multiset内部的最大值和最小值元素,虽然它内部是有序的,但我不确定程序员能否得到其有序列表。

后来看了multiset的API,里面明确说明了multiset默认是从小到大排序,而且其begin()指向最小值rbegin()指向最后一个元素,即最大值。所以multiset是一个功能很强大的容器,它不但可以实现堆的功能,还能查找、删除某个元素,比 priority_queue 更强大。

使用multiset的完整代码如下:

class Solution {
public:
    int longestSubarray(vector<int>& A, int limit) {
        int res = 0, n = A.size(), i = 0, j;
        multiset<int> m;
        for (j = 0; j < n; ++j) {
            m.insert(A[j]);
            if (*m.rbegin() - *m.begin() > limit)
                m.erase(m.find(A[i++]));
            else
                res=max(res,j-i+1);
        }
        return res;
    }
};

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

另外,我们还可以指定multiset内部的排序规则,让其表现为最大堆或最小堆。

LeetCode Check If All 1’s Are at Least Length K Places Away

1437. Check If All 1’s Are at Least Length K Places Away

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true

Constraints:

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length
  • nums[i] is 0 or 1

给定一个0/1数组,问数组中所有1的间隔是否超过某个阈值。

简单题,一遍扫描数组,使用双指针记录相邻两个1,并实时计算它们的距离,完整代码如下:

class Solution {
public:
	bool kLengthApart(vector<int>& nums, int k) {
		int n = nums.size();
		int i = 0, j = 0;
		while (i < n) {
			while (i < n&&nums[i] == 0)++i;
			if (i >= n - 1)break;
			j = i + 1;
			while (j < n&&nums[j] == 0)++j;
			if (j - i - 1 < k)return false;
			i = j;
		}
		return true;
	}
};

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

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时循环终止。 完整代码如下: [cpp] #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; } [/cpp] 无奈,提交后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开始重新遍历,这种方法需要的遍历数其实是很少的。 完整代码如下: [cpp] #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; } [/cpp] 本代码提交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 [c language=",d"][/c] 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]。
完整代码如下: [cpp] 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 }; } }; [/cpp] 本代码提交AC,用时1016MS。 因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。 求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下: [cpp] 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 }; } }; [/cpp] 本代码提交AC,用时56MS。  ]]>

LeetCode Minimum Size Subarray Sum

209. Minimum Size Subarray Sum 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: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).  209. Minimum Size Subarray Sum


给定一个正整数数组和一个数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得到。具体看代码: [cpp] 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 ""; } }; [/cpp] 本代码提交AC,用时135MS。]]>

LeetCode Move Zeroes

283. Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

本题要把数组中的所有0元素移到数组末尾,同时保证其他元素的相对顺序不变,并且要求in-place和尽量少的操作。
我的思路是首先找0元素,然后在0后面找第一个非0元素,交换它们,直到数组末尾。完整代码如下:

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] != 0) {
                        swap(nums[i], nums[j]);
                        break;
                    }
                }
            }
        }
    }
};

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

后来在网上看了看别人的解法,发现只需要一遍循环就可以,而且代码非常简洁,真是太棒了。
思路是找非0元素,然后和之前的元素交换,但是之前的元素(下标j对应元素)不一定是0,因为只有非0时才交换,所以交换次数是非0元的个数。
完整代码如下:

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        for (int i = 0, j = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j++]);
            }
        }
    }
};

本代码提交AC,用时13MS,果然快了不少。

二刷。简单方法,两个指针,j指针一直往前走,i指针指向当前可以填入非0元素的位置。j扫完之后,i后面的都应该是0。

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		int n = nums.size(), num_zeors = 0;
		int i = 0;
		for (int j = 0; j < n; ++j) {
			if (nums[j] != 0)nums[i++] = nums[j];
		}
		for (int j = i; j < n; ++j)nums[j] = 0;
	}
};

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