精华内容
下载资源
问答
  • 思想策略: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解...

    1、分治法

    概念:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

    思想策略:

    对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

    特征:

    1. 该问题的规模缩小到一定的程度就可以容易地解决

    2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

    3. 利用该问题分解出的子问题的解可以合并为该问题的解;

    4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

    第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;

    第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

    第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

    基本步骤:

    1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

    2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题 

    3 合并:将各个子问题的解合并为原问题的解。

    适用分治法求解的经典问题:

    1)二分搜索

    2)大整数乘法

    3)Strassen矩阵乘法

    4)棋盘覆盖

    5)合并排序

    6)快速排序

    7)线性时间选择

    8)最接近点对问题

    9)循环赛日程表

    10)汉诺塔


    2、动态规划

    概念:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

    思想策略:

    将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。

    在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。

    依次解决各子问题,最后一个子问题就是初始问题的解。

    特征:

    能采用动态规划求解的问题的一般要具有3个性质:

    (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

    (3) 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

    基本步骤:

    (1)分析最优解的性质,并刻画其结构特征。

    (2)递归的定义最优解。

    (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值 

    (4)根据计算最优值时得到的信息,构造问题的最优解

    适用动态规划求解的经典问题:

    • 矩阵连乘

    • 走金字塔

    • 最长公共子序列(LCS) 

    • 最长递增子序列(LIS) 

    • 凸多边形最优三角剖分 

    • 背包问题 

    • 双调欧几里得旅行商问题


    3、贪心法

    概念:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

    思想策略:

    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    基本步骤:

    1. 建立数学模型来描述问题。

    2. 把求解的问题分成若干个子问题。

    3. 对每一子问题求解,得到子问题的局部最优解。

    4. 把子问题的解局部最优解合成原来解问题的一个解。

    适用贪心法求解的经典问题:

    • 活动选择问题,

    • 钱币找零问题,

    • 再论背包问题,

    • 小船过河问题,

    • 区间覆盖问题,

    • 销售比赛,

    • Huffman编码,

    • Dijkstra算法(求解最短路径),

    • 最小生成树算法


    4、回溯法

    概念:回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

    思想策略:

    在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

    特征:

    (1)针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

    (2)确定结点的扩展搜索规则 

    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    适用回溯法求解的经典问题:

    • 八皇后问题

    • 图的着色问题

    • 装载问题

    • 批处理作业调度问题

    • 再再论背包问题

    • 最大团问题

    • 连续邮资问题

    • 符号三角形问题


    5、字符串匹配算法

    求两个字符串的最长公共序列或最长公共子串

    求字符串的最长回文子串

    翻转单词顺序列,例如:“student. a am I”转为“I am a student.”

    参考链接:我画了29张图,做了4个动画,就是要帮你彻底搞懂面试必备的字符串匹配算法!

    展开全文
  • JavaScript之算法设计思想

    千次阅读 2021-10-27 00:36:43
    排序算法 一、冒泡排序 二、选择排序 三、插入排序 四、归并排序 五、快速排序 查找方法 一、顺序查找 二、二分查找 算法设计思想 一、动态规划 二、分而治之 三、贪心算法 四、回溯算法

    1️⃣排序算法

    一、冒泡排序

    1. 比较所有相邻的元素,如果第一个比第二个大,则交换他们的位置
    2. 一轮比较可以保证最后一个数是最大的,然后继续遍历剩余的数
    3. 代码实现
    const arr = [5,4,3,7,0,2,1]
    let temp = 0;
    //执行arr.length-1次数组中冒泡的过程
    for(let i = 0; i < arr.length -1; i++){
    	//遍历整个数组,将数组中最小的一个移动到数组最后面
    	//因为每一轮循环后,都是将数组中最小的移动到后面,所以arr.length-i,数组末尾已经是最小元素就不再遍历了
        for(let j = 0; j < arr.length - i; j++){
        //将如果相邻元素中,第一个比第二个大,则第一个元素向后移
            if(arr[j]>arr[j+1]){
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp
            }
        }
    }
    
    

    二、选择排序

    1. 找到未排序的数组中的最小值,将他和第一位互换位置
    2. 找到未排序数组中第二小的值,选中并将其放置在第二位
    3. 执行n-1轮后得到的就是一个升序数组
    4. 代码实现
    const arr = [5,4,3,7,0,2,1]
    let temp = 0;
    //执行arr.length-1次选择
    for(let i = 0; i < arr.length - 1; i++){
    	//遍历整个数组
    	//一轮循环数组中最小的元素保证在第一位。后续循环以此类推
    	//所以每一轮循环结束,数组前面都是交换出来的最小值
    	//使j=i,可以在后续遍历中忽略前面已经确认的较小值
        for( let j = i; j < arr.length - 1; j++){
        //如果数组中存在元素小于第一位,则两者互换位置-
            if(arr[j] > arr[j+1]){
                temp = arr[j+1];
                arr[j+1] = arr[i];
                arr[i] = temp
            }
       
        }    
    }
    

    三、插入排序

    1. 从第二个数开始往前比
    2. 遇到大于自己的就将其(大值)位置向后移一位,小于自己的就插入到这个值后面
    3. 以此类推执行n-1次
    
    const arr = [0,5,2,6,1,9]
    //因为是从第二位开始比所以i=1开始
    for(let i = 1; i < arr.length; i++){
        let temp = arr[i];
        let j = i;
        while( j > 0){
            if( arr[j-1] > temp ){
                //将大于当前元素的值向后移
                arr[j] = arr[j-1]
            }
            //当前元素大于前面元素时跳出循环,比较下一位
            //这里break跳出的是while循环,因为前面的元素比较过了,都是有序的数组,所以当arr[j-1] < temp是可以判断temp比之前所有的元素都大,跳出本次循环即可
            else break;
            // j-=1如果放在if前面,当前元素大于前面值时arr[j] = temp依然会将当前元素插入到前面的位置
            //而放在后面break跳出循环j-=1没有执行,相当于arr[j] = arr[j],插入操作值未改变
            j -= 1;
        }
    //交换元素位置(此时j已经执行了-1操作),如果是通过break跳出来的,实际上j并未发生改变,arr[j] = temp相当于给自身赋值
        arr[j] = temp;
    }
    //console.log(arr)
    

    四、归并排序

    1. 分:把数组从中间分成两半,在不断递归的对数组进行“分”的操作,直到分成一个个只存在单独数的数组
    2. 合:把不能再分的两个数组合并为有序数组,然后再对有序数组进行合并,直到全部子数组合并为一个完整的数组

    合并方法:

    1. 新建一个空数组res用于存放最终排序后的数组
    2. 比较两个有序数组的头部·,较小者出队(将拆分后的数组视为为队列)并推入res数组中
    3. 如果数组还有值就重复一二步操作

    代码实现

    const merge = (arr) => {
        // 如果数组长度为1,相当于不能再拆分时返回这些单个数组
        if(arr.length === 1) {return arr;}
        // 获取数组的中间值
        const mid = Math.floor(arr.length / 2)
        // 将数组从中间拆分成开,记为左右新两个数组
        const left = arr.slice(0,mid)
        const right = arr.slice(mid,arr.length)
    
        // 递归拆分
        const orderLeft = merge(left)
        const orderRight = merge(right)
        let res = []
        //当拆分后的数组不为空时
        while(orderLeft.length || orderRight.length){
            // 如果拆分后左右都存在就比较头元素的大小
            if(orderLeft.length && orderRight.length){
                // 将头元素较小的取出然后加到res数组中
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
                // 拆分后只有左边数组存在
            }else if(orderLeft.length){
                res.push(orderLeft.shift())
                // 拆分后只有右边数组存在
            }else if(orderRight.length){
                res.push(orderRight.shift())
            }
        }
        return res;
    }
    const arr = [1,4,3,9,2]
    console.log(merge(arr))
    
    

    五、快速排序

    1. 分区: 从数组中任意选择一个基准,比基准大的元素放在基准后面,比基准小的元素放在基准前面
    2. 递归: 分区后得到的数组左边都比基准值小,右边都比基准值大。然后递归的对基准值前后的子数组再进行分区

    代码实现

    const fastSort = (arr) => {
        if(arr.length === 0) {return arr;}
        // 定义左右两个数组,大于基准的放右边数组,小于基准的放左边基准
        const left = []
        const right = []
        // 基准是随机挑选的一个数
        const stand = arr[0]
        // 因为数组第一个数被挑出来作为基准了,所以这里i从1开始
        for(let i = 1; i < arr.length; i++){
            if(arr[i] < stand){
                left.push(arr[i])
            }else{
                right.push(arr[i])
            }
        }
        // 这里左数组、右数组、基准为三个独立的部分。需要将三者合成一个数组
        //...是ES6中新增的扩展运算符,数组中的扩展运算符(…)用于取出参数数组中的所有可遍历属性,拷贝到当前数组之中。
        return [...fastSort(left),stand,...fastSort(right)]
    }
    const arr = [1,4,0,3,7]
    console.log(fastSort(arr))
    

    但是其实这种快速排序方法是错误的,虽然也是利用快速排序的原理左右分区然后递归,但是使用了两个数组,空间复杂度增加

    下面因该是比较贴切一点的快速排序,可以使用console.time()方法来测试一下排序用时

    // 计算程序执行时间
    console.time('a')
    // 函数传入三个参数,依次是:待排序的数组,待排序数组左边第一个元素的索引,待排序元素右边得第一个元素的索引
    const fastSort = (arr,began,end) => {  
        // 取数组的第一个元素为基准值
        let print = arr[began]
        //如果不定义i,j 直接改变began,end的值,会影响后面递归开始和结束的索引值
        let i = began;
        let j = end;
        //当左边的索引值大于右边的时,说明本轮排序结束
        if(began >= end) {
            // 将本轮排序后的数组返回
            return arr
        }
        //把所有比基准值小的元素放在基准值左边,大的元素放在基准值右边
        while(i < j){
            // 从后往前查找到比基准值小的元素交换
            //继续判断i<j是因为:如果print值较小,arr[j]>print会持续成立,导致j<=i,索引j<=i表示整个数组已经排序结束
            while(arr[j] >= print && i < j){
                j--
            }
            // 比基准值小的元素放左边,如果不存在比基准值小的元素,此时j=i相当于自身给自身赋值
            arr[i] = arr[j] 
            // 找到比基准值大的元素交换
            // 继续判断i<j,因为print值较大时,arr[i] <= print会持续成立,导致j<=i
            while(arr[i] <= print && i < j){
                i++
            }
            // 比基准值大的元素放在右边,如果不存在比基准值大的元素,此时i=j相当于自身给自身赋值
            arr[j] = arr[i]       
        }
        //一次循环结束,将基准值放在中间位置(此时i=j,arr[i]或者arr[j]都可以)
        arr[j] = print
        //递归,继续对基准值左右两边的数组进行排序
        // 这里began不能直接传入0,会影响到第三轮之后的递归,
        // 因为对基准值右边的数组再进行分区排序时也会使用到began,而此时began并不是0
        fastSort(arr,began,j-1)
        fastSort(arr,j+1,end)
        //返回排序后的数组
        return arr
    }	 	  
    const arr = [9,5,1,4,8]
    console.log(fastSort(arr,0,arr.length-1))
    console.timeEnd('a')
    

    之所以从右边开始排序,是因为基准值选择的是最左边,举个例子7 1 2 3 4执行快速排序,假如从左开始排,就会出现1,7,2,3,4

    附:这里有一个25w个数据的乱序数组(有重复),可以用来测试这些排序算法的速度 https://download.csdn.net/download/aaahuahua/34715763

    2️⃣查找方法

    搜索:js中通常使用indexOf方法(返回元素在数组中的下标,不存在返会-1)

    一、顺序查找

    1. 遍历数组
    2. 找到和目标值相等的元素,返回下标
    3. 遍历所有值后如果没有目标值返回-1

    代码实现

    // 在Array数组原型上添加一个方法
    Array.prototype.searchWay = function (item){
    // this指代这个数组
        for(let i = 0; i < this.length; i++){
            if(item === this[i]){
                return i
            }
        }
        return -1
    }
    const arr = [1,3,5,2,9]
    //调用searchWay方法
    console.log(arr.searchWay(5))
    

    二、二分查找

    前提: 查找的是有序数组

    如果是一个无序数组,需要先将其化为有序数组之后再进行二分搜索

    搜索方法

    1. 从中间元素开始,如果正好是目标值,则搜索结束
    2. 如果目标值小于或者大于中间元素,则在大于或者小于目标值的部分数组中继续进行搜索
    // 在数组的原型上添加一个search方法
    Array.prototype.search = function (item){4
        // 定义查找的起始位置和结束位置
        let low = 0;
        let height = this.length - 1;
        // 等于号用于判断数组中只剩下最后一个数时,是否为目标值
        while(low <= height){
            // 选取数组中间元素为基准值
            let mid = Math.floor((low + height) / 2);
            const num = this[mid]
            // 如果目标值就是基准值则返回基准值的下标
            if(item === num){    
                return console.log(mid)
            }else if(item > num){ //当目标值大于基准值时,将查找范围缩小为基准值右边的数组
                low = mid + 1
            }else if(item < num ){//当目标值小于基准值时,将查找范围缩小为基准值左边的数组
                height = mid - 1
            }
        }
        // 查找结束后如果还是没有找到目标元素,则返回该元素不存在
        return console.log("该元素不存在")
    }
    //调用数组原型上的search方法
    const arr = [1,2,3,4,5].search(0)
    

    3️⃣算法设计思想

    一、动态规划

    将一个问题分解成相互重叠的子问题,通过反复求解子问题,来解决原来的问题

    步骤:

    1. 定义子问题
    2. 循环执行子问题中定义的公式

    实战练习

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    注意:给定 n 是一个正整数。

    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
    1 阶 + 1 阶 + 1 阶
    1 阶 + 2 阶
    2 阶 + 1 阶

    动态规划

    1. 定义子问题,到达第n阶可以有两种方法
      (1)从第n-1阶爬一阶
      (2)从第n-2阶爬两阶

    所以到达第n阶的方法就是到达第n-1阶的方法加上到达第n-2阶方法之和:F(n)=F(n-1)+F(n-2)

    1. 从n=2开始循环执行F(n)=F(n-1)+F(n-2)

    代码实现

    
    var climbStairs = function(n) {
    //当阶数小于2,也就是1阶时,直接返回1(n为正整数所以不存在复数的情况)
        if(n<2) return 1;
    //定义数组dp存放到达每一阶的方法数,下标代表阶数,对应值为到达改阶的方法数
    //虽然这里0阶定义的是1,但是n为正整数,不会存在n=0的情况
        const dp = [1,1];
    //因为前两次已经被列举出来了,所以i从2开始
        for(let i = 2;i <= n; i++){
            dp[i]=dp[i-1]+dp[i-2]
        }
        return dp[n]
    };
    
    //代码优化,因为定义了数组,所以空间复杂度为O(n),可以只定义两个变量将复杂度降到O(1)
    var climbStairs = function(n) {
        if(n<2) return 1;
        const dp0 = 1;
        const dp1 = 1;
        for(let i = 2;i <= n; i++){
        //临时存储到达第n-2阶的方法
            const temp = dp0;
            dp0 = dp1;
            dp1 = temp + dp1;
        }
        return dp1;
    };
    

    二、分而治之

    将原问题为很多个相似的小问题,递归的解决这些小问题,然后再将结果并以解决原有的问题

    1. 设计案例之归并排序

    • 分:将数组一分为二
    • 解:递归的对两个子数组进行归并排序
    • 合:合并有序数组(将递归后长度为1的数组合并成有序数组,然后再把这些有序数组继续合并)

    2. 设计案例之快速排序

    • 分:选择基准值将原数组分成大于基准值和小于基准值的两个数组
    • 解:递归的对两个子数组进行快速排序
    • 合:递归到数组中只剩下一个·元素时排序完毕,返回该数组即可

    实战练习

    猜数字游戏的规则如下:

    每轮游戏,都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。

    你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):

    1. -1:选出的数字比你猜的数字小 pick < num
    2. 1:选出的数字比你猜的数字大 pick > num
    3. 0:选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num 返回选出的数字。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/guess-number-higher-or-lower

    示例 1: 输入:n = 10, pick = 6 输出:6
    示例 2:输入:n = 1, pick = 1 输出:1
    示例 3:输入:n = 2, pick = 1 输出:1
    示例 4:输入:n = 2, pick = 2 输出:2

    解题思路:

    使用二分搜索,分,解,和,利用分而治之的思想来做

    1. 分:计算中间元素,分割数组
    2. 解:递归的在较大的或者较小的数组中进行二分搜索
    3. 合:这一步可以省略,因为如果在子数组中搜索到目标值后就直接将其返回了

    代码实现:

    var guessNumber = function(n) {
    //这里定义一个二分查找的函数
        const divide = (low,height) => {
        //当最小值大于最大值时直接return
            if(low > height) return;
            //取两个数的中间值
            const mid = Math.floor((low+height)/2);
            //调用接口判断猜测结果是否正确
            const res = guess(mid);
            if(res === 0 ){
                return mid
            }else if(res === -1){
            //猜测结果小于真实值
                return divide(1,mid-1)
            }else if(res === 1 ){
            //猜测结果大于真实值
                return divide(mid+1,height)
            }
        }
        return divide(1,n)
    };
    

    对称二叉树

    给定一个二叉树,检查它是否是镜像对称的。

    例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
    在这里插入图片描述
    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    在这里插入图片描述

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/symmetric-tree

    解题思路:

    可以转换为左右子树是否为镜像的,然后分解为树1的左子树和树2的右子树是否为互为镜像,树1右子树和树2的左子树是否为互为镜像

    代码实现:

    var isSymmetric = function(root) {
    //如果二叉树为空,返回为true
      if(!root) return true;
      //定义一个镜像判断函数
      const isCheck = (left,right) => {
      //如果左右子树都不存在,返回为true
          if(!right && !left){
              return true
          }
          //左右子树存在,值相等,递归左右子节点
          if(right && left && right.val === left.val &&
            isCheck(left.left,right.right) &&
            isCheck(left.right,right.left)
          ){
              return true
          }
          //其他情况下返回false
          return false
      }
        return isCheck(root.left,root.right)
    }; 
    

    三、贪心算法

    期盼通过每个阶段的局部最优选择,从而达到全局的最优。但是结果有可能并不是最优的

    分发饼干

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

    对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/assign-cookies

    示例1:

    输入: g = [1,2,3], s = [1,1]
    输出: 1
    解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
    虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。

    示例2:

    输入: g = [1,2], s = [1,2,3]
    输出: 2
    解释:
    你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2.

    解题思路:

    局部最优:分发的饼干既能满足孩子,还消耗最少,即先将较小的饼干分给胃口小的孩子

    解题步骤:

    1. 对饼干数组和胃口数组进行升序排序
    2. 遍历饼干数组,找到能满足第一个孩子(胃口最小的孩子)的饼干
    3. 继续遍历饼干数组,找到剩下能满足第二、第三、第四…个孩子的饼干

    代码实现:

    var findContentChildren = function(g,s) {
    //快速排序
        const fastSort = (arr,began,end) => {
            let print = arr[began]
            let i = began;
            let j = end;
            if(began >= end){
                return arr;
            }
            while(i < j){
                while(arr[j] >= print && i < j){
                    j--
                }
                arr[i] = arr[j]
                while(arr[i] <= print && i < j){
                    i++
                }
                arr[j] = arr[i];
            }
            arr[j] = print;
            fastSort(arr,began,j-1)
            fastSort(arr,j+1,end)
            return arr
        } 
        //对小孩的胃口和饼干尺寸两个数组进行排序
        fastSort(s,0,s.length-1)
        fastSort(g,0,g.length-1)
        //定义能满足的小孩个数
        let i = 0;
        //遍历所有饼干
        s.forEach(item =>{
        //如果饼干尺寸大于小孩的胃口,能满足的小孩数加1
            if(item >= g[i]){
                i+=1
            }
        })
        //返回满足的小孩个数
        return i
    };
    

    四、回溯算法

    一种渐进式寻找并构建问题解决方式的策略,即从一个可能的情况开始解决问题,如果不行,就回溯到另一种情况,直到问题被解决(也可以理解为暴力破解)

    回溯思路

    1. 使用递归模拟出所有的情况
    2. 遇到不满足条件的情况就回溯
    3. 收集所有能到达递归终点的情况,并返回

    实战练习

    全排列规则如下:

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序返回答案。


    示例 1:

    输入:nums = [1,2,3]
    输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    示例 2:
    输入:nums = [0,1]
    输出:[[0,1],[1,0]]

    示例 3:
    输入:nums = [1]
    输出:[[1]]

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/permutations

    代码实现

    var permute = function(nums) {
    	//定义结果集
        let res = []
        //定义已排列结果
        let way = []
        //used(标记数组),用于记录当前该元素是否已经被添加到已排列数组(way)中了
        const backtrack = (arr,used) =>{
        //递归结束条件,当已排列数组的长度等于原数组长度时,表明所有元素都已经被添加到已排列数组中了
            if(way.length === arr.length) {
                //将本次排列的结果添加到结果集中
                res.push([...way])
                return;
            }
            // 遍历数组
            for(let i = 0; i < arr.length; i++){
    
        // if(way.indexOf(arr[i]) != -1)
        //  不使用这个方法是因为查找的时间复杂度为O(n),同样的引入used数组会增加空间复杂度也是O(n)
    
                // undefind转换为布尔值是false
                if(used[i])  // 判断该元素是否已经存在于已排列数组中
                continue;
                //向结果集中添加元素
                way.push(arr[i])
                //标记该元素为已添加,使下一层遍历能够区分哪些元素是未排列的剩余元素
                used[i] = true
                // 递归遍历数组,递归遍历arr.length次就可以将数组中的元素全部添加到排列数组中
                backtrack(arr,used)
                // 这个是本次全排列中回溯的重要体现
                // 使用pop方法删除已经添加到排列数组中的元素,可以使排列过程回到上一层递归
                way.pop()
                // 删除已经添加到排列数组中的元素标记
                used[i] = false
            }    
        }
        backtrack(nums,[])
        return res
    };
    

    子集规则如下

    给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
    解集不能包含重复的子集。你可以按任意顺序返回解集。

    示例 1:
    输入:nums = [1,2,3]
    输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

    示例 2:
    输入:nums = [0]
    输出:[[],[0]]

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/subsets

    代码实现

    const subsets = (nums) => {
        const res = [];
        const sun = (index, temp) => {
          if (index == nums.length) { // 索引等于数组长度时
            res.push(temp.slice());   // 加入解集
            return;                   // 结束当前的递归
          }
          temp.push(nums[index]); // 将该元素加入数组
          sun(index + 1, temp);   // 往下递归,添加剩余元素
          temp.pop();             // 上面的递归结束,逐步删除已经添加过的元素
          // 删除已添加的元素后,将剩余结果加入结果集;操作剩余元素
          sun(index + 1, temp);   
        };
        sun(0, []);
        return res;
      };
    
    展开全文
  • KMP算法思想

    2020-12-23 09:32:47
    思想:相比暴力算法kmp是利用之前已经匹配获得的有效信息,比较指针不回溯,而是直接跳过一些字符串(利用next数组),使得原来模式串中的前缀直接移动到后缀位置上(这里的前后缀应该是最长的,注意:不能是比较...

    思想:相比暴力算法kmp是利用之前已经匹配获得的有效信息,比较指针不回溯,而是直接跳过一些字符串(利用next数组),使得原来模式串中的前缀直接移动到后缀位置上(这里的前后缀应该是最长的,注意:不能是比较指针左边本身长度),当移动是如果模式串超过被匹配(主串)串范围,则匹配失败。
    第一步:
    在这里插入图片描述
    第二步:
    在这里插入图片描述
    第三步:
    在这里插入图片描述

    next数组:定义从0开始使得前k位字符,恰好等于后k位字符的最大k,next数组中的值应从模式串中获得。如下列表:(列表第一位写默认0,第二位写1,第三位开始看前边有没有匹配的,没有就写
    1,有一位就写2,两位就写3…):
    如下示例

    abcac
    01112
    展开全文
  • 最近考研复习到图的一些算法,但书上对这些算法解释只是一笔带过,更多的是如何做,如何使用。对于我这种又笨又固执的人来说,无疑非常难受,甚至一开始想不明白这个地方,但又说不出来,所以昨天很长时间都在思考这...

    最近考研复习到图的一些算法,但书上对这些算法解释只是一笔带过,更多的是如何做,如何使用。对于我这种又笨又固执的人来说,无疑非常难受,甚至一开始想不明白这个地方,但又说不出来,所以昨天很长时间都在思考这个算法是为什么。

    看了很多博客,发现也鲜有人去写怎么理解,大都是代码加栗子,接下来说说我从另一个方面的理解,如果有不对的地方,希望大家指正。
    首先定义一下图的结构

    typedef struct {
    	char vex[MAXVERTEXNUM];   //顶点表
    	int edge[MAXVERTEXNUM][MAXVERTEXNUM];   //邻接矩阵
    	int vexnum;    //当前图的顶点数
    	int edgenum;   //当前图的边数
    }Graph;
    

    弗洛伊德算法的核心代码

    for(int k=0; k<g.vexnum; k++)          //最外层循环为中间顶点
    	for(int i=0; i<g.vexnum; i++)      //i为起点
    		for(int j=0; j<g.vexnum; j++)  //j为终点
    			if(dist[i][j] > dist[i][k]+dist[k][j]) {
    				//更新最短路径  若此处还需path矩阵应同步更新
    				dist[i][j] = dist[i][k] + dist[k][j];
    			}
    

    核心代码非常简单,只有短短几行,便可寻找出图中任意两点之间的最短路径,真的非常佩服创造这些算法的前辈
    接下来说说自己的一些理解:

    1. 从核心代码可以看出,每次更新的只是不超过3个点之间的最短路径,即在尝试向两点i,j之间插入第三点k。由此我产生了一个疑问,若两点之间的最短路径长度大于2,弗洛伊德算法是如何寻找到的呢?
    2. 两点之间的最短路径分为3种情况:无路径,路径长度为1或2(即有一个中间顶点),路径长度大于2(即有多个中间顶点)
    3. 对于前两种情况可以通过弗洛伊德算法很好的得到,对于第三种情况,例如i和j之间的最短路径为i–>k1–>k2–>…–>km–>j,通过对最短路算法的分析,显然得该路径中任意两点kiki+2的最短路径仍属于该路径即ki–>k(i+1)–>k(i+2),反过来说只要找到所有长度小于等于2的最短路径,就可以得到(组合为)任意两点之间的最短路径,因此(1)中的问题就解决了,也可以理解为弗洛伊德算法核心代码遍历的过程,对于比较长的最短路径来说就是不断寻找到中间顶点ki(1<=i<=m)的过程,而且寻找的顺序是无所谓的。
    展开全文
  • 递归算法思想

    2021-03-24 12:04:57
    递归算法思想 递归也是一种很常见的算法思想,使用该算法可以很有效的解决一些问题,往往可以简化代码的编写,提高可读性。但是如果有不适合的递归,反而会适得其反。 算法思路: 所谓递归,就是程序中不断反复的...
  • 分支限界算法设计与实现 1.分支限界法求解布线问题 (1)问题描述 印刷电路板不限区域划分成n*m个方格阵列。如下图所示 精确的电路布线问题要求确定连接方格a的中点,到连接方格b的中点的最短布线方案。 (2)问题求解 ...
  • 银行家算法思想

    2021-03-20 17:14:05
    银行家算法思想 检查进程请求资源数目是否超过最大需求量 检查系统当前可用资源是否满足进程请求数目 试探着分配 修改各数据结构 利用安全性算法 看是否进入安全状态 安全性算法 检查系统当前可用资源是否满足进程...
  • 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。 分治法所能解决的问题一般具有以下几个特征: ...
  • 常用5大算法思維 1. 动态规划简单介绍 推荐博文-漫画动态规划 动态规划中的三个重要的概念: 最优子结构 边界 状态转移公式 【例】爬楼梯问题,一次一步或者两步, F(1) = 1; F(2) = 2; F(n) = F(n-1) + F(n-2) (n&...
  • 代码链接:pan.baidu.com/s/1rIugypf7lhUTfwdAG0Gv_w 码:w38a 算法分析与设计第 2 次实验 时间 ... 通过上机实验,要求掌握贪心算法的问题描述、算法设计思想、程序设计。 ...
  • 标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N]标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N]计算机算法设计五大常用算法的分析及实例摘要算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的...
  • 1、数据结构的存储方式 ...设计不同的数据结构其根本目的是使得增删改查尽可能的高效。例如对于银行办理业务这个实际问题,使用队列来存储数据就比其他的数据结构更加高效。究其根本,数据结构其实是对现实世界的抽象。
  • 文本分类的基本思想和朴素贝叶斯算法原理
  • 掌握贪心算法的基本思想和解决问题的基本步骤,认识贪心算法和动态规划的联系与区别,对比解决同一问题的两种算法设计策略的时间复杂性。 二、实验要求 用c++语言实现用贪心算法解决汽车加油问题,分析时间复杂性,...
  • 题目描述 有 n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请找出这 n个人排队的一种顺序,使得n个人的平均等待时间最小。 输入 两行。 第一行,一个整数n,表示排队的人数。(n<...
  • 在程序设计算法是独立于语言的,无论使用哪一种语言都可以使用这些算法,本文笔者将以Java语言为例介绍一些常用的算法思想。分类穷举算法思想递推算法思想递归算法思想分治算法思想概率算法思想穷举算法思想穷举...
  • 《算法设计与分析基础》是一本由Anany levitin著作,清华大学出版社出版的胶版纸图书,本书定价:49.00元,页数:409,特精心从...●了解一些常用的算法设计思想......实战性不强,主要是算法的启蒙和了解一些领域话...
  • 算法设计与分析

    2020-12-21 05:37:09
    强调 算法 与 数据结构 之间密不可分的联系,因而强调融数据类型与定义在该类型上的运算于一体的抽象数据类型,为面向对象的程序设计方法奠定基础,体现计算机科学方法论的理论、抽象和设计三个过程,知识面较宽,且...
  • 算法思想无处不在,在计算机科学和其他领域中的体现都很明显。因特网路由标准的一些 主要变化,可以看成是人们对一种最短路径算法的不足和另一种算法的相对优势的争论。生物学家用于表示基因和基因组之间相似性的...
  • 算法思路 先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大 于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行 检查。若安全,则分配;若不安全,则拒绝申请,恢复到原来...
  • 1 枚举算法基本思想 枚举算法,也称之为穷举算法,就是按照问题本身的性质,一 一列举出该问题所有可能的解,并在列举的过程中,逐一检验每个可能解是否是问题的真正解。若是则采纳这个解;否则抛弃它。 注意: ...
  • 算法设计与分析常见习题及详解

    千次阅读 2021-01-11 21:54:02
    无论在以后找工作还是面试中,都离不开算法设计与分析。本博文总结了相关算法设计的题目,旨在帮助加深对贪心算法、动态规划、回溯等算法的理解。
  • 二分 二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。 二分查找很好写,却很难写对,据统计只有10%的程序员可以写...
  • 2016年第2学期实验班级:学生姓名:学 号:指导老师:信息工程学院实验项目名称:子集和问题的回溯算法实验日期:2016年 6月 1 日实验类型: 验证性 □设计性实验目的1、掌握回溯法解题的基本思想;2、掌握回溯算法...
  • 算法设计方法的基本思想及其适用特征——分治法、动态规划法、贪心法、回溯法、分支限界法。
  • 算法1[单选题]以下算法设计基本方法中基本思想不属于归纳法的是( )A.递推法B.递归法C.减半递推技术D.回溯法参考答案:D2[单选题]算法的有穷性是指( )。参考答案:A参考解析:算法的有穷性是指算法必须能在有限的...
  • 1)用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、 算法实现 7、程序调试 8、结果整理文档编制(2)算法定义:算法是指在解决问题时,按照某种机械步骤一定可以...
  • 算法分析与设计中的五大常用算法一、分治算法1. 基本概念2. 基本思想及策略3. 分治法适用的情况4. 分治法的基本步骤5. 分治法求解的一些经典问题二、 动态规划算法1. 基本概念2. 基本思想与策略3. 适用的情况4. 求解...
  • “自顶向下”的循环算法设计方法 自顶向下的设计方法是从全局走向局部、从策略走向详尽的设计方法。自顶向下是系统分解和细化的过程。 首先,根据题意,总体规划设计算法的主要组成或步骤。 其次,分别对各
  • 蛮力法的设计思想为:遍历,也就是说依次遍历集中的所有元素直到找到符合要求的元素。比如说,要用蛮力法在数组中寻找值为x的元素,那么就需要从数组的第一个元素开始,依次遍历数组中的元素直到找到值为x的元素或...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 300,261
精华内容 120,104
关键字:

算法设计思想