暴力递归

我要就业
Created At :
Count:2.2k Views 👀 :
  1. 暴力递归
    1. 汉诺塔问题
    2. 用递归逆序一个栈(考验脑回路)
    3. 打印n层汉诺塔从最左边移动到最右边的全部过程
    4. 打印一个字符串的全部子序列
    5. 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
    6. 打印一个字符串的全部排列
    7. 打印一个字符串的全部排列，要求不要出现重复的排列
    8. 从左往右尝试模型:数字字符转化问题
    9. 从左往右尝试模型:背包价值问题
    10. 范围上的尝试模型:玩家抽取纸牌问题
    11. 范围上的尝试模型:N皇后问题
    12. 过河问题:
    13. 海盗分硬币
    14. 欧拉信封问题
    15. N皇后问题
    16. 如何尝试一件事？

暴力递归

  1. 思维:暴力递归实质就是尝试
  2. 概念解释：
    1. 回溯-表示大问题被拆解为小问题，小问题返回给大问题信息，就是回溯
    2. 分治：大问题被拆解成小的子问题，就是分治
  3. 步骤
    1. 把问题转化为规模缩小了的同类问题的子问题
    2. 有明确的不需要继续进行递归的条件（base case）
    3. 有当得到了子问题的结果之后的决策过程
    4. 不记录每个子问题的解（如果记录每个子问题的解，就是我们熟悉的动态规划）

汉诺塔问题

  1. 题目解释:
    1. 打印n层汉诺塔从最左边移动到最右边的全部过程
    2. 汉诺塔圆盘移动，如果杆子上没有圆盘，可以移动到该杆，如果有圆盘则必须移动比该圆盘小的圆盘到该圆盘上
  2. 思路1：
    1. 先想办法把1到N-1层圆盘移动到中间杆
    2. 再把N层的圆盘移动到最右侧的杆上
    3. 把1到N-1个圆盘从中间杆移动到最右侧。
    4. 结束
  3. 思路2：
    1. 忘掉左中右，理解为从from移动到to，from和to都有可能是左中右。所以定义from，to，other三个杆子。
    2. 把1到N-1移动到other上。
    3. 把第N层移动到to上。
    4. 把1到N层从other移动到to上。
    5. 结束
  4. 思路3：
    1. 递归改非递归实现
  5. N层汉诺塔，从左移动到右最优步数是2^N - 1 步。
    1. 递归公式 T(N) = T(N-1) + 1 + T(N-1)。
    2. 化简为等比数列，高中数学内容
  6. 尝试是有优劣之分的，譬如思路1和思路二。在动态规划章节，可以用动态规划优化我们的尝试到最优版本

用递归逆序一个栈(考验脑回路)

  1. 题目解释::
    1. 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
  2. 思路:先不要想着逆序它，实现一个f函数，f函数的作用是把栈传进去，想办法拿到栈低元素并返回。

打印n层汉诺塔从最左边移动到最右边的全部过程

打印一个字符串的全部子序列

打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

打印一个字符串的全部排列

  1. 打印一个字符串的全部排列,process
  2. 打印一个字符串的全部排列，要求不要出现重复的排列.process2。
    1. 方法1,可以用HashSet最后去重，该方式是把递归的所有结果进行筛选。
    2. 方法2:分支限界(提前杀死一个分支).可以抛弃重复元素，例如a在0位置已经尝试完毕，再有一个元素也是a要到0位置，那么禁止，该方法是递归的时候事先判断要不要进行下一步递归，更快一点。

打印一个字符串的全部排列，要求不要出现重复的排列

从左往右尝试模型:数字字符转化问题

  1. 题目解释:
    1. 规定1和A对应，2和B对应，3和C对应…。那么一个数字字符比如”111”就可以转化为：“AAA”,“KA”,“AK”。
    2. 给定一个只有数字字符组成的字符串str,返回有多少种转化结果
  2. 思路：根据从左往右，我们划分多大，来尝试，比如111，我们尝试一个1，为”A”,剩下两个1去继续尝试。如果我们两个1尝试，就是”K”。三个1超过26字符，无法尝试。继续如此周而复始

从左往右尝试模型:背包价值问题

  1. 题目解释:
    1. 给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。
    2. 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

范围上的尝试模型:玩家抽取纸牌问题

  1. 题目解释:
    1. 给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请赶回最后获胜者的分数
    2. 绝顶聪明学术上的解释：双方玩家都会使得对方玩家在当前单独改变策略时，不会获得更大的收益。

范围上的尝试模型:N皇后问题

  1. 题目解释:
    1. N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。
    2. 给定一个整数n，返回n皇后的摆法有多少种。
    3. n=1，返回1
    4. n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0
    5. n=8，返回92
    6. 最优的N皇后的尝试方法，时间复杂度为N^N，但是process2是用位运算加速了常数项的时间

过河问题:

  1. 题目解释:
    1. 人要过河，河里有鳄鱼，鳄鱼会吃人，如果鳄鱼吃了人，鳄鱼就会变弱，其他的鳄鱼就会来吃这个变弱的鳄鱼！问河里有多少条鳄鱼人可以平安过河
    2. 河里一条鱼，人会被吃掉
    3. 河里两条鱼，如果其中一条鱼吃掉人的话，另一条鱼就 会吃掉吃人的这条鱼，所以两条鱼谁也不敢去吃这条鱼！
  2. 偶数条鳄鱼可以安全过河,奇数条鳄鱼时,会被吃掉

海盗分硬币

  1. 题目解释
    1. 什么叫做投票通过?:同意人数>一半
    2. 人性?:人性本恶(不同方案得到金币数量一样多时,会不会打人)
    3. 100个硬币，A、B、C、D、E五个人来分，
    4. 按照A、B、C、D、E的顺序来提出分配方案，超过半数的人赞成(>一半)，方案才能被采纳，可以分走硬币。
    5. 如果方案不被采纳，那么提出方案的人会被打死！
    6. 问如何分硬币，A、B、C、D、E五个人才能都活着！
  2. 思路:从小的地方往大想
    1. 若ABCD都死掉了，只剩E，E：100
    2. 若ABC死掉了，剩DE，无论D投赞成还是反对，都会被杀掉，D：0，E：100
    3. 若AB死掉了，剩CDE，如果C死掉了，则只剩DE，则D必死，D为了不死，所以D只能投赞成票，C: 100，D：0，E：0
    4. 若A死掉了，剩BCDE，如果B想赢，所以B就得拉拢D、E，B：98，C: 0，D：1，E：1
    5. ABCDE，若A想赢，所以A需要拉拢C、DE中的任何一个人，A：97，B：0，C: 1，D：2，E：0(或者给D0,给E2)
  3. 其他题目解释(同意人数>=一半,并且人性本善)

欧拉信封问题

  1. 题目解释:
    1. 一个村里的人相互寄信，一个人只能寄一封信，只能收一封信，不能寄给自己！假设村里有i个人，问有多少种寄信方式？
      1. 假设i=5,
      2. 假设B->E
  2. 思路
    1. 若E->B,就转化为ACD三个人的寄信方式了
    2. 若E不寄信给B,此时，B可以收一封信，E可以寄出一封信，所以可以把BE看成一个人，就转化为了ABCD四个人的寄信方式了
  3. B可以寄给ACDE四个人中的一个
  4. 所以F(5) = 4 * (F(3) + F(4))
  5. 通项公式
    1. f(i)=(i-1) * (f(i-1)+f(i-2))

N皇后问题

  1. 题目解释:
    1. N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。
    2. 给定一个整数n，返回n皇后的摆法有多少种。
      1. n=1，返回1
      2. n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0
      3. n=8，返回92
  2. 最优的N皇后的尝试方法，时间复杂度为N^N，但是process2是用位运算加速了常数项的时间

如何尝试一件事？

  1. 有经验但是没有方法论
  2. 怎么判断一个尝试
  3. 难道尝试这件事真的只能拼天赋么，该怎么搞定面试？
  4. 动态规划是啥？好高端的样子，和尝试有什么关系？
    请见下一章，暴力递归到动态规划的转移套路，解决面试中动态规划的问题。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。

©2016-2020 HITlittlefox

Built with Hexo and 3-hexo theme