数据结构与算法学习(十九)
1、最大数
1.1、题目描述
给定一组非负整数
nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
1
2输入:nums = [10,2]
输出:"210"示例 2:
1
2输入:nums = [3,30,34,5,9]
输出:"9534330"
1.2、解题思路
使用排序的方法来解决这道题,解题思路就是分析传入数组的每一个元素,让最高位的值最大
- 对于没有相同数字开头的输入,我们直接比较这些输入的最高位大小,然后将最高位大的数放在结果高位上即可,例如:{45,56,81,76,123}
- 对于拥有相同数字开头的输入的字符串,我们需要比较它们评价后得到的结果大小来决定这两个元素的前后顺序,比如 {3,30,34} 中,由于 330 > 303 ,所以结果中 3 应该排在 30 前面;同时由于 3430 > 3034 ,所以结果中 34 应该排在 30 前面;又由于 343 > 334 ,所以结果中 34 应该排在 3 前面,于是我们得到结果为 {34330}
我们可以构建一个特殊的堆来完成这个操作,这个堆的顺序不再由元素数值的大小确定,而是表示这个元素在堆中的优先级,比如说,在上面的例子中,由于结果中数字的出现顺序为 34、 3、 30 ,所以 34 应该在堆中的优先级最大。
1.3、解题代码
1 | public String largestNumber(int[] nums) { |
2、旋转数组
2.1、题目描述
给定一个数组,将数组中的元素向右移动
k
个位置,其中k
是非负数。
- 示例 1:
1 | 输入: nums = [1,2,3,4,5,6,7], k = 3 |
2.2、解题思路
- 方法一
我们可以将数组右边需要调换位置的元素看为一组,而左边其他元素看为一组,以示例一为例,它旋转后的结果为 [5,6,7,1,2,3,4] ,要做到这一点,我们只需要
将左边这一组的元素看为一个整体,进行逆序,左边元素变为 [4,3,2,1]
将右边这一组的元素看为一个整体,进行逆序,右边元素变为 [7,6,5]
最后将整个数组整体进行一次逆序操作即可,变为 [5,6,7,1,2,3,4]
- 方法二
- 如果左部分数组和右部分数组一样长,那么只需要将两部分元素中下标相同的元素进行交换即可
比如说在 [1,2,3,4,5,6] 中,只需要将左部分第 i 个元素和右部分第 i 个元素进行交换即可
- 如果左部分数组长度大于右部分数组长度,此时以右侧短的部分为主,将右侧数据与左部分数据中最左边的数据一一对应交换
比如说在 [1,2,3,4,5,6] 中,此时 k 为 2 ,现在需要将 1 和 5 交换,然后 2 与 6 交换。
进行交换后,交换过后的 5 和 6 元素不变,因为它们已经确定了自己的位置,而剩下的 [1,2,3,4] 按照上面的规则进行交换
- 如果右部分数组长度大于左部分数组长度,那么此时以左侧短的为主,左侧元素交换后不改变位置。
2.3、解题代码
- 方法一
1 | public void rotate(int[] nums, int k) { |
3、岛屿数量
3.1、题目描述
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
其实就是在问有多少连成一片的 “1”
- 示例:
1 | 输入:grid = [ |
示例中有三片连在一起的 “1” ,分别是左上角的 4 个 1 ,中间的单独一个 1 和右下角的两个 1 ,所以返回 3
3.2、解题思路
- 感染过程
- 遍历二维数组中的每一个元素,如果当前遍历到的元素是
1
,那么进入感染过程,感染过程会将这个位置的上下左右的1
元素都变为2
示例中,当遍历到 {0,0} 中的 1 时,它会将它上下左右的 1 元素都变为 2 元素,同时分别向它的上下左右元素进行递归。
进行递归, {0,1} 元素、{1,0} 元素也会将它的上下左右是 1 的元素都变为 2
在遍历过程中,如果遍历到一个
1
,那么证明找到了一个感染入口,此时让 count++ 即可
3.3、解题代码
1 | public int numIslands(char[][] grid) { |
4、肯尼迪数
4.1、题目描述
编写一个算法来判断一个数
n
是不是快乐数,快乐数的定义如下
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回 false 。
- 示例
4.2、解题思路
- 找出过程中重复的数字避免进入无限循环
- 初始化一个 Set 对象,将 n 加入到 Set
- 将 n 替换为它每个位置上的数字的平方和,并将其加入 Set
- 重复这个过程,一直到新出现的数字等于 1 时,返回 true
- 当新出现的数字已经存在于 Set 时,返回 false
4.3、解题代码
1 | public boolean isHappy(int n) { |
5、寻找重复数
5.1、题目描述
给定一个包含
n + 1
个整数的数组nums
,其数字都在1
到n
之间(包括1
和n
),可知至少存在一个重复的整数。假设
nums
只有 一个重复的整数 ,找出 这个重复的数 。你设计的解决方案必须不修改数组
nums
且只用常量级O(1)
的额外空间。
示例 1:
1
2输入:nums = [1,3,4,2,2]
输出:2示例 2:
1
2输入:nums = [3,1,3,4,2]
输出:3
5.2、解题思路
- 题目给的数组中,数字都在 1 - n 之间,我们可以将数组下标与其对应的值勾连成一个链表
例如在右边所给的数组 {5,3,4,6,7,4,1,8,2} 中
- 0 下标对应的值为 5 ,故此时得到一个链表为 0->5
- 5 下标对应的值为 4 ,故此时链表为 0 -> 5 -> 4
- 4 下标对应的值为 7 ,故此时链表为 0 -> 5 -> 4 -> 7
- 以此类推,得到链表为 0 -> 5 -> 4 -> 7 -> 8 -> 2 -> 4
当又得到 4 时,我们可以假设此时 2 的 next 指向了前面的 4 元素,即形成了一个环,这样,原题就给我们转换为了一个查找链表第一个入环节点的问题
5.3、解题代码
1 | public int findDuplicate(int[] nums) { |
6、丢失的数字
6.1、题目描述
给定一个包含
[0, n]
中n
个数的数组nums
,找出[0, n]
这个范围内没有出现在数组中的那个数。
示例 1:
1
2
3输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。
6.2、解题思路
- 使用一个 Set 来存储数组中所有的值,然后遍历 [0,n] 范围的数,查找不存在于 Set 中的数即可
6.3、解题代码
1 | public int missingNumber(int[] nums) { |
7、移动零
7.1、题目描述
给定一个数组
nums
,编写一个函数将所有0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
1
2输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
7.2、解题思路
使用 left 指针与 right 指针两个指针来解决这个问题,开始时,将左指针和右指针都指向 0 位置
- 其中左指针 left 指向已经处理好的序列的下一个位置,即下一个可以被非 0 元素占据的位置
- 右指针 right 用来遍历数组,如果遍历到非 0 元素,那么让左右指针指向的元素进行交换,同时左右指针同时右移
- 如果遍历到 0 ,那么让右指针直接右移即可。
7.3、解题代码
1 | public void moveZeroes(int[] nums) { |
8、Morris 遍历
8.1、什么是 Morris 遍历 ?
对于一般的遍历算法,我们都是利用栈来存储之后需要再次访问的节点。
最差情况下,我们需要存储整个二叉树中所有的节点,所以空间复杂度为 O(n) ,而 Morris 遍历则是将空间复杂度降到 O(1) 级别。
Morris遍历用到了线索二叉树的概念,其实就是利用了叶子节点的左右空指针来存储某种遍历前驱节点或者后继节点。因此没有使用额外的空间。
8.2、算法思想
- 创建一个变量
cur
,cur
表示当前节点,一开始,cur
来到整棵树的根节点,即root
- 如果
cur
没有左子节点,那么cur
直接向右移动(cur = cur.right) - 如果
cur
有左子节点,那么找到它左子树的最右节点,将这个节点记为mostRight
- 如果
mostRight
的右指针为空,那么让mostRight
指向当前节点cur
(mostRight.right = cur
),然后让当前节点cur
向左移(cur = cur.left
) - 如果
mostRight
的右指针指向当前节点cur
,为什么会出现这种情况?
这是因为我们在进行 Morris 算法的过程中会改动树的结构,这种情况下,我们将
mostRight.right
置为空(mostRight.right = null
),然后将当前节点右移(cur = cur.right
)
- 当
cur
为空时,流程结束
8.3、举例说明
以下面的二叉树为例,我们称 cur 节点到达二叉树的顺序为 Morris 序
- 初始化
cur
节点为根节点root
,此时Morris
序列为 {1} - 由于
cur
存在左子树,所以我们找到cur
左子树的最右节点,即mostRight
此时指向 5 的位置,将 5 的右指针指向当前节点,即让 5 的右指针指向 1 ,此时cur
向左移,指向 2 ,此时Morris
序列为 {1,2}
- 由于
cur
存在左子树,所以我们找到cur
左子树的最右节点mostRight
,让mostRight.right
指向cur
,同时cur
左移来到 4 位置,此时Morris
序列为 {1,2,4}
- 由于此时
cur
没有左子节点,所以cur
直接向右移动,此时cur
来到 2 位置,此时Morris
序列为 {1,2,4,2}
- 此时
cur
节点存在左树,所以找到mostRight
为 4 ,发现此时它的 right 指针指向了cur
,那么我们让mostRight
的右指针指向空(还原树结构),同时让cur
向右移,来到 5 的位置,此时Morris
序列为 {1,2,4,2,5} - 由于此时
cur
没有左子树,所以cur
直接右移,cur
从 5 变为 1 ,此时Morris
序列为 {1,2,4,2,5,1} - 由于此时
cur
存在左子树,所以找到cur
左子树中最右的节点 5 ,由于它的右指针指向cur
,所以将 5 的右指针直接置为空(还原树结构),同时让cur
右移,此时Morris
序列为 {1,2,4,2,5,1,3} - 此时由于
cur
存在左子树,那么找到它左子树上的最右节点mostRight
(6) ,让mostRight
的右指针指向cur
,然后左移,此时Morris
序列为 {1,2,4,2,5,1,3,6} cur
(6)没有左子树向右移,来到 3 ,此时Morris
序列为 {1,2,4,2,5,1,3,6,3},又因为此时mostRight
的右指针不为空,所以还原树结构,让cur
来到 7 ,此时Morris
序列为 {1,2,4,2,5,1,3,6,3,7}
8.4、Morris 序的规律
- 如果一个节点存在左树,那么在 Morris 序中一定出现两次,这是因为该节点会被它的
mostRight
的下一次向右移动遍历到
比如说 8.3 中的 1 、 2 、 3 节点均出现了两次
- 如果一个节点不存在左树,那么在 Morris 序中一定出现一次,一个节点如果往右走,那么再也不会回头(要不往右下角走,要不往上面走)
8.5、代码实现
1 | public static void morris(TreeNode root) { |
8.6、Morris 遍历实现先序遍历
- 当一棵树存在左子树时,它会被遍历到两次,先序遍历就是只在第一次遍历中打印节点,得到的顺序就是先序遍历
对于那些没有左子树的节点,那么直接输出即可,因为这种节点只会被遍历到一次,而对于那些存在左子树的节点,我们只需要在第一次遍历时打印。
1 | public List<Integer> preorderTraversal(TreeNode root) { |
8.7、Morris 遍历实现中序遍历
- 在中序遍历中,我们只需要让那些会被遍历到两次的节点(存在左子树),在第二次被遍历到时打印,而对于那些只会被遍历到一次的节点,直接打印,这样得到的序列就是中序遍历序列
当一个节点要向右移动时,进行收集 / 打印,得到的序列就是中序遍历序列。
对于一个存在左子树的节点,它会在第二次遍历时将
mostRight
置为空,然后让 cur 向右移动,此时就是第二次遍历,所以打印;对于一个不存在左子树的节点,在遍历到这类节点后会直接右移,所以直接打印即可;
1 | public List<Integer> inorderTraversal(TreeNode root) { |
8.8、Morris 遍历实现后序遍历
- 对于那些拥有左子树的节点,我们在第二次访问该节点时逆序打印该节点左树的右边界
- 最后单独逆序打印整个树的右边界
何为右边界?下图中划线的节点就是这棵树的右边界
- 其中穿过 4 的线为节点 2 的右边界
- 穿过 2 5 节点的线为 1 的右边界,穿过 6 的线为 3 的右边界,穿过 1 3 7 的线为整棵树的右边界
- 其中,逆序表示打印顺序从右下角 –> 左上角
以下面的树为例,它的 Morris 序列为: {1,2,4,2,5,1,3,6,3,7}
- 第二次遍历到 2 时,逆序打印它的右边界,只有 4 ,故后序序列此时为 {4}
- 第二次遍历到 1 时,逆序打印 1 的右边界,此时后序序列变为 {4,5,2}
- 第二次遍历到 3 时,逆序打印 3 的右边界,此时后序序列变为 {4,5,2,6}
- 最后逆序打印整个树的右边界,此时后序序列变为 {4,5,2,6,7,3,1},我们得到了最终解
如何逆序打印整棵树的右边界,我们忽略整棵树右边界上 TreeNode 节点的左指针,将其想象为一条单链表,然后进行单链表反转即可。
- 方法一,反转单链表
这个方法是为了逆序输出某棵树的右边界而编写的,将该右边界看为一个单链表
1 | public TreeNode reverseNode(TreeNode root) { |
- 方法二,收集右边界的逆序节点,然后将该节点再次逆序回来,恢复结构
1 | public void collectRightEdge(TreeNode root, List<Integer> result) { |
- 方法三,使用 Morris 序得到后序遍历结果
1 | public List<Integer> postorderTraversal(TreeNode root) { |
9、二叉树的最小高度
9.1、题目描述
给定一棵树,请找出距离它的根节点到它任一叶子节点的最短距离。
9.2、解题思路
- 递归解
如果 root 为空,那么返回 0
如果 root 的左右子树均为空,那么返回 1
如果 root 的左子树为空,那么我们设它的右子树的最小高度为 minRight ,返回
minRight + 1
如果 root 的右子树为空,那么我们设它的左子树的最小高度为 minLeft ,返回
minLeft + 1
如果 root 的左右子树均不为空,那么结果为
Math.min(minRight,minLeft) + 1
9.3、解题代码
1 | public int minLength(TreeNode root) { |
10、判断一棵树是不是合法的 BST
10.1、题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树,有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
10.2、解题思路
之前使用过递归来完成过这道题,这次使用 Morris 遍历完成这道题目
- 对于一棵二叉树来说,如果它的中序序列是第一个递增序列,那么证明它是一棵合法的 BST
- 在一个节点即将向右移时,进行比对,使用一个值 pre 来表示中序序列中的前一个值
- 如果 pre 的值大于当前节点的值,那么直接返回 false
- 如果整个遍历中都没有出现 1 中情况,那么证明这棵树是 BST
10.3、解题代码
1 | public boolean isValidBST(TreeNode root) { |
11、奇偶链表
11.1、题目描述
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
- 示例
1 | 输入: 1->2->3->4->5->NULL |
11.2、解题思路
- 将输入链表分流为两个链表,第一个链表存放序号为奇数的节点,第二个链表存放序号为偶数的节点,最后将存放着偶数节点的链表挂在存放着奇数节点的链表的尾部即可。
- 定义一个奇数头和一个偶数头,然后遍历输入链表
- 如果当前遍历元素的序号为奇数,那么将该元素放在奇数链表中,否则挂在偶数链表中
- 最后将偶数链表挂在奇数链表最后
如何确定当前遍历元素的序号?使用一个全局变量
count
判断即可。
- 以下面链表来说明这道题
初始化奇数链表的头 oddHead 指向第一个元素
初始化偶数链表的头 evenHead 指向第二个元素
让
oddHead.next = oddHead.next.next
,即将第一个元素与第三个元素连接起来,同时让oddHead= oddHead.next
让奇数的下一个节点向后移动,偶数链表同理最后将两个链表合并即可
11.3、解题代码
1 | public ListNode oddEvenList(ListNode head) { |
12、递增的三元子序列
12.1、题目描述
给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足
i < j < k
,使得nums[i] < nums[j] < nums[k]
,返回 true ;否则,返回 false 。示例 1
1 | 输入:nums = [1,2,3,4,5] |
- 示例 2
1 | 输入:nums = [5,4,3,2,1] |
12.2、解题思路
- 使用一个变量
min
表示当前数组内出现的最小值,使用一个变量second
表示当前数组内出现的次小值,遍历数组过程中维护这两个值,当发现有元素比second
大时就可以判断存在递增子序列 min
一定要在second
之前- 举例说明
以数组
[5,4,1,3,2]
举例说明
- 初始化
min
和second
均为Integer.MAX_VALUE
- 遍历数组,当遍历到元素 5 时,由于此时 5 <
Integer.MAX_VALUE
,将 min 更新为Integer.MAX_VALUE
- 遍历到元素 4 时,将 min 更新为 4 ;遍历到元素 1 时,将 min 更新为 1 ;
- 遍历到元素 3 时,此时由于 min 的值小于 3 且 3 < second 当前值,所以将 3 更新为次小值,即
second = 3
- 当遍历到 2 时,由于此时 min < 2 < second ,所以直接跳过,遍历结束,返回 false
如果以数组
[5,4,1,3,2,6]
为例,那么在遍历到 6 时,由于此时 6 大于 second ,所以返回 true
12.3、解题代码
1 | public boolean increasingTriplet(int[] nums) { |
13、二叉搜索树的公共祖先
13.1、题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
13.2、解题思路
- 与之前做过的二叉树最近公共祖先相同,我们判断要寻找的两个节点是否分布在 root 的异侧,如果是,返回 root ,否则就需要进行递归查找。
- 题目给的是一棵二叉搜索树,于是当两个节点不是分布在 root 异侧时,我们只需要向那两个节点所在的一边进行递归即可。
- 如何判断两个节点是否在异侧?
我们可以通过
(root.val - p.val) * (root.val - q.val)
的值来判断,如果
- 这个值大于 0 ,那么证明
p
、q
在同一侧,这是因为此时(root.val - p.val)
和(root.val - q.val)
的值同号 - 这个值等于 0,那么证明
p
、q
中有一个节点为 root ,此时直接返回 root 即可 - 这个值小于 0,那么证明
p
和q
异侧
- 当
pq
处于一侧时,我们需要判断当前这两个节点在哪一侧,然后再对那一侧进行递归
13.3、解题代码
1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
14、盛最多水的容器
14.1、题目描述
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
- 示例 1:
1 | 输入:[1,8,6,2,5,4,8,3,7] |
14.2、解题思路
- 使用双指针解决这道题
- 初始化左指针
left
指向 0 ,右指针right
指向数组的最后一个元素 - 在双指针进行移动的过程中,容器能装的水的值为
(right - left) * min(arr[left], arr[right])
- 如果
arr[left]
小于arr[right]
,则我们需要让left
向中间移动;反之则需要移动right
- 树状数组
14.3、解题代码
- 双指针
1 | public int maxArea(int[] height) { |
15、打家劫舍
15.1、题目描述
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。
示例 1:
1
2
3
4输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2:
1
2
3
4输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
15.2、解题思路
- 使用动态规划来解决这道题
在解决这道题时,我们根据从左到右的顺序偷东西,这样的话,我们在考虑是否偷第 n 家时就只需要考虑第 n - i 家的情况就可以了,因为第 n + 1 家还没光顾。
- 对于每间房子,我们只有两个选择,即偷与不偷,如果我们选择偷第 n 间房子,那么第 n - 1 间房子只能选择不偷
- 使用一个二维数组来表示状态
1 | f[0][i]:对前 i 个房子进行偷窃,在第 i 个房子不偷的情况下,所能获得的最大收益 |
我们要获得的答案其实就是 max{
f[0][n - 1]
,f[1][n - 1]
}
- 转移方程为
1 | f[1][i] = f[0][i - 1] + arr[i]:如果偷第 i 间房子,那么第 i - 1 间房子只能不偷,同时需要加上在第 i 间房子中偷得的钱 |
- 由于第 i 间房子的状态只与第 i - 1 个房子的状态有关,所以我们使用滚动数组进行优化
15.3、解题代码
1 | public int rob(int[] nums) { |
16、二叉树结构数目
16.1、题目描述
给定一个正整数 n ,代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
16.2、解题思路
- 当 n == 0 时,此时只有一种结构,即空树
- 当 n == 1 时,只有一种树结构;当 n == 2 时,此时有两种树结构
- 当有 n 个节点时,此时我们分情况进行讨论,我们记一棵有 n 个节点的二叉树有 F(n) 种结构
- 如果此时根节点的左子树为空,除 root 节点以外的所有节点都分布在右子树上,那么这种情况下有 F(n - 1) 种二叉树结构
- 如果此时根节点的左子树只有一个节点,那么除 root 节点和左子树节点以外的所有节点都会分布在右子树上,这种情况下有 1 * F(n - 2) 种结构,其中 1 为左子树的情况
- 同理,如果根节点的左子树有 a 个节点,而右子树有 n - a - 1 个节点,那么这种情况下将会有
F(a) * F(n - a - 1)
种结构
将上面所有的情况累加起来,就是答案
16.3、解题代码
1 | public int numTrees(int n) { |
17、Fizz Buzz
17.1、题目描述
给你一个整数
n
,找出从1
到n
各个整数的 Fizz Buzz 表示,并用字符串数组answer
(下标从 1 开始)返回结果,其中:
answer[i] == "FizzBuzz"
如果 i 同时是 3 和 5 的倍数。answer[i] == "Fizz"
如果 i 是 3 的倍数。answer[i] == "Buzz"
如果 i 是 5 的倍数。answer[i] == i
如果上述条件全不满足。
示例 1:
1
2输入:n = 3
输出:["1","2","Fizz"]示例 2:
1
2输入:n = 5
输出:["1","2","Fizz","4","Buzz"]
17.2、解题思路
- 如果 i 是 3 的倍数,那么直接往列表中添加一个 Fizz
- 如果 i 是 5 的倍数,那么直接往列表中添加一个 Buzz
- 如果是 15 的倍数,那么直接添加 FizzBuzz ,否则添加 i
17.3、解题代码
1 | public List<String> fizzBuzz(int n) { |
18、下一个排列
18.1、题目描述
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
18.2、解题思路
- 从尾到头,找到一个严格降序的数对,即存在两个相邻元素,满足
arr[i] < arr[i + 1]
如果找不到这样的一个数对,那么证明整个数组组成的数呈现一个递减的趋势,此时这个串就是一个最大的串,我们需要将数字重新进行升序排序(旋转数组)
- 如果能够找到这样的一个数对,那么我们从尾到头,找到第一个下标 j ,满足
i < j
且arr[i] < arr[j]
这样的
j
一定是存在的,因为如果这样的数对可以找到,那么i + 1
位置的元素满足这个条件
- 交换
arr[i]
和arr[j]
,然后将arr[i + 1]
到末尾的这段后缀整个翻转过来
将「大数」换到前面后,需要将「大数」后面的所有数重置为升序,升序排列就是最小的排列。
以
123465
为例:首先按照上一步,交换 5 和 4,得到123564
;然后需要将 5 之后的数重置为升序,得到 123546。显然 123546 比 123564 更小,123546 就是 123465 的下一个排列
18.3、解题代码
1 | public void nextPermutation(int[] nums) { |
19、打乱数组
19.1、题目描述
给你一个整数数组
nums
,设计算法来打乱一个没有重复元素的数组。
Solution(int[] nums)
使用整数数组nums
初始化对象int[] reset()
重设数组到它的初始状态并返回int[] shuffle()
返回数组随机打乱后的结果
19.2、解题思路
- 使用随机数
- 对于
Math.random()
函数,这个函数会生成一个范围在 [0,1) 上的小数 - 如果我们记上面函数返回的结果为
random
,那么我们让random
乘上一个正整数,这个时候我们就可以得到一个处于 [0,k) 的一个随机小数,我们再将得到的小数转换为 int ,同时让正整数变为 k + 1 ,这样我们最终可以得到一个处于 [0,k] 的随机整数 - 我们就得到了一个新函数
f(k)
,这个函数可以随机返回 [0,k - 1] 范围内的一个整数
如何打乱这个数组?
调用上面定义的函数 f(k) ,生成一个范围在 [0, k - 1] 间的随机数
i
,然后在原有数组中,将数组下标为i
的元素与最后一个元素交换位置调用上面定义的函数 f(k - 1),生成一个范围在 [0, k - 2] 间的随机数 j ,然后在原有数组中,将数组下标为 j 的元素与倒数第二个元素交换位置
如此往复,直到范围缩小至 0 为止
19.3、解题代码
1 | class Solution { |
20、字符串中的第一个唯一字符
20.1、题目描述
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
示例:
1
2
3
4
5s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
20.2、解题思路
使用一个长度为 256 数组(ASCII码)来代替哈希表
遍历一遍字符串,将每个字符对应的 ASCII 码和出现的次数记录进表
遍历数组,将第一个值为一的下标返回
20.3、解题代码
1 | public int firstUniqChar(String s) { |