LeetCode Praticing Record | 宇宙よりも遠い場所

March 1, 2017

LeetCode Praticing Record

_(:з」∠)_ 因为实在是太久没有写文章但是又找不到有什么东西好写的,正好最近被某 Tyanboot 带入了 LeetCode 刷题的坑,所以想了想,索性就开了这个帖子记录一下在 LeetCode 的刷题历程好了。因为不想用一题一篇文章的记录方式,所以就直接扔在一整篇博文里。因为时间比较少(被续掉的(不是))所以大概就是 1~2 周做一题、更一题的样子。当然遇到更难的题目另外说……

(题外:西方的 LeetCode 比什么 *gu 一类的 Online Judge 不知道高到哪里去了!)

目录 (Content)

[Problem 1] Two sum 简单的两数求和(斜眼笑) [Problem 2] Add Two Numbers 真 · 两数求和 [Problem 3] Longest Substring Without Repeating Characters 找到一串字符串最长不重复的子串

[Problem 1] Two sum

一开始看难度 Easy,以为又是普通 OJ 的那种 A+B 问题,点进去一看才发现……我毕竟还是图样图森破啊。 呐。问题的大意就是给你一个不定长的整数数组 nums,里面的数不会重复;再给你一个目标数 target,然后让你求出数组中的哪两个数加起来等于目标数。 (喂,这和我们说好的水题不一样啊!) 其实还是可以的啦,题目给的标签是哈希表,那就照着这个方向写吧。这里哈希表用STL 的 map 来建好了,也是很方便的(问题是写这题之前还没试过用 map 呢 orz) 代码 Gist 地址:https://gist.github.com/kirainmoe/919ee87b7653ada8689fbe2384503bd5#file-two_sum-cpp 做题的时候参考的: 《C++ 中的 STL 中 map 用法详解》:http://blog.sina.com.cn/s/blog_a9303fd9010195hm.html


[Problem 2] Add Two Numbers

稍有常识的人就能看出,如果我们的铁骑继续前进 这道题目就是一个高精度加法运算的链表实现形式: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 把高精度的模板套过来使之与链表相适即可。但是受 Top solution 的一个题解的启发,原来代码可以写得更简洁,如下,代码不长不扔 Gist 了。

/**
 * 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 a = ListNode(0), *ans = &a;
        int remain = 0;         // 剩余
    // l1, l2 都为空之后,切记要处理最后剩余的
    while (l1 != NULL || l2 != NULL || remain != 0)
        {
            int cur = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + remain;
            remain = cur / 10;
            ans->next = new ListNode(cur % 10);
            ans = ans->next;
            
            // 下一位,记得判断一下 l1, l2 的 next 是否为 NULL
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
        }
        
        return a.next;
    }
};

就是这样的喵。


[Problem 3] Longest Substring Without Repeating Characters

其实做这道题目距离今天已经有一段日子了……也是我 LeetCode 的入坑题。难度是 Medium ,但是我觉得这个比上一题简单的说。

题目大意是给你一个字符串,找出最长的不重复子串,然后返回这个不重复子串的长度。比如说:

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.

刚看到这道题目的时候,想到以前好像做过类似的题目可以用 DP 来求解,仔细想想发现不需要用动态规划,并且可以把时间复杂度控制在 O(n)。具体的做法如下:

首先维护一个长度为 96 的数组 pos,因为这里题目给出来的字符串不只包括大小写字母,还包括特殊符号(喂,不带不给数据范围的啊),但是都在 ASCII 能表示的范围内,用这个数组作为 Flag。用 memset() 把这个数组赋上初值 -1。定义一个叫 ans 和 cur 的整形变量,分别用来存储最终答案和当前搜到的最长不重复子串的长度,初值都让他们为 0。最后我们还需要一个作为指针作用的变量 flag = s.length().

接下来就是求解。将这个字符串从后往前搜(length-1→0),定义一个叫做 tmp 的变量保存当前遍历到的字符的 ASCII 码与 32 的差(s[i]-32,这里与 32 做差的原因是我们上文只定义了 96 的数组长度)。接着对 pos[tmp] 做判断: 如果 pos[tmp] == -1,说明到目前为止还没有遇到过这个字母,那么令 cur += 1,接着判断 cur 和 ans 的关系,如果 cur > ans,就用 cur 的值替换 ans 的值。

如果 pos[tmp] != -1,说明在之前已经遇到了这个字母,而现在又遇到了,这个时候需要判断 pos[tmp] 和 flag 的大小关系。

== 如果 pos[tmp] > flag,这个时候说明 flag 在当前搜到的字符(tmp) 上一次出现之后已经更新过了,那么这时候我们就令 cur = flag-i(这个时候,从 i 到 flag 的字符共同组成从 s[i] 开始往下能取到的最长不重复子串),然后比较 ans 和 cur,更新 ans 的值。

== 如果 pos[tmp] < flag,那么更新 flag 的值,让 flag = pos[tmp](这么做的原因是因为如果 pos[tmp] 在 flag 之前,那么从 i 开始能取到的最长不重复子串就会变成 i 到 pos[tmp]-1之间的所有字符)。这个时候就可以令 cur = flag-i 了。由于这个时候得到的新值必定比 ans 小,所以就不需要做比较了。

做完这一切还有最后一件事,就是更新当前字母出现的位置啦。别忘记在循环体最后加上 pos[tmp] = i 更新一下位置。最后就大胆地 return ans; 吧。

代码 Gist 地址:https://gist.github.com/kirainmoe/a39a65e73efc95012bb7be84d32337c7 由于理想情况下复杂度是 O(n) ,所以实测最快可以在 LeetCode 跑到 9ms 左右(这个成绩是超过 99.57% 的提交)

©2018 YumeのDiary / Published with Hugo / Theme