Skip to content

Commit 3f31ca2

Browse files
linwtlinwt
authored
Add files via upload
1 parent 572ca46 commit 3f31ca2

File tree

100 files changed

+2052
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

100 files changed

+2052
-0
lines changed

‎leetcode/001.两数之和.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# 方法一：暴力破解
2+
class Solution(object):
3+
def twoSum(self, nums, target):
4+
for i in range(len(nums)-1):
5+
for j in range(i+1, len(nums)):
6+
if target-nums[i]==nums[j]:
7+
return [i, j]
8+
9+
# 方法二：字典存储值和索引
10+
class Solution(object):
11+
def twoSum(self, nums, target):
12+
d = {}
13+
for i,num in enumerate(nums):
14+
if target-num in d:
15+
return [d[target-num], i]
16+
else:
17+
d[num] = i

‎leetcode/002.两数相加.py

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
class ListNode(object):
2+
def __init__(self, x):
3+
self.val = x
4+
self.next = None
5+
6+
# 方法一：转为字符串，相加后再转为链表
7+
class Solution(object):
8+
def addTwoNumbers(self, l1, l2):
9+
if not l1:
10+
return l2
11+
if not l2:
12+
return l1
13+
s1, s2 = '', ''
14+
while l1:
15+
s1 += str(l1.val)
16+
l1 = l1.next
17+
while l2:
18+
s2 += str(l2.val)
19+
l2 = l2.next
20+
s = str(int(s1[::-1]) + int(s2[::-1]))[::-1]
21+
l3 = ListNode(int(s[0]))
22+
l = l3
23+
for i in s[1:]:
24+
l3.next = ListNode(int(i))
25+
l3 = l3.next
26+
return l
27+
28+
# 方法二：使用递归，每次相加一位
29+
class Solution(object):
30+
def addTwoNumbers(self, l1, l2):
31+
if not l1:
32+
return l2
33+
if not l2:
34+
return l1
35+
if l1.val + l2.val < 10:
36+
l = ListNode(l1.val+l2.val)
37+
l.next = self.addTwoNumbers(l1.next, l2.next)
38+
else:
39+
l = ListNode(l1.val+l2.val-10)
40+
temp = ListNode(1)
41+
temp.next = None
42+
l.next = self.addTwoNumbers(l1.next, self.addTwoNumbers(l2.next, temp))
43+
return l

‎leetcode/003.无重复字符的最长字串.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 滑动窗口，遇到重复的字符就从该字符下一位开始计算
2+
class Solution(object):
3+
def lengthOfLongestSubstring(self, s):
4+
d = {}
5+
start = res = 0
6+
for i, v in enumerate(s):
7+
if v in d:
8+
start = max(start, d[v]+1)
9+
d[v] = i
10+
res = max(res, i-start+1)
11+
return res

‎leetcode/004.两个排序数组的中位数.py

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# 将两个数组相加、排序，再算中位数
2+
class Solution(object):
3+
def findMedianSortedArrays(self, nums1, nums2):
4+
nums = nums1 + nums2
5+
nums.sort()
6+
length = len(nums)
7+
if length%2 == 0:
8+
return (nums[length/2-1] + nums[length/2])/2.0
9+
else:
10+
return nums[length/2]

‎leetcode/007.反转整数.pyi

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 直接判断正负两种情况
2+
class Solution(object):
3+
def reverse(self, x):
4+
x = -int(str(x)[::-1][:-1]) if x<0 else int(str(x)[::-1])
5+
return x if abs(x)<0x7FFFFFFF else 0
6+
# return x if -2**31<=x<=2**31-1 else 0
7+
8+
# 标记正负两种情况
9+
class Solution(object):
10+
def reverse(self, x):
11+
sign = 1 if x>0 else -1
12+
x = sign * int(str(abs(x))[::-1])
13+
return x if abs(x)<0x7FFFFFFF else 0

‎leetcode/008.字符串转整数.py

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# 逐个条件进行判断
2+
class Solution(object):
3+
def myAtoi(self, s):
4+
s = s.strip()
5+
if len(s)==0:
6+
return 0
7+
8+
s0 = s[0]
9+
res, sign = 0, 1
10+
if s0=='+' or s0=='-':
11+
if s0=='-':
12+
sign = -1
13+
s = s[1:]
14+
for i in s:
15+
if i>='0' and i<='9':
16+
res = res*10+int(i)
17+
else:
18+
break
19+
20+
if res>2147483647:
21+
if sign==1:
22+
return 2147483647
23+
else:
24+
return -2147483648
25+
return sign*res

‎leetcode/019.删除链表的倒数第N个结点.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution(object):
2+
def removeNthFromEnd(self, head, n):
3+
res = left = right = ListNode(0)
4+
res.next = head
5+
# 右指针先走n步
6+
while n:
7+
right = right.next
8+
n -= 1
9+
# 左右指针同时向前走，右指针到底时，左指针的下一结点为倒数第N个结点
10+
while right.next:
11+
left = left.next
12+
right = right.next
13+
left.next = left.next.next
14+
return res.next

‎leetcode/021.合并两个有序链表.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution(object):
2+
def mergeTwoLists(self, l1, l2):
3+
# 一个链表为空则返回另一个链表
4+
if not l1 or not l2:
5+
return l1 or l2
6+
# 新链表的头结点
7+
head = cur = ListNode(0)
8+
while l1 and l2:
9+
if l1.val < l2.val:
10+
cur.next = l1
11+
l1 = l1.next
12+
else:
13+
cur.next = l2
14+
l2 = l2.next
15+
cur = cur.next
16+
# 其中一个链表先结束时，将另一个链表剩余部分连接到新链表
17+
cur.next = l1 if l1 else l2
18+
return head.next

‎leetcode/023.合并K个排序链表.py

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# 方法一：将所有链表结点存放在数组中，排序后再转化为链表
2+
class Solution(object):
3+
def mergeKLists(self, lists):
4+
res = []
5+
for l in lists:
6+
while l:
7+
res.append(l.val)
8+
l = l.next
9+
res.sort()
10+
head = h = ListNode(None)
11+
for i in res:
12+
h.next = ListNode(i)
13+
h = h.next
14+
return head.next
15+
16+
# 方法二：将每个链表的一个结点放入数组，使用最小堆弹出最小结点，再存入新结点比较
17+
class Solution(object):
18+
def mergeKLists(self, lists):
19+
import heapq
20+
res = cur = ListNode(-1)
21+
q = []
22+
# 各链表的头结点
23+
for head in lists:
24+
if head:
25+
heapq.heappush(q, (head.val, head))
26+
# 弹出最小结点，若该结点还有下一个结点，则将下一个结点存入数组
27+
while q:
28+
cur.next = heapq.heappop(q)[1]
29+
cur = cur.next
30+
if cur.next:
31+
heapq.heappush(q, (cur.next.val, cur.next))
32+
33+
return res.next

‎leetcode/024.两两交换链表中的结点.py

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 递归
2+
class Solution(object):
3+
def swapPairs(self, head):
4+
if not head or not head.next:
5+
return head
6+
lat = head.next
7+
head.next = self.swapPairs(lat.next)
8+
lat.next = head
9+
return lat
10+
11+
############## 递归思路 ###################
12+
# 方法作用极简化：先考虑无、1、2个结点的情况。
13+
# 方法作用描述：参数给一个头结点，两个结点交换后，返回新的头结点。由于剩余部分需要同样操作，使用递归
14+
class Solution(object):
15+
def swapPairs(self, head):
16+
if not head or not head.next:
17+
return head
18+
lat = head.next
19+
head.next = None
20+
lat.next = head
21+
return lat

‎leetcode/025.K个一组翻转链表.py

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# 方法一
2+
class Solution(object):
3+
def reverseKGroup(self, head, k):
4+
h = ListNode(-1)
5+
h.next = head
6+
pre = h
7+
cur = head
8+
9+
while cur:
10+
t = cur
11+
count = 1
12+
# 遍历k个为一组
13+
while count<k and t:
14+
t = t.next
15+
count += 1
16+
# 凑够一组进行翻转
17+
if count==k and t:
18+
# 每次将当前结点的后一个结点移到该组的最前面
19+
for _ in range(k-1):
20+
lat = cur.next
21+
cur.next = lat.next
22+
lat.next = pre.next
23+
pre.next = lat
24+
pre = cur
25+
cur = cur.next
26+
# 凑不够一组则结束
27+
else:
28+
break
29+
return h.next
30+
31+
# 方法二：递归
32+
class Solution(object):
33+
def reverseKGroup(self, head, k):
34+
h = ListNode(-1)
35+
h.next = head
36+
pre = h
37+
cur = head
38+
t = 1
39+
while cur:
40+
if t % k == 0:
41+
pre = self._reverseGroup(pre, cur.next)
42+
cur = pre.next
43+
else:
44+
cur = cur.next
45+
t += 1
46+
return h.next
47+
48+
def _reverseGroup(self, pre, lat):
49+
lpre = pre.next
50+
cur = lpre.next
51+
# 每次将cur指向的结点移到该组最前面，然后cur指针再指向下一个结点
52+
while cur != lat:
53+
lpre.next = cur.next
54+
cur.next = pre.next
55+
pre.next = cur
56+
cur = lpre.next
57+
return lpre

‎leetcode/061.旋转链表.py

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
# 方法一：将倒数k个结点移到前面。使用数组存放结点值，位置移动后再转为链表
2+
class Solution(object):
3+
def rotateRight(self, head, k):
4+
if not head:
5+
return
6+
res = []
7+
while head:
8+
res.append(head.val)
9+
head = head.next
10+
K = k%len(res)
11+
res = res[-K:] + res[:-K]
12+
head = h = ListNode(None)
13+
for i in res:
14+
head.next = ListNode(i)
15+
head = head.next
16+
return h.next
17+
18+
# 方法二：将链表首尾连接成环，再根据要求确定新的头结点，断开环
19+
class Solution(object):
20+
def rotateRight(self, head, k):
21+
if not head or not head.next:
22+
return head
23+
24+
h = head
25+
length = 1
26+
while h.next:
27+
length += 1
28+
h = h.next
29+
30+
h.next = head
31+
step = length - k%length
32+
33+
for _ in range(step):
34+
h = h.next
35+
res = h.next
36+
h.next = None
37+
return res

‎leetcode/066.加1.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
# 整型列表转化为数字，加1后再转化为整型列表
2+
class Solution(object):
3+
def plusOne(self, digits):
4+
num = int(''.join(str(i) for i in digits)) + 1
5+
new_digits = []
6+
for i in str(num):
7+
new_digits.append(int(i))
8+
return new_digits

‎leetcode/082.删除排序链表中的重复元素II.py

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# 方法一：数组去重再连接成链表
2+
class Solution(object):
3+
def deleteDuplicates(self, head):
4+
if not head:
5+
return
6+
# 将链表结点值存放在数组
7+
res = []
8+
while head:
9+
res.append(head.val)
10+
head = head.next
11+
# 去除重复的元素
12+
res2 = []
13+
for i in res:
14+
if res.count(i) == 1:
15+
res2.append(i)
16+
# 将数组元素连接成链表
17+
h = head = ListNode(0)
18+
for i in res2:
19+
head.next = ListNode(i)
20+
head = head.next
21+
return h.next
22+
23+
# 方法二：pre跟踪head的前一个结点进行判断，cur跟踪新链表的尾结点
24+
class Solution(object):
25+
def deleteDuplicates(self, head):
26+
# 创建起始结点，不影响原链表
27+
res = pre = cur = ListNode(None)
28+
# 遍历链表结点
29+
while head:
30+
# 结点值与左或右相同时，说明重复，指针向前移动。求结点的值时要先判断结点是否存在
31+
while head and ((head.val==pre.val) or (head.next and head.val==head.next.val)):
32+
pre = head
33+
head = head.next
34+
# 不重复时连接到新链表
35+
cur.next = head
36+
cur = cur.next
37+
# 尾结点可能为重复结点，需要先判断head是否为空，再继续遍历下一个结点
38+
if head:
39+
head = head.next
40+
return res.next
41+
42+
# 方法三：递归
43+
class Solution(object):
44+
# 方法的作用是：参数给一个跟前面结点不重复的head，再判断跟后面结点是否重复，
45+
# 不重复则返回head，重复则返回head.next，head.next可能有不重复结点也可能为空
46+
def deleteDuplicates(self, head):
47+
if not head:
48+
return None
49+
lat, dup = head.next, False
50+
while lat and lat.val == head.val:
51+
lat, dup = lat.next, True
52+
head.next = self.deleteDuplicates(lat)
53+
return head.next if dup else head

‎leetcode/083.删除排序链表中的重复元素.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# 值相同则将next指针指向下下位，重复判断每个结点
2+
class Solution(object):
3+
def deleteDuplicates(self, head):
4+
res = head
5+
while head:
6+
while head.next and head.val == head.next.val:
7+
head.next = head.next.next
8+
head = head.next
9+
return res

0 commit comments

Comments
 (0)