搜索[国密算法]结果-低调大师优秀个人博客

精选列表

搜索[国密算法]，共10000篇文章

数据结构与算法之约瑟夫问题

约瑟夫问题介绍：据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。编程描述: 有N个孩子手拉手围成一圈，从第M个孩子开始报数，报到第K个孩子出队，然后从下一个孩子继续开始报数，问：所有孩子的出队顺序？如下图：约瑟夫问题的数据结构引出：图 1-1：问：用什么数据结构来处理这个问题比较合适呢？我们不妨将图1-1稍作处理，如下图1-2：如果我们将每一个小人看人一个node节点，每一个节点都有一个指针指向下一个节点，我们很容易的就想到一种数据结构便是单向链表，如果我们将该单项链表的尾和首相连，将尾部指向首部便是图1-1了，便很适合解决该约瑟夫问题，于是我们可以使用单向环形链表数据结构来模拟解决该问题。数据结构的实现基础类如下：模拟孩子的类Child: class Child { private int no; private Child next; public Child(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Child getNext() { return next; } public void setNext(Child next) { this.next = next; } } 模拟约瑟夫环的类CircleSingleLinkedList: class CircleSingleLinkedList { private Child head; public void init(int n) { //todo } public void show() { //todo } public void delete(int no) { //todo } } CircleSingleLinkedList的方法实现：初始化创建带有N个节点的约瑟夫环：分析：我们只要做到将上一个节点的next指向下一个节点，最后一个节点的next指向第一个即可 public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { child = new Child(1); child.setNext(child); } else { child = new Child(1); child.setNext(child); cur = child; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(child); } } } 2.打印约瑟夫环：分析：从头结点遍历每一个节点，当节点的getNext()==head时，便遍历结束了，相当于遍历到了最后一个 public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); } 3.为约瑟夫环增加一个节点到最后:分析：从头结点遍历到最后，将最后一个节点的next指向增加的节点，将增加的节点next指向头结点head即可 public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur.setNext(child); child.setNext(head); } 4.删除一个约瑟夫环的节点：遍历约瑟夫环，找到待删除节点的上一个节点，将上一个节点的next指向待删除节点的next即可，但是如果是删除的头结点，则需要将头结点的下一个节点指定为头结点 public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } } 至此约瑟夫环的数据结构及基础方法如下： class CircleSingleLinkedList { private Child head; public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { head = new Child(1); head.setNext(head); } else { head = new Child(1); head.setNext(head); cur = head; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(head); } } } public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur.setNext(child); child.setNext(head); } public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); } public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } } } 在约瑟夫环数据结构上解决约瑟夫问题我们从beginNo个孩子开始报数，每一次报readNum个数，则如何进行出队呢？分析：从第beginNo个孩子作为游戏的开始，就相当于移动约瑟夫环的头结点，将第beginNo个节点作为头结点。我们需要一个辅助指针来进行出队，该指针初始指向尾节点。报数相当于移动头结点和辅助指针，头结点到出队的那一个节点，将辅助指针的next指向头结点的next便完成了出队。然后将辅助指针的next作为头结点即可，直到只剩下最后一个节点。及头结点和辅助指针指向的节点是同一个接点。 public void josephPop(int beginNo, int readNum) { if (head == null) { return; } Child helper = head; while (true) { if (helper.getNext() == head) { break; } helper = helper.getNext(); } for (int i = 1; i < beginNo; i++) { head = head.getNext(); helper = helper.getNext(); } while (head != helper) { for (int i = 0; i < readNum - 1; i++) { head = head.getNext(); helper = helper.getNext(); } System.out.println(head.getNo()); helper.setNext(head.getNext()); head = helper.getNext(); } System.out.println(helper.getNo()); } 至此约瑟夫环及约瑟夫问题模拟如下： class CircleSingleLinkedList { private Child head; public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { head = new Child(1); head.setNext(head); } else { head = new Child(1); head.setNext(head); cur = head; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(head); } } } public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在！！"); } cur.setNext(child); child.setNext(head); } public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); } public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } } public void josephPop(int beginNo, int readNum) { if (head == null) { return; } Child helper = head; while (true) { if (helper.getNext() == head) { break; } helper = helper.getNext(); } for (int i = 1; i < beginNo; i++) { head = head.getNext(); helper = helper.getNext(); } while (head != helper) { for (int i = 0; i < readNum - 1; i++) { head = head.getNext(); helper = helper.getNext(); } System.out.println(head.getNo()); helper.setNext(head.getNext()); head = helper.getNext(); } System.out.println(helper.getNo()); } } 测试创建一个5个节点的约瑟夫环，从第一个节点开始报数，每次报3个数，出队顺序如下： public static void main(String[] args) { CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.init(5); circleSingleLinkedList.josephPop(1, 3); } 出队顺序为：3 1 5 2 4

2019-09-10

初探|Zookeeper基础之Paxos算法详解（一）

对于 zk 理论的学习，最重要也是最难的知识点就是 Paxos 算法。所以我们首先学习 Paxos 算法。

2019-09-05

算法：二叉树代码示例

二叉树特点左节点值小于根节点值，右节点值大于根节点 public class BinaryTree { private Node root; @Data private static class Node { private int data; private Node left; private Node right; public Node(int data){ this.data = data; } } public Node find(int key){ Node current = root; while(current != null){ if(current.data > key){ current = current.left; } if(current.data < key){ current = current.right; } if(current.data == key){ return current; } } return null; } public boolean insert(int data){ Node newNode = new Node(data); if(root == null){ root = newNode; return true; }else{ Node current = root; Node parent = null; while (current != null){ parent = current; if(current.data > data){ current = current.left; if(current == null){ parent.left = newNode; return true; } } else{ current = current.right; if(current == null){ parent.right = newNode; return true; } } } } return false; } public Node findMax(){ Node current = root; while(current != null){ current = current.right; } return current; } public Node findMin(){ Node current = root; while (current != null) { current = current.left; } return current; } //删除没有子节点的节点 public boolean delete(int key){ Node current = root; Node parent = current; boolean isLeft = false; while (current.data != key){ parent = current; if(current.data > key){ isLeft = true; current = current.left; }else { isLeft = false; current = current.right; } if(current == null){ return false; } } if(current.left == null && current.right == null){ if(current == root){ root = null; } if(isLeft){ parent.left = null; }else{ parent.right = null; } return true; } return false; } }

2019-08-05

smart-socket内存管理：首次适应算法

比较常见的内存管理算法有以下几种：首次适应算法（First-Fit）从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。

2019-05-13

python实现顺序查找和哈希查找算法

顺序查找顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法，顺序查找是最简单的搜索算法，其实现如下： defsequential_search(items,item): foriinitems

2019-04-20

C++实用编程——随机生成迷宫算法

2.随机生成算法： void init_maze(void); //初始化迷宫 void gotoxy(int x, int y); //移动光标 void path_up(int *x, int *y

2018-12-31

OpenCV中MeanShift算法视频移动对象分析

MeanShift算法Mean Shift是一种聚类算法，在数据挖掘，图像提取，视频对象跟踪中都有应用。OpenCV在图像处理模块中使用均值迁移可以实现去噪、边缘保留滤波等操作。

2018-12-18

言简意赅了解十大常见AI算法

基本假设是条件独立性决策树 decision tree 多分类，回归是一种分类和回归算法。

2018-10-23

逻辑回归模型算法研究与案例分析

训练算法: 大部分时间将用于训练，训练的目的是为了找到最佳的分类回归系数。测试算法: 一旦训练步骤完成，分类将会很快。

2018-09-05

【算法导论】最大子数组——暴力求解

1. 暴力方法求解最大子数组问题：求出所有子数组的和并比较； 2. 伪代码 FIND-MAXIMUM-SUBARRAY(A) max = -∞ for i = 1 to A.length sum = 0 for j = i to A.length sum += A[j] if sum > max max = sum low = i high = j return (low, high, max) 3. 代码实现 java public class MaxArray { private static class Result { int low; int high; int sum; public Result(int low, int high, int sum) { this.low = low; this.high = high; this.sum = sum; } } static Result findMaximumSubarray(int[] A){ int max = Integer.MIN_VALUE; int low = 0; int high = 0; for (int i = 0; i < A.length; i++) { int sum = 0; for (int j = i; j < A.length; j++) { sum += A[j]; if (sum > max) { max = sum; low = i; high = j; } } } return new Result(low, high, max); } } python 之前用切片其实也是暴力求解 def find_maximum_subarray1(nums): max_sum = -float('inf') result = {} for i in range(len(nums)): total = 0 for j in range(i, len(nums)): print(j) total += nums[j] if total > max_sum: max_sum = total result["low"] = i result["high"] = j result["sum"] = max_sum return result C语言 typedef struct { int low; int high; int sum; } result; result find_maximum_subarray(int arr[], int len) { int max = -((unsigned)(~0) >> 1); int low, high, i, j; for (i = 0; i < len; i++) { int sum = 0; for(j = i; j < len; j++) { sum += arr[j]; if (sum > max) { max = sum; low = i; high = j; } } } result re; re.low = low; re.high = high; re.sum = max; return re; }

2018-09-02

Python数据结构与算法——顺序表

概念在程序中，经常需要将一组(通常为同一个类型的)数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等(例如，Python中的列表)。一组数据中包含的元素个数可能发生变化(可以增加或者删除元素)。对于元素增删改查的需求，最简单的解决办法就是将这一组元素当做一个序列，用元素序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。这样的一组序列元素的组织形式，即可抽象为线性表，一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一。根据线性表的实际存储方式，分为两种实现模型：顺序表：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示链表：将元素存放再通过链接构造起来的一系列存储块中顺序表的基本形式数据元素本身连续存储，每个元素所占的存储单元大小相同，元素的下标是其逻辑地址，而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址加上逻辑地址与存储单元大小的乘积计算而得即： L0c(i) = L0 + i * c 作图解释为下： 1_note_shunxubiao.png 32位操作系统中，一个整型占用4个字节(Byte)，因此列表my_list中四个整型占用字节数为16个字节，且每个元素所占用字节数相同所以访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1). 顺序表的基本形式的特殊形式如果元素的大小不统一，则须采用元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。此时公式中的 c 则不再是数据元素大小，而是存储一个链接地址所需的存储量。顺序表的结构不考虑用Python语言具体实现，真正实现数据表结构的时候，怎么构造数据 2_note_顺序表的结构.png 出了存储数据的数据区之外，往往还会加上表头信息表头信息即：上图中上面的部分下面部分为数据区 (连续的存储空间，内存的概念见后面的图解) 构造一个数据表的时候，首先要预估数据需要多少的空间，指明数据存储所需空间，即数据区。如上图中所示，即为8个数据。那么就要向计算机申请8个空间，在表头指明一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储去的容量和当前表中已有的元素个数两项。顺序表的两种基本实现方式一体式结构： 3_note_顺序表的两种实现方式一.png 一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象，这种结构整体性强，易于管理。由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了分离式结构： 4_note_顺序表的两种实现方式二.png 分离式结构，表对象里只保存与整个表有关的信息(容量个元素个数),实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。元素存储区替换一体式结构由于顺序表信息区与数据区连续存储在一起，所以想要更换数据区，就只能整体搬迁，即整个顺序表对象(存储顺序表的结构信息的区域)改变了。分离式结构想要更换数据区，只需要将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。元素存储区扩充采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。此种顺序表被称为动态顺序表，因为其容量可以在使用中动态变化。扩充的两种策略每次扩充增加固定数目的存储位置，如每次扩充增加8个元素位置，这种策略称为线性增长每次扩充容量加倍，如每次扩充增加一倍存储空间。特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。补充：内存： 5_内存.png 思维导图 6_顺序表思维导图.png 顺序表的操作增加元素 7_顺序表的操作.png 尾端加入元素，如图所示，直接在顺序表的元素末尾加上元素，其时间复杂度为O(1) 保序的加入元素，如图所示，将增加的元素50，放在索引为1的位置，则对应的其他元素则分别向后移动，此为保序，没有破坏增加元素之前的元素顺序，但因会让增加元素所在位置之后的元素都产生移动，其时间复杂度为O(n) 非保序的加入元素,其时间复杂度为O(1)，由于其会破坏顺序表原有的元素顺序，因此不常用删除元素 8_顺序表的操作_删除元素.png ) 删除表尾的元素，其时间复杂度为O(1) 保序的元素删除，时间复杂度为O(n) 非保序的元素删除，时间复杂度为O(1) Python 中的顺序表 Python 中的list和tuple两种类型采用了顺序表的实现技术 tuple 是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似 list 的基本实现技术 Python 标准类型list 就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序(即保序)，而且还具有以下行为特征：基于下标(位置) 的高效元素访问和更新，时间复杂度是O(1); 为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。允许任意加入元素，而且在不断加入元素的过程中，表对象的标识不变；为满足该特征，必须能更换元素存储区，并且为保证更换存储区时list对象的标识不变，只能采用分离式实现技术。在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。因此，使用list.append()加入元素比在指定位置插入元素效率高。重点总结：在Python的官方实现中，list实现采用了下面的策略，在建立空表时，系统分配一块能容纳8个元素的存储区；在执行插入操作(insert和append)时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大(目前的阈值为50000)，则改变策略，采用加一倍的方法。引入这种改变策略的方式是为了避免出现过多空闲的存储位置。作者：techLee 个人博客地址：www.limiao.tech 原创文章，转载请告知

2018-08-26

算法之搜索(Java版)-持续更新补充

一、顺序查找顺序查找对序列本身没有要求（比如不需要是已经排序好的），也不仅限于数字、字符，也可以用于前缀，对象信息的关键信息的匹配（比如查找指定id的相应信息）。衡量查找性能的一个指标是————ASL(Average Search Length)，ASL=Pi乘Ci，Pi是查找第i个元素的概率，Ci是找到第i个已经比较过次数。哨兵方式的顺序查找相比较基础的顺序查找在循环的比较部分减少了一般。 //1. 顺序查找 public class SequentialSearch { private int[] array; public SequentialSearch(int[] array) { this.array = array; } public int search(int key) { for(int i = 0; i < array.length; i++) { if(array[i] == key) { return i; } } return -1; } } //2. 哨兵方式顺序查找 public class Search2 { private int[] array; public Search2(int[] array) { this.array = array; } public int search(int key) { if(key == array[0]) { return 0; } int temp = array[0]; array[0] = key; int index = array.length-1; while(array[index] != key) { index--; } array[0] = temp; if(index == 0) { return -1; }else { return index; } } } 二、二分查找如果是顺序查找，7个数最多可能会比较7次，但用二分查找，最多只要3次就能OK。时间复杂度是O（logn）(底数为2)。二分查找的优化————插值查找如果数据范围是1~100000,让你找10,那么就不一定要从中间找起了。可以三分之一，四分之一处查找，比如1~10，待查为3，那可以从前面三分之一为划分点。对于要查找的位置有个精确的计算公式P=low+（key-a[low])/(a[high]-a[low])*(high-low) //1. 二分查找递归与非递归的实现 public class BinarySearch { private int[] array; public BinarySearch(int[] array) { this.array = array; } public int searchRecursion(int target) { if(array == null) { return -1; } return searchRecursion(target, 0, array.length - 1); } public int search(int target) { if(array == null) { return -1; } int start = 0; int end = array.length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(array[mid] == target) { return mid; }else if(target < array[mid]) { end = mid - 1; }else { start = mid + 1; } } return -1; } private int searchRecursion(int target, int start, int end) { if(start > end) { return -1; } int mid = start + (end - start) / 2; if(array[mid] == target) { return mid; }else if(array[mid] < target) { return searchRecursion(target, mid + 1, end); }else { return searchRecursion(target, start, mid -1); } } } //2. 二分插入排序 public class BinaryInsertSort { private int[] array; public BinaryInsertSort(int[] array) { this.array = array; } public void sort() { int length = array.length; for(int i = 1; i < length; i++) { int temp = array[i]; int insertIndex = binarySearch(i - 1, temp); if(insertIndex != i) { for(int j = i; j > insertIndex; j--) { array[j] = array[j - 1]; } array[insertIndex] = temp; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } private int binarySearch(int end, int target) { int start = 0; int mid = -1; while(start <= end) { mid = start + (end - start) / 2; if(array[mid] > target) { end = mid - 1; }else { //如果相等，也插入到后面 start = mid + 1; } } return start; } } 三、杨氏矩阵的的查找杨氏矩阵就是行列递增的矩阵。杨氏矩阵的操作插入。插入一个数，需要移动其他元素删除。给定x,y坐标，删除那个数，伴随其他元素移动，怎样移动操作最少？查找t是否存在于矩阵中。这也是这篇博客里所要关注的。返回第k大的数。涉及到堆查找，后续博客再细说。关于查找t是否存在于矩阵，书中给了几种实现的方法：递归实现和非递归实现优化：每次不都从每行的第一个数开始查找，左右上下进行比较然后查找。分治法。杨氏矩阵行列是递增的，那么对角线也是递增的，可以利用对角线划分的区域来缩小要查找数的范围。（实现略）定位查找法。先定位到第一行最右的数，然后只需要往下走，往左走两种操作即可，相比方法2省掉了往右走。 public class YoungSearch { private int[][] array; public YoungSearch(int[][] array) { this.array = array; } //1.递归实现 public boolean recursionSearch(int x, int y, int target) { if(x == array.length || y == array[0].length) { return false; } if(target < array[x][y]) { return false; } if(target == array[x][y]) { System.out.println(String.format("x: %d, y: %d", x, y)); return true; } return recursionSearch(x + 1, y, target) || recursionSearch(x, y + 1, target); } //非递归实现 public boolean search(int target) { for(int i = 0; i < array.length; i++) { for(int j = 0; j < array[0].length && target >= array[i][j]; j++) { if(target == array[i][j]) { System.out.println(String.format("x: %d y: %d", i, j)); return true; } } } return false; } //2.简单优化（向左/右/下走） public boolean search2(int target) { int width = array[0].length; int height = array.length; if(target >= array[0][0]) { int i = 0; for(; i < width && target >= array[0][i]; i++) { if(target == array[0][i]) { System.out.println(String.format("x: %d, y: %d", 0, i)); return true; } } if(i > width - 1) { i--; } //循环向下查找 for(int j = 1; j < height; j++) { if(target == array[j][i]) { System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target < array[j][i]) { for(; i >= 0; i--) { if(target == array[j][i]) { System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target > array[j][i]) { break; } } if(i < 0) { i++; } }else if(target > array[j][i]) { for(; i < width; i++) { if(target == array[j][i]){ System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target < array[j][i]) { break; } } if(i > width - 1) { i--; } } } } return false; } //3.进一步优化（从第一行最右边的数开始，只需要向下和向左两个操作） public boolean search3(int target) { int i = 0; int j = array[0].length - 1; int temp = array[i][j]; while(true) { if(target == temp) { System.out.println(String.format("x: %d, y: %d", i, j)); return true; }else if(j > 0 && target < temp){ temp = array[i][--j]; }else if(i < array.length - 1 && target > temp) { temp = array[++i][j]; }else { return false; } } } } 四、分块查找对于待查找的数据列表来说，如果元素变动很少，那么可以先进行排序再查找。但如果这个数据经常需要添加元素，那么每次查找前都需要排序，这并不是一个好的选择。就有了分块查找，这个概念再学数据库的时候听过。分块查找里有索引表和分块这两个概念。索引表就是帮助分块查找的一个分块依据，就是一个数组，用来存储每块最大的存储值（范围上限）；分块就是通过索引表把数据分为几块。原理：当需要增加一个元素的时候，先根据索引表，获取这个元素应该在那一块，然后直接把元素加入到相应的块里，而块内的元素直接不需要有序。从上面可知，分块查找只需要索引表有序，每一个块里的元素可以是无序的，但第i块的每个元素一定比第i-1块的每一个元素大（小）。当索引表很大的时候，可以对索引表进行二分查找，锁定块的位置，然后对块内的元素进行顺序查找。总性能不如二分查找，但强过顺序查找，更好的是不需要数列完全有序。举个例子，比如索引表为【10，20，30】,分块一【2，1，4，2】分块二【19，15，18，】分块三【22，27，23】，现在要增加22这个数，直接根据索引表把22放到分块三最后就行了【22,27,23,22】。可以看出，分块查找同时有顺序查找和二分查找的有点————不需要有序、速度快。应用场景视频网站对用户观看行为记录，每个用户分别观看了一个视频多久，如果对每条这样的记录都放到一个表里，那太多了，可以根据具体业务做分表，一天一个表，表名如t_user_watch_xxx_20180806，存储查询的时候就可以根据时间去做一个表的分块，在查询详细的记录。 //分块查找 import java.util.ArrayList; public class BlockSearch { private int[] index; private ArrayList<ArrayList<Integer>> list; public BlockSearch(int[] index) { this.index = index; list = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < index.length; i++) { list.add(new ArrayList<Integer>()); } } public void insert(Integer value) { int i = binarySearch(value); list.get(i).add(value); } public boolean search(int data) { int i = binarySearch(data); for(int j = 0; j < list.get(i).size(); j++) { if(data == list.get(i).get(j)) { return true; } } return false; } public void printAll() { for(int i = 0; i < list.size(); i++) { ArrayList<Integer> l = list.get(i); System.out.println("ArrayList: " + i + ":"); for(int j = 0; j < l.size(); j++) { System.out.println(l.get(j)); } } } private int binarySearch(int target) { int start = 0; int end = index.length - 1 ; int mid = -1; while(start <= end) { mid = (start + end) / 2; if(target == index[mid]) { return mid; }else if(target < index[mid]) { end = mid - 1; }else { start = mid + 1; } } return start; } }

2018-08-05

算法之排序(Java版)-持续更新补充

开始复习排序，主要是按照《轻松学算法》这本书的目录来学习，同时搜索网上的博客文章来辅助，参考的来源均在文章底部标明。

2018-08-02

LCS 算法：Javascript 最长公共子序列

LCS问题的算法用途广泛，如在软件不同版本的管理中，用LCS算法找到新旧版本的异同处;在软件测试中，用LCS算法对录制和回放的序列进行比较，在基因工程领域，用LCS算法检查患者DNA连与键康DNA链的异同

2018-07-22

C++泛型线性查找算法——find

C++泛型线性查找算法——find 《泛型编程和STL》笔记及思考。线性查找可能是最为简单的一类查找算法了。他所作用的数据结构为一维线性的空间。

2018-07-16

Java高级编程——MySql采用的算法原理

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

2018-07-10

KernelML——一种广义机器学习算法

最近，我创造了一个自定义的“粒子优化算法”，并制作了一个叫做KernelML的Python包。创造这种算法是为了给数据分析师和数据科学家提供一个针对复杂损失函数和非线性系数的广义机器学习算法。

2018-05-21

图解React Diff算法及新架构Fiber

首先从高阶组件的思想开始谈起，帮助我们灵活管理代码，介绍了简单的HOC示例、传递参数的HOC示例、反向继承HOC，进而讲述了HOC库recompose，然后通过图解重点说明了DOM DIFF算法，最后对新架构

2018-04-27

[2]十道算法题【Java实现】

前言清明不小心就拖了两天没更了～～这是十道算法题的第二篇了～上一篇回顾：十道简单算法题最近在回顾以前使用C写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用Java改写一下，重温一下

2018-04-06

算法题丨Remove Duplicates from Sorted Array

算法分析难度：低分析：要求给定的排序后的数组，将其中重复的元素去除（是的每个元素只出现一次），并返回最终数组的长度。算法不要分配额外的数组空间。

2018-03-29

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。