精华内容
下载资源
问答
  • 算法设计分析题库三

    千次阅读 多人点赞 2020-07-04 08:35:21
    1、单选 二分搜索算法是利用( C)实现的算法。 A回溯法 B动态规划法 C分治策略 D... 4、判断 出于“平衡子问题”的思想,通常分治法在分解原问题时,形成若干子问题,这些子问题的规模都大致相同。( A) A√ B×

    算法设计分析题库三

      大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客

    本文原创为亓官劼,请大家支持原创,部分平台一直在盗取博主的文章!!!

    博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客


    在这里插入图片描述


    选择题

    1、单选 二分搜索算法是利用( C)实现的算法。
    A回溯法 B动态规划法 C分治策略 D贪心法
    2、单选 实现合并排序利用的算法是( B)。
    A贪心法 B分治策略 C回溯法 D动态规划法

    3、单选 分治法的思想是( D )。
    A将小问题合并成大问题 B随机产生解
    C 用树的方式解决 D将大问题分解成小问题
    4、判断 出于“平衡子问题”的思想,通常分治法在分解原问题时,形成若干子问题,这些子问题的规模都大致相同。( A)

    A√ B×

    展开全文
  • 平衡子问题算法应用1. [50. Pow(x, n)](https://leetcode-cn.com/problems/powx-n/)2. [53. 最大子段和](https://leetcode-cn.com/problems/maximum-subarray/)3. [169. 多数元素]...

    分而治之好——算法复习I 分治算法

    分治算法介绍

    1. 设计思想

    分治法将一个难以解决的大问题划分为一些规模较小的子问题,分别求解各个子问题,再合并子问题得到原问题的解。

    2. 算法步骤

    • 划分:将规模为nn的原问题划分为kk个(通常k=2k=2)规模较小、相互独立的子问题。
    • 求解子问题:由于子问题的解法与原问题通常是相同的,可以用递归或循环求解子问题。
    • 合并:将子问题的解合并起来。

    3. 平衡子问题

    • 最好使子问题的规模大致相同。
    • 各子问题之间相互独立。

    算法应用

    1. 50. Pow(x, n)

    • 题目描述

      实现 pow(x, n),即计算 xn 次幂函数。

      示例 1:

      输入: 2.00000, 10
      输出: 1024.00000
      

      示例 2:

      输入: 2.10000, 3
      输出: 9.26100
      

      示例 3:

      输入: 2.00000, -2
      输出: 0.25000
      解释: 2-2 = 1/22 = 1/4 = 0.25
      

      说明:

      -100.0 < x < 100.0
      n是 32 位有符号整数,其数值范围是$[−2^{31}, 2^{31} − 1] $。

    • 解题思路

      1. 划分:不断对nn除以2,并更新nn值,直到n=0n=0
      2. 求解子问题:递归求解。
    • 通过代码

      class Solution {
          public double myPow(double x, int n) {
              if(n == 0) { 
                  return 1;
              }
              if(n == 1) { 
                  return x;
              }
              if(n == -1) { 
                  return 1 / x;
              }
              // 求解子问题
              double x1 = myPow(x, n / 2);
              double x2 = myPow(x, n % 2);
      
              return x1 * x1 * x2;
          }
      }
      

    这道题用到的是减治的思想,如果n=1n=1n=1n=-1n=0n=0,可以直接返回。nn取其他值可以直接将子问题的规模减半。

    减治的时间复杂度是O(log2n)O(log_2n),分治的时间复杂度O(n)O(n),相较于暴解没有提升。

    2. 53. 最大子段和

    • 题目描述

      给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

      示例:

      输入: [-2,1,-3,4,-1,2,1,-5,4]
      输出: 6
      解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。解题思路
      
    • 解题思路

      1. 划分:这里同样采用二分。二分法将数组分为左右两部分,其中,最大子段和可能出现在左半部分或右半部分,也可能横跨两个子序列。
      2. 求解子问题:对于出现再左半部分或右半部分的情况,可以递归求解子问题。如果出现在中间,则以划分位置为起始位置,向左和向右求解最大子段和,然后相加。
      3. 合并:三种情况中取最大者为最大子段和。
    • 通过代码

      class Solution {
          public int maxSubArray(int[] nums) {
              int len = nums.length;
              int left = 0, right = len - 1;
              int sum = subMaxSubArray(nums, left, right);
              return sum;
          }
      
          public int subMaxSubArray(int[] nums, int left, int right) {
              if(left == right) return nums[left];
              int sum = 0, leftSum = 0, rightSum = 0, midSum = 0;
              int mid = (left + right) / 2;
              leftSum = subMaxSubArray(nums, left, mid); // 递归求解子问题
              rightSum = subMaxSubArray(nums, mid + 1, right);
              // 求解第三种情况
              int s1 = -0xffff, lefts = 0;
              for(int i = mid; i >= 0; --i) {
                  lefts = lefts + nums[i];
                  if(lefts > s1) {
                      s1 = lefts;
                  }
              }
              int s2 = -0xffff, rights = 0;
              for(int i = mid + 1; i <= right; ++i) {
                  rights = rights + nums[i];
                  if(rights > s2) {
                      s2 = rights;
                  }
              }
              midSum = s1 + s2;
              sum = leftSum > rightSum ? leftSum:rightSum;
              sum = sum > midSum ? sum:midSum;
              return sum;
          }
      }
      

    3. 169. 多数元素

    • 题目描述

      给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

      你可以假设数组是非空的,并且给定的数组总是存在多数元素。

      示例 1:

      输入: [3,2,3]
      输出: 3
      

      示例 2:

      输入: [2,2,1,1,1,2,2]
      输出: 2
      
    • 解题思路

      • 先排序,然后直接取中间值。
      • 快排切分,类比于“求第k大元素”
    • 通过代码

      class Solution {
          public int majorityElement(int[] nums) {
              int len = nums.length;
              Arrays.sort(nums, 0, len);
              return nums[len / 2];
          }
      }
      
      class Solution {
          public int majorityElement(int[] nums) {
              return quickSearch(nums, 0, nums.length - 1, nums.length / 2);
          }
      
          private int quickSearch(int[] nums, int lo, int hi, int k) {
              int j = partition(nums, lo, hi);
              if (j == k) {
                  return nums[j];
              }
              return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
          }
      
          private int partition(int[] nums, int lo, int hi) {
              int v = nums[lo];
              int i = lo, j = hi + 1;
              while (true) {
                  while (++i <= hi && nums[i] < v);
                  while (--j >= lo && nums[j] > v);
                  if (i >= j) {
                      break;
                  }
                  int t = nums[j];
                  nums[j] = nums[i];
                  nums[i] = t;
              }
              nums[lo] = nums[j];
              nums[j] = v;
              return j;
          }
      }
      
    展开全文
  • 将集合S分成两个子集S1和S2,根据平衡子问题原则,每个子集中的点数大致都为n/2。这样分治后,最近点对将会出现三种情况:在S1中,在S2中或者最近点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况,第三种...

    1.问题

    用分治法解决最近对问题。

    2.解析

    在利用分治法思想解决此问题时,首先考虑将最近对问题进行分治,设计其分治策略。将集合S分成两个子集S1和S2,根据平衡子问题原则,每个子集中的点数大致都为n/2。这样分治后,最近点对将会出现三种情况:在S1中,在S2中或者最近点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况,第三种方法另外分析。求解出三类子情况后,再合并三类情况,比较分析后输出三者中最小的距离。
    分解:
    1、对所有的点按照x坐标(或者y)从小到大排序(排序方法时间复杂度 O(nlogn))。
    2、根据下标进行分割,使得点集分为两个集合。
    解决:
    1、递归的寻找两个集合中的最近点对。
    2、取两个集合最近点对中的最小值。
    合并:
    1、最近距离不一定存在于两个集合中,可能一个点在集合A,一个点在集合B,而这两点间距离小于最小值。

    3.设计

    EfficientClosestPair(P,Q)
    if n≤3
    	返回由蛮力算法求出的最小距离
    else
    	将P的前⌈n/2 ⌉个点复制到P1
    	将Q的前⌈n/2 ⌉个点复制到Q1
    	将P中余下的⌊n/2 ⌋个点复制到Pr 
    	将Q中余下的⌊n/2 ⌋个点复制到Qr
    
    	d1←EfficientClosestPair(P1,Q1)
    	dr←EfficientClosestPair(Pr,Qr)
    	d←min{d1,dr}
    	m←P [⌈n/2-1].x
    	将Q中所有|x-m|<d的点复制到数组S[0..num-1]
    	dminsq ←d2
    	for i ← 0 to num - 2 do
    		k←i+1
    		while  k≤ num-1  and  (S[k].y-S[i].y)2< dminsq
    			dminsq←min((S[k].x-S[i].x)2+(S[k].y-S[i].y)2, dminsq)
    			k←k+1
    return  sqrt(dminsq)
    

    4.分析

    当k=2时,T(n)=1;
    当k>2时,T(n)=2T(n/2)+n;
    T(n)=O(n log2 n)

    5.源码

    https://github.com/Hyacincy/-/blob/main/closestPair.cpp

    展开全文
  • (事实上这种使子问题大致相同的做法是一种自平衡子问题思想)。 定义: 分治法的思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。 解决方法: 我们可以递归的解决这些子...

    通俗的来说:就是把一个问题分解成为大小相同的k个子问题是比较不错的。(事实上这种使子问题大致相同的做法是一种自平衡子问题的思想)。

    定义:

    分治法的思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。

    解决方法:

    我们可以递归的解决这些子问题,然后将这些小的子问题和原问题合并,进而各个击破,达到解决整个原问题的目的!
    分治算法分解为多少个子问题比较的合适呢?
    其实这个问题前人也是经过了很多的经验才发现了在使用分治法设计算法时,最好使子问题的规模大致相同,即讲一个子问题分解为大小相同的k个子问题比较的合适。这种使子问题的 规模大致相同的做法是一种自平衡的思想。并且使用分治法的算法一般是递归的算法。

    分治法比较常见的一种使用方式(二分搜索算法)

    下面是我总结的二分题目链接:

    2020 CCPC Wannafly Winter Camp Day1 F 乘法

    Codeforces 1323 D. Present

    Codeforces 1238 B. Kill 'Em All

    Codeforces 1324 D. Pair of Topics

    Codeforces D. Xenia and Colorful Gems

    展开全文
  • 算法4_分治

    2020-05-10 18:55:30
    这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题思想,它几乎总是比子问题规模不等的做法要好。 适用条件 分治法所能解决的问题一般具有以下几个特征: 1.该问题的规模缩小到一定的程度就可以...
  • 至于什么是AVL树和AVL树的一些概念问题在这里就不多说了,下面是我写的代码,里面的注释非常详细地说明了实现的思想和方法。 因为在操作时真正需要的是子树高度的差,所以这里采用-1,0,1来表示左子树和右树的...
  • 合并排序算法

    2021-04-30 21:22:59
    (2)求解子问题:用合并排序法分别对两个子序列递归地进行排序。 (3)合并:将排好序的有序子序列进行合并,得到符合要求的有序序列。 例如:设待排序序列A=<8,3,2,9,7,1,5,4>,采用合并排序算法对序列A进行...
  • 递归算法的执行过程分两个阶段:_________________递推和回归 ...将一个问题分成大小相等的k个子问题的处理方法是行之有效的,这是什么思想________________________平衡(balancing)子问题思想 快速排序的...
  • 算法——分治法讲解

    2016-01-20 17:49:18
    这种做法是出自一种平衡子问题的启发思想。 然后这么多个规模大小一样的子问题就可以通过递归进行求解。下面举个小例子:例如:现在要求3的4次幂。 蛮力法的思想:3*3*3*3 分治法的思想: 可能说起来比较抽象。...
  • 如果右树部位空,则右树上所有的节点均小于它根节点的值 任意节点的左右子树均为二叉查找树 红黑树 特殊的 二叉查找树 具有二叉查找树的所有的特性 每个节点都是黑色或者红色的,根节点是黑色 叶子节点为空的...
  • baggingbagging算是很基础的集成学习的方法,他的提出是为了增强分类器效果,但是在处理不平衡问题上却有很好的效果。模型如下:如上图,原始数据集通过T次随机采样,得到T个与原始数据集相同大小的数据集,分别...
  • 1. 平衡子问题:最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题(通常k=2),这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题的思想,它几乎总是比子问题规模不等...
  • 也就是将一个问题划分成大小相等的k个子问题(通常k=2),这种使子问题规模大致相等的做法是出自一种平衡子问题思想,它几乎总是比子问题规模不等的做法要好。 2. 独立子问题:各子问题之间相互独立,这涉及到...
  • 平衡粒子群算法的全局寻优能力和局部寻优能力,提高粒子群算法的求解精度和效率,本文在新种群寻优过程中引入具有强收敛能力Hooke-Jeeves搜索法,提出了IMPSO算法。雅文网www.lunwendingzhi.com,并用IMPSO算法对...
  • 1.分治算法的主要思想:将原问题划分成若干的子问题,分而治之,最后将若干个子问题的解合并得到原问题的解。常常含有二分、递归的方法在里面 2.分析分治算法的工具——递归方程; 3.每次划分的时候子问题的规模尽量...
  • 算法笔记 胡凡 曾磊

    2018-10-16 17:38:13
    426 11.2 最大连续序列和 429 11.3 最长不下降序列(LIS) 432 11.4 最长公共序列(LCS) 434 11.5 最长回文子串 436 11.6 DAG最长路 439 11.7 背包问题 442 11.7.1 多阶段动态规划问题 442 11.7.2 01背包问题...
  • 目录什么是递归与分治策略?...分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题(由于“平衡子问题”的思想,子问题规模应该都要大致相同),这些子问题相互独立且与原问题相同。递归地解这些子问题,
  • 就个人而言,本身我觉得这个...(事实上这种使子问题大致相同的做法是一种自平衡子问题思想)。 定义:分治法的思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。 解...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    平衡二叉树 红黑树 多叉树 B树 查找节点 插入节点 删除节点 左旋 B+树 查找节点 插入节点 删除节点 图 分类 有向图 无向图 表示方法 邻接矩阵 邻接表 ...
  • 递归与分治1、 分治法的基本思想“分”:将问题分解为规模更小的子问题“治”:求解规模较小的子问题“合”:将已解决的子问题合并,得出原问题的解2、 应用分治法求解的2个前提最优子结构性质,平衡子问题3、 ...
  • 如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。...
  • 本书的特色有二,旨在提高读者的问题求解能力,使读者能够理解算法设计的过程和思想:一是强调算法设计的创造性过程,注重算法设计背后的创造性思想,而不拘泥于某个具体算法的详细讨论;二是将算法设计类比于定理...
  • 本书内容包括:C/C++快速入门、入门模拟、算法初步、数学问题、C++标准模板库(STL)、数据结构专题(两章)、搜索专题、图算法专题、动态规划专题、字符串专题、专题扩展。书中每小节的末尾均印有二维码,用以实时...
  • 算法笔记上机训练实战指南》是《算法笔记》的配套习题集,内容按照《算法笔记》的章节顺序进行编排,其中整理归类了PAT甲级、乙级共150多道题的详细题解,大部分题解均编有题意、样例解释、思路、注意点、参考代码...
  • 生成高度平衡二叉搜索树一、算法描述二、JAVA 实现总结 一、算法描述        给定一个数组,如何以数组中的元素生成二叉搜索树?要解决这个问题首先我们需要理解二叉搜索树的定义: 1.节点的左...
  • 剑指offer-平衡二叉树

    2018-02-28 10:26:10
    这是一道关于二叉树经典套路问题,因为二叉树本身就是用递归定义的,所以关于二叉树的一些算法题大部分可用递归解。大致思路便是:根据题意,写一个递归函数,函数内部对左子树递归,收集信息,对右树递归,收集...
  • 最近点对问题问题描述算法思路穷举法分治法伪...将集合S分成两个子集S1和S2,根据平衡子问题原则,每个子集中的点数大致都为n/2。这样分治后,最近点对将会出现三种情况:在S1中,在S2中或者最近点对分别在集合S1和S2中
  • 一开始就求出根节点 root 的左子树高度 DLeft 与右树高度 RLeft,如果高度查大于 1,那么就不是平衡二叉树; 根节点 root 的 DLeft 与 DRight 没问题,不能证明每一棵子树的最大高度都没有...
  • bagging算法是很基础的集成学习的方法,他的提出是为了增强分类器效果,但是在处理不平衡问题上却有很好的效果。 如上图,原始数据集通过T次随机采样,得到T个与原始数据集相同大小的数据集,分别训练得到T个弱...

空空如也

空空如也

1 2 3 4
收藏数 66
精华内容 26
关键字:

平衡子问题思想算法