-
第 91 樓 / webdriver
- 時間: 2014-9-30 01:26算法問題推薦解法來了...
Jump to the position where we can jump farthest (index + A[index]) next time.
解法（Python）
代碼: class Solution:
def jump(self, A):
step, reachable, i = -1, 0, 0
while i < len(A) and i <= reachable:
next_reachable = 0
while i <= reachable and i < len(A):
next_reachable = max(next_reachable, A[i] + i)
i += 1
reachable = next_reachable
step += 1
return step -
-
- 時間: 2014-9-30 01:26S算法問題: Jump Game
問題描述:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false. -
-
- 時間: 2014-9-30 01:27算法問題推薦解法來了...
Updated solution: try every reachable index.
Thank to Wenxin Xing for kindly feedback and pointing out my big mistake
解法（Python）
代碼: class Solution:
def canJump(self, A):
reachable = 0
for i in range(len(A)):
if i > reachable:
return False
reachable = max(reachable, i + A[i])
return True -
- 時間: 2014-9-30 01:28
-
- 時間: 2014-9-30 01:29算法問題推薦解法來了...
1. Only calucate area when reaching local maximum value.
2. Keep a non-descending stack. O(n).
解法（Python）
代碼: class Solution:
def largestRectangleArea(self, height):
increasing, area, i = [], 0, 0
while i <= len(height):
if len(increasing) == 0 or (i < len(height) and height[i] > height[increasing[-1]]):
increasing.append(i)
i += 1
else:
last = increasing.pop()
if len(increasing) == 0:
area = max(area, height[last] * i)
else:
area = max(area, height[last] * (i - increasing[-1] - 1))
return area -
- 時間: 2014-9-30 01:31S算法問題: Length of Last Word
問題描述:
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5. -
- 時間: 2014-9-30 01:32
-
- 時間: 2014-9-30 01:34S算法問題: Letter Combinations of a Phone Number
問題描述:
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input
igit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want. -
- 時間: 2014-9-30 01:35算法問題推薦解法來了...
...
解法（Python）
代碼: class Solution:
def letterCombinations(self, digits):
lookup, res = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"], []
self.letterCombinationsRecur(lookup, res, "", digits)
return res
def letterCombinationsRecur(self, lookup, res, current, digits):
if digits == "":
res.append(current)
return
for choice in lookup[int(digits[0])]:
self.letterCombinationsRecur(lookup, res, current + choice, digits[1:]) -
- 時間: 2014-9-30 01:38
Leetcode Hacking Practice -- Solution in Python Part 1
