- 剑指 Offer 50. 第一个只出现一次的字符
- 剑指 Offer 52. 两个链表的第一个公共节点
- 剑指 Offer 53 - I. 在排序数组中查找数字 I
- 剑指 Offer 53 - II. 0～n-1中缺失的数字
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 二叉搜索树的遍历问题
- 剑指 Offer 55 - II. 平衡二叉树
- 剑指 Offer 56 数组中出现数字的次数
- 剑指 Offer 57. 和为某个数字
- 剑指 Offer 58 - I. 翻转单词顺序
- 剑指 Offer 58 - II. 左旋转字符串
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
s = "abaccdeff"
返回 "b"
class Solution:
def firstUniqChar(self, s):
lists = list(s)
d = dict()
for ss in lists:
d[ss] = not ss in d # 没出现过=1，出现过=0
find = False
for key in d.keys():
if d[key]: # 没出现过=1
find = True
break
if find:
return key
if not find:
return ' '
剑指 Offer 52. 两个链表的第一个公共节点
交替遍历！！！这段code 我直接好家伙！！
巧妙的消除两个链表的长度差
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA, headB):
node1, node2 = headA, headB
while node1 != node2:
node1 = node1.next if node1 else headB
# 当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点
node2 = node2.next if node2 else headA
# 当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点.
return node1
剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
nums = [5,7,7,8,8,10]
target = 8
count = 0
for num in nums:
if num == target:
count += 1
if num > target:
break
print(count)
剑指 Offer 53 - II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
输入: [0,1,2,3,4,5,6,7,9] 输出: 8
输入：[1,2] 输出0
输入：[0,1] 输出2
class Solution:
def missingNumber(self, nums):
'''
解法一
for _ in range(len(nums)+1):
if _ not in nums:
return _
'''
# 解法二（数学逻辑）
n = len(nums)
total = n * (n + 1) // 2
return total - sum(nums)
剑指 Offer 54. 二叉搜索树的第k大节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 定义测试用例
t1 = TreeNode(5)
t2 = TreeNode(3)
t3 = TreeNode(9)
t1.left = t2; t1.right = t3
t4 = TreeNode(1)
t5 = TreeNode(4)
t6 = TreeNode(18)
t2.left = t4; t2.right = t5; t3.right = t6
二叉搜索树的遍历问题
参考链接题解https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/
首先搞清楚遍历规则：
- 前序：5 3 1 4 9 18
- 中序 1 3 4 5 9 18
- 后序 1 4 3 18 9 5
- 层次 5 3 9 1 4 18
递归解法
# 前序
def qianxu(root):
res = []
def dfs(root):
nonlocal res
if not root:
return
else:
res.append(root.val) # 变动位置
dfs(root.left)
dfs(root.right)
dfs(root)
return res
print(qianxu(t1))
# 中序
def zhongxu(root):
res = []
def dfs(root):
nonlocal res
if not root:
return
else:
dfs(root.left)
res.append(root.val) # 变动位置
dfs(root.right)
dfs(root)
return res
print(zhongxu(t1))
# 后序
def houxu(root):
res = []
def dfs(root):
nonlocal res
if not root:
return
else:
dfs(root.left)
dfs(root.right)
res.append(root.val) # 变动位置
dfs(root)
return res
print(houxu(t1))
迭代解法
- 层次遍历——队列，左子节点先进先出
- 前序遍历——1.栈，右子节点先进后出，之后append；2.栈，左子节点一边先进一边，再轮到右子节点
- 中序遍历——栈，左子节点先进，全进之后append
- 后序遍历——1.前序遍历左右互换，最后反向输出；2.用一个flag 让根节点保持在队伍前方，从而晚于子节点输出。
# 层次——队列迭代
def cengci(root):
res = []
if not root:
return res
nodelist = [root]
while nodelist:
cur = nodelist.pop(0)
res.append(cur.val)
if cur.left:
nodelist.append(cur.left)
if cur.right:
nodelist.append(cur.right)
return res
print(cengci(t1))
# 前序遍历迭代第一种
def qianxu2(root):
res = []
if not root:
return res
nodelist = [root]
while nodelist:
# nodelist右子节点先进——栈pop左子节点先出
cur = nodelist.pop()
res.append(cur.val)
if cur.right:
nodelist.append(cur.right)
if cur.left:
nodelist.append(cur.left)
return res
print(qianxu2(t1))
# 前序遍历迭代第二种
def qianxu2(root):
res = []
if not root:
return res
nodelist = []
cur = root
while nodelist or cur:
while cur:
nodelist.append(cur)
res.append(cur.val)
cur = cur.left
cur = nodelist.pop()
cur = cur.right
return res
print(qianxu2(t1))
# 中序遍历
def zhongxu2(root):
res = []
if not root:
return res
cur = root
nodelist = []
while nodelist or cur:
while cur:
nodelist.append(cur)
cur = cur.left
cur = nodelist.pop()
res.append(cur.val)
cur = cur.right
return res
print(zhongxu2(t1))
# 后序遍历第一种——把前序左右反过来，然后倒序输出
def houxu2(root):
res = []
if not root:
return res
nodelist = []
cur = root
while nodelist or cur:
while cur:
nodelist.append(cur)
res.append(cur.val)
cur = cur.right
tmp = nodelist.pop()
cur = tmp.left
return res[::-1]
print(houxu2(t1))
# 后序遍历第二种——栈操作，前序根-左-右，后续左-右-根，
# 如果是根节点先append回去最后pop
def houxu3(root):
res = []
if not root:
return res
nodelist = [(0, root)]
while nodelist:
flag, cur = nodelist.pop()
if flag == 1: # 如果是1
res.append(cur.val)
else: # 如果不是重新append回去
nodelist.append((1, cur))
if cur.right:
nodelist.append((0, cur.right))
if cur.left:
nodelist.append((0, cur.left))
return res
print(houxu3(t1))
剑指 Offer 55 - II. 平衡二叉树
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def maxDepth(root):
if not root:
return 0
return max(maxDepth(root.left),maxDepth(root.right))+1
if not root:
return True
diff = abs(maxDepth(root.left) - maxDepth(root.right))
if diff > 1:
return False
else:
return self.isBalanced(root.left) and self.isBalanced(root.right)
s7 = Solution()
s7.isBalanced(t1)
剑指 Offer 56 数组中出现数字的次数
——字典通解
#在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
def findUnique(nums):
d = dict()
res = []
for num in nums:
d[num] = 0 if num in d else 1
for num in d:
if d[num]:
res.append(num)
return res
findUnique([9,1,7,9,7,9,7]), findUnique([1,2,10,4,1,4,3,3])
剑指 Offer 57. 和为某个数字
1.找出和为X的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
- 开始的二重for暴力超时了！
- 要充分利用这个数组递增的性质，提高运算效率
class Solution:
def twoSum(self, nums, target):
# 使用双指针
n = len(nums)
left, right = 0, n-1
while left < right:
tmpsum = nums[left] + nums[right]
if tmpsum == target:
return [nums[left], nums[right]]
if tmpsum > target:
right -= 1
if tmpsum < target:
left += 1
找出所有和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
- 方法一：循环/滑动窗口
target = 9
12345如果有一颗等于则输出，一旦大于就break，下一次从2开始 - 方法二：利用求和公式找到i，从而减少一次循环次数——时间复杂度大大降低
### 1.方法1 二重循环
target = 15
res = []
for i in range(1, target//2 + 1): # 至少含有两个数字
tmpsum = i
tmp_res = [i]
for j in range(i+1, target):
tmpsum += j
tmp_res.append(j)
if tmpsum == target:
break
if tmpsum > target:
tmp_res = []
break
if tmp_res:
res.append(tmp_res)
print(res)
### 2.方法2 滑动窗口
i, j = 1, 2
res2 = []
while j <= target//2 + 1 and i < j:
cur_sum = sum(list(range(i, j+1))) # 当前和
if cur_sum < target:
j +=1
if cur_sum > target:
i +=1
if cur_sum == target:
res2.append(list(range(i, j+1)))
i += 1 # 进行下一种情况
print(res2)
### 3.运用数列求和公式找到可能的i，从而减少一次循环次数
res3 = []
for k in range(1, target//2):
i = ((2 * target) / (k+1) - k) / 2
if i >0 and i%1==0:
res3.append(list(range(int(i), int(i)+k+1)))
print(res3[::-1])
剑指 Offer 58 - I. 翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。同时删掉多余的空格！
e.g.输入: " hello world! "
输出: "world! hello"
str = ' I am a a student. !!! '
strlist = list( str )
res = []
i = 0
while i < len( strlist ):
tmp = []
j = 0
# 每一个单词作为一个[] 整体
while ( i + j < len(strlist) ) and ( strlist[ i + j] != ' ' ):
tmp.append(strlist[ i + j ])
j += 1
# 对下一个字符进行操作
i += j + 1
if tmp:
res.append(tmp)
# 结果——一个嵌套list
print(res)
# 用一个栈倒序输出
ress = []
while res:
ress.append(''.join(res.pop()))
print(' '.join(ress))
[['I'], ['a', 'm'], ['a'], ['a'], ['s', 't', 'u', 'd', 'e', 'n', 't', '.'], ['!', '!', '!']]
!!! student. a a am I
剑指 Offer 58 - II. 左旋转字符串
是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
s = "yangshuyi";n = 4
# 1.直接切片
print(s[n:] + s[:n])
# 2.队列问题
strlist = list(s)
for i in range(n):
tmp = strlist.pop(0)
strlist.append(tmp)
print(''.join(strlist))
shuyiyang
shuyiyang