设计问题

1. Shuffle an Array

打乱一个没有重复元素的数组

1
2
3
4
5
6
7
8
9
10
11
12
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

实现思路
先深度复制nums到变量ans,然后从ans末尾到开头遍历,每次随机选择一个index,然后交换数值,最后返回ans,原来的nums不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:

def __init__(self, nums: List[int]):
self.nums = nums[:]
self.base = nums[:]

def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
self.nums = self.base
return self.nums

def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
for i in range(len(self.nums)):
j = random.randint(0, i)
self.nums[i], self[j] = self.nums[j], self.nums[i]
return self.nums

使用内置shuffle模块

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 __init__(self, nums):
"""
:type nums: List[int]
"""
self.data = nums

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.data

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
ans = copy.deepcopy(self.data)
random.shuffle(ans)
return ans

2. 最小栈

设计一个支持pushpoptop操作,并能在常数时间内检索到最小元素的栈。

  • push(x):将元素x推入栈
  • pop():删除栈顶元素,并删除元素
  • top():获取栈顶元素,不删除元素
  • getMin():检索栈中的最小元素
1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -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
30
31
32
33
34
35
36
37
38
39
class MinStack:

def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []

def push(self, x: int) -> None:
if x is None:
pass
else:
self.stack.append(x)

def pop(self) -> None:
if self.stack is None:
return "error"
else:
self.stack.pop()

def top(self) -> int:
if self.stack is None:
return "error"
else:
return self.stack[-1]

def getMin(self) -> int:
if self.stack is None:
return 'error'
else:
return min(self.stack)


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

数学问题

1. Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”;
  2. 如果 n 是5的倍数,输出“Buzz”;
  3. 如果 n 同时是3和5的倍数,输出 “FizzBuzz”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 15,

返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
res = []
for i in range(1, n+1):
if i % 15 == 0:
res.append("FizzBuzz")
elif i % 3 == 0:
res.append("Fizz")
elif i % 5 == 0:
res.append("Buzz")
else:
res.append(str(i))
return res

2. 计数质数

统计所有小于非负整数n的质数的数量

1
2
3
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

实现思路
质数(素数)prime number 有无限个,质数定义为在大于1 的自然数中,除了1和它本身之外不再有其他的数称之为质数。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def countPrimes(self, n: int) -> int:
cnt = 0
if i < 2:
return cnt
for i in range(2, n):
for j in range(2, int(i**0.5)+1): # 检查i除了1和自身之外时候存在被整除
if i % j == 0:
break
else: # 不能被自身和1整除
cnt += 1
return cnt

上述方法只适合小的数据,数据量大的话会造成超时timeout。

第二中方法:

厄拉多塞筛法:
西元前250年,希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法,减少了逐一检查每个数的的步骤,可以比较简单的从一大堆数字之中,筛选出质数来,这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
具体操作:先将 2~n 的各个数放入表中,然后在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于n的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

1
2
3
4
5
6
7
8
9
10
class Solution:
def countPrimes(self, n: int) -> int:
if n < 2:
return 0
prime = [1] * n
prime[0], prime[1] = 0, 0
for i in range(2, int(n**0.5)+1):
if prime[i] == 1:
prime[i*i:n:i] = [0]*len(prime[i*i:n:i])
return sum(prime)

3. 3的幂

给定一个整数,写一个函数来判断它是否是一个3的幂次方

1
2
3
4
5
6
7
8
9
10
11
输入: 27
输出: true

输入: 0
输出: false

输入: 9
输出: true

输入: 45
输出: false

进阶:你能不使用循环或者递归来完成本题吗?

实现思路
第一种方法:
循环实现

1
2
3
4
5
6
7
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
while n % 3 == 0:
n //= 3
return n == 1

第二种方法:
使用 3^19次幂进行整除,如果能被整除,则表示是3的幂。

1
2
3
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 1162261467 % n == 0;

4. 罗马数字转整数

罗马数字包含以下其中字符: I, V, X, L, C, DM

1
2
3
4
5
6
7
8
字符          数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

实现思路

  • 如果当前数字是最后一个数字,或者之后的数字比它小的话,那么就加上当前的数字
  • 如果其它情况就减去这个数字
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def romanToInt(self, s: str) -> int:
target = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
res = 0
n = len(s)
for i in range(n):
if i+1 >= n or target[s[i]] >= target[s[i+1]]:
res += target[s[i]]
else:
res -= target[s[i]]
return res

其他

1. 位1的个数

编写一个函数,输入是一个无符号的整数,返回其二进制表达式中的数字为1的个数(也称为汉明重量)。

1
2
3
4
5
6
7
8
9
10
11
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。

进阶:
如果多次调用这个函数,你将如何优化你的算法?

实现思路

方法一:和数字1与运算
通过和1进行与运算实现判断,做一次就计数一次,右移一次

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
cnt = 0
while n > 0:
if n & 1 == 1:
cnt += 1
n = n >> 1
return cnt

方法二:
把一个整数减去1之后再和原来的整数进行做位的与运算,得到的结果相当于把整数的二进制表示中最右边的一位变成了0

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
cnt = 0
while n > 0:
n = n & (n - 1)
cnt += 1
return count

2. 汉明距离

两个整数之间的汉明距离指的是两个数字对应的二进制位不同的位置的数目。

注意:
0 ≤ x, y < 2^31.

1
2
3
4
5
6
7
8
9
10
输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

实现思路
码字A为 10001001
码字B为 10110001
那么不同的字符数为3,汉明距离就是3
不难看出,汉明距离就是两个码不同的数的个数。
所以直接将两个数进行异或运算然后统计1的个数即可

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
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
z = x^y
cnt = 0
while z:
z = z & (z - 1)
cnt += 1
return cnt

class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
return bin(x^y).count('1')

class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
b = bin(x ^ y)
data = 0
for i in list(b):
if i == '1':
data += 1
return data

3. 颠倒二进制位

颠倒给定的32位无符号整数的二进制位

1
2
3
4
5
6
7
8
9
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。

输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

实现思路
方法一:
预先定义一个数res=0,然后每次取n的最后一位,赋值给res的最后一位,而后res左移,左移的目的是为了给下次的添加的值让出位置,同时n右移一位。

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
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res = 0
for _ in range(32):
res = res << 1
res = res | (n & 1)
n = n >> 1
return res

class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
# 如何来颠倒二进制位
# str.zfill(width)方法返回指定长度的字符串,原字符串右对齐,前面填充0
n = bin(n)[2:].zfill(32)
return int(n[::-1], 2)

class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res=list('{:032b}'.format(n))[::-1]
return int(''.join(res),2)

4. 杨辉(帕斯卡)三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

在杨辉三角中,每个数是它左上方和右上方的数之和

1
2
3
4
5
6
7
8
9
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
1
2
3
4
5
6
7
8
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
i, rose, jack = 0, [1], []
while i < numRows:
jack.append(rose)
rose = [1] + [rose[x] + rose[x + 1] for x in range(len(rose) - 1)] + [1]
i += 1
return jack

4. 缺失的数字

给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

1
2
3
4
5
输入: [3,0,1]
输出: 2

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

实现思路
方法一:
直接计算,时间复杂度和空间复杂度最低
题中的数组的中元素是一个连续序列,这就意味这这序列的和是可以根据等差数列公式计算出来的,计算出序列的总和然后减去数组的总和就得到了缺失的数字。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
total = n * (n + 1) // 2
target = total - sum(nums)
return target

方法二:
集合求差集,先生成完整序列的集合,然后将数组转换成集合进行求差集。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 集合difference方法实现
total = [i for i in range(len(nums)+1)]
target = set(total) - set(nums)
return target.pop()

5. 有效的括号

给定一个只包括(, ), {, }, [, ]的字符串,判定字符串是否有效。
有效的字符串必须满足:

  • 左括号必须用相同的类型的右括号闭合
  • 左括号必须以正确的顺序闭合

注意空字符串是被认为有效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

实现思路
方法一:
这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。这里我们需要用一个栈,我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回false,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回false。

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
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for elem in s:
if elem == '(' or elem == '[' or elem == '{':
stack.append(elem)
else:
if not stack:
return False
if elem == ')' and stack[-1] != '(':
return False
if elem == ']' and stack[-1] != '[':
return False
if elem == '}' and stack[-1] != '{':
return False
stack.pop()
return not stack

class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
mapping = {")":"(", "]":"[", "}":"{"}
stack = []
for i, char in enumerate(s):
if char not in mapping:#left
stack.append(char)
else:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()

return len(stack) == 0

方法二:
使用字符串替换,只要遇到一对”()”、”[]”或”{}”,就从字符串中删掉,直到字符串中没有上述重复的括号为止,根据最终是否剩下空串来判断括号是否有效。

1
2
3
4
5
6
7
class Solution:
def isValid(self, s):
while '{}' in s or '()' in s or '[]' in s:
s = s.replace('{}', '')
s = s.replace('[]', '')
s = s.replace('()', '')
return s == ''