3.数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
解法
1 | class Solution: |
使用 O(1) 空间的解法: 但条件一定要明确,存在重复数字。思维类似于寻找链表环的入口。
1 | class Solution: |
4.二维数组中的查找
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解法:
1 | class Solution: |
5.替换空格
题目描述
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为 We Are Happy .则经过替换之后的字符串为 We%20Are%20Happy 。
解法:
1 | class Solution: |
6.从尾到头打印链表
题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
解法:
1 | # class ListNode: |
还可以递归实现:
1 | class Solution: |
7.重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
解法:
1 | # class TreeNode: |
1 | class Solution: |
8.二叉树的下一个节点
题目描述
给定一个二叉树和其中的一个节点,请找出中序遍历顺序的下一个节点并且返回。注意,树中的节点不仅包含左右子节点,同时包含指向父节点的指针。
解法:
1 | # Definition for a binary tree node. |
9.用两个栈实现队列
题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
解法:
1 | class Solution: |
10.斐波那契数列
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
解法:
1 | class Solution: |
1 | class Solution: |
1 | class Solution: |
11.旋转数组中的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
解法:
1 | class Solution: |
12.矩阵中的路径
题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。
注意:
输入的路径不为空;
所有出现的字符均为大写英文字母;
解法:
1 | class Solution(object): |
13.机器人的运动范围
题目描述
地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。但是不能进入行坐标和列坐标的数位之和大于 k 的格子。请问该机器人能够达到多少个格子?
解法:
1 | class Solution: |
14.剪绳子
题目描述
给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少?例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。
解法:
1 | class Solution: |
1 | class Solution: |
15.二进制中 1 的个数
题目描述
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
解法:
1 | class Solution: |
16.数值的整数次方
题目描述
实现函数double Power(double base, int exponent),求base的 exponent次方。不得使用库函数,同时不需要考虑大数问题。
解法:
1 | class Solution: # 简单快速幂解法 |
18.删除列表中重复的节点
题目描述
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
解法:
1 | # class ListNode: |
19.正则表达式匹配
题目描述
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配。
解法:
1 | class Solution(object): |
20.表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
解法:
两种写法: 第一种是一次遍历所有条件判断,第二种就好理解很多。
1 | class Solution(object): |
1 | class Solution: |
21.调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。
解法:
1 | class Solution: |
22.链表中倒数第 k 个节点
题目描述
输入一个链表,输出该链表中倒数第k个节点。
解法:
1 | # class ListNode: |
23.链表中环的入口节点
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口节点,否则,输出null。
解法:
1 | # class ListNode: |
24.反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
解法:
1 | # class ListNode: |
1 | class Solution: |
25.合并两个排序的链表
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
解法:
1 | # class ListNode: |
26.树的子结构
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。我们规定空树不是任何树的子结构。
解法:
1 | # Definition for a binary tree node. |
27.二叉树的镜像
题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述
1 | 二叉树的镜像定义:源二叉树 |
解法:
1 | # class TreeNode: |
28.对称的二叉树
题目描述
请实现一个函数,用来判断一棵二叉树是不是对称的。
如果一棵二叉树和它的镜像一样,那么它是对称的。
输入描述
1 | 如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树: |
解法:
1 | # Definition for a binary tree node. |
29.顺时针打印矩阵
题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
解法:
1 | class Solution: |
动用了hin多空间
1 | class Solution: |
30.包含min函数的栈
题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
解法:
1 | class MinStack: |
进阶牛逼版 O(1)空间复杂度 O(1)时间复杂度
1 | class MinStack: |
31.栈的压入弹出序列
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
注意:若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空,则视为是一个栈的压入、弹出序列。
解法:
1 | class Solution: |
32.从上到下打印二叉树
题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
解法:
1 | # class TreeNode: |
33.二叉搜索树的后序遍历序列
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false.假设输入的数组的任意两个数字都互不相同。
解法:
1 | class Solution: |
34.二叉树中和为某一值的路径
题目描述
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解法:
分析: 分为两个解法,一种是递归的做法,另外一种是迭代的做法。
1 | # Definition for a binary tree node. |
迭代法
1 | class Solution: |
35.复杂链表的复制
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
解法:
1 | # class RandomListNode: |
36.二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
注意:需要返回双向链表最左侧的节点。
解法:
1 | # Definition for a binary tree node. |
37.序列化二叉树
题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。
解法:
1 | # Definition for a binary tree node. |
38.字符串的排列
题目描述
输入一组数字(可能包含重复数字),输出其所有的排列方式。
解法:
1 | class Solution: |
39.数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
解法:
1 | class Solution: |
40.最大的k个数
题目描述
在未排序的数组中找到前k个大的元素。 请注意,它们是排序顺序中前k个大的元素,而不是前k个不同的元素。
解法:
1 |
41.数据流的中位数
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
解法:
1 | from heapq import * |
42.连续子数组的最大和
题目描述
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2},最大连续子数组的和为5+2-1+2=8。
解法:
1 | class Solution: |
43.1~n整数中1出现的次数
题目描述
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含“1”的数字有1,10,11和12,其中“1”一共出现了5次。
解法:
1 | class Solution: |
44.数字序列中某一位的数字
题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等。请写一个函数求任意位对应的数字。
解法:
1 | class Solution(object): # 快速跳过不用检查的位数,确定区间。 |
45.把数组排成最小的数
题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组[3, 32, 321],则打印出这3个数字能排成的最小数字321323。
解法:
1 | class Solution: |
46.把数字翻译成字符串
题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。
一个数字可能有多个翻译。例如12258有5种不同的翻译,它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
解法:
1 | class Solution: |
可简化为 O(1) 空间
1 | class Solution: |
47.礼物的最大价值
题目描述
在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。
你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?
解法:
1 | class Solution: |
48.最长不含重复字符的子字符串
题目描述
给定一个字符串,找到最长子字符串的长度而不重复字符。
解法:
分析: 滑动窗口解决问题,如果遍历一遍 s,如果遍历到没有出现的元素,窗口右端立马扩张,并计算最大长度。如果遍历到之前出现的元素,则将窗口左端置为上次出现的位置的后一位。只有出现没有遍历过的元素才会计算最大长度。因为一旦是遍历过的元素,只有可能是保持不变或者缩小。
1 | class Solution: |
49.丑数
题目描述
我们把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。求第n个丑数的值。
解法:
1 | class Solution: |
1 | class Solution: |
50.第一个只出现一次的字符
题目描述
在字符串中找出第一个只出现一次的字符。如输入”abaccdeff”,则输出b。如果字符串中不存在只出现一次的字符,返回#字符。
解法:
1 | class Solution: |
52.两个链表的第一个公共节点
题目描述
输入两个链表,找出它们的第一个公共节点。
解法:
1 | # class ListNode: |
1 | class Solution: |
53.在排序数组中查找数字
题目描述
统计一个数字在排序数组中出现的次数。如果不存在返回 0。
例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。
解法:
1 | class Solution: |
54.二叉搜索树的第k个结点
题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。
你可以假设树和k都存在,并且1≤k≤树的总结点数。
解法:
1 | # class TreeNode(object): |
55.二叉树的深度
题目描述
输入一棵二叉树,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
解法:
1 | # class TreeNode: |
56.数组中数字出现的次数
56-1.数组中只出现一次的两个数字
题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。你可以假设这两个数字一定存在。
解法:
1 | import functools |
56-2.数组中唯一只出现一次的数字
题目描述
在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。你可以假设满足条件的数字一定存在。
思考题:
如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?
解法:
1 | class Solution: # 面试用装x解法 |
1 | class Solution: # 常规解法 |
57.和为S的两个数
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
解法:
1 | class Solution: |
57 - 1.和为S的连续正数序列
题目描述
输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。例如输入15,由于1+2+3+4+5=4+5+6=7+8=15;所以打印出三个连续序列1 ~ 5, 4 ~ 6, 7 ~ 8
解法:
1 | class Solution: |
58.翻转字符串
题目描述
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串“I am a student.”,则输出“student. a am I”
解法:
1 | class Solution: |
59.队列的最大值
题目描述
给定一个数组和滑动窗口的大小,请找出所有滑动窗口的最大值。例如,输入数组{2,3,4,2,6,2,5,1}和数字3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}。
解法:
1 | class Solution: |
60.n个骰子的点数
题目描述
将一个骰子投掷n次,获得的总点数为s,s的可能范围为n~6n。掷出某一点数,可能有多种掷法,例如投掷2次,掷出3点,共有[1,2],[2,1]两种掷法。请求出投掷n次,掷出n~6n点分别有多少种掷法。
解法:
1 | class Solution(object): |
61.扑克牌中的顺子
题目描述
从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,大小王可以看做任意数字。为了方便,大小王均以0来表示,并且假设这副牌中大小王均有两张。
解法:
1 | class Solution: |
62.圆圈中最后剩下的数字
题目描述
题目:0,1,…,n-1这n个数字拍成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里身下的最后一个数字。
解法:
递归法 代码不好理解并且递归深度大,不推荐。在牛客网上无法 AC 。但思路正确。
1 | class Solution: |
循环迭代法
1 | class Solution: |
63.股票的最大利润
题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
解法:
1 | class Solution: |
64.求 1+2+3+…+n
题目描述
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
解法:
1 | class Solution: |
65.不用加减乘除做加法
题目描述
写一个函数,求两个整数之和,要求在函数体内不得使用四则运算符号。
解法:
1 | class Solution: |
66.构建乘积数组
题目描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0] A[1] … A[i-1] A[i+1] … A[n-1]。不能使用除法。
解法:
1 | class Solution: |