2019-11-28 308 views 评论

Leetcode题目解析（191128）：2&3&72&75&76

标签：leetcode

Leetcode 2：两数相加

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

代码实现

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *tmp=new ListNode(-1);
        ListNode *res=tmp;
        ListNode *add1=l1;
        ListNode *add2=l2;
        int ge=0;
        int jin=0;
        while(add1!=NULL || add2!=NULL||jin)
        {
            ge=(add1?add1-&gt;val:0)+(add2?add2-&gt;val:0)+jin;
            jin=ge/10;
            ge=ge%10;
            ListNode *newnode = new ListNode(ge);
            tmp-&gt;next=newnode;
            tmp=tmp-&gt;next;
            if(add1)
                add1=add1-&gt;next;
            if(add2)
                add2=add2-&gt;next;
        }

        return res-&gt;next;
    }

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

if(l1==NULL)

return l2;

if(l2==NULL)

return l1;

ListNode *tmp=new ListNode(-1);

ListNode *res=tmp;

ListNode *add1=l1;

ListNode *add2=l2;

int ge=0;

int jin=0;

while(add1!=NULL || add2!=NULL||jin)

{

ge=(add1?add1->val:0)+(add2?add2->val:0)+jin;

jin=ge/10;

ge=ge%10;

ListNode *newnode = new ListNode(ge);

tmp->next=newnode;

tmp=tmp->next;

if(add1)

add1=add1->next;

if(add2)

add2=add2->next;

}

return res->next;

}

执行用时&内存消耗

复杂度分析

Leetcode 3：无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

代码实现

int lengthOfLongestSubstring(string s) {
        int len = s.size();
        vector&lt;int&gt; a(256,-1);
        int maxlen = 0;
        int l = -1;
        for(int i=0; i&lt;len; i++){
            l = max(l,a[s[i]]);
            a[s[i]] = i;
            maxlen = max(maxlen,i-l);
        }
        
       return maxlen; 
    }

int lengthOfLongestSubstring(string s) {

int len = s.size();

vector<int> a(256,-1);

int maxlen = 0;

int l = -1;

for(int i=0; i<len; i++){

l = max(l,a[s[i]]);

a[s[i]] = i;

maxlen = max(maxlen,i-l);

}

return maxlen;

}

执行用时&占用空间

复杂度分析

Leetcode 72：编辑距离

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解题思路

代码实现

int min3(int a, int b, int c)
{
    return (a &lt; b) ? (a &lt; c ? a : c) : (b &lt; c ? b : c);
}
int minDistance(string word1, string word2) {
    int strlen1 = word1.size();
    int strlen2 = word2.size();
    vector&lt;vector&lt;int&gt;&gt;dp(strlen1 + 1, vector&lt;int&gt;(strlen2 + 1, 0));
    for (int i = 1; i &lt;= strlen1; i++)
        dp[i][0] = i;
    for (int i = 1; i &lt;= strlen2; i++)
        dp[0][i] = i;
    for (int i = 1; i &lt;= strlen1; i++)
    {
        for (int j = 1; j &lt;= strlen2; j++)
        {
            int diff;
            if (word1[i - 1] == word2[j - 1])
                diff = 0;
            else
                diff = 1;
            dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + diff);
        }
    }
    return dp[strlen1][strlen2];
}

int min3(int a, int b, int c)

{

return (a < b) ? (a < c ? a : c) : (b < c ? b : c);

}

int minDistance(string word1, string word2) {

int strlen1 = word1.size();

int strlen2 = word2.size();

vector<vector<int>>dp(strlen1 + 1, vector<int>(strlen2 + 1, 0));

for (int i = 1; i <= strlen1; i++)

dp[i][0] = i;

for (int i = 1; i <= strlen2; i++)

dp[0][i] = i;

for (int i = 1; i <= strlen1; i++)

{

for (int j = 1; j <= strlen2; j++)

{

int diff;

if (word1[i - 1] == word2[j - 1])

diff = 0;

else

diff = 1;

dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + diff);

}

return dp[strlen1][strlen2];

}

复杂度

时间复杂度：算法有两个for循环，一个双重for循环。如果两个字符串分别是m和n，前两个for循环时间复杂度为O(n)和O(m)。双重for循环时间复杂度为O(n * m)，所以总时间复杂度是O(n * m)。

空间复杂度：O(n * m)

复杂度分析

Leetcode 75：颜色分类

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

解题思路

此题是一个荷兰国旗问题，曾经在博客和公众号中都推送过这个问题的解决方案。所谓荷兰国旗问题，或者说黑猫白猫灰猫问题，其实都是一样的，就是说有三类数据乱序排列，然后要求用O(N)的时间复杂度，O(1)的空间复杂度使其有序。因其类似于荷兰国旗，所以被称为荷兰国旗问题（德国、法国在这里表示不服~）。

具体思路如下：

排序方法：设置start/end/current三个指针，分别指向开头、开头、结尾。在current<=end的背景下，然后开始判断current的值：

若current==0，因为0要排在前面，所以则将start指向的值和current的值交换，然后start++,current++；
若current==1，因为1是排在中间，所以current++，start不变；
若current==2，则将current和end的元素交换，将end--，但是current不变，如果current后移1位，那么current这一位就无法判断了。

代码实现

void sortColorsl(vector&lt;int&gt; &amp;nums)
{
    int len = nums.size();
    int start = 0, current = 0, end = len - 1;
    //在current&lt;=end的背景下，然后开始判断current的值
    while (current &lt;= end)
    {
        //1.若current==0，则将start指向的值和current的值交换，然后start++,current++；
        if (nums[current] == 0)
        {
            swap(nums[current], nums[start]);
            ++current;
            ++start;
        }
        //3.若current==2，则将current和end的元素交换，将end--，但是current不变。
        else if (nums[current] == 2)
        {
            swap(nums[current], nums[end]);
            --end;
        }
        //2.若current==1，则current++，start不变；
        else if (nums[current] == 1)
        {
            ++current;
        }
    }
}

void sortColorsl(vector<int> &nums)

{

int len = nums.size();

int start = 0, current = 0, end = len - 1;

//在current<=end的背景下，然后开始判断current的值

while (current <= end)

{

//1.若current==0，则将start指向的值和current的值交换，然后start++,current++；

if (nums[current] == 0)

{

swap(nums[current], nums[start]);

++current;

++start;

}

//3.若current==2，则将current和end的元素交换，将end--，但是current不变。

else if (nums[current] == 2)

{

swap(nums[current], nums[end]);

--end;

}

//2.若current==1，则current++，start不变；

else if (nums[current] == 1)

{

++current;

}

复杂度

时间复杂度：O(n)

复杂度分析

Leetcode 76：最小覆盖子串

题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

如果 S 中不存这样的子串，则返回空字符串 ""。如果 S 中存在这样的子串，我们保证它是唯一的答案。

示例

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

解题思路

其实这个题的题目的英文Minimum winow substring给了我们一个答案，就是用窗来解决，但是中文名称却掩盖了这一点。

简单来说思路就是这样：设置一个左指针left，设置一个有指针right，然后不断移动右指针right，然后可以寻找到一个覆盖面最广的子串（最长覆盖子串），当然如果right移动到最后一个字母都没有找到覆盖子串的话，就是找不到了。完成这一步之后，开始移动left，这个时候寻找最小覆盖子串。

代码实现

string minWindow(string s, string t)
{
    int count[256] = { 0 };
    for (auto c : t)++count[c];//统计t中每个字符出现的次数
    int len = 0, minlen = s.size();//minlen最大为s的长度
    string res;
    for (int l = 0, r = 0; r &lt; s.size(); ++r) {
        if (--count[s[r]] &gt;= 0)++len;
        //上面这句话的意思是：不断移动窗口的right，同时若在s中发现t中有的字符，则len++
        //直到len加到和t相同，也就是在s中找到了一个字符串
        //下面就是找最优字符串了
        while (len == t.size()) {
            if (r - l + 1 &lt;= minlen) {
                minlen = r - l + 1;
                res = s.substr(l, minlen);
            }
            if (++count[s[l++]] &gt; 0)--len;
        }
            
    }
    return res;
}