leetcode 1-5题题解 - dblank

leetcode 1-5题题解

代码在我的github上也有

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].

题意

找到数组两个元素相加等于target,返回下标

思路

  • 有两种方法,一种是基于排序,一种使用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;
        }
    }
};

然而他们的运行时间都是一样的

2. Add Two Numbers

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

题意

给两个单链表,每个链表表示一个数,每个节点存一位数,返回他们相加的链表.

思路

  • 类似于大数加法,从头到为对应位相加,注意__进位__
/**
 * Definition for singly-linked list.
 * 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

题意:

给出两个有序的数组,找到他们合并后的中位数,要求时间复杂度O(log(n+m)).

思路

  • 对于(n+m)为奇数中位数就是第(n+m)/2+1大的数,偶数是第(n+m)/2 和第(n+m)/2+1大的数
    的平均值,于是变成找连个有序区间第k大数.
  • 采取二分的思想,因为他们之前是有序的,那么我们先取数组1的第k/2个和数组2的第(k - k/2)个.
  • 如果arr1[k/2] == arr2[k-k/2],则第k大找到为arr1[k/2];
  • 如果arr1[k/2] < arr2[k-k/2], 则第k大一定不在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"

题意:

找到最长的回文字串

思路

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

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

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

相关文章

发表新评论