刷一下剑指offer题

Posted by 甘家城 on 2020-09-13 Viewed times

题库地址:https://leetcode-cn.com/problemset/lcof/

数组中重复的数字

放到set判断

二维数组中的查找

二位数组左下角作为开始点,target比当前大的话往有移动,target比当前小的话往上移动,只到不能移动或者找到target

替换空格

字符串遍历替换空格并拼接

从尾到头打印链表

链表从头到尾取出,放到栈中,再从栈中取出打印

重建二叉树

前序遍历节点为根节点,将中序遍历分为左子树和右子树,由此递归

用两个栈实现队列

先往栈1加元素,当遇到删除的时候,判断栈2存不存在元素,不存在则将栈1弹入到栈2,存在则删除栈2最上面元素。

斐波那契数列

a, b = b, a+b

青蛙跳台阶问题

一阶或两阶表示f(n) = f(n-1) + f(n-2)
同斐波那契

旋转数组的最小数字

二分查找,中间值比右边大则在右边,比右边小则在左边,相等则右边向左位移

矩阵中的路径

dfs

机器人的运动范围

bfs

剪绳子

剪长度为3最优先,将绳子变成3a+b,b分情况讨论

剪绳子 II

同上+取余

二进制中1的个数

数与1进行&操作,使用移位操作>>

数值的整数次方

将n转为2进制 x^9 转为 x^(11)x^(20)x^(40)x^(80)
二进制从尾向头遍历,遍历中x
=x,为1增乘到结果中

打印从1到最大的n位数

直接打印1 - 10^n-1

删除链表的节点

遍历链表节点,相等的话node.next=node.next.next

正则表达式匹配

表示数值的字符串

有限状态自动机

调整数组顺序使奇数位于偶数前面

左右指针,左边遇到偶数和右边遇到奇数进行交换

链表中倒数第k个节点

左右指针

反转链表

next = cur.next
cur.next = prev
prev = cur
cur = next

合并两个排序的链表

新链表,迭代两个链表往里加

树的子结构

先序遍历a,判断两个树是否全等

二叉树的镜像

left,right = func(right), func(left)

对称的二叉树

func(l.left, r.right) and func(l.right, r.left)

顺时针打印矩阵

一次遍历一圈

包含min函数的栈

用另一个栈,栈顶存储最小值

栈的压入、弹出序列

每压入一个数,都进行循环判断出栈

从上到下打印二叉树

bfs

从上到下打印二叉树 II

bfs

从上到下打印二叉树 III

bfs

二叉搜索树的后序遍历序列

最后一个为根节点,小的在左侧,大的在右侧,由此递归

二叉树中和为某一值的路径

先序遍历,记下路径和总和

复杂链表的复制

深拷贝

二叉搜索树与双向链表

序列化二叉树

字符串的排列

dfs, 交换字符位置,剪枝

数组中出现次数超过一半的数字

相同数+1,不相同数-1,最后留下的数

最小的k个数

快排,左侧如果数量为k则返回,如果大于k则继续快排 // 小顶堆

数据流中的中位数

连续子数组的最大和

局部和,全局和

1~n整数中1出现的次数

0-hd 1-hd+l+1 2-h*d+d

数字序列中某一位的数字

位数d9,找到数字在的位的第n个,找到在哪个数10*(d-1)+(n-1)//d,找到在这个数的第几个(n-1)%d

把数组排成最小的数

基于xy > yx 则 x>y进行排序,连接

把数字翻译成字符串

dfs

礼物的最大价值

动态规划,左上开始,每格+=max(左,上)

最长不含重复字符的子字符串

双指针+hash表,i=max(dic[s[j]], i) j=max(res, j-i)

丑数

三个指针a,b,c指向0位1,分别乘2,3,5取min,与min相等的往后+1位

第一个只出现一次的字符

哈希表,遍历两次字符

数组中的逆序对

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

双指针,一个链表到结尾了返回头,直到相交或一起为null

在排序数组中查找数字 I

二分找到数字,然后向左向右找

0~n-1中缺失的数字

二分看数字和index对不对应

二叉搜索树的第k大节点

反向中序遍历,到底k个

二叉树的深度

后序遍历,层序遍历

平衡二叉树

先序遍历,根据深度判断