在讲插值查找前，我们先来看一个二分查找的场景。tip：建议先搞懂二分查找再来看本篇。关于二分查找请看 数据结构与算法——查找算法-二分查找先来看一个场景 /*** 先来看一个场景，在二分查找中查找需要几次*/@Testpublic void binary2Test() {int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1234, 1234};int findVal = 1;Integer result = binary(arr, 0, arr.length - 1, findVal);System.out.println("查找值 " + findVal...
1、八皇后问题//8皇后问题--回溯算法publicclass Recall {int[] result = newint[8];//全局或成员变量，下标表示行，值表示queue存储在哪一列publicstaticvoid main(String[] args) {Recall recall = new Recall();recall.cal8queues(0);}publicvoid cal8queues(int row) {//调用方式：cal8queues(0)if(row == 8) {//8个棋子都放置好了，打印结果 printQueues(result);return;//8行棋子都放好了，已经没法再往下递归了，...
ahalei · 更新于 2018-11-28 11:00:43排序总结：小哼买书之前讲了三种常用的经典排序。排序算法还有很多，例如选择排序、计数排序、基数排序、插入排序、归并排序和堆排序等等。堆排序是基于二叉树的排序，以后再说吧。先分享一个超酷的排序算法的视频。再来看一个具体的例子《小哼买书》来看看三个排序在应用上的区别和局限性。 小哼的学校要建立一个图书角，老师派小哼去找一些同学做调查，看看同学们都喜欢读哪些书。小哼让每个...
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.一、问题描述：输入一个整数数组，求数组中连续的子数组使其和最大。二、解题方法：//从左至右扫描数组，如果前面一段连续子数组的和小于0，则置为0，重新从下个元素开始累加
int maxSubArray(vect...
一、冒泡排序（Bubble Sort）public class BubbleSort {public static void main(String[] args) {int[] arr = {3, 4, 2, 9, 10, 15, 11, 0, 1};System.out.println(Arrays.toString(bubbleSort(arr)));}public static int[] bubbleSort(int[] arr){for (int i = 0; i < arr.length - 1; i++) {for(int j = 0; j < arr.length - 1 - i; j++){if(arr[j] > arr[j + 1]){int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}...
历届试题 九宫重排
时间限制：1.0s 内存限制：256.0MB
问题描述如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。我们把第一个图的局面记为：12345678.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为句点。本题目的任务是已知九宫的初态和终态，求最少经过多少步的移...
概述在数论中，水仙花数（Narcissistic number），也被称为超完全数字不变数（pluperfect digital invariant, PPDI）、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数（Armstrong number） ，用来描述一个N位非负整数，其各位数字的N次方和等于该数本身。举例 例如153、370、371及407就是三位超完全数字不变数，其各个数之立方和等于该数： 153 = 13 + 53 + 33。370 = 33 + 73 + 03。371 = 33 + 73 + 13。407 = 43 + 03 + 73。Java算法...
首先链表分三种：单链表，双链表，循环单链表写个例子说明列表的创建和遍历：publicclassLinkList{
privateNode head;privateNode current;privatevoid add(int data){
if(head ==null){head =newNode(data,null);current = head;
}else{
//创建新的结点
Node node =newNode(data,null);
//新创建的节点和列表进行关联
current.next = node;
//移动当前链表的索引位置
current = node;
}
}privatevoid print(Node node){
if(node ...
思路：这是ST表模板。遇到一道indeed笔试题需要用这个算法，顺便学习一下。那道题是说给定一个一维数组和一些查询[Li, Ri]，要求计算[Li, Ri]区间内子段和的绝对值的最大值。解法是使用ST表计算所求区间内最大前缀和 - 最小前缀和即可。实现： 1 #include <bits/stdc++.h>2usingnamespace std;3constint N = 1000005;4int a[N], st[N][20];5int log2(int x)6{7int res = -1;8while (x)9 {
10 x >>= 1;
11 res++...
希尔排序的实质就是分组插入排序，该方法又称为缩小增量排序。基本思想为：先将整个带排元素序列分割成若干个子序列（由相隔某个增量的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。因此希尔排序在时间效率上比前两种方法有较大提高。示例代码上传至：...
本文的基础是红黑树 算法导论–红黑树通过在基础的数据结构中添加一些附加信息，来扩张一种标准的数据结构，然后编写新的操作来支持所需要的应用。下面是介绍在红黑树的基础上扩张的数据结构。1.动态顺序统计动态顺序统计可以在O(lgn)时间内确定任何的顺序统计量(即在n个元素的集合中，能在O(lgn)的时间内确定第i小的元素)，同时也可以在O(lgn)的时间内计算一个元素的秩(即它在中序遍历下的位置顺序)。1 添加附加信息结点x中加入...
与归并排序一样，快速排序使用也使用了分治的思想。下面是对一个典型的子数组A[p,...,r]进行快速排序的三步分治过程： 分解：数组A[p,...,r]被划分成两个（可能为空）子数组A[P,...,q-1]和A[q+1,...,r]，使得A[p,...,q-1]中每个元素都小于等于A[q]，而A[q]也小于等于A[q+1,...,r]中的每个元素。其中，计算下标q也是划分过程的一部分。 解决：通过递归调用快速排序，对子数组啊A[P,...,q-1]和A[q+1,...,r]进行排序。 合并：...
问题描述有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。输入格式第一行2个整数n，m。接下来一行n个整数表示n个格子的初始权值。接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。输出...
数据结构可以归类两大类型：线性结构与非线性结构，本文的内容关于非线性结构：树的基本定义及相关算法。关于树的一些基本概念定义可参考：维基百科
树的ADT模型：
根据树的定义，每个节点的后代均构成一棵树树，称为子树。因此从数据类型来讲，树、子树、树节点是等同地位，可将其看作为一个节点，用通类：Tree表示。如下图所示：
图：Tree ADT模型示意图
可采用“父亲-儿子-兄弟”模型来表示树的ADT。如图所示，除数据项外，分...
这篇博客主要介绍LRU LFU 算法，因为在Mybatis的缓存中会用到，所以放到这个系列中了。此外，这是我翻译的一篇文章，觉得原文已经写的很好了，所以就直接翻译一下，留作知识整理。英文原文出处如下：https://xuri.me/2016/08/13/lru-and-lfu-cache-algorithms.html鼓励大家多读读英文的资料。好处不多说。自己体会。在此声明，文章只是翻译了一个大体意思，有些词汇翻译的不准确，不要砸我。 最少最近使用(LRU)丢弃掉最近期间最少使...
