简单篇
面试题 01.01. 判定字符是否唯一面试题 01.02. 判定是否互为字符重排面试题 01.03. URL化面试题 01.04. 回文排列面试题 01.06. 字符串压缩面试题 01.09. 字符串轮转面试题 02.01. 移除重复节点面试题 02.02. 返回倒数第 k 个节点面试题 02.03. 删除中间节点面试题 02.06. 回文链表面试题 02.07. 链表相交面试题 03.02. 栈的最小值面试题 04.02. 最小高度树面试题 04.04. 检查平衡性面试题 05.06. 整数转换面试题 05.07. 配对交换面试题 08.03. 魔术索引面试题 08.06. 汉诺塔问题面试题 08.10. 颜色填充面试题 10.01. 合并排序的数组面试题 10.05. 稀疏数组搜索面试题 16.05. 阶乘尾数面试题 16.07. 最大数值面试题 16.11. 跳水板面试题 16.17. 连续数列面试题 17.01. 不用加号的加法面试题 17.04. 消失的数字面试题 17.10. 主要元素面试题 17.12. BiNode面试题 17.16. 按摩师 总结
简单篇 面试题 01.01. 判定字符是否唯一实现一个算法，确定一个字符串 s 的所有字符是否全都不同。 输入: s = "leetcode" 输出: false
class Solution:
def isUnique(self, astr: str) -> bool:
mark = 0
for char in astr:
move_bit = ord(char) - ord('a')
if (mark & (1 << move_bit)) != 0:
return False
else:
mark |= (1 << move_bit)
return True
# 如果bool数组中对应的下标（'a'->0, ..., 'z'->25）的值为1则重复出现，
# 返回false，否则设置对应下标值为1
基于位运算的方法： 我们可以使用一个int类型的变量（下文用mark表示）来代替长度为26的bool数组。 假设这个变量占26个bit（在多数语言中，这个值一般不止26）， 那么我们可以把它看成000...00(26个0)， 这26个bit对应着26个字符，对于一个字符c，检查对应下标的bit值即可判断是否重复。 那么难点在于如何检查？这里我们可以通过位运算来完成。 首先计算出字符char离'a'这个字符的距离，即我们要位移的距离，用move_bit表示， 那么使用左移运算符1 << move_bit则可以得到对应下标为1，其余下标为0的数， 如字符char = 'c'，则得到的数为000...00100，将这个数跟mark做与运算， 由于这个数只有一个位为1，其他位为0，那么与运算的结果中，其他位肯定是0， 而对应的下标位是否0则取决于之前这个字符有没有出现过， 若出现过则被标记为1，那么与运算的结果就不为0； 若之前没有出现过，则对应位的与运算的结果也是0，那么整个结果也为0。 对于没有出现过的字符，我们用或运算mark | (1 << move_bit)将对应下标位的值置为1。
class Solution:
def isUnique(self, astr: str) -> bool:
frequenncy = collections.Counter(astr)
for i, ch in enumerate(astr):
if frequenncy[ch] > 1:
return False
return True
面试题 01.02. 判定是否互为字符重排
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。 输入: s1 = "abc", s2 = "bca" 输出: true
class Solution:
def CheckPermutation(self, s1: str, s2: str) -> bool:
# len1, len2 = len(s1), len(s2)
# if len1 != len2: return False
# frequency1 = collections.Counter(s1)
# frequency2 = collections.Counter(s2)
# for i, ch in enumerate(s2):
# if frequency1[ch] != frequency2[ch]: return False
# return True
# 哈希表方法
# 若 s1, s2 长度不同，则不互为重排
if len(s1) != len(s2):
return False
# 初始化字典 dic ，且所有 key 的初始 value 都为 0
dic = defaultdict(int)
# 统计字符串 s1 各字符数量，遇到 +1
for c in s1:
dic[c] += 1
# 统计字符串 s2 各字符数量，遇到 -1
for c in s2:
dic[c] -= 1
# 遍历 s1, s2 中各字符的数量差
for val in dic.values():
# 若 s1, s2 中某字符的数量不一致，则不互为重排
if val != 0:
return False
# 所有字符数量都一致，因此互为重排
return True
面试题 01.03. URL化
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上 *** 作。） 输入："Mr John Smith ", 13 输出："Mr%20John%20Smith"
class Solution {
public String replaceSpaces(String S, int length) {
// return S.substring(0,length).replace(" ","%20");
// int length = s.length();
// return "%20".join(S[:length].split(" "))
// tmp = S.split()
// n = len(tmp) - 1
// S = S.replace(' ', "%20", n).strip()
// return S
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = S.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
}
面试题 01.04. 回文排列
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。 回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。 回文串不一定是字典当中的单词。 输入："tactcoa" 输出：true（排列有"tacocat"、"atcocta"，等等）
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
# # 初始化哈希表
# dic = defaultdict(int)
# # 统计字符串中各字符的数量
# for c in s:
# dic[c] += 1
# odd = 0
# for val in dic.values():
# # 统计“数量为奇数”字符的个数
# if val % 2 == 1:
# odd += 1
# # 若“数量为奇数”的字符个数 > 1 ，则不是回文串排列
# if odd > 1:
# return False
# # 若“数量为奇数”的字符个数 <= 1 ，则是回文串排列
# return True
frequency = collections.Counter(s)
count = 0
if len(s) % 2 == 0:
for i, ch in enumerate(s):
if frequency[ch] % 2 != 0: return False
else:
for i, ch in enumerate(s):
if frequency[ch] % 2 == 0: continue
elif frequency[ch] > 2 and frequency[ch] % 2 == 1: return True
elif frequency[ch] == 1: count += 1
if count > 1: return False
return True
面试题 01.06. 字符串压缩
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。 比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短， 则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。 输入："aabcccccaaa" 输出："a2b1c5a3"
class Solution:
def compressString(self, S: str) -> str:
if not S:
return ''
ch = S[0]
cnt = 0
ans = ''
for c in S:
if c == ch: cnt += 1
else:
ans += ch + str(cnt)
ch = c
cnt = 1
ans += ch + str(cnt)
return ans if len(ans) < len(S) else S
面试题 01.09. 字符串轮转
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成 （比如，waterbottle是erbottlewat旋转后的字符串）。 输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True
class Solution:
def isFlipedString(self, s1: str, s2: str) -> bool:
if not s1 and not s2: return True
m, n = len(s1), len(s2)
if m != n: return False
for i in range(n):
if s2[i:] + s2[:i] == s1: return True
return False
面试题 02.01. 移除重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if not head:
return head
occurred = {head.val} # 创建集合存放节点值
pos = head
# 枚举前驱节点
while pos.next:
# 当前待删除节点
cur = pos.next
if cur.val not in occurred:
occurred.add(cur.val)
pos = pos.next
else:
pos.next = pos.next.next
return head
面试题 02.02. 返回倒数第 k 个节点
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。 输入： 1->2->3->4->5 和 k = 2 输出： 4
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
# 使用快慢指针
fast = head
slow = head
# 移动快指针走 k 步
for i in range(k):
fast = fast.next
# 快慢指针一起移动,当fast走到低的时候，slow 移动到 n - k 的位置
while fast:
fast = fast.next
slow = slow.next
return slow.val
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
a = []
while head:
a.append(head.val)
head = head.next
return a[-k]
面试题 02.03. 删除中间节点
若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。 例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f 输入：节点 5 （位于单向链表 4->5->1->9 中） 输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
面试题 02.06. 回文链表
编写一个函数，检查输入的链表是否是回文的。 输入： 1->2 输出： false
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
a = []
while head:
a.append(head.val)
head = head.next
return a == a[::-1]
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A, B = headA, headB
while A != B: # 双指针
A = A.next if A else headB
B = B.next if B else headA
return A
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set visited = new HashSet();
ListNode tmp = headA;
while(tmp != null){
visited.add(tmp);
tmp = tmp.next;
}
tmp = headB;
while(tmp != null){
if(visited.contains(tmp)){
return tmp;
}
tmp = tmp.next;
}
return null;
}
}
面试题 03.02. 栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数， 该函数返回栈元素中的最小值。执行push、pop和min *** 作的时间复杂度必须为O(1)。 MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minstack = [math.inf]
def push(self, x: int) -> None:
self.stack.append(x)
self.minstack.append(min(x, self.minstack[-1]))
def pop(self) -> None:
self.stack.pop()
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]
面试题 04.02. 最小高度树
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
self.build(nums, 0, len(nums)-1)
def build(self, nums, left, right):
if left > right: return None
mid = int(left + (right - left) / 2)
root = nums[mid]
root.left = self.build(nums, left, mid - 1)
root.right = self.build(nums, mid + 1, right)
return root
面试题 04.04. 检查平衡性
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root: return True
def maxDepth(root):
if not root: return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1
return abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
面试题 05.06. 整数转换
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。 输入：A = 29 （或者0b11101）, B = 15（或者0b01111） 输出：2
class Solution {
public int convertInteger(int A, int B) {
int xor = A ^ B, ans = 0;
for(int i = 0; i < 32; i++){
ans += (xor & 1) == 1 ? 1: 0;
xor >>= 1;
}
return ans;
}
}
面试题 05.07. 配对交换
配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令 （也就是说，位0与位1交换，位2与位3交换，以此类推）。 输入：num = 2（或者0b10） 输出 1 (或者 0b01)
class Solution:
def exchangeBits(self, num: int) -> int:
return (((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1))
面试题 08.03. 魔术索引
魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。 给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引， 如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。 输入：nums = [0, 2, 3, 4, 5] 输出：0 说明: 0下标的元素为0
class Solution {
public int findMagicIndex(int[] nums) {
return getAnswer(nums, 0, nums.length - 1);
}
public int getAnswer(int[] nums, int left, int right) {
if (left > right) {
return -1;
} // 二分法
int mid = (right - left) / 2 + left;
int leftAnswer = getAnswer(nums, left, mid - 1);
if (leftAnswer != -1) {
return leftAnswer;
} else if (nums[mid] == mid) {
return mid;
}
return getAnswer(nums, mid + 1, right);
}
}
class Solution:
def findMagicIndex(self, nums: List[int]) -> int:
for i in range(len(nums)):
if nums[i] == i:
return i
return -1
面试题 08.06. 汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 你需要原地修改栈。 输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0]
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
"""
Do not return anything, modify C in-place instead.
"""
# for i in A:
# C.append(i)
# return C
n = len(A)
self.move(n, A, B, C)
def move(self, n, A, B, C):
if n == 1:
C.append(A[-1])
A.pop()
return
else:
self.move(n-1, A, C, B)
C.append(A[-1])
A.pop()
self.move(n-1, B, A, C)
面试题 08.10. 颜色填充
编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。 待填充的图像用二维数组 image 表示，元素为初始颜色值。 初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。 请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。 输入： image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 输出：[[2,2,2],[2,2,0],[2,0,1]] 解释: 初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。 初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。 注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
oldColor = image[sr][sc]
q = deque([[sr, sc]])
m, n = len(image), len(image[0])
while q:
x, y = q.popleft()
image[x][y] = newColor
for dx, dy in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and image[nx][ny] != newColor and image[nx][ny] == oldColor:
q.append([nx, ny])
return image
面试题 10.01. 合并排序的数组
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。 初始化 A 和 B 的元素数量分别为 m 和 n。 输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
A[m : ] = B
A.sort()
return A
面试题 10.05. 稀疏数组搜索
稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。 输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1 说明: 不存在返回-1。
class Solution {
public int findString(String[] words, String s) {
int l = 0, r = words.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
// 如果mid指向空字符串，则将右指针(r)向左移动一个位置
if (words[mid].equals("")) {
// 移动右指针(r)之前先判断是否指向目标字符串，防止错过目标字符串
if (words[r].equals(s)) return r;
r--;
} else if (words[mid].equals(s)) return mid;
else if (words[mid].compareTo(s) > 0) r = mid - 1;
else l = mid + 1;
}
return -1;
}
}
class Solution:
def findString(self, words: List[str], s: str) -> int:
for i in range(len(words)):
if words[i] == s: return i
return -1
面试题 16.05. 阶乘尾数
设计一个算法，算出 n 阶乘有多少个尾随零。 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n >= 5){
n = n / 5;
count += n;
}
return count;
}
}
面试题 16.07. 最大数值
编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。 输入： a = 1, b = 2 输出： 2
class Solution:
def maximum(self, a: int, b: int) -> int:
return ((a + b) + abs(a - b)) // 2
面试题 16.11. 跳水板
你正在使用一堆木板建造跳水板。 有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。 你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。 输入： shorter = 1 longer = 2 k = 3 输出： [3,4,5,6] 解释： 可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。
class Solution:
def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
if k == 0: return []
if shorter == longer: return [shorter * k]
lengths = []
for i in range(k + 1):
lengths.append(shorter * (k - i) + longer * i)
return lengths
面试题 16.17. 连续数列
给定一个整数数组，找出总和最大的连续数列，并返回总和。 输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre, ans = 0, nums[0]
for i in range(len(nums)):
pre = max(nums[i], pre + nums[i])
ans = max(ans, pre)
return ans
面试题 17.01. 不用加号的加法
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 输入: a = 1, b = 1 输出: 2
class Solution:
def add(self, a: int, b: int) -> int:
while b != 0:
tmp = (a & b) << 1
a = (a ^ b)
b = tmp
return a
面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？ 输入：[3,0,1] 输出：2
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length, sum = n * (n + 1) / 2;
for (int i : nums) sum -= i;
return sum;
}
}
// return sum(range(len(nums) + 1)) - sum(nums) python
面试题 17.10. 主要元素
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。 若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。 输入：[1,2,5,9,5,9,5,5,5] 输出：5
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# frequency, n = collections.Counter(nums), len(nums)
# for num in nums:
# if frequency[num] > n/2: return num
# return -1
# nums.sort()
# return nums[len(nums)//2]
# 投票算法
candidate, count = -1, 0
for num in nums:
if count == 0: candidate = num
if num == candidate: count += 1
else: count -= 1
count = 0
length = len(nums)
for num in nums:
if num == candidate: count += 1
return candidate if count * 2 > length else -1
面试题 17.12. BiNode
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。 实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质， 转换 *** 作应是原址的，也就是在原始的二叉搜索树上直接修改。 返回转换后的单向链表的头节点。 输入： [4,2,5,1,3,null,6,0] 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
class Solution {
TreeNode minNode;
public TreeNode convertBiNode(TreeNode root) {
if(root == null) return null;
convertBiNode(root.right);
root.right = minNode;
minNode = root;
convertBiNode(root.left);
root.left = null;
return minNode;
}
}
面试题 17.16. 按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。 输入： [1,2,3,1] 输出： 4 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
class Solution:
def massage(self, nums: List[int]) -> int:
n = len(nums)
if n==0: return 0
dp0, dp1 = 0, nums[0]
for i in range(1, n):
tq0 = max(dp0, dp1)
tq1 = dp0 + nums[i]
dp0, dp1 = tq0, tq1
return max(dp0, dp1)
总结
学习笔记，用于睡前方便阅读复习。答案来自力扣和评论区各方大佬。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）