Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
解法相对简单，根据规律写出就可以了。
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0: return []
if numRows == 1: return [[1]]
re = []
re.append([1])
for i in range(1,numRows):
oneline = []
oneline.append(1)
for j in range(1,i):
oneline.append(re[i-1][j-1]+re[i-1][j])
oneline.append(1)
re.append(oneline)
return re
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3, Return [1,3,3,1].
参考下面的解法，上一题也可以这么简洁。 class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
line = [1]
for i in xrange(rowIndex):
line = [1] + [line[k] + line[k+1] for k in xrange(len(line) - 1)] + [1]
return line
Implement pow(x, n).
注意这里对边界、负值和重复计算的处理。
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1
if n < 0:
return 1.0/self.myPow(x,-n)
if n % 2 == 0:
re = self.myPow(x,n/2)
return re * re
else:
return self.myPow(x,n-1) * x
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
注意这里对逆转数的处理rev = rev * 10 + x % 10;
另外对溢出和负数的处理要根据语言的特性来决定。
public class Solution {
public int reverse(int x) {
long rev = 0;
while(x != 0) {
rev = rev * 10 + x % 10;
x = x / 10;
if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) {
return 0;
}
}
return (int)rev;
}
}
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
range的做法是第一个参数会取到，最后一个参数不会取，注意这里的用法。
另外这里要注意进位的情况。
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
l = len(digits)
carry = 1
for i in range(l-1,-1,-1):
if carry + digits[i] == 10:
digits[i] = 0
carry = 1
else:
carry = 0
digits[i] = digits[i] + 1
break
print carry
if carry == 1:
re = [1]
for i in range(l):
re.append(0)
return re
else:
return digits
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
这里如果使用递归的话，会超时。 class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if (m == 1 and n == 1) or (m == 1 and n == 2) or (m == 2 and n == 1):
return 1
if n == 1:
return self.uniquePaths(m-1,n)
if m == 1:
return self.uniquePaths(m,n-1)
return self.uniquePaths(m-1,n) + self.uniquePaths(m,n-1)
因此考虑数学方法。 这是一个排列组合的问题。 C(m-1)(m+n-2)
from math import *
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
return factorial(m+n-2)/factorial(n-1)/factorial(m-1)
Determine whether an integer is a palindrome. Do this without extra space.
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
x = str(x)
l, r = 0, len(x)-1
while (l < r):
if not x[l] == x[r]:
return False
else:
l = l + 1
r = r - 1
return True
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
这里注意对问题的数学化的处理。
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
total = 1
factorial = [1]
for i in range(1,n+1):
total = total * i
factorial.insert(i,total)
numbers = range(1,n+1)
k = k - 1
re = ''
for i in range(1,n+1):
index = k/factorial[n-i]
re = re + str(numbers[index])
numbers.remove(numbers[index])
k = k - index * factorial[n-i]
return re
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
注意到根据起始位置排序后，融合的情况只可能发生在前后的两个interval之间。使用一个堆栈即可处理连续的融合。注意一下这里使用lambda表达式实现的排序。
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if len(intervals) < 2:
return intervals
intervals.sort(key=lambda intervals: intervals.start)
stack = []
stack.append(intervals[0])
l = len(intervals)
for i in range(1, l):
if stack[-1].end >= intervals[i].start:
tmp = stack.pop()
interval = Interval(tmp.start, max(tmp.end, intervals[i].end))
stack.append(interval)
else:
stack.append(intervals[i])
return stack
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
递归可以做。如下：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
或者用数学的方法来做也可以，斐波那契数列：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
fab = [1,2]
for i in range(2,n):
fab.append(fab[i-1]+fab[i-2])
return fab[n-1]