自猿其说动态规划 最大连续乘积子串
最大连续乘积子串 题目描述 给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是...
数据结构与算法 第4页
自猿其说记录站长成长点滴，将工作所学所思所看分享到这里，介绍基础数据结构，常用算法，进阶算法，编程经验，常见面试算法，希望您能通过本站有所成长。
动态规划
本章导读 学习一个算法，可分为3个步骤：首先了解算法本身解决什么问题，然后学习它的解决策略，最后了解某些相似算法之间的联系。例如图算法中， 广搜是一层一层往外遍历，寻找最短路径，其策略是采取队列的方法。 最小生成树是最小代价连接所有点，其策...
查找匹配 出现次数超过一半的数字
出现次数超过一半的数字 题目描述 题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 分析与解法 一个数组中有很多数，现在我们要找出其中那个出现次数超过总数一半的数字，怎么找呢？大凡当我们碰到某一个杂乱无序的东西时，我们人...
查找匹配 有序数组的查找
有序数组的查找 题目描述 给定一个有序的数组，查找某个数是否在数组中，请编程实现。 分析与解法 一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？ 二分查找可以解决（预排序数组的查...
树
本章导读 想要更好地理解红黑树，可以先理解二叉查找树和2-3树。为何呢？首先，二叉查找树中的结点是2-结点（一个键两条链），引入3-结点（两个键三条链），即成2-3树；然后将2-3树中3-结点分解，即成红黑树，故结合二叉查找树易查找和2-3...
数组 跳台阶
跳台阶问题 题目描述 一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 分析与解法 解法一 首先考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的...
数组 奇偶排序
#奇偶调序 题目描述 输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。 分析与解法 最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个...
数组 最大连续子数组和
最大连续子数组和 题目描述 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值，要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7...
数组 寻找和为定值的两个数
寻找和为定值的两个数 题目描述 输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15...
数组 寻找和为定值的多个数
寻找和为定值的多个数 题目描述 输入两个整数n和sum，从数列1，2，3…….n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。 分析与解法 解法一 注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一...
