leetcode 1-5题题解 - dblank

# leetcode 1-5题题解

## 1.Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

### 思路

• 有两种方法，一种是基于排序，一种使用unordered_map。
• 基于排序复杂度O(nlogn),可以二分查找和双指针法。

• unordered_map，内部使用hash实现不是树结构查找比较快。

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int, int> >p;
p.push_back(make_pair(0, 0));
for(int i = 0; i<nums.size(); i++)
{
p.push_back(make_pair(nums[i], i+1));
}
sort(p.begin()+1, p.end());
vector<int> ans;
for(int i = 1; i<=nums.size(); i++)
{
ans.clear();
int l = i+1, r = nums.size(), mid;
while(l<=r)
{
mid = (l+r)>>1;
if(p[i].first + p[mid].first == target)
{
ans.push_back(p[i].second-1), ans.push_back(p[mid].second-1);
return ans;
}
else if(p[i].first + p[mid].first > target)
r = mid - 1;
else l = mid + 1;
}
}
}
};

class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<pair<int, int> >p;
for(int i = 0; i<nums.size(); i++)
p.push_back(make_pair(nums[i], i));
sort(p.begin(), p.end());

int l = 0, r = nums.size() - 1;
vector<int> tmp;
while(l<r)
{
if(p[l].first + p[r].first == target)
{
tmp.push_back(p[l].second);
tmp.push_back(p[r].second);
return tmp;
}
else if(p[l].first + p[r].first < target)
l++;
else r--;
}
}
};

unordered_map。

class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> ans;
unordered_map<int, int> Hash;

for(int i = 0; i<nums.size(); i++)
{
if(Hash.find(target - nums[i]) != Hash.end())
{
ans.push_back(Hash[target - nums[i]]);
ans.push_back(i);
return ans;
}
Hash[nums[i]] = i;
}
}
};

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

### 思路

• 类似于大数加法，从头到为对应位相加，注意__进位__
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *p, *ans;
ans = new ListNode(0);
p = ans;
int c = 0;
while(l1  != NULL || l2 != NULL)
{
int a = (l1 == NULL ? 0 : l1->val);
int b = (l2 == NULL ? 0 : l2->val);
c = c + a + b;
if(l1)
l1 = l1->next;
if(l2)
l2 = l2->next;
ans->next = new ListNode(c%10);
c = c/10;
ans = ans->next;
}
if(c)
ans->next = new ListNode(c);
return p->next;
}
};

## 3. Longest Substring Without Repeating Characters

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

### 思路

• 双指针法，开l和r指针找到所有合法的区间，更新答案，时间复杂的O(n)．
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int vis[200] = {0};
int l = 0, r = 0, ans = 0;
while(l < s.size())
{
while(vis[s[r]] == 0 && r<s.size())
{
vis[s[r]] ++;
r++;
}
ans = max(r - l, ans);
vis[s[l]]--;
l++;
}
return ans;
}
};

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

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


### 思路

• 对于(n+m)为奇数中位数就是第(n+m)/2+1大的数,偶数是第(n+m)/2 和第(n+m)/2+1大的数
的平均值，于是变成找连个有序区间第ｋ大数．
• 采取二分的思想，因为他们之前是有序的，那么我们先取数组１的第k/2个和数组２的第(k - k/2)个.
• 如果arr1[k/2] == arr2[k-k/2],则第ｋ大找到为arr1[k/2];
• 如果arr1[k/2] < arr2[k-k/2], 则第ｋ大一定不在arr1前k/2个里面，可以舍去，反之一样．
int min(int a, int b)
{
return a > b ? b : a;
}

int kth(int *nums1, int n, int *nums2, int m, int k)
{
if(n < m)
return kth(nums2, m, nums1, n, k);

if(m == 0)
return nums1[k-1];

if(k == 1)
return min(nums1[0],nums2[0]);

int p = min(k/2, m);
int o = k - p;

if(nums1[o-1] > nums2[p-1])
return kth(nums1, n, nums2+p, m-p, k-p);
return kth(nums1+o, n-o, nums2, m, k-o);

}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
int cnt = nums1Size + nums2Size;
int k = (nums1Size + nums2Size)/2;

if(cnt % 2 == 0)
return ((double)kth(nums1, nums1Size, nums2, nums2Size, k + 1) +
kth(nums1, nums1Size, nums2, nums2Size, k))/2;
else
return kth(nums1, nums1Size, nums2, nums2Size, k + 1);
}

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

Input: "babad"

Output: "bab"


Note: "aba" is also a valid answer.
Example:

Input: "cbbd"

Output: "bb"


### 思路

• 暴力Ｏ(n*n)也是可以的
• manacher算法复杂度O(n)

manachar说起来有点复杂,是ｄｐ的思想:

class Solution
{
public:
string longestPalindrome(string s)
{
int l = s.size();
int len[2*l+10], id = 0;
char ss[2*l+ 10];
for(int i = l; i>=0; i--)
{
ss[i*2 + 2] = s[i];
ss[i*2 + 1] = '#';
}
ss[0] = '*';
int maxx = 0, maxi;
memset(len, 0, sizeof(len));
for(int i = 1; i<=2*l; i++)
{
if(id + len[id] > i)
len[i] = min(len[2*id-i], len[id] + id - i);
while(ss[i+len[i]] == ss[i-len[i]]) len[i] ++;
if(len[i] + i > len[id] + id)
id = i;
if(maxx < len[i])
maxx = len[i], maxi = i;
}
string ans = "";
for(int i = maxi - maxx + 1; i<=maxi + maxx-1; i++)
if(ss[i]!='#')
ans += ss[i];
return ans;
}
};