-
第 61 樓 / webdriver
- 時間: 2014-9-30 00:34
-
-
- 時間: 2014-9-30 00:35S算法問題: Edit Distance
問題描述:
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character -
-
- 時間: 2014-9-30 00:36算法問題推薦解法來了...
Dynamic Programming.
1. Time: O(mn) Space: O(mn)
2. Time: O(mn) Space: O(n);
解法（Python）
代碼: class Solution:
def minDistance(self, word1, word2):
distance = [[i] for i in range(len(word1) + 1)]
distance[0] = [i for i in range(len(word2) + 1)]
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
deletion = distance[i - 1][j] + 1
addition = distance[i][j - 1] + 1
substitution = distance[i - 1][j - 1]
if word1[i - 1] != word2[j - 1]:
substitution += 1
distance[i].append(min(deletion, addition, substitution))
return distance[-1][-1]
def minDistance(self, word1, word2):
"""This is an example of horrible code. Long statement inside the nested for loop
is hard to understand.
"""
distance = [[i] for i in range(len(word1) + 1)]
distance[0] = [i for i in range(len(word2) + 1)]
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
distance[i].append(min(distance[i - 1][j] + 1, distance[i][j - 1] + 1, distance[i - 1][j - 1] + (word1[i - 1] != word2[j - 1])))
return distance[-1][-1] -
- 時間: 2014-9-30 00:38S算法問題: Evaluate Reverse Polish Notation
問題描述:
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 -
- 時間: 2014-9-30 00:40算法問題推薦解法來了...
stack.
解法（Python）
代碼: class Solution:
def evalRPN(self, tokens):
numerals, operators = [], {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div}
for token in tokens:
if token.isdigit() or token[1:].isdigit():
numerals.append(int(token))
else:
x, y = numerals.pop(), numerals.pop()
numerals.append(int(operators[token](y * 1.0, x)))
return numerals.pop() -
- 時間: 2014-9-30 00:42
-
- 時間: 2014-9-30 00:44算法問題推薦解法來了...
Although we can only use constant space, we can still exchange elements within input A!
Swap elements in A and try to make all the elements in A satisfy: A[i] == i + 1.
Pick out the first one that does not satisfy A[i] == i + 1.
解法（Python）
代碼: class Solution:
def firstMissingPositive(self, A):
i = 0
while i < len(A):
if A[i] > 0 and A[i] - 1 < len(A) and A[A[i] - 1] != A[i]:
A[A[i] - 1], A[i] = A[i], A[A[i] - 1]
else:
i += 1
for i in range(len(A)):
if A[i] != i + 1:
return i + 1
return len(A) + 1 -
- 時間: 2014-9-30 00:47S算法問題: Flatten Binary Tree to Linked List
問題描述:
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node
of a pre-order traversal. -
- 時間: 2014-9-30 00:48
-
- 時間: 2014-9-30 00:49S算法問題: 4Sum
問題描述:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note:
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a <= b <= c <= d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
Leetcode Hacking Practice -- Solution in Python Part 1
