LeetCode Python题解

已经放弃使用Python,转向Java了

  • Python的语言特性使得很多问题有简洁、巧妙却不通用的解法
  • Python的性能低,很多答案无法通过OJ的时间限制
  • 我参考的算法书给出的是Java代码

LeetCode刷题之旅

1. Two Sum

  • Difficulty: Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]

Better Solution:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def twoSum(self, nums, target):
if len(nums) <= 1:
return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

两个用链表表示的逆序整数求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
x1 = 0
x2 = 0
s1 = []
s2 = []
ans = []
while(l1):
s1.append(l1.val)
l1 = l1.next
while(l2):
s2.append(l2.val)
l2 = l2.next
for i in s1[::-1]:
x1 = x1 * 10 + i
for i in s2[::-1]:
x2 = x2*10 + i
x3 = x1 + x2
if x3<10:
return ListNode(x3)
while(x3 > 0):
ans.append(ListNode(x3 % 10))
x3 = x3 // 10
for i in range(len(ans)-1):
ans[i].next = ans[i+1]
return ans[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l = p = ListNode(0)
inc = 0
while(l1 or l2):
if not l1:
q = ListNode(l2.val + inc)
l2 = l2.next
elif not l2:
q = ListNode(l1.val + inc)
l1 = l1.next
else:
q = ListNode(l1.val + l2.val + inc)
l1 = l1.next
l2 = l2.next
if q.val > 9:
inc = 1
q.val = q.val % 10
else:
inc = 0
p.next = q
p = p.next
if inc > 0 :
q = ListNode(inc)
p.next = q
p = p.next
return l.next

7.Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if x >= 0:
x = int(str(x)[::-1])
else:
x = 0 - int(str(-x)[::-1])
if (x > 0x7FFFFFFF) or (x < -0x80000000):
return 0
return x

9. Palindrome Number

回文数字

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isPalindrome(self, x):
s = str(x)
if s == s[::-1]:
return True
return False
"""
:type x: int
:rtype: bool
"""

标签云