无聊的刷题笔记

0~n-1中缺失的数字

剑指Offer 53-II

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

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

限制:

1 <= 数组长度 <= 10000

Solution

func missingNumber(nums []int) int {
for i := range nums {
if nums[i] != i {
return i
}
}
return len(nums)
}

二分

在排序数组中查找数字 I

剑指Offer 53-I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制:

0 <= 数组长度 <= 50000

Solution

func search(nums []int, target int) int {
result := 0
for i := range nums {
if target < nums[i] {
return result
}
if target == nums[i] {
result ++
}
}
return result
}

二分法

两个链表的第一个公共节点

剑指Offer 52 LeetCode 160

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表:

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

Solution

双指针

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
h1, h2 := headA, headB
for h1 != h2 {
if h1 == nil {
h1 = headB
} else {
h1 = h1.Next
}
if h2 == nil {
h2 = headA
} else {
h2 = h2.Next
}
}
return h1
}

走一遍再通过步长差 可以不走完n


lcof-21

剑指Offer 21

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

提示:

0 <= nums.length <= 50000
1 <= nums[i] <= 10000

Solution

func exchange(nums []int) []int {
j, k := 0, len(nums)-1
for j < k {
for j < len(nums) && nums[j] %2 != 0{
j ++
}
for k > -1 && nums[k] %2 == 0 {
k --
}
if j >= k {
return nums
}
tmp :=nums[j]
nums[j] = nums[k]
nums[k] = tmp
j ++
k --
}
return nums
}

旋转数组的最小数字

剑指Offer 10 LeetCode 153

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

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

输入:[2,2,2,0,1]
输出:0

Solution

遍历

func findMin(nums []int) int {
n := 0
for ; n <len(nums)-1; n ++ {
if nums[n] > nums[n+1] {
return nums[n+1]
}
}
return nums[0]

}

二分

func findMin(nums []int) int {
if nums[0] < nums[len(nums)-1] {
return nums[0]
}
l, r := 0, len(nums)-1
for l != r && l != r-1{
m := (l +r) /2
if nums[l] < nums[m] {
l = m
} else {
r = m
}
}
return nums[r]
}

第一个只出现一次的字符

剑指Offer 50

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 “ “

限制:

0 <= s 的长度 <= 50000

func firstUniqChar(s string) byte {
if len(s) == 0 {
return ' '
}
hash := make([]int, 26)
for i := range s {
hash[s[i] - 'a'] += 1
}
for i := range s {
if hash[s[i] - 'a'] == 1 {
return s[i]
}
}
return ' '
}

binary-tree-preorder-traversal

LeetCode 144

给你二叉树的根节点 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 preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = []
result = []
while root:
result.append(root.val)
stack.append(root)
root = root.left
while len(stack) != 0:
node = stack.pop()
node = node.right
while node:
result.append(node.val)
stack.append(node)
node = node.left
return result