Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit36d8774

Browse files
author
ssjssh
committed
完成leecode中的两个题目.
1 parent53510bf commit36d8774

File tree

4 files changed

+147
-1
lines changed

4 files changed

+147
-1
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -95,7 +95,7 @@ algorithm
9595
* 在学习redis源码的过程中修改各个数据结构的实现,目的是使用更加精细的规则去提高数据结构的性能
9696
* 添加更多注释并且格式化代码,注释中注重于设计的思考
9797
* 添加算法导论中其他高级的数据结构
98-
* 计划完成一些在线的题库
98+
* 计划完成一些在线的题库,比如leecode和projecteuler
9999

100100

101101

‎src/leecode/__init__.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
#!/usr/bin/env python
2+
#-*- coding:UTF-8
3+
__author__='shenshijun'

‎src/leecode/add_two_numbers.py

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
"""
5+
You are given two linked lists representing two non-negative numbers. 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.
6+
7+
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
8+
Output: 7 -> 0 -> 8
9+
"""
10+
11+
12+
classListNode(object):
13+
def__init__(self,x):
14+
self.val=x
15+
self.next=None
16+
17+
18+
classSolution(object):
19+
def__addUpDigit(self,node,up_digit):
20+
last_node=None
21+
whilenodeisnotNoneandup_digit>0:
22+
node.val+=up_digit
23+
ifnode.val>=10:
24+
node.val-=10
25+
up_digit=1
26+
else:
27+
up_digit=0
28+
last_node=node
29+
node=node.next
30+
ifup_digit>0andlast_node:
31+
last_node.next=ListNode(up_digit)
32+
33+
defaddTwoNumbers(self,l1,l2):
34+
"""
35+
:type l1: ListNode
36+
:type l2: ListNode
37+
:rtype: ListNode
38+
"""
39+
cur_l1=l1
40+
cur_l2=l2
41+
last_l1=None
42+
last_up_digit=0
43+
whilecur_l1isnotNoneandcur_l2isnotNone:
44+
this_val=cur_l1.val+cur_l2.val+last_up_digit
45+
ifthis_val>=10:
46+
cur_l1.val=this_val-10
47+
last_up_digit=1
48+
else:
49+
cur_l1.val=this_val
50+
last_up_digit=0
51+
last_l1=cur_l1
52+
cur_l1=cur_l1.next
53+
cur_l2=cur_l2.next
54+
55+
ifcur_l1isNoneandcur_l2isNoneandlast_up_digit>0andlast_l1isnotNone:
56+
last_l1.next=ListNode(last_up_digit)
57+
self.__addUpDigit(cur_l1,last_up_digit)
58+
self.__addUpDigit(cur_l2,last_up_digit)
59+
60+
# 如果l1比较短,需要把l2长的部分合并到l1后面
61+
ifcur_l2isnotNone:
62+
iflast_l1isNone:
63+
returnl2
64+
else:
65+
last_l1.next=cur_l2
66+
67+
returnl1
68+
69+
70+
defmain():
71+
pass
72+
73+
74+
if__name__=="__main__":
75+
main()

‎src/leecode/two_sum.py

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
"""
4+
Given an array of integers, find two numbers such that they add up to a specific target number.
5+
The function twoSum should return indices of the two numbers such that they add up to the target,
6+
where index1 must be less than index2.Please note that your returned answers (both index1 and index2) are not zero-based.
7+
8+
You may assume that each input would have exactly one solution.
9+
10+
Input: numbers={2, 7, 11, 15}, target=9
11+
Output: index1=1, index2=2
12+
"""
13+
14+
__author__='shenshijun'
15+
16+
"""
17+
本题有两个思路:
18+
一: 利用排序和二分查找
19+
先排序得到一个排序的数列,复杂度是O(nlgn),然后遍历数列,每遍历到一个元素的时候使用二分查询查找另外一个数字是否存在,复杂度仍然是O(nlgn)
20+
21+
二: 使用hash表
22+
思路一为了快速查找而把数据都排了序,为了查找,显然可以使用hash表.而hash表是更高效的实现.一遍完成,因此复杂度是O(n)
23+
"""
24+
25+
26+
classSolution(object):
27+
deftwoSum(self,nums,target):
28+
"""
29+
:type nums: List[int]
30+
:type target: int
31+
:rtype: List[int]
32+
"""
33+
d= {}
34+
forind,numinenumerate(nums):
35+
# 为了防止列表中出现重复的数,并且保证列表前面的index比后面的index小
36+
ifnumind:
37+
iftype(d[num])islist:
38+
d[num].append(ind)
39+
else:
40+
d[num]= [d[num],ind]
41+
else:
42+
d[num]=ind
43+
44+
fornum,indind.iteritems():
45+
# 注意:要同时考虑ind和d[other_part]都为list的情况
46+
# 还要考虑,找到的index不能是同一个,并且不能重复
47+
this_indexs=indiftype(ind)==listelse [ind]
48+
other_part=target-num
49+
forthis_indexinthis_indexs:
50+
ifother_partind:
51+
iftype(d[other_part])==list:
52+
forother_indexind[other_part]:
53+
ifother_index!=this_index:
54+
return [min(other_index,this_index)+1,max(other_index,this_index)+1]
55+
elifd[other_part]!=this_index:
56+
return [min(d[other_part],this_index)+1,max(d[other_part],this_index)+1]
57+
58+
return [-1,-1]
59+
60+
61+
defmain():
62+
print(Solution().twoSum([0,4,3,0],0))
63+
print(Solution().twoSum([2,7,11,15],9))
64+
print(Solution().twoSum([-3,4,3,90],0))
65+
66+
67+
if__name__=="__main__":
68+
main()

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp