Monthly Archives: January 2016

LeetCode ZigZag Conversion

6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

估计大多数人看到这题都不知道Zigzag具体是怎样一个pattern,题目也只给了一个例子,不好找规律,这是维基百科上介绍Zigzag时给的一张图片: 也就是先下后上来回走两条路径,下去和上来的路径是各自平行的。这一题中,下去是竖直下去的,上来是45°斜着走上来的。使用数组模拟走路过程即可。 代码如下:

class Solution {
public:
    string convert(string s, int numRows)
    {
        int n = s.size();
        if (numRows >= n || numRows == 1)
            return s;
        vector<vector<char> > board(numRows);
        int k = 0, i = 0;
        bool up = false;
        while (k < n) {
            board[i].push_back(s[k]);
            if (i >= numRows - 1)
                up = true;
            else if (i <= 0)
                up = false;
            if (up)
                i--;
            else
                i++;
            k++;
        }
        string ret = "";
        for (int i = 0; i < numRows; i++)
            for (int j = 0; j < board[i].size(); j++)
                ret += board[i][j];
        return ret;
    }
};

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

LeetCode Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

这题要求我们找出一个字符串S中的最长回文子串,之前在hihoCoder 1032-最长回文子串就详细讨论过相关问题,这里就不再赘述了,代码完全一样,如下:

class Solution {
public:
	string preProcess(string s)
	{
		int n = s.size();
		if (n == 0)
			return "^#";
		string ret = "^";
		for (int i = 0; i < n; i++)
			ret += "#" + s.substr(i, 1);
		return ret + "#$";
	}
	string longestPalindrome(string s) {
		string t = preProcess(s);
		vector<int> p(t.size(), 0);
		int c = 0, r = 0, n = t.size();
		for (int i = 1; i < n - 1; i++)
		{
			int i_mirror = 2 * c - i;
			p[i] = (r > i) ? min(p[i_mirror], r - i) : 0;
			while (t[i + p[i] + 1] == t[i - p[i] - 1])
				p[i]++;
			if (i + p[i] > r)
			{
				c = i;
				r = i + p[i];
			}
		}
		
		int maxLen = 0, centerIndex = 0;
		for (int i = 1; i < n - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		
		return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
	}
};

本代码提交AC,用时12MS,击败了73%的CPP用户,看来效率不错,估计中心扩展法$O(n^2)$也能过。

二刷。上面的Manacher’s算法过于小众,咱们还是来点大众算法吧,容易理解和记忆。

首先是DP方法,设dp[i][j]=1表示s[i:j]形成回文,=0表示不是回文。则如果s[i:j]形成回文,且s[i-1]==s[j+1],则可以在s[i:j]的基础上进一步扩展,使得s[i-1:j+1]也是回文,即dp[i-1][j+1]=1。

稍微要注意的是DP的时候,第一层循环是子串的长度,因为我们是在短的子串上看起周围2个字符是否相等,所以先要求出短的dp[i][j],再求长的dp[i-1][j+1]。

完整代码如下:

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		if (n == 0)return "";
		vector<vector<int>> dp(n, vector<int>(n, 0));
		int ans = 1, u = 0, v = 0;
		for (int len = 0; len < n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len;
				if (j >= n)break;

				if (len == 0)dp[i][j] = 1;
				else if (len == 1) {
					if (s[i] == s[j]) {
						dp[i][j] = 1;
						if (2 > ans) {
							ans = 2;
							u = i;
							v = j;
						}
					}
				}
				else {
					if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
						dp[i][j] = 1;
						if (j - i + 1 > ans) {
							ans = j - i + 1;
							u = i;
							v = j;
						}
					}
				}
			}
		}
		return s.substr(u, v - u + 1);
	}
};

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

还有一种中心扩展法也很好理解,即假设每个字符是回文的中心字符,然后看看两端字符是否相等,如果相等的话,则继续扩展。需要注意的是,回文有两种形式,一种是aba,即中心只有一个字符,且总长度是奇数;另一种是abba,即中心有两个字符,且总长度是偶数。这种解法相比于上一种解法,只需要O(1)的空间复杂度。

完整代码如下:

class Solution {
public:
	int expand(string &s, int l, int r) {
		int n = s.size();
		while (l >= 0 && r < n&&s[l] == s[r]) {
			--l;
			++r;
		}
		return r - l - 1;
	}
	string longestPalindrome(string s) {
		if (s.size() == 0)return "";
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			int len1= expand(s, i, i);
			int len2= expand(s, i, i + 1);
			if (len1 > len2&&len1 > ans.size()) {
				ans = s.substr(i - len1 / 2, len1);
			}
			if (len2 > len1&&len2 > ans.size()) {
				ans = s.substr(i - len2 / 2 + 1, len2);
			}
		}
		return ans;
	}
};

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

LeetCode Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

这道题很有意思,虽然本科的时候就做过练习题,用二分查找递归的减少数据规模,但是当时只写过伪代码,这次真正写代码提交的时候,发现有很多BUG。

这个题的思路有3种:1)两个数组放一起排序,取中位数O((m+n)lg(m+n));2)用归并排序的方式把他们Merge到一块,取中间数O(m+n),其实边Merge边数数,Merge到(m+n)/2个数的时候就已经是中位数了;3)二分的思路,比较A,B数组的中位数,根据大小关系选择在前半段或后半段继续递归。
我开始尝试了二分的思路,很多测试样例不能通过,要考虑奇偶性等问题也导致代码不够优雅。查看网络发现可以把这一题转换为从两个已排序数组A,B中取第k小的元素的问题,如果是m+n是奇数,则取中间那个数,偶数则取中间两个数求平均。

关于从两个已排序数组A,B中取第k小的元素的问题,这篇文章有较详细的讨论

下面简要讲一下最后一种O(lgm+lgn)的方法。

如果A的某个元素$A_i$和B的某两个连续元素$B_j$和$B_{j-1}$有关系$B_{j-1}\leq A_i\leq B_j$,那么可以确定$A_i$就是AB合起来的第$i+j+1$小的元素,因为$A_i$大于A中前$i$个元素,$A_i$又大于$B_{j-1}$,而$B_{j-1}$又大于B前面$j-1$个元素,所以在AB合起来的数组中,$A_i$大于A前面$i$个元素和B前面$j$个元素,排在第$i+j+1$的位置。同理如果$A_{i-1}\leq B_j\leq A_i$,则$B_j$是第$i+j+1$小的元素。
如果我们令$k=i+j+1$,则可以容易得到第$k$小的元素。关于i,j的取值问题,理论上i,j可以取任意值,只要满足$i+j=k-1$就可以了。不过常见的取法是先取$i$为A的中点,然后取$j=k-1-i$;或者按A,B元素个数的比例取值,比如上述链接中的代码。

上述链接中给出了如果A,B中不存在相同元素时的代码,如下:

int findKthSmallest(int A[], int m, int B[], int n, int k)
{
    assert(m >= 0);
    assert(n >= 0);
    assert(k > 0);
    assert(k <= m + n);
    int i = (int)((double)m / (m + n) * (k – 1));
    int j = (k – 1) – i;
    assert(i >= 0);
    assert(j >= 0);
    assert(i <= m);
    assert(j <= n); // invariant: i + j = k-1 // Note: A[-1] = -INF and A[m] = +INF to maintain invariant
    int Ai_1 = ((i == 0) ? INT_MIN : A[i – 1]);
    int Bj_1 = ((j == 0) ? INT_MIN : B[j – 1]);
    int Ai = ((i == m) ? INT_MAX : A[i]);
    int Bj = ((j == n) ? INT_MAX : B[j]);
    if (Bj_1 < Ai && Ai < Bj)
        return Ai;
    else if (Ai_1 < Bj && Bj < Ai)
        return Bj;
    assert((Ai > Bj && Ai_1 > Bj) || (Ai < Bj && Ai < Bj_1)); // if none of the cases above, then it is either:
    if (Ai < Bj) // exclude Ai and below portion // exclude Bj and above portion
        return findKthSmallest(A + i + 1, m – i – 1, B, j, k – i – 1);
    else /* Bj < Ai */ // exclude Ai and above portion // exclude Bj and below portion
        return findKthSmallest(A, i, B + j + 1, n – j – 1, k – j – 1);
}

针对本题C++代码如下:

class Solution {
public:
    double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k) //find kth smallest
    {
        int m = nums1.size(), n = nums2.size(); //always assume that m is equal or smaller than n
        if (m > n)
            return findKthSmallest(nums2, nums1, k);
        if (m == 0)
            return nums2[k – 1];
        if (k == 1)
            return min(nums1[0], nums2[0]); //divide k into two parts
        int i = (int)((double)m / (m + n) * (k – 1));
        int j = (k – 1) – i;
        int Ai_1 = ((i == 0) ? INT_MIN : nums1[i – 1]);
        int Bj_1 = ((j == 0) ? INT_MIN : nums2[j – 1]);
        int Ai = ((i == m) ? INT_MAX : nums1[i]);
        int Bj = ((j == n) ? INT_MAX : nums2[j]);
        if (Bj_1 < Ai && Ai < Bj)
            return Ai;
        else if (Ai_1 < Bj && Bj < Ai)
            return Bj;
        if (Ai < Bj) {
            vector<int> v1(nums1.begin() + i + 1, nums1.end());
            vector<int> v2(nums2.begin(), nums2.begin() + j);
            return findKthSmallest(v1, v2, k – i – 1);
        }
        else if (Ai > Bj) {
            vector<int> v1(nums1.begin(), nums1.begin() + i);
            vector<int> v2(nums2.begin() + j + 1, nums2.end());
            return findKthSmallest(v1, v2, k – j – 1);
        }
        else
            return Ai;
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int total = nums1.size() + nums2.size();
        if (total & 0x01)
            return findKthSmallest(nums1, nums2, total / 2 + 1);
        else
            return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
    }
};

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

二刷。
上面的解法真的太复杂了,完全记不住。从两个有序数组中求第K大的数,在http://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/有非常详细的解法,归并O(m+n)的解法就不说了。
O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2],如果mid1+mid2<k,说明两个中位数的位置都太小了,第k大的数比较大。如果arr1[mid1]<arr2[mid2],则mid1左边是这四块中最小的一块,k肯定不在这里,所以可以递归在[mid1+1,end1]和[start2,end2]之间找;arra1[mid1]>arr2[mid2]的情况类似。
如果mid1+mid2>k,说明第K大的数比较小,根据上面的分析,下次递归时,可以舍弃掉[start1,mid1], (mid1,end1], [start2,mid2], (mid2,end2]中较大的那块。比如arr1[mid1]>arr2[mid2],则可以舍弃掉(mid2,end2]。
这样每次都可以舍弃掉两个数组中的某个的一半,时间复杂度是O(lgm+lgn),代码在GeeksforGeeks中。
更优的O(lg(k))的方法是,每次我们不是取中值,而是取arr1[k/2]和arr2[k/2],直接根据这两个值的大小关系去分割递归。代码见GeeksforGeeks中最后一个版本的代码,简洁。
针对这一题,求两个有序数组的中位数,如果两个有序数组的总长度len是奇数,则中位数就是两个有序数组中的第len/2大数;如果len是偶数,则中位数是第len/2和len/2的平均数,所以最多需要两次调用findKth就可以得到结果。完整代码如下:

class Solution {
private:
    int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k)
    {
        int len1 = e1 – s1 + 1, len2 = e2 – s2 + 1;
        if (len1 > len2)
            return findKth(nums2, s2, e2, nums1, s1, e1, k);
        if (len1 == 0)
            return nums2[s2 + k – 1];
        if (k == 1)
            return min(nums1[s1], nums2[s2]);
        int i = s1 + min(k / 2, len1) – 1, j = s2 + min(k / 2, len2) – 1;
        if (nums1[i] > nums2[j])
            return findKth(nums1, s1, e1, nums2, j + 1, e2, k – (j – s2 + 1));
        else
            return findKth(nums1, i + 1, e1, nums2, s2, e2, k – (i – s1 + 1));
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size(), n = nums2.size();
        if ((m + n) % 2) {
            return findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1);
        }
        else {
            return (findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2) + findKth(nums1, 0, m – 1, nums2, 0, n – 1, (m + n) / 2 + 1)) / 2.0;
        }
    }
};

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

三刷。

这题有点难,还是看官方题解吧: https://leetcode.com/problems/median-of-two-sorted-arrays/solution/

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如上图所示。其实本质是我们要对数组A和B进行划分,使得left_part_A加left_part_B的元素个数等于right_part_A加right_part_B的元素个数。因为总元素个数是m+n,所以总的left_part的个数应该是(m+n)/2,当然为了统一处理奇偶问题,可以让left_part数目多一点为(m+n+1)/2。那么很自然的,如果A的划分点为i的话,为了满足总的left_part数目为(m+n+1)/2,则B的划分点就要为(m+n+1)/2-i。

也就是说,如果A的划分点为i,B的划分点为(m+n+1)/2-i时,我们就能保证left_part和right_part的数目相等。我们可以想象一下,i和j相当于两个隔板,当i向右移动时,left_part_A元素增加,为了维持平衡,则j一定要向左移动。那么问题就转换为这个i到底等于多少才能找到中位数。

中位数的含义是,所有左边的数都小于它,所有右边的数都大于它。因为A[i-1]<A[i]和B[j-1]<B[j]是天然成立的,为了找中位数,还需要保证A[i-1]<B[j]和B[j-1]<A[i]。所有,我们找i的过程就是在找满足A[i-1]<B[j]和B[j-1]<A[i]的i的过程。

那么,很自然的解法就是,假设i是A的中点,即二分m/2,求出对应的j的位置:(m+n+1)/2-i。然后看看A[i-1]<B[j]和B[j-1]<A[i]是否都满足,如果是的话,就找到了i和j,也就找到了中位数,中位数就是在i和j隔板附近的4个数中间。如果不满足A[i-1]<B[j],即A[i-1]>B[j],说明i的隔板太靠右了,导致A[i-1]太大了,所以要把i往左移一点。类似的,如果不满足B[j-1]<A[i],则把i往右移一点。

如果还不理解的话,可以看油管上的视频讲解: https://youtu.be/LPFhl65R7ww,下面的代码就是模仿这个视频写的。

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		if (m > n)return findMedianSortedArrays(nums2, nums1);
		int low = 0, high = m;
		while (low <= high) {
			int partition1 = (low + high) / 2;
			int partition2 = (m + n + 1) / 2 - partition1;
			
			int maxleft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
			int minright1 = (partition1 == m) ? INT_MAX : nums1[partition1];

			int maxleft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
			int minright2 = (partition2 == n) ? INT_MAX : nums2[partition2];

			if (maxleft1 <= minright2 && maxleft2 <= minright1) {
				if ((m + n) % 2 == 0) {
					int mid1 = maxleft1 > maxleft2 ? maxleft1 : maxleft2;
					int mid2 = minright1 < minright2 ? minright1 : minright2;
					return (mid1 + mid2) / 2.0;
				}
				else {
					return maxleft1 > maxleft2 ? maxleft1 : maxleft2;
				}
			}
			else if (maxleft1 > minright2) {
				high = partition1 - 1;
			}
			else if (maxleft2 > minright1) {
				low = partition1 + 1;
			}
		}
		return 0;
	}
};

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

LeetCode Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

本题要求找出字符串中没有重复字母的最长连续子串。最快想到的是两重遍历i,j,每次用set判断是否重复,重复就进行下一次遍历i++,但是这样显然超时。 因为字符串中只有ASCII,所以可以用bool hash[128]来判断是否有重复字符,比set要快(用空间换时间)。
另外,假设遍历状态是abcdefgc,发现有两个’c’,下一次遍历的时候没必要从b开始遍历,因为从b开始肯定也会遇到后面的两个’c’,但此时字符串长度比之前的少1,所以可以直接从上次的’c’的下一个字母’d’开始重新遍历,这样可以节省不少时间。
完整代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int longest = 0, n = s.size(), cur = 0;
        vector<int> hash(128, 0);
        for (int i = 0; i < n; i++) {
            if (hash[s[i]]) {
                if (cur > longest)
                    longest = cur;
                cur = 0;
                i = hash[s[i]]; //从重复字符下一个字符开始遍历
                //memset(&hash[0], 0, 128*sizeof(int));//比fill更快,但是没fill安全
                fill(hash.begin(), hash.end(), 0);
            }
            hash[s[i]] = i + 1; //记录下一个字符下标
            cur++;
        }
        return (longest > cur) ? longest : cur;
    }
};

本代码提交AC,用时68MS。
二刷,上面我的解法太过复杂。其实我们可以用一个map保存出现字符的最大下标,start保存一个下标,使得从start到当前字符这个区间不存在重复字符。
每来一个字符,我们去map中找一下,如果该字符之前存在,则更新start为最大下标(为了满足从start到当前字符这个区间不存在重复字符),然后不重复子串的长度就是i-start。
完整代码如下,因为s只包含字符,所以也可以用一个256长的数组表示map。

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        map<char, int> visited;
        int ans = 0, start = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (visited.find(s[i]) != visited.end())
                start = max(start, visited[s[i]]);
            visited[s[i]] = i;
            ans = max(ans, i – start);
        }
        return ans;
    }
};

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

三刷。首尾指针法,令[i,j)为不含重复字符的子串的区间,用一个hash数组存储某个字符是否出现过。开始的时候,j不断往前走,直到遇到区间[i,j)中出现过的字符,假设这个字符下标为k的话,则需要把[i,k]之间的hash全部重置为0,i跳到k+1,此后j继续往前走。

完整代码如下:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return n;
		vector<int> hash(256, 0);
		int i = 0, j = 1;
		hash[s[0]] = 1;
		int ans = 0;
		while (j < n) {
			while (j < n&&hash[s[j]] == 0) {
				hash[s[j]] = 1;
				++j;
			}
			if (j - i > ans)ans = j - i;
			if (hash[s[j]] == 1) {
				while (s[i] != s[j]) {
					hash[s[i]] = 0;
					++i;
				}
				hash[s[i]] = 0;
				++i;
			}
		}
		return ans;
	}
};

本代码提交AC,用时8MS,虽然比解法2快,但解法2代码最简单了。