KelvinMao

287.Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

之前也有过与duplicate相关的Array类题目，大多是删除元素，而这次要求找出其中的duplicates，本来不是什么很难的要求，但由于有了题目上的种种限制，比如不能改变Array(也就不能通过排序的方法判断相邻元素是否相等)，时间复杂度低于O(n2)，这道题目就有了难度。

对于这样的数组，我们很难将其与二分查找联系起来，不过它们之间确实有着练习

既然是从1~n的n+1个数，那么根据抽屉原理就必然有一个重复的数，那么先计算mid，算出mid之后计算数组中比mid小的数有几个，如果多于mid个，根据抽屉原理，则说明区间[low,mid-1]必存在重复，否则调整区间到[mid+1,high]。代码如下:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low=0,size=nums.size(),high=size-1,mid=0,count=0,i=0;
        while(low<=high){
            count=0;
            mid=low+(high-low)/2;
            for(i=0;i<size;i++){
                if(nums[i]<=mid)
                    count++;
            }
            if(count>mid)
                high=mid-1;
            else
                low=mid+1;
        }
        return low;
    }
};
KelvinMao

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.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. 要求将数组中的0放在数组末尾，并且其余元素不能改变相对顺序，不能用额外空间，尽可能减少操作。介绍两种解法: 1.遍历数组，将数组中所有非0值通过赋值放到前面来，并且记录0的个数，然后在最后把0补进去。见代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        // move all the nonzero elements advance
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (;j < nums.size(); j++) {
            nums[j] = 0;
        }
    }
};

2.利用vector内置函数 这是一个十分惊艳的解法，是我在讨论区看到的，只用了一行代码就解决了问题，使用了remove和fill函数。算法是遍历整个vector，发现等于c的元素就用后一个元素值来替代当前元素值。vector整体的size()不变。（比如对1234这个序列remove 2，返回的序列是 1344（3被复制到2的位置，4被复制到3的位置））。然后返回一个迭代器（第一个是c的位置的迭代器）。看代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        fill(remove(nums.begin(),nums.end(),0),nums.end(),0);
    }
};
KelvinMao

5. Longest Palindromic Substring

Description

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Analysis

非常经典的一个问题，求最长回文字串。

这道题看似容易解决，似乎将字符串逆置后，和原字符串作比较，找出两者的最长公共字串即可。

但实际上此种解法只是看似可行,比如对于babad，可以用这种方法找到其最长回文字串。但如果一个较长的非回文字串出现在原字符串中，比如abcdefghg`,那么很容易就能证明，上述算法会得出一个错误的答案，所以需要换一个角度进行考虑。

那么下一个比较容易想到的方法就是暴力破解了，穷举所有字串，判断其是否是回文字符串。但这样的时间空间复杂度都相当高(O（N^3）)，所以只能放弃这个方法。

考虑构成回文串的条件，如果区间(i,j)能构成回文串，那么(i+1,j-1)一定也能构成回文串。所以我们可以以一个字母为”mid”,不断向两边扩张，直到不构成回文串为止。计算回文串长度和起始位置。

待mid指针遍历过所有字母之后，通过之前维护的max_left,max_len两个变量，计算出最长回文字符串。

时间复杂度为O（N^2),空间复杂度O（1），代码耗时6ms

code

class Solution {
public:
    string longestPalindrome(string s) {
		if(s.size()<2)
			return s;
		int max_len=1,max_left=0;
		for(int mid=0;mid<s.size();){
		    int left=mid;
			int right=mid; 
			while(right<s.size()-1&&s[left]==s[left+1])	++left;
			mid=left+1;
			while(right<s.size()-1&&left>0&&s[left-1]==s[right+1]){--left; ++right;}
			int new_len=right-left+1;
			if(new_len>max_len){max_left=left; max_len=new_len;}
		}
		return s.substr(max_left,max_len);
    }
};

动态规划解法

刚才在上一种解法中，已经找到了一个串为回文串的条件。

  • dp[i][j]==true为串s[i][j]为回文
  • 将dp[i][i]，dp[i][i-1]初始化为true，其余全为false(即一个或两个字母组成的字符串均认为是回文)
  • 之后穷举字串长度的值，对于其是否为回文，取决于 (s[i] == s[j] && dp[i+1][j-1] == true)

时间复杂度O（N^2),空间复杂度O(N^2)

code

/*Dynamic programming*/
class Solution {
public:
    string longestPalindrome(string s) {
		if(s.size()<2)
			return s;
		int max_len=1,max_left=0,s_len=s.size();
		bool dp[s_len][s_len]={false};
		dp[0][0]=true;
		for(int i=1;i<s_len;++i){
			dp[i][i]=true;
			dp[i][i-1]=true;
		}
		for(int len=2;len<s_len;++len){
			for(int i=0;i<=s_len-len;++i){
				if(s[i]==s[i+len-1]&&dp[i+1][i+len-2]){
					dp[i][i+len-1]=true;
					if(len>max_len){
						max_left=i;
						max_len=len;
					}
				}
			}
		}
		return s.substr(max_left,max_len);
    }
};