
算法
OneDeveloper
当你无所事事的时候,就得好好想想还缺少什么!!!
展开
-
【基础算法】直接插入排序法
引用自:https://blog.csdn.net/dd864140130/article/details/50845945插入排序的基本思想是: 将一个待排序的记录,按照其关键字的大小将其插入到前边已经排好序的子序列的适当的位置,直到全部插入完毕。这就像我们在玩扑克牌时,将每一张拍插入到其他已经有序的牌中适当的位置。在计算及中,为了给要插入的元素腾出位置,需要将其余所有元素在插入位置之前都...原创 2019-02-21 23:58:33 · 2649 阅读 · 0 评论 -
【LeetCode】135. 分糖果
参考链接:leetcode 135. Candy 分糖果 + 很经典的贪心算法根据题意,孩子 X 分配的糖果与第 X-1 和 X+1 个孩子的评分都有关系,即与前后孩子的评分有关系。因此可以分为两个阶段来处理。第一阶段,对于孩子 i,只去比较他与前一个孩子的比分,来确定自己需要分配的糖果数量。第二阶段,对于孩子 i,再去比较他与后一个孩子的比分,再来补充自己分配的糖果数量。public...原创 2019-08-26 21:09:29 · 246 阅读 · 0 评论 -
【LeetCode】55. 跳跃游戏
解法 1从左到右遍历数组,假设当 index = x1 时,nums[x1] = 0,则继续向右遍历,直接遇到不为 0 的元素,假设此时 index = x2。且在遍历的时候,记录 index 在 x1 之前的元素,有 maxIndex = index+nums[index](maxIndex 表示下标为 index 对应的元素值所能跨到最远位置)。如果 maxIndex < x2,...原创 2019-08-22 22:45:53 · 229 阅读 · 0 评论 -
【LeetCode】134. 加油站
(注意题目给出的条件)1. 暴力破解如果对于起点 index 有 gas[index] - cost[index] < 0,则 index 肯定无法作为起点。因此肯定是从 start = x && gas[x] - cost[x] >= 0 的点开始,该点才有可能是答案。为什么说是有可能,因为还要计算该点之后的所有点是否符合要求。否则就要再换一个起点继续去...原创 2019-08-24 11:32:05 · 881 阅读 · 0 评论 -
【剑指 2】面试题 44:数字序列中某一位的数字
题目:数字以 0123456789101112131415... 的格式序列化到一个字符序列中。在这个序列中,第 5 位(从 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。写出一个函数,求任意第 n 位对应的数字。解题思路:题目中的序列,存在一个规律:即依次由一位的数字,两位的数字,三位的数字,X 位的数字,对应的数字序列从小到大,拼接而成。第 0 至第 10 位由...原创 2019-06-03 23:41:09 · 316 阅读 · 0 评论 -
【剑指 2】面试题 43:1~n 整数中 1 出现的次数
题目:输入一个整数 n,求 1~n 这 n 个整数的十进制表示中 1 出现的次数。例如,输入 12,1~12 这些整数中包含 1 的数字有 1、10、11 和 12,1 一共出现了 5 此。对于 X ∈ [1, 9],1~n 整数中 X 出现的次数在算法一样。(0 的比较特殊,不过大致思想类似)。解题思路:分别以 12493、12593、12693 为例,计算数字 5 出现的次数。其中,...原创 2019-06-05 21:31:38 · 373 阅读 · 0 评论 -
【基础算法】计数排序
具体的讲解参见:理解计数排序算法的原理和实现主要的原理,就是用一个辅助数组 b,对于目标数组 a,对于 a 中的每个元素 a[i],将其出现的次数映射到 b[j] 中,其中有 j = a[i]。然后需要注意的三个点就是:1、尽量的节省空间,假设有数组 10, 11, 20, 30,辅助数组的大小没必要为 30,可以根据数组中的最大值与最小值来进行优化。2、要支持负数的排序3、具有稳定性,...原创 2019-03-11 20:32:41 · 810 阅读 · 0 评论 -
【基础算法】冒泡排序法
public void sort(int[] a) { if (a == null || a.length == 0) return; // 外层的循环代表遍历的次数 for (int i = 0; i &lt; a.length - 1; i++) { boolean flag = true; // 内层的循环是为了实现相邻两元素的交换...原创 2019-02-20 22:13:07 · 753 阅读 · 0 评论 -
【基础算法】堆排序
具体的演示过程可以参考:https://www.cnblogs.com/chengxiao/p/6129630.html// 最大堆排序,可以得到递增序列public void heapSort(int[] a) { if (a == null || a.length == 0) { return; } // 从后往前遍历所有元素,构建出最大堆 ...原创 2019-03-02 00:07:46 · 485 阅读 · 0 评论 -
【基础算法】快速排序
采用交换法的实现:// 递归实现public void digui(int[] a, int left, int right) { if (left >= right) return; int pivot = left; int l = left + 1; int r = right; // 注意三个地方为 l <= r(而不是 l <...原创 2019-02-25 23:36:03 · 639 阅读 · 0 评论 -
【基础算法】简答选择排序法
选择排序法,核心思想就是,对于数组 A,假设其长度为 len,则第一次遍历,找到 [0,len-1] 中最小的那一个放在 A[0] 的位置,第二次遍历,找到 [1,len-1] 中最小的那一个放在 A[1] 的位置…如此循环,直到整个数组有序为止。该排序是一种不稳定的排序。public void sort(int[] a) { if (a == null || a.length =...原创 2019-02-19 22:20:40 · 380 阅读 · 0 评论 -
【基础算法】二分查找法
二分查找法的前提就是针对于有序的序列,基于分治的思想,提高查询的效率。参考:https://zh.wikipedia.org/wiki/二分搜索算法迭代实现:public static int binarySearch(int[] arr, int aim) { if (arr == null || arr.length == 0) return -1; int left =...原创 2019-02-18 21:45:55 · 471 阅读 · 0 评论 -
【基础算法】归并排序
可以参考:35. 排序算法(8):归并排序的迭代实现 的图解这里在实现上,把递归与迭代的都贴出来:首先是递归的实现,比较简单明了public void digui(int[] a, int left, int right) { if (left >= right) { return; } int mid = (right + left) / 2...原创 2019-02-27 21:52:50 · 245 阅读 · 0 评论 -
【LeetCode】115. 不同的子序列
规定 :(1)S(0, i-1) 表示 S 的前 i 个字符组成的字符串,因此基数为 0,所以最后一个字符即第 i-1 个。(2)S[i-1] 即表示 S 的第 i-1 个字符。使用动态规划来处理,则有 dp[i][j] 代表 S(0, i-1) 与 T(0, j-1) 对应的解。对于 dp[i][j] 有:当 S[i-1] 与 T[j-1] 不相等时,则 S 的第 i-1 个字...原创 2019-08-28 11:54:22 · 310 阅读 · 0 评论