20、2n皇后问题(使用回溯太难，首先得学N皇后问题)

给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200。

思路：

1. 先将16进制转换成2进制，并严格格式化成1位16进制数对应4位二进制数的格式。
2. 将2进制串转化为8进制串，严格按照3个二进制数对应一个8进制数。
3. 8进制数忽略前导0

• 使用的API

  • 使用Integer类
  • 使用StringBuilder类

注意数据范围，此处int类型有一个数据测试不通过，使用long类型。

思路：使用纯字符的码表相对位置计算。

• ​ 十进制转化为n进制，则是将数不断求余数，余数倒序输出，使用 栈结构最好，数据先进后出。

思路：拿到数据后循环取余数放入栈中，数据缩小n倍。直到数据的余数为0.

考点：给定数字取各个位数上的数字，这里数据少不用循环去取，用数组存了。

• 使用三层循环暴力匹配

• 问题描述：

1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。

• 要求：

按从小到大的顺序输出满足条件的四位十进制数。

• 思路：1221以2位数为对称点，故只需要两层for循环即可。

• 由于位数比较少，可以把每一位取数出来

• 题目描述：

153是一个非常特殊的数，它等于它的每位数字的立方和，即153=111+555+333。编程求所有满足这种条件的三位十进制数。

• 题目要求

按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。

• 思路：

由于只是三位数数据比较小，一个for循环就可以解决，分别取出每一位上的数字做平方计算。

• 题目描述：

杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

给出n，输出它的前n行。

• 输入格式：
  输入包含一个数n。
• 输出格式：

输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。

• 数据规模： 1 <= n <= 34。

• 思路：

将所有数据对齐后发现，对角线和每行最左边的第一个元素为1，其余的都是当前位置的上一行同一个位置的数，加上上一行最左斜方的数。

• 代码：

• 题目描述

给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。

• 输出格式

如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。

• 数据规模

1 <= n <= 1000

• 思路：

将输入的数据作为可变字符串(节省空间，不用频繁的创建对象，而消耗内存)，之后使用字符串API查询目标值。

• 数组暴力查询

• 可以考虑二分法查找（首先得排序）。

• 题目描述

给出n个数，找出这n个数的最大值，最小值，和。

• 输入格式

第一行为整数n，表示数的个数。
第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

• 输出格式

输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。

• 样例输入

• 样例输出

• 思路

用min，max ,sum 分别表示，一次循环

• 题目描述

利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

• 输入格式

输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。

• 输出格式

输出n行，每个m个字符，为你的图形。

• 样例输入

5 7

• 样例输出

• 数据规模

1 <= n, m <= 26

• 思路

看着输出案例，当i=j时you（i，j）= A，然后往左右两边每一个位置相加一

所以每次都只需要在当前需要初始化的位置初始化A，在求当前位置（i，j）与(i,i)的相对位置，在A的基础上加上相对应的数，再转化为char类型存入。

• 问题描述

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

• 考点Integer类的方法使用

• 题目描述

给定一个年份，判断这一年是不是闰年。

当以下情况之一满足时，这一年是闰年：

年份是4的倍数而不是100的倍数；

年份是400的倍数。

其他的年份都不是闰年。

• 数据规模与约定

1990 <= y <= 2050

• 问题描述

• 数据规模

1 <= n <= 1,000,000。

• 思考：首先想到的是先把Fn出，再去邱Fn%10007的余数，由于数据规模太大，这昂做数据会溢出。我们得换思路，使用动态规划
• 动态规划步骤：
  • 确定dp数组：一维数组还是二维数组？含义是什么？
  • 此题dp[i]:表示第i+1个斐波那契数列余10007的值
  • 数值较大建议使用long类型，其实Java中Int也能通过。
• 代码

• 题目描述

• 思考

Java数学类的使用，浮点表示，格式化输出

• 题目描述

• 思考：由于数据规模较大，使用常规方法求和数据一定会溢出。使用大数List存储，在使用分治求和。
• 将大数序列拆分成若干个小数序列，每个小数序列的长度不超过一个阈值，这个阈值可以根据具体问题而定。
• 对于每个小数序列，使用合适的方法计算出它们的和。
• 将每个小数序列的和合并得到大数序列的和。

数据过大，只通过70%，其余超时。

• 换一种思路，这是一个等差数列，使用高斯求和。

• 前n项和公式为：Sn=na1+n(n-1)d/2或Sn=n(a1+an)/2

悲哀啊！忘记数学公式了~~

• 题目描述

• 数据规模表较小可以考虑Java大数暴力求解。

• 题目描述

• 思路

由于题目中构造的方法原理的每次从数列中取出两个最小值相加得到代价。仔细观察题目初始的数据并不是有规律（按大小排序）、

取最小值的方法可以每次求得最代价之后存入两者较小数的第一位，记录下这一为代价。将另一个较小值复制为0.再一次排序。一次遍历完数组。

• 实现

• 题目描述

• 思考

看到题目感觉，好复杂数据很多。但是仔细一想不就是一个数字对应一个英文，

0-20是对应的，30 40 50 也是对应的；其余的就是拼接，例如23 59 这种就是

twenty three fifty nine 这种格式；这就涉及到了数字位上的字符处理。考到了Map的使用。

其实这道题就是考耐心，初始化数据麻烦一点。

• 代码

22.1 方法一–模拟

• 题目描述

• 思考(同下题)

不同在于，方向不一样而已。

• 代码

• 时间复杂度同下

22.1 方法二–按层模拟

• 思路：

• 题目描述：

给你一个 行 列的矩阵 ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

• 题目链接：

• 思考：一开始我以为会像n*n的矩阵采用循环不变量螺旋输出，但是一写我发现不对。经过看官方题解，后来才明白，官方使用了同等大小的二维数组Boolean标识是否已经访问过。

采用一个方向数组，当前数组中的索引坐标不断加上方向数组即可完成旋转（前提是没有越界，超过原来的二维数组，超过、访问过就转向继续移动。

• 解题步骤

  1. 创建返回值对象
  2. 判断给定数组是否合法，不合法返回该空对象
  3. 定义一个与所求数组等大的Boolean数组visited，默认值为false
  4. 定义方向数组directions，分别表示分别表示向右、向下、向左、向上
  5. 循环遍历二维数组

• 代码

• 时间复杂度分析

​ 本题时间复杂度为O(m * n), m ,n 分别是二维数组的行数和列数。由于二维数组中的每个元素都会被访问一次，数组的元素个数为n*m，因此，时间复杂度取决于矩阵的大小。

• 空间复杂度分析

​ 本题额外使用了m*n的额外数组，记录当前元素是否被访问过。有m * n个元素，还需要一个一维列表 directions来存储访问矩阵的顺序，其长度也不会超过 m * n，因此额外的空间复杂度为 O(m * n),所以空间复杂度为O(m * n)。

• 题目描述

• 输入输出格式

• 样例

• 思考

根据题目所说，兔子领先t米后会休息s秒，在这期间我们让乌龟继续跑，兔子的已经跑路程

不变，由于乌龟的路程一直在变，所以乌龟所跑一次就需要判断一次是否产生了胜利者。在兔子没有休息的时候兔子和乌龟的已走路程都在变化，也需要判断是否产生了胜利者。

• 代码实现

• 题目描述

• 思考

基于题目所说，好芯片大于一半，好的芯片测出来的是1，而坏的芯片测出来的结果可能是1,0不确定。且对角线i==j永为1.

这是二维数组表示（i，j）表示，用i芯片去测试j芯片的结果,体重要求芯片编号从1开始，数组中索引为0开始，所以第一i行表示，用（i+1）号芯片测试j+1号芯片的结果。

我们得这样想，假如所有的芯片都是好的，那么所测出来的结果肯定都是1

这里会发现他们的测试结果（每一行）都是1.假如第二个芯片坏了。

这里可以看出第二块芯片是坏的，因为测试数据与其他的都不一样l，是吧。

题目有告诉我们坏的芯片可能会测出0和1的结果，也就是号的和坏的是吧。那假如用它来测试其他芯片的结果恰好产生了正确的测试结果，那不就和其他的一样了吗。这里不会出现这样的情况 。因为对角线恒伟1.就算它残生了器他芯片是正确的也不会和其他正确的芯片所测说出来的结果一样。因为正确的芯片在测试坏的芯片时，它的值只能为0.接下来请看图。

假设第二块芯片还是坏的，也就是第二行.

所以看出规律了吗，我们只要在二维数组中找到相同一维数组的数量大于一半n/2,就默认在着相同的一维数组中（其中一个）的非零值的索引加一就是芯片的编号。这里用j+1表示更容易。

• 代码

• 这种是正常的解法，还有一种就是，因为对角线的值很为1，我们发现在测试数据中第一块和最后一块永远是正确的。也是基于上面的想法，只要两块芯片都是好的，他们的互相测试的结果都是一样的，且都是1，简而言之，只要是沿着做斜对角线对称且值为1的就是好芯片，所以我们课在左斜上三角遍历对称比较就行，遍历整个矩阵就会重复。这样就会出现第一个个芯片和最后一个芯片是特殊情况。没有人和他们对称，他们与自己对称，它们两个永远是好的。这个方法可能有局限性，基于这道题目的册十数据来说是能够通过的。

• 题目描述

• 思考

仔细观察会发现，后者与前者有关； A_i = A_i-1 + 字母表中的第i个字母 + A_i-1（i大于1）,所以此题用动态规划比较适合。

A1=“A"

A2 = “ABA” = A1 + B + A1

……

A_i = A_i-1 + 字母表中的第i个字母 + A_i-1 （i大于1）

A在ASCII码表中的位置是 65，这样我们就可以用循环拼接字符串了。

这样做显然是可以通过但是呢，由于String是不可变字符，每一次操作都会产生对象。开辟了一个n的字符串数组，导致空间复杂度为O(n),时间复杂度为O(n),其实这里是可以优化一下空间复杂度的。只需要O(1)的空间复杂度即可完成。

那就是使用两个循环变量来迭代循环。

• 题目描述

• 思考

开始看这题目挺难，多读几遍发现是找规律。解释代码中有

• 代码优化分析：

由于String是不可变字符串，所以每一次拼接，操作都会产生一个新的对象，极大花费内存。我们可以在这里改变为StringBuilder可变字符串，每次操作都是在原来的基础上修改，节省了很多的内存开销。

• 优化后

• 题目描述：

• 思考：

这题就是简单的考了字符串的简单处理和分支语句判断。和一些API的使用。

29.1 埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种简单而高效的素数筛法，可以用来找出小于等于n的所有素数。

• 算法思想

​ 从2开始，将每一个素数的倍数标记成合数，然后找到下一个未标记的数，将其作为素数，继续进行标记，直到筛选范围内的所有数都被标记过。

• 题目描述

• 思考

判断一个数是否是质数，且要求的数能否被该质素整除，能就凭借在字符串中。每拼接一次要求的数除以当前质数为1时结束循环。

• 什么叫回溯法？

回溯法也叫回溯搜索法，它是一种搜索的方式。回溯是递归的衍生产品，只要是递归就一定会有回溯。也就是说，回溯函数也就是递归函数，指的是一个函数。

• 回溯算法的效率

会所算法很抽象，但其实并不是什么很高深的算法。其本质上就是暴力穷举，穷举所有的可能，然后选出我们的答案，如果想提高回溯算法的效率，可以加一些剪枝的操作，但也是改变不了回溯的本质。

• 回溯法解决的问题
  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按照一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少个符合条件的子集
  • 排列问题：N个数按照一定规则的去全排列，有几种排列的方式
  • 棋盘问题：N皇后，解数独等问题
• 何为组合？何为排列？

组合是不强调元素的顺序，排列是强调元素的排列顺序的。

例如：{1,2}和{2,1}在组合上，就是一个集合，因为不强调顺序，二排列的话就是要强调顺序，{1,2}和{2,1}是不同的集合。

组合无序，排列有序。

• 回溯法模板

  • 回溯函数模板返回值及参数，在回溯算法中，习惯函数起名为backtracking，也可以为别的。但返回值一般为void 。
  • 回溯函数终止条件
  • 回溯算法模板框架

• 如何理解回溯法

回溯法解决的问题度介意抽象成树形结构。

回溯法解决的都是在集合中递归查找子集，集合的大小就构成数的宽度，递归的深度，就构成了树的深度。

递归一定是有种植条件的，所以必然是一棵高度有限度的树（N叉树）。

参数在一开始不确定，后期需要什么就传入什么。

从树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

2.1 第77题：组合

• 力扣题目链接：https://leetcode.cn/problems/combinations/

• 题目描述

• 思路

直接的解法当然是使用for循环，例如示例中k=2，就很容易想到for循环实现，也可以达到题目要求的结果：

n = 100, k = 3 那么就三层for循环，代码如下：

这还可以接受，可是如果n为100，k为50呢？要用50个循环？？n为1000，k为200呢？

所以显然这样的方式是行不通的。

So？

就用到了回溯法，虽然回溯也是暴力搜索，但是至少能解出来，而不是for循环让人绝望。

要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

分析结构

• 回溯实现

• 部分解释

方法的作用是递归求解所有符合要求的组合，并将它们添加到列表中。

方法首先判断当前列表中是否已经有k个数了。如果是，则将列表添加到列表中，然后返回。

如果列表中的元素数量还不足k个，那么就从当前位置开始，循环遍历1~n范围内的所有数。

对于每个遍历到的数i，将它添加到列表中，然后递归调用方法，传递参数n、k和i+1。这里传递i+1是为了保证组合中的数字是递增的，避免重复的组合出现。

在递归调用方法之后，需要将最后添加的元素从列表中删除，以便进行下一次循环遍历。

最终，方法会递归求解所有符合要求的组合，并将它们添加到列表中。最后，方法返回列表，即为所有符合要求的组合。

• 题目描述：同上。
• 思路

举个梨子，

我们假设n=4，k=4，我们画图来看，发现哪一些步骤是多余的。

第一层for循环的时候，从元素2开始遍历都没有意义了，从2开始后面不论怎么取都拿不到要求的k个数的组合。所以我们把它剪掉不需要遍历。

画×的分支是永远不可能达到题目所要求的k个数的集合的，所以直接去掉，不进行遍历。

图中的么一个节点（矩形），就代表一个for循环，就会发现每一层从第二个数开始遍历都是无效遍历！

所以，可以剪枝的地方就在每一层递归中的for循环中的起始位置。如果for循环的起始位置之后的元素个数加上已经取到的元素不足k个，则就没必要遍历了。

注意代码中i，就是for循环里选择的起始位置。

• 优化过程
  • 当前已经选择的元素个数：path.size()
  • 所需要的元素个数为：k - path.size()
  • 列表中所剩余的元素（n-i) >= 所需要的元素个数（k - path.size())
  • 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
• 对于找边界的方法理解

path.size():已经找到的个数。

k-path.size():还需要找的个数

在[x,n]的区间上的数组长度起码是在k - path.size()才有继续搜索的可能，那么就有

n - x + 1 = k - path.size();此处的 n - x + 1 表示：在该区间上总的元素个数

解上列方程得:

​ x = n + 1 -(k - path.size())

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

所以优化之后的for循环是：

• 代码实现

• 题目描述：同上。
• 思路

举个梨子，

我们假设n=4，k=4，我们画图来看，发现哪一些步骤是多余的。

第一层for循环的时候，从元素2开始遍历都没有意义了，从2开始后面不论怎么取都拿不到要求的k个数的组合。所以我们把它剪掉不需要遍历。

[外链图片转存中…(img-9EDP1lLj-1680651749739)]

画×的分支是永远不可能达到题目所要求的k个数的集合的，所以直接去掉，不进行遍历。

图中的么一个节点（矩形），就代表一个for循环，就会发现每一层从第二个数开始遍历都是无效遍历！

所以，可以剪枝的地方就在每一层递归中的for循环中的起始位置。如果for循环的起始位置之后的元素个数加上已经取到的元素不足k个，则就没必要遍历了。

注意代码中i，就是for循环里选择的起始位置。

• 优化过程
  • 当前已经选择的元素个数：path.size()
  • 所需要的元素个数为：k - path.size()
  • 列表中所剩余的元素（n-i) >= 所需要的元素个数（k - path.size())
  • 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
• 对于找边界的方法理解

path.size():已经找到的个数。

k-path.size():还需要找的个数

在[x,n]的区间上的数组长度起码是在k - path.size()才有继续搜索的可能，那么就有

n - x + 1 = k - path.size();此处的 n - x + 1 表示：在该区间上总的元素个数

解上列方程得:

​ x = n + 1 -(k - path.size())

[外链图片转存中…(img-gtsf6otl-1680651749740)]

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

所以优化之后的for循环是：

• 代码实现