LeetCode 刷题总结（四），使用Python 实现。该篇题目类型主要包含无法归类到上述三篇的题目。
7. Reverse Integer
在c++ 中使用 long long来处理数字溢出的问题。对于case -123 和 120 下面的代码是能够处理的。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int reverse(int x) {
long long res =0;
while(x)
{
res = res *10 + x %10;
x /= 10;
}
if(res < INT_MIN || res > INT_MAX) return 0;
return res;
}
};
|
在c++ 中使用 -134 %10 =-4 而在python 中使用 -134 %10 =6，所以两者的实现是不一样的。 所以在python 中进行整数除法运算的时候，需要转换成正数（记录flag），在整除的时候需要考虑 整除。
需要注意的一点是，使用“数字相加”的概念 而不是字符串相加的概念去处理。如果是字符串的话，需要单独处理最后可能存在多个0的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
# python 中也是可以使用 整数的，不仅仅只是有list
flag =1 if x >0 else -1
x =abs(x)
res =0
while x:
res = res * 10 + x%10
x =x//10
if res > 1 << 31:
res =0
return flag * res
|
8. String to Integer (atoi)
Implement atoi which converts a string to an integer.
Tips: 涉及到bit 级别数字处理的一般都会用到 res =res 10 + something 这样的东西。对于能够表示的数字的判断 max(-pow(2, 31), min(ressign, pow(2, 31) -1)) 这个还是挺经典的代码的。
核心操作是 while 操作中对于字符串的解析，其他的边界条件是考虑周到与否。基本思路是写出一个版本，然后根据bad case 进行考虑。对于这种类型，可以想到的case： 正负号，int 类型的越界（c++ 中，python 中不存在这样的现象）
ord() 函数就是用来返回单个字符的ascii值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str =str.strip()
if str =='':
return 0
res =0
flag = 1
i =0
if i < len(str) and str[i] =='-':
flag =-1
i +=1
if i < len(str) and str[i] =='+':
if flag ==-1:
return 0
i +=1
while i < len(str) and str[i].isdigit():
res = res * 10 + ord(str[i]) -ord('0');
i +=1
return res * flag
|
c++代码。在该版本的测试样例中，没有超过int 的范围。
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
|
class Solution {
public:
int myAtoi(string str) {
int i =0;
int res =0;
int flag = 1;
while(i < str.size() && str[i] ==' ')
i ++;
if (str[i] =='-')
{
flag =-1;
i ++;
}
if (str[i] =='+')
{
if (flag ==-1)
return 0;
i ++;
}
while (i < str.size() && str[i] >='0' && str[i] <= '9')
{
res = res * 10 + str[i] -'0';
i ++;
}
return res *flag;
}
};
|
（3）Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Tips： 回文数。代码写的很巧妙，整体上说是通过 / 和 % 获得数字的头和尾，在实现的时候有若干细节。 这道题目是可以被当做是一个模拟题进行解答的。
注意是先取尾，然后去头部。因为，如果反过来，那么ranger 就是不准的，所以一定要先使用了ranger 求解余数，然后再使用 去头的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
# 数字的取整和取余 计算
ranger =1
while x //ranger >9:
ranger *= 10
while x:
left = x //ranger
right =x % 10
if left != right:
return False
x = (x% ranger)//10
ranger =ranger //100
return True
|
需要 $O(n)$ 的空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
# 数字的取余 和取整数部分。
nums =[]
if x <0: return False
while x:
nums.append(x %10)
x =x //10
for i in range(len(nums) //2):
if nums[i] != nums[len(nums) -i-1]:
return False
return True
|
** Integer to Roman **
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Tips： 基于roman 数字规则的转换。代码实现角度 tuple都是要好于 list （内存和速度方面都是），如果你想要存储的是静态的可以遍历的数据，不需要每次进行修改的话，why not
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution(object):
def intToRoman(self, num):
if num <= 0:
return ""
digits = { "I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000 }
nums = (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
chs = ("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
len = 13
s = ""
while num > 0:
for i in range(0, len):
if num >= nums[i]:
num -= nums[i]
s += chs[i]
break
return s
|
** Roman to Integer**
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Tips： 和上一道题目相似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution(object):
def romanToInt(self, s):
"""
这个是输入时 string，所以是 index 遍历的在 dict 中进行访问，但是上一个题目是总的 number，是没有办法的
"""
digits = { "I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000 }
len_s = len(s)
num = 0
# 这个少遍历了一个 ，因为其中有 i+1 的存在
for i in range(0, len_s - 1):
cur = digits[s[i]]
next_s = digits[s[i + 1]]
if cur >= next_s:
num += cur
else:
num -= cur
# 处理的是最后一个
num += digits[s[len_s - 1]]
return num
|
** Letter Combinations of a Phone Number**
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Tips：使用循环的方式表示层级的关系（使用二层循环，第一层表示外围a， 第二层表示 def 等）。
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
|
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits or digits == "":
return []
# 命名很到位
maps ={
'1': (),
'0': (),
'2': ('a', 'b', 'c'),
'3': ('d', 'e', 'f'),
'4': ('g', 'h', 'i'),
'5': ('j', 'k', 'l'),
'6': ('m', 'n', 'o'),
'7': ('p', 'q', 'r', 's'),
'8': ('t', 'u', 'v'),
'9': ('w', 'x', 'y', 'z')
}
results = [""]
for digit in digits:
tuple1 = maps[digit]
tmp =[]
if len(tuple1) == 0:
continue
# 二重循环
for prefix in results:
for suffix in tuple1:
tmp.append(prefix + suffix)
results = tmp
return results
|
Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Tips： 不让使用乘除和 mod 操作，只能使用位运算符了。在python 中0 == False 这个在逻辑判断中是等价的（1 ==True）。计算的时候使用 « （不断的*2）, ,maybe 是二分。 实际上位运算本质也是除法运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution(object):
def divide(self, divident, divisor):
sign =-1 if divident* divisor<0 else 1
divident, divisor =abs(divident), abs(divisor)
ans =0
while divisor <= divident:
div =divisor
tmp =1
while (div <<1) <= divident:
div <<= 1
tmp <<= 1
divident -= div
ans += tmp
return max(-pow(2, 31), min(ans*sign, pow(2, 31) -1))
|
相比之下使用 减法代替除法就比较实在一些。如果使用普通的减法运算，那么是$O(x)$，所以可以倍增作减法, 最后的时间复杂度是 $(log x) ^ 2$。
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
|
class Solution {
public:
int divide(int dividend, int divisor) {
long long x =dividend, y = divisor;
bool flag;
if( x >0 && y >0 || x<0 && y <0) flag =true;
else flag =false;
long long ans =0;
x =abs(x), y =abs(y);
while ( x>= y)
{
long long t =y , c =1;
while (x >= t +t)
{
t += t;
c += c;
}
x -= t;
ans += c;
}
if(flag ==false)
ans = -ans;
if( ans < INT_MIN || ans > INT_MAX)
return INT_MAX;
return int(ans);
}
};
|
小的细节， 长整型中可以直接使用 abs(x)，不存在溢出报错。
Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (xn)
$O(n)$ 时间复杂度是不行的，最优的解法是 $log(n)$. 该题目返回的值，从实际问题意义上是 double 类型的。
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
double myPow(double x, int n) {
double res =1, p =x;
long long t =abs((long long)n); // 当n为 INT_MIN 的时候，abs 会爆掉
for(; t; t >>= 1)
{
if(t & 1) // 如果是奇数的话，
res =res *p;
p = p * p; // 这里体现的是 logn 的算法
}
return n >0? res : 1.0/ res;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def myPow(self, x: float, n: int) -> float:
res =1
p = x
t =abs(n)
while t :
if t & 1 ==1:
res = res * p;
p = p* p
t =t >>1
return res if n > 0 else 1.0/ res
|
** Add Binary **
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Tips：二级制相加，从后往前走，使用 carry 位置记录进位数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
i, j, carry, res =len(a) -1, len(b) -1, 0, ''
while i>=0 or j >=0 or carry:
if i >=0:
carry += int(a[i])
i -=1
if j>=0:
carry += int(b[j])
j -=1
res =str(carry%2) +res
carry //=2
return res
|
** Max Points on a Line**
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Tips：当使用除法的时候，因为精度问题造成的误差，所以这里使用最大的公约数进行化简。使用以下三种方式处理。
- Map from (a,b,c,d) representing y=(a/b)x+(c/d) to set of indices of points that are on that line. a/b and c/d are reduced, i.e. a and b are divided by their GCD and so are c and d.
- Vertical lines are represented by a tuple with 1 element, the x-axis value
- Single points are represented by a 2-tuple (x, y).
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
41
42
43
44
45
46
47
48
|
import collections
import math
def fraction(x, y):
if x < 0:
x, y = -x, -y
gcd = math.gcd(x, y)
return x // gcd, y // gcd
class Solution:
def maxPoints(self, points):
if not points:
return 0
if len(points) == 1:
return 1
aligned_points = collections.defaultdict(set)
duplicates = collections.defaultdict(set)
for i, p in enumerate(points):
for j, q in enumerate(points[i + 1:], start=i + 1):
# x 是否相同
if q[0] == p[0]:
if q[1] == p[1]:
duplicates[i].add(j)
key = tuple(p)
else:
key = (q[0],)
else:
a, b = fraction(q[1] - p[1], q[0] - p[0]) # k斜率
c, d = fraction(p[1] * q[0] - q[1] * p[0], q[0] - p[0]) # b 位移
key = (a, b, c, d)
#aligned_points[key] = aligned_points[key] or {i, j} # 因为之前定义的是set
aligned_points[key] |= {i, j}
for p, dups in duplicates.items():
for key in aligned_points:
if p in aligned_points[key]:
#aligned_points[key] = aligned_points[key] or dups # 这个or 不是选择的意思，是两者都要的意思
aligned_points[key] |= dups
max_points = 0
for aliged in aligned_points.values():
max_points = max(max_points, len(aliged))
return max_points
|
** Happy Number**
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Tips: 使用set 的思路，没有重复之前就一直遍历；对于数字转成 string 逐个进行处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
visited =set() # 这个set 每次add 都是add 到最前面一个，是规律吧
while n not in visited:
visited.add(n)
n =sum((int(x) **2 for x in str(n)))# () 要比 [] 使用较少的内存
return n ==1
|
**Sum of Two Integers **
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Input: a = 1, b = 2
Output: 3
Tips: 下面的add()函数只是在以下场景中 work: a*b>=0 , or the negative number has a larger absolute value( a < 0 and abs(a) > b > 0 , or b < 0 and abs(b) > a > 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
def add(a, b):
if not a or not b:
return a or b
# # ^ get different bits and & gets double 1s, << moves carry ， 这个可能是加法吧，
return add(a^b, (a&b) << 1)
if a*b < 0: # assume a < 0, b > 0
if a > 0:
return self.getSum(b, a)
if -a == b:
return 0
if -a < b:
return -add(-a, -b)
return add(a, b)
|
** Fizz Buzz ***
Write a program that outputs the string representation of numbers from 1 to n.
n = 15,
Return:
[
“1”,
“2”,
“Fizz”,
“4”,
“Buzz”,
“Fizz”,
“7”,
“8”,
“Fizz”,
“Buzz”,
“11”,
“Fizz”,
“13”,
“14”,
“FizzBuzz”
]
Tips: 这是一个 for 循环就可以解决的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution(object):
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
# 使用一个 result append一下
result = []
for i in xrange(1, n + 1):
if i % 3 != 0 and i % 5 != 0:
result.append(str(i))
elif i % 3 == 0 and i % 5 != 0:
result.append("Fizz")
elif i % 3 != 0 and i % 5 == 0:
result.append("Buzz")
else:
result.append("FizzBuzz")
return result
|
Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Tips: 主要难点在于数据流，难在数据结构，使用最小根堆实现。这个是需要寻找 median （中位数），使用大小根堆，分别存储较小的一半 和 较大的一半。那么大根堆的堆顶就对应着较小一半的最大值，小根堆对应着较大部分的最小值。所以中位数就可以 快速的从两个堆顶元素中获得。
https://leetcode.com/problems/find-median-from-data-stream/
简单说一下在python 中heapq -小根堆的实现。将数值转成负数，那么就可以使用小根堆来mimic 大根堆，因为堆顶是负数最小的。（对应正数最大的）
heap.heappush(heap, item), 把一个item 添加到heap中
heap.heappushpop(heap, item), 先把item 放入到堆中，然后再pop() , 这样比 heappush() 然后再heappop() 快一些
push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush
followed by a separate call to heappop()
Note that the heapq in python is a min heap, thus we need to invert the values in the smaller half to mimic a 'max heap'
the add operation is O(nlogn), the find operation is O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
from heapq import *
class MedianFinder(object):
def __init__(self):
self.small =[] # max heap (the smaller half of the list), 大根堆存放的是小值，然后根存放的就是最大值, 这个转成-num 当然就是 smaller part
self.large =[] # min heap (the larger half of the list), 小根堆存放的是大值，然后根就是存放的最小值
def addNum(self, num):
if len(self.small) ==len(self.large):
heappush(self.large, -heappushpop(self.small, -num))
else:
heappush(self.small, -heappushpop(self.large, num))
def findMedian(self):
if len(self.small) ==len(self.large):
return float(self.large[0] -self.small[0])/2.0
else:
return float(self.large[0])
|
** Flatten Nested List Iterator **
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Tips: 迭代器和 generator 感觉都是差不多的操作，产生一个数字。这个看懂 API 更重要。只要数字内容，不要嵌套的关系。yield 关键字，调用完之后，程序不结束。
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
41
42
43
44
45
46
47
48
49
50
|
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class NestedIterator(object):
def __init__(self, nestedList):
def gen(nestedList):
for x in nestedList:
if x.isInteger():
yield x.getInteger()
else:
for y in gen(x.getList()):
yield y
self.gen = gen(nestedList)
def next(self):
return self.value
def hasNext(self):
try:
self.value = next(self.gen)
return True
except StopIteration:
return False
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
|
** Insert Delete GetRandom O(1) **
Design a data structure that supports all following operations in average O(1) time.
- insert(val): Inserts an item val to the set if not already present.
- remove(val): Removes an item val from the set if present.
- getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
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
41
42
43
44
45
46
|
class RandomizedSet(object):
# 就是一个维持list 的东西
def __init__(self):
"""
Initialize your data structure here.
"""
self.list =[]
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val not in self.list:
self.list.append(val)
return True
return False
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.list:
self.list.remove(val)
return True
return False
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
length =len(self.list)
import random
index =random.randint(0,length-1)
return self.list[index]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
|
** Perfect Squares**
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Tips: 再次理解一下二重循环，如果第二层中的遍历次数和 第一层是有关系的，往往是 O(N*N/2) 的复杂度（这种记法是错误的），用于遍历前 i 个元素。
···python
class Solution(object):
# dp[i] 的定义表示 i 这个数字最少使用的 squares 数量
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = [float(‘inf’)]*(n+1)
dp[0]=0
count = 2
for i in range(1,n+1):
if i>=count*count:
count += 1
for j in range(1,count):
dp[i] = min(dp[i],dp[i-j*j]+1)
return dp[n]
"""
# 这样做是不可行的，在于可能重复使用一个，如果没有最大的合适的话
square =[pow(num, 2) for num in range(1, int(math.sqrt(n) +1))]
square =square[::-1]
count =0
for sq in square:
if n-sq >0:
n -= sq
count +=1
return count
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
** Factorial Trailing Zeroes**
> Given an integer n, return the number of trailing zeroes in n!.
Tips: 数学问题
···python
class Solution(object):
# 这里的 += n/div 已经就表示了 5的个数， 这样是可以加快运算的
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
div =5
res =0
while div <=n:
res += n/div
div =div *5
return res
|
** Count Primes **
Count the number of prime numbers less than a non-negative number, n.
Tips: 主要是质数倍数的优化，否则是time out
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution(object):
# prime 质数， 1 既不是质数也不是 合数
# 当前数为质数时，排除掉剩下的数中该数的整倍数。遍历过所有的数之后剩下的数全是质数。提升效率的方法是减少遍历的长度。
# 还有一个优化点，可以不必从2~m-1，只需遍历2 ~ √m.因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如16能被2,4,8整除
# 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
# 最后 return 的是 counter，个数 而不是具体的数字
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return 0
prime = [True] * n
prime[:2] = [False, False]
for base in range(2, int((n ) ** 0.5) + 1): # 时间上是 [2, sqrt(m)] ，但是在python 中实现是这样的
if prime[base]:
prime[base ** 2::base] = [False] * len(prime[base ** 2::base])
return sum(prime)
|
** Missing Number**
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Tips: 使用公式 index 和前 n数的问题。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution(object):
# 如果没有限制内存，那么是可以使用dict，然后根据index 和value 进行判断的
# 凡是和对应的index 发生关系，那么这个就有优化的可能，就变得比较有意思
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n =len(nums)
return n*(n+1)/2 -sum(nums)
|
** Power of Three**
Given an integer, write a function to determine if it is a power of three.
Tips: 求余 and /= 相结合的常见手法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution(object):
# 这个是在考察除法的运算过程
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
if n <=0:
return False
if n ==1:
return True
while n >1:
if n %3 !=0:
return False
n /= 3
return True
|
**Implement Trie (Prefix Tree) **
Implement a trie with insert, search, and startsWith methods.
Tips: 这个数据结构很有用，字典树。
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
41
42
43
44
45
|
class TrieNode:
# Initialize your data structure here.
# https://www.cnblogs.com/beiyeqingteng/p/5625540.html，这里面有个图
# 还是挺形象的
def __init__(self):
# 这个是什么数据结构呀
self.children = collections.defaultdict(TrieNode) # 这种设置还是理解不够深刻
self.is_word = False
# 考察的是字典树，这种数据结构
# 保存字母的话，是 26叉树，保存数字的话10 叉树
class Trie(object):
def __init__(self):
self.root =TrieNode()
def insert(self, word):
current =self.root
for letter in word:
current =current.children[letter]
current.is_word =True
def search(self, word):
current =self.root
for letter in word:
current =current.children.get(letter)
if not current:
return False
return current.is_word
def startsWith(self, prefix):
current =self.root
for letter in prefix:
current =current.children.get(letter) # dictionary 操作，得到的是值
if not current:
return False
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
|