左耳听风-ARTS-第一周

什么叫ARTS?

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

作者:陈皓
链接:https://www.zhihu.com/question/301150832/answer/529809529
来源:知乎

Algorithm

第一个问题

1
2
3
4
5
6
7
8
9
10
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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解决方案如下,这里主要考察链表的使用,主要注意几点:

  1. 因为会不断往链表后面添加新的节点,所以最好ListNode preHead(0), *p = &preHead;来进行定义,后面能直接通过头节点preHead找到链表头。
  2. 连接下一个节点的时候采用p->next = new ListNode(sum % 10);的形式,不要试图通过p->val=val来进行,这是错误的,新的节点是要开辟空间并进行赋值的。
  3. 注意进位处理,其余都是代码能力问题了,多写写慢慢提升。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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 preHead(0), *p = &preHead;
int extra = 0;
while (l1 || l2 || extra) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
extra = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return preHead.next;
}
};

第二个问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3. Longest Substring Without Repeating Characters

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

解决方案如下,这里主要考察数组的随机访问功能,但是这里有一个思想很重要,利用字符串的字符大小作为数组的index,数组存入的是字符的个数,当数据位已经被赋值时,重新初始化计数参考位start,由于maxLen只有一个值,故采用max函数得到最大值以后将原来的maxLen进行覆盖处理,具体如图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int start=-1;
int maxLen=0;

for(int i=0;i<s.length();i++) {
if(dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i-start);
}

return maxLen;
}
};

Review

Tip

Share

nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!