无聊的刷题笔记

二叉搜索树的第k大节点

剑指Offer 54

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
stack = [root]
while root.right:
stack.append(root.right)
root = root.right
while len(stack) != 0:
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.left
while node:
stack.append(node)
node = node.right
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthLargest(root *TreeNode, k int) int {
stack := []*TreeNode{root}
for root.Right != nil {
stack = append(stack, root.Right)
root = root.Right
}
for len(stack) != 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if k== 1 {
return node.Val
}
k -= 1
node = node.Left
for node != nil {
stack =append(stack, node)
node = node.Right
}
}
return -1
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthLargest(root *TreeNode, k int) int {
s := []int{}
var helper func(node *TreeNode)
helper = func(node *TreeNode) {
if node == nil {
return
}
helper(node.Right)
s =append(s, node.Val)
helper(node.Left)
}
helper(root)
return s[k-1]
}

Binary Tree Level Order Traversal

LeetCode 94

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while root.left:
stack.append(root.left)
root = root.left
while len(stack) != 0:
node = stack.pop()
result.append(node.val)
node = node.right
while node:
stack.append(node)
node = node.left
return result
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}
stack := []*TreeNode{root}
var result []int
for root.Left != nil {
stack = append(stack, root.Left)
root =root.Left
}
for len(stack) != 0 {
node:= stack[len(stack)-1]
result = append(result, node.Val)
right := node.Right
stack[len(stack)-1] = nil
stack = stack[:len(stack)-1]
for right != nil {
stack =append(stack, right)
right = right.Left
}
}
return result
}

链表中倒数第k个节点

剑指Offer 22

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
cur = nxt = head
for i in range(k-1):
nxt = nxt.next
while nxt.next:
cur = cur.next
nxt = nxt.next
return cur

和为s的连续正数序列

顺时针打印矩阵

剑指Offer 29 LeetCode 54

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if len(matrix)==0:
return []
a, b = 0, len(matrix[0])-1
j, k = 0, len(matrix)-1
result = []

while a<=b and j <=k:
# print(a,b,j,k)
for i in range(a, b+1):
result.append(matrix[j][i])
for i in range(j+1, k+1):
result.append(matrix[i][b])
if j!=k:
for i in range(b-1,a-1,-1):
result.append(matrix[ k][i])
if a!=b:
for i in range(k-1, j, -1):
result.append(matrix[i][a])
# print(result)
a, b = a+1, b -1
j, k = j+1, k-1
return result

最小的K个数

剑指Offer 40

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

限制:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

只接受n log(n) 的时间复杂度

class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
arr = self.quick_sort(arr, 0, len(arr)-1)
return arr[:k]

def quick_sort(self, lists, i , j):

return lists

和为s的连续正数序列

剑指Offer 57-II

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]
示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

限制:

1 <= target <= 10^5

等差数列

class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
result = []
for a in range(1, (target+1)//2):
b = (2*target + 0.25 + a**2 -a)**0.5-1/2
if int(b) == b:
result.append(list(range(a, int(b)+1)))
return result

二进制中1的个数

剑指Offer 15 LeetCode 191

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。
示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。
示例 3:

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

提示:

输入必须是长度为 32 的 二进制串 。

class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
for i in range(32):
if n & 0x01:
res += 1
n = n >> 1
return res