# 287.Find the Duplicate Number

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.

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;
}
};



# 283.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.

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);
}
};


# 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"


## 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)

## 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);
}
};
`