晓生寒
TA的个人档案
个人介绍
大数据开发与数据分析
擅长的技术
- Java
获得更多能力
通用技术能力：
-
Java
中级
能力说明：
掌握封装、继承和多态设计Java类的方法，能够设计较复杂的Java类结构；能够使用泛型与集合的概念与方法，创建泛型类，使用ArrayList，TreeSet，TreeMap等对象掌握Java I/O原理从控制台读取和写入数据，能够使用BufferedReader，BufferedWriter文件创建输出、输入对象。
云产品技术能力：
-
Clouder
-
Apsara Clouder大数据技能认证：搭建运营工单数据分析系统
获得于2019-02-14 10:05:24
-
Apsara Clouder大数据技能认证：海量电力设备监测数据存储分析
获得于2019-02-14 10:02:14
-
Apsara Clouder大数据技能认证：数据仓库系统的运维优化
获得于2019-01-09 22:57:20
-
Apsara Clouder大数据技能认证：使用深度学习TensorFlow框架进行图片识别
获得于2019-01-01 12:16:21
-
Apsara Clouder大数据技能认证：模拟搭建数据中心
获得于2018-12-31 13:35:09
-
Apsara Clouder大数据技能认证：搭建运营工单数据分析系统
阿里云技能认证
详细说明
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2019-05-24
数据结构六：图（DataWhale系列）
Datawhale 系列数据结构 Task6 图 图，基本概念：  1.邻接：如果两个定点同一条边连接，就成这两个定点是邻接的。 2.路径：路径是边的序列，比如从顶点B到定点J的路径为BAEJ，当然还有别的路径BCDJ。 3.连通图和非连通图：如果至少一条路径可以连接所有的定点，这个图称为联通图。如果存在从某个定点不能到达另外一个定点，则称为非联通的。 4.有向图和无向图：如果图中的边没有方向，可以从任意一边到达另一边，则称为无向图。例如从A城市可以到B城市，也可以从B城市到A城市，这叫做无向图。但是如果只能从A城市驶向B城市的图，称为有向图。 5.有权图和无权图：图中的边呗赋予一个权值，全职是一个数字，代表两个定点间的物理距离，或者从一个顶点到另一个顶点时间，这种图被称作有权图。反之边没有赋权的图被称为无权图 6.1实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法 //图所需要的，节点，队列，栈 //节点 public class Vertex { public char label; public boolean wasVisited; public Vertex(char label){ this.label = label; wasVisited = false; } } //队列 public class QueueX { private final int SIZE = 20; private int[] queArray; private int front; private int rear; public QueueX(){ queArray = new int[SIZE]; front = 0; rear = -1; } public void insert(int j) { if(rear == SIZE-1) { rear = -1; } queArray[++rear] = j; } public int remove() { int temp = queArray[front++]; if(front == SIZE) { front = 0; } return temp; } public boolean isEmpty() { return (rear+1 == front || front+SIZE-1 == rear); } } //栈 public class StackX { private final int SIZE = 20; private int [] st; private int top; public StackX(){ st = new int[SIZE]; top=-1; } public void push(int j){ st[++top] = j; } public int pop(){ return st[top--]; } public int peek(){ return st[top]; } public boolean isEmpty(){ return (top == -1); } } //无权无向图，用邻接表表示， public class Graph { private final int MAX_VERTS = 20;//表示定点的个数 private Vertex vertexList[];//用来存储定点的数组 private int adjMat[][];//用邻接矩阵来存储边，数组元素0表示没有边界，1表示有边界 private int nVerts; private StackX theStack;//用栈实现深度优先搜多 private QueueX queue; public Graph(){ vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0;//初始化顶点个数为0 //初始化邻接矩阵所有元素都为0，即所有顶点都没有边 for(int i = 0; i < MAX_VERTS; i++) { for(int j = 0; j < MAX_VERTS; j++) { adjMat[i][j] = 0; } } theStack = new StackX(); queue = new QueueX(); } //将顶点添加到数组中，是否访问标志置为wasVisited=false（未访问） public void addVertex(char lab){ vertexList[nVerts++]=new Vertex(lab); } //注意用临界矩阵表示边，是对称的，两部分都要赋值 public void addEdge(int start,int end){ adjMat[start][end]=1; adjMat[end][start]=1; } //打印某个顶点表示的值 public void displayVertex(int v){ System.out.println(vertexList[v].label); } /**深度优先搜索算法 * 1.用peek()方法检查栈顶的顶点 * 2.用getAdjUnvisitedVertex()方法找到当前栈顶邻接且未被访问的顶点 * 3.第二步方法值不等-1则找到下一个未访问的邻接顶点，访问这个顶点，并入栈 * 如果第二步方法返回值等于-1,则没有找到，出栈 */ public void depthFirstSearch(){ vertexList[0].wasVisited = true;//访问之后标记未true displayVertex(0); theStack.push(0); while(!theStack.isEmpty()){ int v=getAdjUnvisitedVertex(theStack.peek()); if(v==-1){ theStack.pop(); }else{ vertexList[v].wasVisited = true; displayVertex(v); theStack.push(v); } } for(int i=0;i<nVerts;i++){ vertexList[i].wasVisited=false; } } //找到与某一点邻接且未被访问的顶点 public int getAdjUnvisitedVertex(int v){ for(int i=0;i<nVerts;i++){ if(adjMat[v][i]==1 && vertexList[i].wasVisited == false){ return i; } } return -1; } /**广度优先搜索算法： * 1.用remove()方法检查栈顶的顶点 * 2.试图找到这个顶点还未访问的邻接点 * 3.如果没有找到，该顶点出列 * 4.如果找到这样的顶点，访问这个顶点，并把它放入队列中 */ public void breadthFirstSearch(){ vertexList[0].wasVisited = true; displayVertex(0); queue.insert(0); int v2; while(!queue.isEmpty()){ int v1=queue.remove(); while((v2=getAdjUnvisitedVertex(v1))!=-1){ vertexList[v2].wasVisited = true; displayVertex(v2); queue.insert(v2); } } for(int i=0;i<nVerts;i++){ vertexList[i].wasVisited=false; } } } //最小生成树 /**基于深度优先搜索找到最小生成树 *这里是指，用最少的边连接所有顶点。对于一组顶点，可能有多种最小生成树，但是最小生成树的边的数量E总是比顶点V的数量小1，即：V = E+1 */ public void mst(){ vertexList[0].wasVisited = true; theStack.push(0); while(!theStack.isEmpty()){ int currentVertex = theStack.peek(); int v = getAdjUnvisitedVertex(currentVertex); if(v == -1){ theStack.pop(); }else{ vertexList[v].wasVisited = true; theStack.push(v); displayVertex(currentVertex); displayVertex(v); System.out.print(" "); } } //搜索完毕，初始化，以便于下次搜索 for(int i = 0; i < nVerts; i++) { vertexList[i].wasVisited = false; } } 6.2实现图的深度优先搜索、广度优先搜索 //这块参考6.1中代码 6.3.1 实现DijKstra算法 DijKstra算法思想：互补松弛条件：设标量d1,d2,...,dN满足 dj<=di+aij,(i,j)属于A， 且P是以i1为起点ik为终点的路，如果， dj=di+aij，对P的所有边（i,j） 成立，那么P是从i到ik的最短路。其中，满足上面两式的被称为最短路问题松弛条件。 1，令G=（V,E）为一个带权无向图。G中若有两个相邻的节点，i，j。aij为节点i到j的权值，在本算法可以理解为距离。每个节点斗鱼一个值di(节点标记)表示其从起点到它的某条路的距离2，算法储是有个数组V用于存储未访问的节点列表，我们称为候选列表。选定节点1为起始节点。开始时，节点1的d1=0,其他节点di=无穷大，V为所有节点。初始化条件后，然后开始迭代算法，指导B为空集时停止。具体迭代步骤如下： 将d值最小的节点di从候选列表中移除。（本例中V的数据结构采用的是优先队列实现最小值出列，最好使用斐波那契数列？）对于该节点为期待你的每一条边，不包括移除V的节点，(i,j)属于A，若dj>di+dj（违反松弛条件） /**DijKstra算法 *这里使用带权无向图，弥补6.1中知识 */ public class Vertex implements Comparable<Vertex>{ /** * 节点名称(A,B,C,D) */ private String name; /** * 最短路径长度 */ private int path; /** * 节点是否已经出列(是否已经处理完毕) */ private boolean isMarked; public Vertex(String name){ this.name = name; this.path = Integer.MAX_VALUE; //初始设置为无穷大 this.setMarked(false); } public Vertex(String name, int path){ this.name = name; this.path = path; this.setMarked(false); } @Override public int compareTo(Vertex o) { return o.path > path?-1:1; } } public class Vertex implements Comparable<Vertex>{ /** * 节点名称(A,B,C,D) */ private String name; /** * 最短路径长度 */ private int path; /** * 节点是否已经出列(是否已经处理完毕) */ private boolean isMarked; public Vertex(String name){ this.name = name; this.path = Integer.MAX_VALUE; //初始设置为无穷大 this.setMarked(false); } public Vertex(String name, int path){ this.name = name; this.path = path; this.setMarked(false); } @Override public int compareTo(Vertex o) { return o.path > path?-1:1; } } public class Graph { /* * 顶点 */ private List<Vertex> vertexs; /* * 边 */ private int[][] edges; /* * 没有访问的顶点 */ private Queue<Vertex> unVisited; public Graph(List<Vertex> vertexs, int[][] edges) { this.vertexs = vertexs; this.edges = edges; initUnVisited(); } /* * 搜索各顶点最短路径 */ public void search(){ while(!unVisited.isEmpty()){ Vertex vertex = unVisited.element(); //顶点已经计算出最短路径，设置为"已访问" vertex.setMarked(true); //获取所有"未访问"的邻居 List<Vertex> neighbors = getNeighbors(vertex); //更新邻居的最短路径 updatesDistance(vertex, neighbors); pop(); } System.out.println("search over"); } /* * 更新所有邻居的最短路径 */ private void updatesDistance(Vertex vertex, List<Vertex> neighbors){ for(Vertex neighbor: neighbors){ updateDistance(vertex, neighbor); } } /* * 更新邻居的最短路径 */ private void updateDistance(Vertex vertex, Vertex neighbor){ int distance = getDistance(vertex, neighbor) + vertex.getPath(); if(distance < neighbor.getPath()){ neighbor.setPath(distance); } } /* * 初始化未访问顶点集合 */ private void initUnVisited() { unVisited = new PriorityQueue<Vertex>(); for (Vertex v : vertexs) { unVisited.add(v); } } /* * 从未访问顶点集合中删除已找到最短路径的节点 */ private void pop() { unVisited.poll(); } /* * 获取顶点到目标顶点的距离 */ private int getDistance(Vertex source, Vertex destination) { int sourceIndex = vertexs.indexOf(source); int destIndex = vertexs.indexOf(destination); return edges[sourceIndex][destIndex]; } /* * 获取顶点所有(未访问的)邻居 */ private List<Vertex> getNeighbors(Vertex v) { List<Vertex> neighbors = new ArrayList<Vertex>(); int position = vertexs.indexOf(v); Vertex neighbor = null; int distance; for (int i = 0; i < vertexs.size(); i++) { if (i == position) { //顶点本身，跳过 continue; } distance = edges[position][i]; //到所有顶点的距离 if (distance < Integer.MAX_VALUE) { //是邻居(有路径可达) neighbor = getVertex(i); if (!neighbor.isMarked()) { //如果邻居没有访问过，则加入list; neighbors.add(neighbor); } } } return neighbors; } /* * 根据顶点位置获取顶点 */ private Vertex getVertex(int index) { return vertexs.get(index); } /* * 打印图 */ public void printGraph() { int verNums = vertexs.size(); for (int row = 0; row < verNums; row++) { for (int col = 0; col < verNums; col++) { if(Integer.MAX_VALUE == edges[row][col]){ System.out.print("X"); System.out.print(" "); continue; } System.out.print(edges[row][col]); System.out.print(" "); } System.out.println(); } } } 6.3.2 A* 算法 public class AstarPathFind { // 前四个是上下左右，后四个是斜角 public final static int[] dx = { 0, -1, 0, 1, -1, -1, 1, 1 }; public final static int[] dy = { -1, 0, 1, 0, 1, -1, -1, 1 }; // 最外圈都是1表示不可通过 final static public int[][] map = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; public static void main(String[] args) { // TODO Auto-generated method stub Point start = new Point(1, 1); Point end = new Point(10, 13); /* * 第一个问题：起点FGH需要初始化吗？ * 看参考资料的图片发现不需要 */ Stack<Point> stack = printPath(start, end); if(null==stack) { System.out.println("不可达"); }else { while(!stack.isEmpty()) { //输出(1,2)这样的形势需要重写toString System.out.print(stack.pop()+" -> "); } System.out.println(); } } public static Stack<Point> printPath(Point start, Point end) { /* * 不用PriorityQueue是因为必须取出存在的元素 */ ArrayList<Point> openTable = new ArrayList<Point>(); ArrayList<Point> closeTable = new ArrayList<Point>(); openTable .clear(); closeTable.clear(); Stack<Point> pathStack = new Stack<Point>(); start.parent = null; //该点起到转换作用，就是当前扩展点 Point currentPoint = new Point(start.x, start.y); //closeTable.add(currentPoint); boolean flag = true; while(flag) { for (int i = 0; i < 8; i++) { int fx = currentPoint.x + dx[i]; int fy = currentPoint.y + dy[i]; Point tempPoint = new Point(fx,fy); if (map[fx][fy] == 1) { // 由于边界都是1中间障碍物也是1，，这样不必考虑越界和障碍点扩展问题 //如果不设置边界那么fx >=map.length &&fy>=map[0].length判断越界问题 continue; } else { if(end.equals(tempPoint)) { flag = false; //不是tempPoint，他俩都一样了此时 end.parent = currentPoint; break; } if(i<4) { tempPoint.G = currentPoint.G + 10; }else { tempPoint.G = currentPoint.G + 14; } tempPoint.H = Point.getDis(tempPoint,end); tempPoint.F = tempPoint.G + tempPoint.H; //因为重写了equals方法，所以这里包含只是按equals相等包含 //这一点是使用java封装好类的关键 if(openTable.contains(tempPoint)) { int pos = openTable.indexOf(tempPoint ); Point temp = openTable.get(pos); if(temp.F > tempPoint.F) { openTable.remove(pos); openTable.add(tempPoint); tempPoint.parent = currentPoint; } }else if(closeTable.contains(tempPoint)){ int pos = closeTable.indexOf(tempPoint ); Point temp = closeTable.get(pos); if(temp.F > tempPoint.F) { closeTable.remove(pos); openTable.add(tempPoint); tempPoint.parent = currentPoint; } }else { openTable.add(tempPoint); tempPoint.parent = currentPoint; } } }//end for if(openTable.isEmpty()) { return null; }//无路径 if(false==flag) { break; }//找到路径 openTable.remove(currentPoint); closeTable.add(currentPoint); Collections.sort(openTable); currentPoint = openTable.get(0); }//end while Point node = end; while(node.parent!=null) { pathStack.push(node); node = node.parent; } return pathStack; } } class Point implements Comparable<Point>{ int x; int y; Point parent; int F, G, H; public Point(int x, int y) { super(); this.x = x; this.y = y; this.F = 0; this.G = 0; this.H = 0; } @Override public int compareTo(Point o) { // TODO Auto-generated method stub return this.F - o.F; } @Override public boolean equals(Object obj) { Point point = (Point) obj; if (point.x == this.x && point.y == this.y) return true; return false; } public static int getDis(Point p1, Point p2) { int dis = Math.abs(p1.x - p2.x) * 10 + Math.abs(p1.y - p2.y) * 10; return dis; } @Override public String toString() { return "(" + this.x + "," + this.y + ")"; } } 6.4实现拓扑排序的 Kahn 算法、DFS 算法 拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从vi到vj的路径，那么在拓扑排序中，vj就出现在vi的后面。拓扑图中，不能出现圈，如果有圈，那么就没有意义。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。偏序：在有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。所以，有向无环图必然是满足偏序关系的。全序：在偏序的基础之上，有向无环图中的任意一对顶点还需要有明确的关系，反应在图中，就是单向连通的关系。（不能双向连通，否则就是环） // Kahn 算法 public class KahnTopological { private List<Integer> result; // 用来存储结果集 private Queue<Integer> setOfZeroIndegree; // 用来存储入度为0的顶点 private int[] indegrees; // 记录每个顶点当前的入度 private int edges; private Digraph di; public KahnTopological(Digraph di) { this.di = di; this.edges = di.getE(); this.indegrees = new int[di.getV()]; this.result = new ArrayList<Integer>(); this.setOfZeroIndegree = new LinkedList<Integer>(); // 对入度为0的集合进行初始化 Iterable<Integer>[] adjs = di.getAdj(); for(int i = 0; i < adjs.length; i++) { // 对每一条边 v -> w for(int w : adjs[i]) { indegrees[w]++; } } for(int i = 0; i < indegrees.length; i++) { if(0 == indegrees[i]) { setOfZeroIndegree.enqueue(i); } } process(); } private void process() { while(!setOfZeroIndegree.isEmpty()) { int v = setOfZeroIndegree.dequeue(); // 将当前顶点添加到结果集中 result.add(v); // 遍历由v引出的所有边 for(int w : di.adj(v)) { // 将该边从图中移除，通过减少边的数量来表示 edges--; if(0 == --indegrees[w]) // 如果入度为0，那么加入入度为0的集合 { setOfZeroIndegree.enqueue(w); } } } // 如果此时图中还存在边，那么说明图中含有环路 if(0 != edges) { throw new IllegalArgumentException("Has Cycle !"); } } public Iterable<Integer> getResult() { return result; } } //DFS算法 public class DirectedDepthFirstOrder { // visited数组，DFS实现需要用到 private boolean[] visited; // 使用栈来保存最后的结果 private Stack<Integer> reversePost; /** * Topological Sorting Constructor */ public DirectedDepthFirstOrder(Digraph di, boolean detectCycle) { // 这里的DirectedDepthFirstCycleDetection是一个用于检测有向图中是否存在环路的类 DirectedDepthFirstCycleDetection detect = new DirectedDepthFirstCycleDetection( di); if (detectCycle && detect.hasCycle()) throw new IllegalArgumentException("Has cycle"); this.visited = new boolean[di.getV()]; this.reversePost = new Stack<Integer>(); for (int i = 0; i < di.getV(); i++) { if (!visited[i]) { dfs(di, i); } } } private void dfs(Digraph di, int v) { visited[v] = true; for (int w : di.adj(v)) { if (!visited[w]) { dfs(di, w); } } // 在即将退出dfs方法的时候，将当前顶点添加到结果集中 reversePost.push(v); } public Iterable<Integer> getReversePost() { return reversePost; } } 6.5Number of Islands（岛屿的个数） class Solution { public int numIslands(char[][] grid) { int count=0; for(int x=0;x<grid.length;x++) for(int y =0;y<grid[0].length;y++) { if( grid[x][y] =='1') { clear(grid,x,y); ++count; } } return count; } public void clear(char[][] grid,int x,int y) { grid[x][y]=0; if(x+1<grid.length&& grid[x+1][y]=='1')clear(grid,x+1,y); if(x-1>=0&& grid[x-1][y]=='1')clear(grid,x-1,y); if(y+1<grid[0].length&& grid[x][y+1]=='1')clear(grid,x,y+1); if(y-1>=0&& grid[x][y-1]=='1')clear(grid,x,y-1); } } 6.6Valid Sudoku（有效的数独） class Solution { public boolean isValidSudoku(char[][] board) { boolean[] rowFlags = new boolean[9]; boolean[] colFlags = new boolean[9]; boolean[] squareFlags = new boolean[9]; for (int i = 0; i < 9; i++) { Arrays.fill(rowFlags, false); Arrays.fill(colFlags, false); Arrays.fill(squareFlags, false); for (int j = 0; j < 9; j++) { // 行数独 char cell = board[i][j]; if (!isCellValid(rowFlags, cell)) { return false; } // 列数独 cell = board[j][i]; if (!isCellValid(colFlags, cell)) { return false; } // 3*3 方格数独 int row = (j / 3) + ((i / 3) * 3); int col = (j % 3) + ((i % 3) * 3); cell = board[row][col]; if (!isCellValid(squareFlags, cell)) { return false; } } } return true; } //如果之前出现过，就return false。 public boolean isCellValid(boolean[] flags, char cell) { if (cell == '.') { return true; } int value = cell - 49; if (flags[value]) { return false; } flags[value] = true; return true; } }
-
发表了文章 2019-05-18
数据结构四：散列表+字符串（DataWhale系列）
Datawhale 系列数据结构 Task4.1 散列表 基本概念 散列表(Hash Table，又叫哈希表)，是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 散列表思想 （1）使用散列函数将给定键转化为一个“数组的索引”，理想情况下，不同的key会被转化为不同的索引，但是在实际情况中，我们会遇到不同的键转化为相同索引的情况，这种情况叫做散列冲突/碰撞，后文中会详细讲解； （2）得到了索引后，我们就可以像访问数组一样，通过这个索引访问到相应的键值对。 如何设计散列函数 （1）散列函数的设计不能太复杂：减少计算时间 （2）散列函数整成的值要尽可能随机并且均匀分布 主要方法有： a.直接寻址法 b.数字分析法 c.平方取中法 d.折叠法 e.随机数法 f.除留取余法 散列冲突 再好的散列函数也无法避免散列冲突 主要方法有： 直接寻址法 链表法：更常用，4.1.1基于其设计散列表 4.1.1实现一个基于链表解决冲突问题的散列表 /*布谷鸟散列概述 使用hashA、hashB计算对应的key位置： 1、两个位置均为空，则任选一个插入； 2、两个位置中一个为空，则插入到空的那个位置 3、两个位置均不为空，则踢出一个位置后插入，被踢出的对调用该算法，再执行该算法找其另一个位置，循环直到插入成功。 4、如果被踢出的次数达到一定的阈值，则认为hash表已满，并进行重新哈希rehash cuckoo hashing的哈希函数是成对的（具体的实现可以根据需求设计），每一个元素都是两个，分别映射到两个位置，一个是记录的位置，另一个是备用位置。这个备用位置是处理碰撞时用的，cuckoo hashing处理碰撞的方法，就是把原来占用位置的这个元素踢走，不过被踢出去的元素还有一个备用位置可以安置，如果备用位置上还有人，再把它踢走，如此往复。直到被踢的次数达到一个上限，才确认哈希表已满，并执行rehash操作 */ interface HashFamily<AnyType>{ //根据which来选择散列函数，并返回hash值 int hash(AnyType x,int which); //返回集合中散列的个数 int getNumberOfFunctions(); //获取新的散列函数 void generateNewFunctions(); } class CuckooHashTable<AnyType>{ //定义最大装填因子为0.4 private static final double MAX_LOAD = 0.4; //定义rehash次数达到一定时，进行再散列 private static final int ALLOWED_REHASHES = 1; //定义默认表的大小 private static final int DEFAULT_TABLE_SIZE = 101; //定义散列函数集合 private final HashFamily<? super AnyType> hashFunctions; //定义散列函数个数 private final int numHashFunctions; //定义当前表 private AnyType[] array; //定义当前表的大小 private int currentSize; //定义rehash的次数 private int rehashes = 0; //定义一个随机数 private Random r = new Random(); public CuckooHashTable(HashFamily<? super AnyType> hf){ this(hf, DEFAULT_TABLE_SIZE); } public void printArray() { // TODO Auto-generated method stub } //初始化操作 public CuckooHashTable(HashFamily<? super AnyType> hf, int size){ allocateArray(nextPrime(size)); doClear(); hashFunctions = hf; numHashFunctions = hf.getNumberOfFunctions(); } private int nextPrime(int size) { return size*2; } public void makeEmpty(){ doClear(); } //清空操作 private void doClear(){ currentSize = 0; for (int i = 0; i < array.length; i ++){ array[i] = null; } } //初始化表 @SuppressWarnings("unchecked") private void allocateArray(int arraySize){ array = (AnyType[]) new Object[arraySize]; } /** * * @param x 当前的元素 * @param which 选取的散列函数对应的位置 * @return */ private int myHash(AnyType x, int which){ //调用散列函数集合中的hash方法获取到hash值 int hashVal = hashFunctions.hash(x, which); //再做一定的处理 hashVal %= array.length; if (hashVal < 0){ hashVal += array.length; } return hashVal; } /** * 查询元素的位置，若找到元素，则返回其当前位置，否则返回-1 * @param x * @return */ private int findPos(AnyType x){ //遍历散列函数集合，因为不确定元素所用的散列函数为哪个 for (int i = 0; i < numHashFunctions; i ++){ //获取到当前hash值 int pos = myHash(x, i); //判断表中是否存在当前元素 if (array[pos] != null && array[pos].equals(x)){ return pos; } } return -1; } public boolean contains(AnyType x){ return findPos(x) != -1; } /** * 删除元素：先查询表中是否存在该元素，若存在，则进行删除该元素 * @param x * @return */ public boolean remove(AnyType x){ int pos = findPos(x); if (pos != -1){ array[pos] = null; currentSize --; } return pos != -1; } /** * 插入：先判断该元素是否存在，若存在，在判断表的大小是否达到最大负载， * 若达到，则进行扩展，最后调用insertHelper方法进行插入元素 * @param x * @return */ public boolean insert(AnyType x){ if (contains(x)){ return false; } if (currentSize >= array.length * MAX_LOAD){ expand(); } return insertHelper(x); } private boolean insertHelper(AnyType x) { //记录循环的最大次数 final int COUNT_LIMIT = 100; while (true){ //记录上一个元素位置 int lastPos = -1; int pos; //进行查找插入 for (int count = 0; count < COUNT_LIMIT; count ++){ for (int i = 0; i < numHashFunctions; i ++){ pos = myHash(x, i); //查找成功，直接返回 if (array[pos] == null){ array[pos] = x; currentSize ++; return true; } } //查找失败，进行替换操作，产生随机数位置，当产生的位置不能与原来的位置相同 int i = 0; do { pos = myHash(x, r.nextInt(numHashFunctions)); } while (pos == lastPos && i ++ < 5); //进行替换操作 AnyType temp = array[lastPos = pos]; array[pos] = x; x = temp; } //超过次数，还是插入失败，则进行扩表或rehash操作 if (++ rehashes > ALLOWED_REHASHES){ expand(); rehashes = 0; } else { rehash(); } } } private void expand(){ rehash((int) (array.length / MAX_LOAD)); } private void rehash(){ hashFunctions.generateNewFunctions(); rehash(array.length); } private void rehash(int newLength){ AnyType [] oldArray = array; allocateArray(nextPrime(newLength)); currentSize = 0; for (AnyType str : oldArray){ if (str != null){ insert(str); } } } } 4.1.2 实现一个LRU缓存淘汰算法 class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { /** * */ private static final long serialVersionUID = 1L; private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap(int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>(super.entrySet()); } finally { lock.unlock(); } } } 4.1.3 练习：两数之和 class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } TASK4.2 字符串 4.2.1 实现一个字符集，只包含这26个英文字母的Trie树 class Trie_Tree{ private class Node{ private int dumpli_num;////该字串的反复数目， 该属性统计反复次数的时候实用,取值为0、1、2、3、4、5…… private int prefix_num;///以该字串为前缀的字串数。 应该包含该字串本身。。！ private Node childs[];////此处用数组实现，当然也能够map或list实现以节省空间 private boolean isLeaf;///是否为单词节点 public Node(){ dumpli_num=0; prefix_num=0; isLeaf=false; childs=new Node[26]; } } private Node root;///树根 public Trie_Tree(){ ///初始化trie 树 root=new Node(); } /** * 插入字串。用循环取代迭代实现 * @param words */ public void insert(String words){ insert(this.root, words); } /** * 插入字串，用循环取代迭代实现 * @param root * @param words */ private void insert(Node root,String words){ words=words.toLowerCase();////转化为小写 char[] chrs=words.toCharArray(); for(int i=0,length=chrs.length; i<length; i++){ ///用相对于a字母的值作为下标索引，也隐式地记录了该字母的值 int index=chrs[i]-'a'; if(root.childs[index]!=null){ ////已经存在了，该子节点prefix_num++ root.childs[index].prefix_num++; }else{ ///假设不存在 root.childs[index]=new Node(); root.childs[index].prefix_num++; } ///假设到了字串结尾，则做标记 if(i==length-1){ root.childs[index].isLeaf=true; root.childs[index].dumpli_num++; } ///root指向子节点，继续处理 root=root.childs[index]; } } /** * 遍历Trie树，查找全部的words以及出现次数 * @return HashMap<String, Integer> map */ public HashMap<String,Integer> getAllWords(){ // HashMap<String, Integer> map=new HashMap<String, Integer>(); return preTraversal(this.root, ""); } /** * 前序遍历。。。 * @param root 子树根节点 * @param prefixs 查询到该节点前所遍历过的前缀 * @return */ private HashMap<String,Integer> preTraversal(Node root,String prefixs){ HashMap<String, Integer> map=new HashMap<String, Integer>(); if(root!=null){ if(root.isLeaf==true){ ////当前即为一个单词 map.put(prefixs, root.dumpli_num); } for(int i=0,length=root.childs.length; i<length;i++){ if(root.childs[i]!=null){ char ch=(char) (i+'a'); ////递归调用前序遍历 String tempStr=prefixs+ch; map.putAll(preTraversal(root.childs[i], tempStr)); } } } return map; } /** * 推断某字串是否在字典树中 * @param word * @return true if exists ,otherwise false */ public boolean isExist(String word){ return search(this.root, word); } /** * 查询某字串是否在字典树中 * @param word * @return true if exists ,otherwise false */ private boolean search(Node root,String word){ char[] chs=word.toLowerCase().toCharArray(); for(int i=0,length=chs.length; i<length;i++){ int index=chs[i]-'a'; if(root.childs[index]==null){ ///假设不存在，则查找失败 return false; } root=root.childs[index]; } return true; } /** * 得到以某字串为前缀的字串集。包含字串本身。 相似单词输入法的联想功能 * @param prefix 字串前缀 * @return 字串集以及出现次数，假设不存在则返回null */ public HashMap<String, Integer> getWordsForPrefix(String prefix){ return getWordsForPrefix(this.root, prefix); } /** * 得到以某字串为前缀的字串集。包含字串本身。 * @param root * @param prefix * @return 字串集以及出现次数 */ private HashMap<String, Integer> getWordsForPrefix(Node root,String prefix){ HashMap<String, Integer> map=new HashMap<String, Integer>(); char[] chrs=prefix.toLowerCase().toCharArray(); //// for(int i=0, length=chrs.length; i<length; i++){ int index=chrs[i]-'a'; if(root.childs[index]==null){ return null; } root=root.childs[index]; } ///结果包含该前缀本身 ///此处利用之前的前序搜索方法进行搜索 return preTraversal(root, prefix); } } 4.2.2 实现朴素的字符串匹配算法 public static int indext(String src, String target) { return indext(src,target,0); } public static int indext(String src, String target, int fromIndex) { return indext(src.toCharArray(), src.length(), target.toCharArray(), target.length(), fromIndex); } //朴素模式匹配算法 static int indext(char[] s, int slen, char[] t, int tlen, int fromIndex) { if (fromIndex < 0) { fromIndex = 0; } if (tlen == 0) { return fromIndex; } if (slen == 0) { return -1; } int i = fromIndex; int j = 0; while (i <= slen && j <= tlen) { /* cycle compare */ if (s[i] == t[j]) { ++i; ++j; } else { /* point back last position */ i = i - j + 1; j = 0; } } if (j > tlen) { /* found target string retun first index position*/ return i - j; } else { /* can't find target string and retun -1 */ return -1; } } 3.2.3 练习：反转字符串 class Solution { public String reverseString(String s) { final char[] array = s.toCharArray(); final int length = array.length; for (int i = 0; i < length / 2; i++) { char temp = array[i]; array[i] = array[length - i-1]; array[length - i-1] = temp; } return new String(array); } } 3.2.3 练习：反转字符串里的单词 public String reverseWords(String s) { String[] words = s.split(" "); StringBuilder sb = new StringBuilder(); for(String word : words) { sb.append(swapWord(0, word.length()-1, word.toCharArray())).append(" "); } return sb.toString().trim(); } public String swapWord(int s, int e, char[] c) { if(s >= e) { return String.valueOf(c); } char temp = c[s]; c[s] = c[e]; c[e] = temp; return swapWord(s+1, e-1, c); } 3.2.3 练习：字符串转换整数(stoi) public int myAtoi(String str) { //去除掉前后的空格 String strr = str.trim(); //存储最终过滤出来的字符串 String strrr = null; //字符串不为空时并且字符串不全是空白字符串时才转换 if(strr != null && strr.isEmpty() == false){ char f = strr.charAt(0); //判断字符串中的第一个非空格字符是不是一个有效整数字符 if(f >= '0' && f <= '9' || f == '+'|| f == '-'){ strrr = strr.substring(0,1); // 把第一位放进去(只能是数字、正负号) //这时候循环只要数字，因为正负号只能出现在第一位 for(int i = 1; i<strr.length();i++){ if(strr.charAt(i) >= '0' && strr.charAt(i) <= '9'){ strrr = strr.substring(0,i+1); } //这是遇到不符合要求的字符，直接忽略剩余元素 else{break;} } } } //判断最终字符串是否为空或则只有一个正负号 if(strrr == null || strrr.equals("+") || strrr.equals("-")) //此时strrr是String对象，如果使用==比较则比较的时内存地址 return 0; //最终转换成的数字 int num = 0; //使用异常机制打印结果 try{ num = Integer.parseInt(strrr); }catch (Exception e){ if(strrr.charAt(0) == '-') return Integer.MIN_VALUE; return Integer.MAX_VALUE; } return num; } 参考文章： 散列表参考文章： https://blog.csdn.net/ynnusl/article/details/89343419 https://blog.csdn.net/u012124438/article/details/78230478 字符串参考文章： https://www.cnblogs.com/lcchuguo/p/5194323.html
-
发表了文章 2019-05-17
数据结构三：排序+二分查找（DataWhale系列）
Datawhale 系列数据结构 Task3.1 排序 3.1.1归并 //采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全的序列 public static int [] mergeSort(int []arr){ int len =arr.length; if(len<2){ return arr; } int [] left=Arrays.copyOfRange(arr,0,len/2); int [] right=Arrays.copyOfRange(arr,len/2,len); return merge(mergeSort(left),mergeSort(right)); } public static int [] merge(int [] left,int [] right){ int llen=left.length; int rlen=right.length; int[] res=new int[llen+rlen]; int li=0,ri=0,rei=0; while (llen-li>0 && rlen-ri>0) { if (left[li] <= right[ri]) { res[rei++]=left[li++]; } else { res[rei++]=right[ri++]; } } while (llen-li>0) { res[rei++]=left[li++]; } while (rlen-ri>0) { res[rei++]=right[ri++]; } return res; } 3.1.2 快速排序 /*快速排序使用分治法来把一个list分为两个子list: *从数列中跳出一个元素，称为“基准”（pivot） *重新排序数列，所有元素比基准小的摆放在基准前面，所有比基准大的放在基准后面。在这个分区推出后，该基准就处于数列的中间位置。这个称为分区操作。 *递归的，把小于基准值元素的子数列和大于基准值元素的子数列排序 */ public static int partition(int []array,int lo,int hi){ //固定的切分方式 int key=array[lo]; while(lo<hi){ while(array[hi]>=key&&hi>lo){//从后半部分向前扫描 hi--; } array[lo]=array[hi]; while(array[lo]<=key&&hi>lo){从前半部分向后扫描 lo++; } array[hi]=array[lo]; } array[hi]=key; return hi; } public static void sort(int[] array,int lo ,int hi){ if(lo>=hi){ return ; } int index=partition(array,lo,hi); sort(array,lo,index-1); sort(array,index+1,hi); } 3.1.3 插入 public static int [] insertionSort(int []arr){ for(int i=0;i<arr.length;i++){ for(int j=i;j>0;j--){ if(arr[j]<arr[j-1]){ int temp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; } } } return arr; } 3.1.4 冒泡 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]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } return arr; } 3.1.5 选择 public static int [] selectionSort(int [] arr){ int min = 0; for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length-1;j++){ min = arr[i]; if(arr[j]<min){ min=arr[j]; arr[j]=arr[i]; arr[i]=min; } } } return arr; } 3.1.6 堆排序(选做) /*堆排序分为三个步骤： * 创建最大堆 * 确保最大堆中父节点的值比子节点的值都大 * 将根节点与最后一个叶子节点比较，择其大者剔除出堆，再重复第2、3步。 *第二步是整个堆排序的关键。 */ public static void maxHeapify(int[] array, int heapsize, int i){ int l = 2*i + 1; int r = 2*i + 2; int large = i; if (l < heapsize && array[i] < array[l]) { large = l; }else { large = i; } if (r < heapsize && array[large] < array[r]) { large = r; } if (large != i) { int temp = array[i]; array[i] = array[large]; array[large] = temp; //因为将最大值和父节点交换了位置，新的子节点并不能保证一定是比它的子节点大 //所以需要递归，确定交换的子节点比它的子节点都大 //而没有动的子节点是不需要进行递归的，因为它的数值没有变，如果之前满足最大堆条件，现在就还是满足的 maxHeapify(array, heapsize, large); } } //创建堆 public static void buildMaxHeap(int[] array){ int heapsize = array.length; for (int i = heapsize/2; i >= 0; i--) { maxHeapify(array,heapsize,i); } } public static void heapSort(int[] array){ int heapsize = array.length; for (int i = heapsize - 1; i > 0; i--) { if (array[i] < array[0]) { int temp = array[0]; array[0] = array[i]; array[i] = temp; heapsize --; maxHeapify(array, heapsize, 0); } } } 3.1.8 编程实现 O(n) 时间复杂度内找到一组数据第 K 大元素 //采用堆排序的方法 //在创建最小堆，只创建K个元素 public static void maxHeapify(int[] array, int size, int i) { int left = 2 * i + 1; int right = 2 * i + 2; int small = i; if (left < size) { if (array[small] > array[left]) { small = left; } } if (right < size) { if (array[small] > array[right]) { small = right; } } if (small != i) { int temp = array[small]; array[small] = array[i]; array[i] = temp; maxHeapify(array, size, small); } } public static void buildHeap(int[] array, int size) { for (int i = size - 1; i >= 0; i--) { maxHeapify(array, size, i); } } public static int findKByHeap(int[] array, int k) { buildHeap(array, k); for (int i = k + 1; i < array.length; i++) { if (array[i] > array[0]) { int temp = array[i]; array[i] = array[0]; array[0] = temp; maxHeapify(array, k, 0); } } return array[0]; } TASK3.2 查找 3.2.1 实现一个有序数组的二分查找 //默认数组是有序数组 public static int biSearch(int [] arr, int target){ int r = arr.length-1; int l = 0; int mid=r/2; while(l<=r){ mid=(l+r)/2; if(arr[mid]==target) return mid; else if(arr[mid]>target) r=mid; else l=mid; } return -1; } 3.2.2 实现模糊二分查找算法（比如大于等于给定值的第一个元素） //模糊二分查找，返回大于等于给定值的第一个值的下标 public static int blurrySearch(int [] arr, int target){ int r = arr.length-1; int l = 0; int mid=r/2; while(l<=r){ mid=(l+r)/2; if(arr[mid]==target) return mid; else if(arr[mid]>target) r=mid-1; else l=mid+1; } return r+1; } 3.2.3 Sqrt(x)（x的平方根） class Solution { public int mySqrt(int x) { if(x==1) return 1; int min=0; int max = x; while(max-min>1){ int m=(max+min)/2; if(x/m<m) max=m; else min = m; } return min; } }
-
发表了文章 2019-05-12
数据结构二：栈+队列+递归（DataWhale系列）
Datawhale 系列数据结构 Task2.1 栈 2.1.1用数组实现一个顺序栈 public class ArrayStack<T> { private T [] data; private int size; private int cnt; @SuppressWarnings("unchecked") public ArrayStack(){ data= (T[]) new Object [10]; cnt = 0; size =10; } public void push(T t){ if(cnt>=size){ data=Arrays.copyOf(data, data.length*2); size*=2; } data[size] = t; cnt++; } public T peek(){ if (cnt==0) { throw new EmptyStackException(); } return data[cnt]; } public T pop(){ if (cnt==0) { throw new EmptyStackException(); } cnt--; return data[cnt]; } public int search(T t){ for(int i=cnt;i>0;i--){ if(data[i]==t) return i; } return -1; } public boolean isEmpty(){ return cnt==0; } } 2.1.2 用链表实现一个链式栈 public class ListStack<T> { private List<T> data; private int cnt; public ListStack(){ data= new LinkedList<T>(); cnt = 0; } public void push(T t){ data.add(t); cnt++; } public T peek(){ if (cnt==0) { throw new EmptyStackException(); } return data.get(cnt); } public T pop(){ if (cnt==0) { throw new EmptyStackException(); } T t=data.remove(cnt); cnt--; return t; } public int search(T t){ for(int i=cnt;i>0;i--){ if(data.get(i)==t) return i; } return -1; } public boolean isEmpty(){ return cnt==0; } } 2.1.3 编程模拟实现一个浏览器的前进后退功能 public class BrowserSimula { public static void main(String[] args) { Browser b1=new Browser(); b1.open(); b1.open(); b1.open(); b1.open(); System.out.println(b1.backward()); System.out.println(b1.backward()); System.out.println(b1.forward()); System.out.println(b1.forward()); } } class Browser{ private Stack<Integer> s1; private Stack<Integer> s2; int cnt; Browser(){ s1=new Stack<Integer>(); s2=new Stack<Integer>(); cnt=0; } /** * 点开一个新的链接 */ public void open(){ cnt++; s1.push(cnt); } //后退 public Integer backward(){ if(cnt==0) throw new ArrayIndexOutOfBoundsException(cnt); Integer a =s1.pop(); s2.push(a); return s1.peek(); } //前进 public Integer forward(){ if(s2.isEmpty()) throw new ArrayIndexOutOfBoundsException(cnt); Integer a =s2.pop(); s1.push(a); return a; } } 2.1.4 练习 //Valid Parentheses（有效的括号） private HashMap<Character, Character> mappings; public Solution() { this.mappings = new HashMap<Character, Character>(); this.mappings.put(')', '('); this.mappings.put('}', '{'); this.mappings.put(']', '['); } public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (this.mappings.containsKey(c)) { char topElement = stack.empty() ? '#' : stack.pop(); if (topElement != this.mappings.get(c)) { return false; } } else { stack.push(c); } } return stack.isEmpty(); } //Longest Valid Parentheses（最长有效的括号）[作为可选] /*dp 方法: 我们用 dp[i] 表示以 i 结尾的最长有效括号； 1 当 s[i] 为 ( , dp[i] 必然等于0,因为不可能组成有效的括号; 2 那么 s[i] 为 ) 2.1 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2； 2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]； 时间复杂度：O(n) */ public int longestValidParentheses(String s) { if (s == null || s.length() == 0) return 0; int[] dp = new int[s.length()]; int res = 0; for (int i = 0; i < s.length(); i++) { if (i > 0 && s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2); } else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); } } res = Math.max(res, dp[i]); } return res; } //Evaluate Reverse Polish Notatio（逆波兰表达式求值） public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0 ;i < tokens.length;i++){ String str = tokens[i]; if (str.length() == 1){ char ch = str.charAt(0); if (ch-'0' >= 0 && ch - '0' <= 9 ){ Integer a = Integer.valueOf(str); stack.push(a); } else{ if (stack.size() < 2) return 0; int num2 = stack.pop(); int num1 = stack.pop(); switch(ch){ case '+': stack.push(num1 + num2); break; case '-': stack.push(num1 - num2); break; case '*': stack.push(num1 * num2); break; case '/': stack.push(num1 / num2); break; } } }else{ int n = Integer.valueOf(str); stack.push(n); } } return stack.pop(); } TASK2.2 队列 2.2.1 用数组实现一个顺序队列 public class ArrayQueue<T> { private T [] data ; private int cnt;//元素个数 private int size;//队列长度 @SuppressWarnings("unchecked") public ArrayQueue(){ data =(T[]) new Object [10]; cnt = 0; size = 10; } @SuppressWarnings("unchecked") public ArrayQueue(int size){ data =(T[]) new Object [size]; cnt = 0; this.size = size; } public void add(T t){ if(cnt>=size){ throw new IllegalStateException(); } data[cnt]=t; cnt++; } public T remove(){ if(cnt<0){ throw new NoSuchElementException(); } T t= data[0]; data = Arrays.copyOfRange(data,0,size); cnt--; return t; } public boolean offer(T t){ if(cnt>=size){ return false; } data[cnt]=t; cnt++; return true; } public boolean pull(T t){ if(cnt<0){ return false; } data = Arrays.copyOfRange(data,0,size); cnt--; return true; } //返回队列头元素 public T element(){ return data[0]; } public boolean isEmpty(){ return cnt==0 ; } public boolean isFull(){ return cnt==size; } } 2.2.2 用链表实现一个链式队列 public class ListQueue<T> { private List<T> data ; private int cnt;//元素个数 private int size;//队列长度(用链表的话这里可以强行定义) public ListQueue(){ data =new LinkedList<T>(); cnt = 0; size = 10; } public void add(T t){ data.add(t); cnt++; } public T remove(){ if(cnt<0){ throw new NoSuchElementException(); } T t= data.remove(cnt); cnt--; return t; } public boolean offer(T t){ if(cnt>=size){ return false; } data.add(t); cnt++; return true; } public boolean pull(T t){ if(cnt<0){ return false; } data.remove(cnt); cnt--; return true; } //返回队列头元素 public T element(){ return data.get(0); } public boolean isEmpty(){ return cnt==0 ; } public boolean isFull(){ return cnt==size; } } 2.2.3 实现一个循环队列 public class MyCircularQueue { private final int capacity; private final int[] array; private int head = 0; private int tail = 0; private int count = 0; /** * Initialize your data structure here. Set the size of the queue to be k. */ public MyCircularQueue(int k) { this.capacity = k; this.array = new int[this.capacity]; } /** * Insert an element into the circular queue. Return true if the operation is successful. */ public boolean enQueue(int value) { //队列已满 if (count == capacity) { return false; } //队列为空, 重新设置头部 if (count == 0) { head = (head == capacity) ? 0 : head; tail = head; array[head] = value; count++; return true; } //队列未满 (有空位) if (tail == capacity - 1) { //tail 达到 maxIndex, 重置为 0 tail = 0; } else { //tail 未达到 maxIndex, tail++ tail++; } array[tail] = value; count++; return true; } /** * Delete an element from the circular queue. Return true if the operation is successful. */ public boolean deQueue() { if (count == 0) { //队列为空 return false; } count--; head++; return true; } /** * Get the front item from the queue. */ public int Front() { if (count == 0 ) { return -1; } return array[head]; } /** * Get the last item from the queue. */ public int Rear() { if (count == 0 ) { return -1; } return array[tail]; } /** * Checks whether the circular queue is empty or not. */ public boolean isEmpty() { return count == 0; } /** * Checks whether the circular queue is full or not. */ public boolean isFull() { return count == capacity; } } 2.2.4 练习 //Design Circular Deque（设计一个双端队列） class MyCircularDeque { public int k; public int[] numbers; public int head; public int tail; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque(int k) { numbers=new int[k+1]; head=0; tail=0; this.k=k; } /** Adds an item at the front of Deque. Return true if the operation is successful. */ public boolean insertFront(int value) { if(isFull()) return false; else{ head=(head+k)%(k+1); numbers[head]=value; return true; } } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ public boolean insertLast(int value) { if(isFull()) return false; else{ numbers[tail]=value; tail=(tail+1)%(k+1); return true; } } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ public boolean deleteFront() { if(isEmpty()) return false; else{ head=(head+1)%(k+1); return true; } } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast() { if(isEmpty()) return false; else{ tail=(tail+k)%(k+1); return true; } } /** Get the front item from the deque. */ public int getFront() { if(isEmpty()) return -1; return numbers[head]; } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return numbers[(tail+k)%(k+1)]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return tail==head; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (tail+1)%(k+1)==head; } } //Sliding Window Maximum（滑动窗口最大值） class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(k==0){ return new int[0]; } List<Integer> list = new ArrayList<>();//存放窗口内的数字 int max = Integer.MIN_VALUE;//窗口内的最大数字 for(int i = 0; i<k;i++){ if(max<nums[i]){ max = nums[i]; } list.add(nums[i]); } int[] res = new int[nums.length - k + 1];//要返回的结果数据 res[0] = max; for(int i = k; i < nums.length;i++){ int z =list.remove(0);//移走第一位数并插入新的一位数 list.add(nums[i]); if(z!=max){//移走的数不是max，只需判断max与新插入的数哪个大 if(nums[i]> max){ max = nums[i]; } res[i-k+1] = max; }else{//移走的数是max，重新判断列表中哪个数是最大的 if(!list.contains(max)){ max = Integer.MIN_VALUE; for(Integer num : list){ if(max<num){ max = num; } } }else{ if(nums[i]> max){ max = nums[i]; } } } res[i-k+1] = max; } return res; } } 3 递归 3.1 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2) public static int Fibe(int n){ if(n==1) return 1; if(n==2) return 1; return Fibe(n-1)+Fibe(n-2); } 3.2 编程实现求阶乘 n! public static int factorial(int n){ if(n==1) return 1; return factorial(n-1)*n; } 3.3 编程实现一组数据集合的全排列 class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { permition(nums, 0, nums.length-1); return res; } public void permition(int[] nums, int p, int q){ if(p==q){ res.add(arrayToList(nums)); } for(int i = p; i <= q; i++){ swap(nums, i, p); permition(nums, p+1, q); swap(nums, i,p); } } private List<Integer> arrayToList(int[] nums){ List<Integer> res = new ArrayList<>(); for(int i = 0; i < nums.length; i++){ res.add(nums[i]); } return res; } private void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } 3.4 练习 // Climbing Stairs（爬楼梯） //直接递归，但是直接递归leetcode竟然不能通过，于是又方法2 class Solution { public int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; return climbStairs(n-1)+climbStairs(n-2); } } //非递归放啊 class Solution { public int climbStairs(int n) { int [] ways = new int[n+1]; ways[0] = 0; for (int i = 1;i<ways.length;i++){ if (i < 3 ){ ways[i] = i; }else { ways[i] = ways[i-1] + ways[i-2]; } } return ways[n]; } }
-
发表了文章 2019-05-11
数据结构一：数据+链表 （Datawhale 系列）
Task1.1 数组 1.1.1实现一个支持动态扩容的数组 public class EnsureCapacityArray { private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; //传入固定值的情况 public EnsureCapacityArray(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //没有传入数组大小的情况 public EnsureCapacityArray() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容 * @param minCapacity */ public void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //数组容量最大的情况 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } } 1.1.2 实现一个大小固定的有序数组，支持动态增删改操作 这里理解，大小固定的有序数组，那也就是说数组大小和内部的元素个数完全相同。那么增的时候，需要扩容，删的时候，需要减容。然后数组有序，也就是说，改的时候需要重新排序。 public class FixedArray{ private static final int DEFAULT_SIZE = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULT_ELEMENTDATA = new Object[DEFAULT_SIZE]; transient Object[] elementData; private int size; public FixedArray(){ this.elementData=DEFAULT_ELEMENTDATA; } public FixedArray(int initialCapacity){ if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //保证增和删时数组长度和元素长度一致 private void ensureCapacityInternal(int minCapacity ){ if (minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; public void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //数组容量最大的情况 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //去掉删除之后，重新排序的，空的数组 public void trimToSize() { if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //判断数组长度 public int size(){ return size; } //判断数组是否为空 public boolean isEmpty() { return size == 0; } //排序 @SuppressWarnings("unchecked") private <E> void sort() { Arrays.sort((E[]) elementData, 0, size); } //添加 public <E> boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; sort(); return true; } //删除 public <E> boolean remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(); System.arraycopy(elementData, index+1, elementData, index, size-1); size--; trimToSize(); return true; } //改 public <E> boolean set(int index,Object e) { elementData[index] = e; sort(); return true; } //查 public Object get(int index) { return elementData[index]; } } 1.1.3 合并两个有序的数组 public static int[] mergeArrays(int[]a ,int[]b){ int alen=a.length; int blen=b.length; int aindex=0; int bindex=0; int [] re=new int[alen+blen]; for(int i=0;i<alen+blen;i++){ if(aindex<alen && bindex<blen){ re[i]=a[aindex] > b[bindex] ? b[bindex++] :a[aindex++]; continue; } if(aindex==alen && bindex<blen ) re[i]=b[bindex++]; if(bindex==blen &&aindex<alen) re[i]=a[aindex++]; } return re; } 1.1.4学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！ 哈希表 //两数之和 public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } //Happy Number(202) class Solution { public boolean isHappy(int n) { if(n==1) return true; while(n!=1 && n!=4){ int a=0; int ans=0; while(n>0){ a=n%10; ans+=a*a; n /=10; } n=ans; } if(n==1) return true; else return false; } } 1.1.5 练习 //Three Sum public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num); List<List<Integer>> res = new LinkedList<>(); for (int i = 0; i < num.length-2; i++) { if (i == 0 || (i > 0 && num[i] != num[i-1])) { int lo = i+1, hi = num.length-1, sum = 0 - num[i]; while (lo < hi) { if (num[lo] + num[hi] == sum) { res.add(Arrays.asList(num[i], num[lo], num[hi])); while (lo < hi && num[lo] == num[lo+1]) lo++; while (lo < hi && num[hi] == num[hi-1]) hi--; lo++; hi--; } else if (num[lo] + num[hi] < sum) lo++; else hi--; } } } return res; } //Majority Element public int majorityElement(int[] nums) { int res=0; int cnt=0; for(int num:nums){ if(cnt==0){ res=num; ++cnt; } else if(num == res) ++cnt; else --cnt; } return res; } //Missing Positive public int firstMissingPositive(int[] nums) { if(nums == null&&nums.length==0) return 1; int i; for(i=0;i<nums.length;i++){ if(nums[i] != i+1){ while(0<nums[i]&& nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){ int temp = nums[i]; nums[i] = nums[nums[i]-1]; nums[temp-1] = temp; } } } for(i=0;i<nums.length;i++) { if(nums[i]!=i+1) { return i+1; } } return i+1; } TASK1.2 链表 1.2.1 实现单链表、循环链表、双向链表，支持增删操作 //单链表 class singleNode{ public int data; public singleNode next; public singleNode head =null; public singleNode(int data){ this.data=data; } public void addNode(singleNode node){ singleNode newNode = new singleNode(data); if(head == null){ head = newNode; return; } singleNode temp = head; while(temp.next != null){ temp = temp.next; } temp.next = newNode; } public boolean removeNode(int index){ if(index<1 || index>length()){ return false; } if(index == 1){//删除头结点 head = head.next; return true; } singleNode preNode = head; singleNode curNode = preNode.next; int i = 1; while(curNode != null){ if(i==index){//寻找到待删除结点 preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点 return true; } //当先结点和前结点同时向后移 preNode = preNode.next; curNode = curNode.next; i++; } return true; } public int length(){ int length = 0; singleNode curNode = head; while(curNode != null){ length++; curNode = curNode.next; } return length; } } //双向链表 //单向循环链表类 public class CycleLinkList implements List { Node head; //头指针 Node current;//当前结点对象 int size;//结点个数 //初始化一个空链表 public CycleLinkList() { //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。 this.head = current = new Node(null); this.size =0;//单向链表，初始长度为零。 this.head.next = this.head; } //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。 //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域 public void index(int index) throws Exception { if(index <-1 || index > size -1) { throw new Exception("参数错误！"); } //说明在头结点之后操作。 if(index==-1) //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。 return; current = head.next; int j=0;//循环变量 while(current != head&&j<index) { current = current.next; j++; } } @Override public void delete(int index) throws Exception { // TODO Auto-generated method stub //判断链表是否为空 if(isEmpty()) { throw new Exception("链表为空，无法删除！"); } if(index <0 ||index >size) { throw new Exception("参数错误！"); } index(index-1);//定位到要操作结点的前一个结点对象。 current.setNext(current.next.next); size--; } @Override public Object get(int index) throws Exception { // TODO Auto-generated method stub if(index <-1 || index >size-1) { throw new Exception("参数非法！"); } index(index); return current.getElement(); } @Override public void insert(int index, Object obj) throws Exception { // TODO Auto-generated method stub if(index <0 ||index >size) { throw new Exception("参数错误！"); } index(index-1);//定位到要操作结点的前一个结点对象。 current.setNext(new Node(obj,current.next)); size++; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size==0; } @Override public int size() { // TODO Auto-generated method stub return this.size; } } //双向循环链表 //单向链表类 public class DoubleCycleLinkList implements List { Node head; //头指针 Node current;//当前结点对象 int size;//结点个数 //初始化一个空链表 public DoubleCycleLinkList() { //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。 this.head = current = new Node(null); this.size = 0;//单向链表，初始长度为零。 this.head.next = head; this.head.prior = head; } //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。 public void index(int index) throws Exception { if (index < -1 || index > size - 1) { throw new Exception("参数错误！"); } //说明在头结点之后操作。 if (index == -1) return; current = head.next; int j = 0;//循环变量 while (current != head && j < index) { current = current.next; j++; } } @Override public void delete(int index) throws Exception { // TODO Auto-generated method stub //判断链表是否为空 if (isEmpty()) { throw new Exception("链表为空，无法删除！"); } if (index < 0 || index > size) { throw new Exception("参数错误！"); } index(index - 1);//定位到要操作结点的前一个结点对象。 current.setNext(current.next.next); current.next.setPrior(current); size--; } @Override public Object get(int index) throws Exception { // TODO Auto-generated method stub if (index < -1 || index > size - 1) { throw new Exception("参数非法！"); } index(index); return current.getElement(); } @Override public void insert(int index, Object obj) throws Exception { // TODO Auto-generated method stub if (index < 0 || index > size) { throw new Exception("参数错误！"); } index(index - 1);//定位到要操作结点的前一个结点对象。 current.setNext(new Node(obj, current.next)); current.next.setPrior(current); current.next.next.setPrior(current.next); size++; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size == 0; } @Override public int size() { // TODO Auto-generated method stub return this.size; } } 1.2.2 实现单链表反转 public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; } 1.2.3 实现两个有序的链表合并为一个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } } 1.2.4 实现求链表的中间结点 public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode low=head; while(fast != null && fast.next != null){ low = low.next; fast= fast.next.next; } return low; } 1.2.5 练习 //Linked List Cycle I（环形链表） public boolean hasCycle(ListNode head) { ListNode f=head; ListNode s=head; if(head == null || head.next == null) return false; while(f!=null && f.next!=null){ f=f.next.next; s=s.next; if(f == s) return true; } return false; } //Merge k Sorted Lists（合并 k 个排序链表） public ListNode mergeKLists(ListNode[] lists){ if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2){ return mergeTwoLists(lists[0],lists[1]); } int mid = lists.length/2; ListNode[] l1 = new ListNode[mid]; for(int i = 0; i < mid; i++){ l1[i] = lists[i]; } ListNode[] l2 = new ListNode[lists.length-mid]; for(int i = mid,j=0; i < lists.length; i++,j++){ l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1),mergeKLists(l2)); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = null; if (l1.val <= l2.val){ head = l1; head.next = mergeTwoLists(l1.next, l2); } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; }
滑动查看更多
暂无更多信息
-
发表了文章
2019-05-24
数据结构六：图（DataWhale系列）
-
发表了文章
2019-05-18
数据结构四：散列表+字符串（DataWhale系列）
-
发表了文章
2019-05-17
数据结构三：排序+二分查找（DataWhale系列）
-
发表了文章
2019-05-12
数据结构二：栈+队列+递归（DataWhale系列）
-
发表了文章
2019-05-11
数据结构一：数据+链表 （Datawhale 系列）
-
发表了文章
2019-04-08
sql练习三（DataWhale 系列-最终）
-
发表了文章
2019-03-31
SQL练习一（Datawhale系列）
-
发表了文章
2019-03-28
mysql优化
-
发表了文章
2018-11-01
Java学习----Collection总结
滑动查看更多
-
提交了问题
2018-12-14
[@徐雷frank][¥20]ThreadLocal 这个为啥理解起来迷迷糊糊得?
-
提交了问题
2018-12-14
[@徐雷frank][¥20]java如何优化上万条数据修改
-
提交了问题
2018-12-14
[@徐雷frank][¥20]有没有好用的代码生成器，可以生成controller 的 （Java）
-
提交了问题
2018-12-14
[@徐雷frank][¥20]springboot+mybatis企业开发模版
-
提交了问题
2018-12-14
[@徐雷frank][¥20]SpringCloud 隔一段时间去调用服务就返回 read time out
-
提交了问题
2018-12-14
[@炯轩][¥20]JAVA中如何生成多标题结构的word？？
-
提交了问题
2018-12-14
[@倚贤][¥20]小程序商品列表加载图特别的慢怎么解决？
-
提交了问题
2018-12-14
[@倚贤][¥20]数据库设计
-
提交了问题
2018-12-14
[@徐雷frank][¥20]centos7设置mysql自启动的配置文件中[Service] User=mysql Group=mysql，user和group这边的mysql是指的什么？centos的登录用户名？
-
提交了问题
2018-12-14
[@炯轩][¥20]通过mybatis插入mysql上万条数据，代码停在插入方法不继续往下运行
-
提交了问题
2018-12-14
[@徐雷frank][¥20]vmware 使用docker部署的mysql 在vmware挂起在运行后无法连接
-
提交了问题
2018-12-14
[@炯轩][¥20]请问后台和APP之间的接口通信怎么实现用户身份验证
-
提交了问题
2018-12-14
[@炯轩][¥20]Android多进程能否单独开辟一个进程进行图片处理
-
提交了问题
2018-12-14
[@炯轩][¥20]安卓的通话记录究竟是存放在哪个数据库表里面？
-
提交了问题
2018-12-14
[@炯轩][¥20]android 双摄像头开发
-
提交了问题
2018-12-14
[@炯轩][¥20]Android使用zxing二维码框架时候构建apk文件出现的错误
-
提交了问题
2018-12-14
[@炯轩][¥20]移动跨平台APP开发，什么框架比较好？
-
提交了问题
2018-12-14
[@炯轩][¥20]请问，从Android开发到线上过程是什么，比如有了好的安装包后怎么放到阿里云，怎么审核等
-
提交了问题
2018-12-14
[@炯轩][¥20]如何通过基站定位获取地址候选集？
-
提交了问题
2018-12-14
[@炯轩][¥20]离线地图加载问题 高德地图
滑动查看更多