8000 add the LongestSubstringWithoutRepeatingChar · jiaxinhuang/python-test-code@5a857c8 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5a857c8

Browse files
jiaxinhuangjiaxinhuang
committed
add the LongestSubstringWithoutRepeatingChar
1 parent 593503f commit 5a857c8

File tree

3 files changed

+89
-0
lines changed

3 files changed

+89
-0
lines changed

‎leetcode/AddTwoNumbers.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# 题目说明
2+
3+
这题的输入是两个代表逆序数字的链表，这里是使用第三个链表进行保存，这里的关键是理清相应的存储顺序和起终位置的值即可，实现代码如下：
4+
5+
```python
6+
class ListNode(object):
7+
def __init__(self, x):
8+
self.val = x
9+
self.next = None
10+
11+
class Solution(object):
12+
def addTwoNumbers(self, l1, l2):
13+
"""
14+
:type l1: ListNode
15+
:type l2: ListNode
16+
:rtype: ListNode
17+
"""
18+
l3 = ListNode(0)
19+
root = l3
20+
val = 0
21+
while l1 or l2 or val:
22+
tempval = 0
23+
if l1:
24+
tempval += l1.val
25+
l1 = l1.next
26+
if l2:
27+
tempval += l2.val
28+
l2 = l2.next
29+
val, nowval = divmod(tempval + val, 10)
30+
tempList = ListNode(nowval)
31+
l3.next = tempList
32+
l3 = l3.next
33+
return root.next
34+
```
35+

‎leetcode/LongestSubstringWithoutRepeatingCharacters.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 题目说明
2+
3+
给定一个字符串，返回其中不重复子串的长度。
4+
5+
这里的解法是使用一个字典在保存字符和位置信息，使用逐个加入的方式记录字符串中的字符最后的位置的信息，因为连续字符的长度信息保存为另外一个数，所以不会有相应的改变，不会保存相应的字符串内容。
6+
7+
```python
8+
class Solution(object):
9+
def lengthOfLongestSubstring(self, s):
10+
"""
11+
:type s: str
12+
:rtype: int
13+
"""
14+
start = 0
15+
maxLen = 0
16+
usedChar = {}
17+
18+
for i in range(len(s)):
19+
if s[i] in usedChar and usedChar[s[i]] >= start:
20+
start = usedChar[s[i]] + 1
21+
else:
22+
maxLen = max(maxLen, i - start + 1)
23+
usedChar[s[i]] = i
24+
return maxLen
25+
```
26+

‎leetcode/LongestSubstringWithoutRepeatingCharacters.py

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月12日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def lengthOfLongestSubstring(self, s):
9+
"""
10+
:type s: str
11+
:rtype: int
12+
"""
13+
start = 0
14+
maxLen = 0
15+
usedChar = {}
16+
17+
for i in range(len(s)):
18+
if s[i] in usedChar and usedChar[s[i]] >= start:
19+
start = usedChar[s[i]] + 1
20+
else:
21+
maxLen = max(maxLen, i - start + 1)
22+
usedChar[s[i]] = i
23+
return maxLen
24+
25+
if __name__ == '__main__':
26+
print Solution().lengthOfLongestSubstring('abcabcbb')
27+
print Solution().lengthOfLongestSubstring('bbbb')
28+
print Solution().lengthOfLongestSubstring('pwwkew')

0 commit comments

Comments
 (0)
0