回答

收藏

【进击的算法】基础算法——回溯算法

知识点 知识点 24 人阅读 | 0 人回复 | 2023-01-19

帖子摘要:本节主题回溯算法 更多算法深入聊聊KMP算法 我的主页蓝色学者的个人主页   文章目录 一、前言二、概念三、例题1.题目全排列2.解题思路回溯算法的本质问题1问题2问题3        3.总结4.参......8 D# i5 O8 v9 N5 \+ n, m

( E& c0 R1 R" @. e5 s$ m9 a0 r& j大家好,欢迎来到Java吧(www.java8.com),交流、学习Java技术、获取Java资源无任何套路,今天说一说:“【进击的算法】基础算法——回溯算法”
3 `$ g, Y) Y7 Z8 T# x& N) b
6 S: f% M) w. N$ \

% ]# i$ O% R0 I/ N        8 f9 d5 y( y0 |4 ~
               
( q3 I8 J- p- X0 m6 r" F                    
, c7 W/ s: _  a" Q' ?, M                        2 A: Q# m! z" b, K- S
                    
# r3 @5 X( d3 v8 h2 j, N* p+ i8 x6 H# E                     , @: F! ]+ @& R
本节主题回溯算法7 d+ U3 F+ J$ Q! B
更多算法深入聊聊KMP算法1 Y1 K; l/ Q& S) x6 p
我的主页蓝色学者的个人主页% W* J0 P+ Y/ F2 l) w5 ^; [. x! n
- i8 k3 E" R& O- A
; V  u6 }0 C" W; x
" M* K0 b6 O4 d
文章目录
* t8 X' H7 @; g) u& n. r- s
  • 一、前言
  • 二、概念
  • 三、例题
  • 1.题目全排列
  • 2.解题思路
  • 回溯算法的本质
  • 问题1
  • 问题2
  • 问题3
    8 x$ c/ i/ R( m5 H* l2 E' n   
      [4 j' L  p2 L2 S% ^' y$ F
       
  • 3.总结
  • 4.参考代码
    ; R( n5 r6 Q5 ?8 g2 v- E8 n   
  • 四、作业
  • 五、结语
    1 L) W& s" Q$ @3 _" R/ F6 `) ]0 y
    ) d7 ?. n8 L) z/ C7 e9 m) V
    6 p' V" J: B. @4 u( P一、前言
    $ V5 z5 w- O) g很开心又跟大家见面了今天我们来一起学习一下回溯算法的基本思想完成一道经典题目的讲解全排列之后我还会留下本节课的小作业感兴趣的话一起来看看把~- C5 w6 c. O! Y, ]" k+ y# M- w

    2 X3 k) a  `9 }) K2 ^3 I; ?二、概念 ! l, h1 N. {6 X0 ~
    回溯算法又称试探法外文名backtrackingalgorithm这也是为什么我们经常在定义回溯函数的时候为函数取名为 backtracking 回溯算法正如其名在有多种选择的情况下回溯算法会试探性的挨个选择接着再回退到选择前的状态。7 w" P7 a# u& L8 W

      d: E2 ^9 g) c$ F
    / U: O. ^9 V; E: I" t) \& C2 r 其实回溯算法本质上也是一个暴力算法
    5 u/ U: K5 G; n 4 E+ X; p$ [, [3 l# l

    6 u9 H$ M/ R2 s" [6 X( y( U4 r为什么说回溯算法本质上也是暴力算法呢我们通过接下来的一个例题来为大家解释一下
    7 u5 I3 T; V: X
    5 i- \3 I$ @* h% r; Y1 Y三、例题
    2 m3 I$ Q$ l1 V- }3 p1.题目全排列   X7 ?$ |. ]( G5 Z) O& H
    全排列leetcode链接https://leetcode.cn/problems/permutations// u3 u* W2 F  F9 ]
    本题给定我们一个不含重复数字的数组 nums 返回其 所有可能的全排列可以按任意顺序返回答案。
    1 J$ ?1 Z: X) O% q4 T ! v8 x. M# c+ g( Z7 y- w( W% F
    , X$ J. f# m* o: n5 V  [
    示例1& O6 H3 `% ^: v( r" u
    输入nums = [1,2,3]
    5 h  m1 U6 L% n' P 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    , Y% j. Y# q5 x: ?& C& U" H/ \ 示例2
    ' `/ u. n8 }8 @* |) @% k- @ 输入nums = [0,1]) p  X' ]% |) F1 `+ A
    输出[[0,1],[1,0]]
    3 {0 x' B/ e' O0 C
    - X4 G+ |2 G$ D7 A1 K
    , m2 y! c  d! {$ J
    2.解题思路
    , E* }) I  _' K5 W* R$ W全排列想必大家在初高中都应该接触过那么我们都会使用一种方法定住一项让后面交换位置从而达到目的比如: [- z- N5 a& y+ Y9 ?
    , c% h! |1 J5 P& `4 _) ]

      o6 z9 Q8 `( u/ T: z! T( e- d 定住1那么还有2和3一种结果是{123} 交换位置得{132}
    ) `- H. d. ]0 i2 E8 z  F! b 定住2那么还有1和3一种结果是{213} 交换位置得{231}- t) P6 g. C% J# C
    定住3那么还有1和2一种结果是{312} 交换位置得{321}
    7 y! C% h/ X- [/ ]% R" ~  S; S* n; P
    & }0 ^4 U3 d6 n4 a/ P

    $ d6 ]: A. S5 m$ ~, H5 @这样我们便得到了{123}的全排列
    & C5 O& _1 G% R" G' l; L
    * e1 u+ ~" n0 L) t7 \
    ) T# Q6 ]. l" _ 但是假如我们要求{1,2,3,4}的全排列呢
    5 L7 v( S, R& W- c6 b/ Z3 G 3 k0 Z5 f4 t) Y
    8 C6 A' `3 K$ z4 a$ \' {
    很显然我们交换元素的逻辑就会变得复杂2和3交换完以后4怎么办很显然这样会让我们大脑短路如何才能求出呢
    ) J0 f- B) J6 Q! c7 R3 v9 @) V( L
    7 A+ S7 A4 W7 L- B3 S5 g8 y! h + m+ g& o1 Q& h1 ]
    1.                  回溯算法引入 : |- G; g. ~* c( o, ?$ A! L
    复制代码
    9 g6 }3 z% A) _% Z" ]
    8 T& T8 |( w' \  L; m+ }
    回溯算法的本质
    ' ^/ P" f; x- f1 `其实回溯算法本质上也是一种暴力的算法他解决了我们在交换问题上的困惑还拿刚刚{123}的例子
    2 r$ }  y5 j' ^% b$ H7 C ' I" J3 s  U/ D
    481cdcab61a5414ca4cfd5fd7e3b08b6.png (110.28 KB, 下载次数: 0, 售价: 4 金钱)
  • 分享到:
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则