晓生寒_个人页_阿里云开发者社区

发表了文章 2019-05-27

数据结构七：递归+动规+分治+回溯

Datawhale 系列数据结构本文参考链接：01背包问题：https://blog.csdn.net/chanmufeng/article/details/82955730 Task7.1 递归 7.1.1爬楼梯 //爬楼梯： //假设你正在爬楼梯。需要 n 阶你才能到达楼顶 //每次你可以爬 1 或 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]; } } //使用最小花费爬楼梯 //数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。 //每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 //您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 class Solution { public int minCostClimbingStairs(int[] cost) { int length = cost.length; int[] newCost = new int[length+1]; newCost = Arrays.copyOf(cost,length+1); length = length+1; cost = newCost; int[] fn = new int[length]; fn[0] = 0; fn[1] = 0; fn[2] = Math.min(cost[0],cost[1]); for (int i = 3;i<length;i++){ fn[i] = Math.min(fn[i-1] + cost[i-1],fn[i-2]+cost[i-2]); } return fn[length-1]; } } 7.1.2 0-1背包问题（递归方法解决）问题描述：给定 n 种物品重量$ w_1,w_2,w_3,...,w_n $,价值为$v_1,v_2,v_3,...,v_4$，一个容量为$C$的背包，问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？递归思想：首先我们用递归的方式来尝试解决这个问题我们用$F(n,C)$ 表示将前$n$个物品放进容量为$C$的背包里，得到最大的价值。我们用自顶向下的角度来看，假如我们已经进行到了最后一步（即求解将$n$个物品放到背包了获得最大价值），此时我们便有两种选择： 1.不放第$n$个物品，此时总价值为$F(n-1,C)$ 2.放置第$n$个物品，此时总价值为$v_n+F(n-1,C-w_n)$ 两种选择中总价值最大的方案就是我们的最终方案，递推式如下： $F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))$ //递归解法 public static int solveKS(int[] w,int[] v,int index,int capacity ){ if(index<0 || capacity <=0) return 0; int res = solveKS(w,v,index-1,capacity); if(w[index]<=capacity){ res=Math.max(res, v[index]+solveKS(w,v,index-1,capacity-w[index])); } return res; } public static int knapSack(int [] w,int [] v,int C){ int size=w.length; return solveKS(w,v,size-1,C); } Task 7.2 回溯 7.2.1八皇后问题 public static int [][] array=new int[8][8]; public static int map=0; public static void main(String[] args) { System.out.println("八皇后问题"); findQueen(0); System.out.println("八皇后问题共有："+map+"种可能"); } public static void findQueen(int i){ if(i>7){ map++; print();// return; } for(int m=0;m<8;m++){ if(check(i,m)){ array[i][m]=1; findQueen(i+1); array[i][m]=0; } } } public static boolean check(int k, int j){ for(int i=0;i<8;i++){//检查行列冲突 if(array[i][j]==1){ return false; } } for(int i=k-1,m=j-1;i>=0&& m>=0;i--,m--){ if(array[i][m]==1){//检查左对角线冲突 return false; } } for(int i=k-1,m=j+1;i>=0&&m<=7;i--,m++){ if(array[i][m]==1){ return false; } } return true; } public static void print(){ System.out.print("方案"+map+":"+"\n"); for(int i=0;i<8;i++){ for(int m=0;m<8;m++){ if(array[i][m]==1){ //System.out.print("皇后"+(i+1)+"在第"+i+"行，第"+m+"列\t"); System.out.print("o "); } else{ System.out.print("+ "); } } System.out.println(); } System.out.println(); } 7.2.2求解0-1背包问题（回溯方法解决）整体思路：用回溯法需要构造子集树。对于每一个物品i,对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一颗空间树：基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案算法设计：利用回溯设计一个算法求出0-1背包问题的解，也就是求出一个解向量xi(即对n个物品放或不妨的一种的方案) 其中，（xi=0或1，xi=0表示物体i不放入背包，xi=1表示把物体i放入背包）。在递归函数Backtrack中，当i>n时，算法搜索到叶子节点，得到一个新的物品包装方案。此时算法适时更新当前的最有价值。当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树 //回溯 public class KnapSack02 { private static int n=3;//物品数量编号，从0开始 private static double c=5;//背包容量 private static double [] v={12,10,20,15};//各个物品的价值 private static double [] w={2,1,3,2};//各个物品的重量 private static double cw = 0.0;//当前背包重量　current weight private static double cp = 0.0;//当前背包中物品总价值　current value private static double bestp = 0.0;//当前最优价值best price private static double [] perp = new double [4];//单位物品价值(排序后) per price private static int [] order = new int [4];//物品编号 private static int [] put = new int [4];//设置是否装入，1装入，0不装 //按单位价值排序 public static void knapsack(){ int i,j; int temporder = 0; double temp= 0.0; for(i=1;i<=n;i++) perp[i]=v[i]/w[i]; for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j++) if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[] { temp = perp[i]; //冒泡对perp[]排序 perp[i]=perp[i]; perp[j]=temp; temporder=order[i];//冒泡对order[]排序 order[i]=order[j]; order[j]=temporder; temp = v[i];//冒泡对v[]排序 v[i]=v[j]; v[j]=temp; temp=w[i];//冒泡对w[]排序 w[i]=w[j]; w[j]=temp; } } } public static void backtrack(int i){ //i表示到达的层数（第几步，从0开始），同事也只是当前选择玩了几个物品 bound( i); if(i>n){ bestp=cp; return; } //如若左子节点可行，则直接搜索左子树; //对于右子树，先计算上界函数，以判断是否将其减去 if(cw+w[i]<=c)//将物品i放入背包,搜索左子树 { cw+=w[i];//同步更新当前背包的重量 cp+=v[i];//同步更新当前背包的总价值 put[i]=1; backtrack(i+1);//深度搜索进入下一层 cw-=w[i];//回溯复原 cp-=v[i];//回溯复原 } if(bound(i+1)>bestp)//如若符合条件则搜索右子树 backtrack(i+1); } //计算上界函数，功能为剪枝 public static double bound(int i) { //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值 double leftw= c-cw;//剩余背包容量 double b = cp;//记录当前背包的总价值cp,最后求上界 //以物品单位重量价值递减次序装入物品 while(i<=n && w[i]<=leftw) { leftw-=w[i]; b+=v[i]; i++; } //装满背包 if(i<=n) b+=v[i]/w[i]*leftw; return b;//返回计算出的上界 } public static void main(String[] args) { knapsack(); backtrack(1); System.out.println(bestp); } } Task7.3 分治 7.3.1 利用分治算法求一组数据的逆序对个数 public class ReverseOrder { private static int sum = 0; private static int []a ={5,4,2,6,3,1}; private static int []b =new int [6]; public static void worksort(int l,int r){ int mid,tmp,i,j; if(r>l+1){ mid=(l+r)/2; worksort(l,mid-1); worksort(mid,r); tmp=l; for(i=l,j=mid;i<=mid-1 && j<=r;){ if(a[i]>a[j]) { b[tmp++]=a[j++];//快速排序 sum+=mid-i;//统计逆序对个数 } else b[tmp++]=a[i++]; } if(j<=r) for(;j<=r;j++) b[tmp++]=a[j]; else for(;i<=mid-1;i++) b[tmp++]=a[i]; for(i=l;i<=r;i++) a[i]=b[i];//将排好序的b数组赋值给a数组 }else{ if(l+1==r)//递归的边界 if(a[l]>a[r]) { int temp = a[l]; a[l]=a[r]; a[r]=temp; sum++; } } } public static void main(String[] args) { worksort(0,5); System.out.println(sum); } } Task 7.4 动态规划 7.4.1 0-1背包问题 //动态规划 int size = w.length; if (size == 0) { return 0; } int[] dp = new int[C + 1]; //初始化第一行 //仅考虑容量为C的背包放第0个物品的情况 for (int i = 0; i <= C; i++) { dp[i] = w[0] <= i ? v[0] : 0; } for (int i = 1; i < size; i++) { for (int j = C; j >= w[i]; j--) { dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]); } } return dp[C]; } public static void main(String[] args) { int[] w = {2, 1, 3, 2}; int[] v = {12, 10, 20, 15}; System.out.println(knapSack(w, v, 5)); } 7.4.2 编程实现莱温斯坦最短编辑距离 public static int minEditDistance(String dest,String src){ int [][] f=new int[dest.length()+1][src.length()+1]; f[0][0]=0; for(int i=1;i<dest.length()+1;i++){ f[i][0]=i; } for(int i=1;i<src.length()+1;i++){ f[0][i]=i; } for(int i=1;i<dest.length()+1;i++){ for(int j=1;j<src.length()+1;j++){ int cost=0; if(dest.charAt(i - 1) != src.charAt(j - 1)){ cost=1; } int minCost; if(f[i-1][j]<f[i][j-1]){ minCost=f[i-1][j]+cost; }else{ minCost=f[i][j-1]+cost; } f[i][j]=minCost; } } return f[dest.length()][src.length()]; } public static void main(String[] args) { System.out.println(minEditDistance("sot", "stop")); } 7.4.3 编程实现查找两个字符串的最长子序列 //求解str1 和 str2 的最长公共子序列 public static int LCS(String str1, String str2){ int[][] c = new int[str1.length() + 1][str2.length() + 1]; for(int row = 0; row <= str1.length(); row++) c[row][0] = 0; for(int column = 0; column <= str2.length(); column++) c[0][column] = 0; for(int i = 1; i <= str1.length(); i++) for(int j = 1; j <= str2.length(); j++) { if(str1.charAt(i-1) == str2.charAt(j-1)) c[i][j] = c[i-1][j-1] + 1; else if(c[i][j-1] > c[i-1][j]) c[i][j] = c[i][j-1]; else c[i][j] = c[i-1][j]; } return c[str1.length()][str2.length()]; } //test public static void main(String[] args) { String str1 = "BDCABA"; String str2 = "ABCBDAB"; int result = LCS(str1, str2); System.out.println(result); } 7.4.4编程实现一个数据序列的最长递增子序列 class Solution { public int lengthOfLIS(int[] nums) { /** dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数. 由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度. 对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置: 1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp 数组尾部, 并将最长递增序列长度maxL加1 2. dp[i-1] < num <= dp[i], 只更新相应的dp[i] **/ int maxL = 0; int[] dp = new int[nums.length]; for(int num : nums) { // 二分法查找, 也可以调用库函数如binary_search int lo = 0, hi = maxL; while(lo < hi) { int mid = lo+(hi-lo)/2; if(dp[mid] < num) lo = mid+1; else hi = mid; } dp[lo] = num; if(lo == maxL) maxL++; } return maxL; } } Task 7.5 练习 7.5.1 实战递归 //Letter Combinations of a Phone Number(17) String[] button=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; List<String> list=new ArrayList<>(); public List<String> letterCombinations(String digits) { if (digits==null||digits.length()==0) return list; letterCombinations(digits,0,new String()); return list; } public void letterCombinations(String digits,int index,String temp) { if(index==digits.length()){ list.add(temp); return; } int position=digits.charAt(index)-'0'; String str=button[position]; for (int i=0;i<str.length();i++){ letterCombinations(digits,index+1,temp+str.charAt(i)); } } //permutations(46) List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { permutation(nums, 0, nums.length - 1); return res; } private void permutation(int[] nums, int p, int q) { if (p == q) { res.add(arrayToList(nums)); } for (int i = p; i <= q; i++) { swap(nums, i, p); permutation(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; } 7.5.2 实战dp //完成0-1背包问题实现(自我实现)及Leetcode 参考7.4.1 //Palindrome Partitioning II(132) public int minCut(String s) { if(s == null || s.isEmpty()){ return 0; } int len = s.length(); boolean[][] dp = new boolean[s.length()][s.length()]; int[] cut = new int[s.length()]; for(int i = 0; i < len; i++){ //最大划分就是i次 cut[i]= i; for(int j = 0; j <= i; j++){ if(s.charAt(i) == s.charAt(j) &&(i-j <= 1 || dp[j+1][i-1])){ dp[j][i] = true; if(j == 0) { //0-i直接是回文 cut[i] = 0; } else { cut[i] = Math.min(cut[j-1]+1, cut[i]); } } } } return cut[len-1]; } 7.5.2 可选练习 //Regular Expression Matching（正则表达式匹配） class Solution { public boolean isMatch(String text, String pattern) { if (pattern.isEmpty()) return text.isEmpty(); boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')); if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))); } else { return first_match && isMatch(text.substring(1), pattern.substring(1)); } } } //Minimum Path Sum（最小路径和） public int minPathSum(int[][] grid) { int rows=grid.length; int cols=grid[0].length; int [] dp=new int[cols]; dp[0]=grid[0][0]; for(int col=1;col<cols;col++){ dp[col]=dp[col-1]+grid[0][col]; } for(int row = 1; row < rows; row++) { for(int col = 0; col < cols; col++) { if(col > 0){ dp[col] = Math.min(dp[col-1], dp[col]) + grid[row][col]; }else{ dp[col] += grid[row][col]; } } } return dp[cols - 1]; } //Coin Change （零钱兑换）[作为可选] //Best Time to Buy and Sell Stock（买卖股票的最佳时机）[作为可选] //Maximum Product Subarray（乘积最大子序列）[作为可选] //Triangle（三角形最小路径和）[作为可选]

发表了文章 2019-05-24

数据结构六：图（DataWhale系列）

Datawhale 系列数据结构 Task6 图图，基本概念： ![1120165-20180209213532810-1976605857](D:\workspace_kattle\pictures-md\1120165-20180209213532810-1976605857.png) 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-21

数据结构五：树+堆（DataWhale系列）

Datawhale 系列数据结构这一部分内容大多参考网上前辈的分享，由于，当时没有保存浏览记录，所以找不到链接。如果侵权，联系我删除，或者加您的原帖链接在头部。谢谢！！！ Task5.1树 5.1.1实现一个二叉查找树（支持插入，删除，查找操作） public class BSTree<T extends Comparable<T>> { private BSTNode<T> mRoot; // 根结点 @SuppressWarnings("hiding") public class BSTNode<T extends Comparable<T>> { T key; // 关键字(键值) BSTNode<T> left; // 左孩子 BSTNode<T> right; // 右孩子 BSTNode<T> parent; // 父结点 public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) { this.key = key; this.parent = parent; this.left = left; this.right = right; } public T getKey() { return key; } public String toString() { return "key:"+key; } } public BSTree() { mRoot=null; } /* * 前序遍历"二叉树" */ private void preOrder(BSTNode<T> tree) { if(tree != null) { System.out.print(tree.key+" "); preOrder(tree.left); preOrder(tree.right); } } public void preOrder() { preOrder(mRoot); } /* * 中序遍历"二叉树" */ private void inOrder(BSTNode<T> tree) { if(tree != null) { inOrder(tree.left); System.out.print(tree.key+" "); inOrder(tree.right); } } public void inOrder() { inOrder(mRoot); } /* * 后序遍历"二叉树" */ private void postOrder(BSTNode<T> tree) { if(tree != null) { postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+" "); } } public void postOrder() { postOrder(mRoot); } /* * (递归实现)查找"二叉树x"中键值为key的节点 */ private BSTNode<T> search(BSTNode<T> x, T key) { if (x==null) return x; int cmp = key.compareTo(x.key); if (cmp < 0) return search(x.left, key); else if (cmp > 0) return search(x.right, key); else return x; } public BSTNode<T> search(T key) { return search(mRoot, key); } /* * (非递归实现)查找"二叉树x"中键值为key的节点 */ private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) { while (x!=null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else return x; } return x; } public BSTNode<T> iterativeSearch(T key) { return iterativeSearch(mRoot, key); } /* * 查找最小结点：返回tree为根结点的二叉树的最小结点。 */ private BSTNode<T> minimum(BSTNode<T> tree) { if (tree == null) return null; while(tree.left != null) tree = tree.left; return tree; } public T minimum() { BSTNode<T> p = minimum(mRoot); if (p != null) return p.key; return null; } /* * 查找最大结点：返回tree为根结点的二叉树的最大结点。 */ private BSTNode<T> maximum(BSTNode<T> tree) { if (tree == null) return null; while(tree.right != null) tree = tree.right; return tree; } public T maximum() { BSTNode<T> p = maximum(mRoot); if (p != null) return p.key; return null; } /* * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。 */ public BSTNode<T> successor(BSTNode<T> x) { // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。 if (x.right != null) return minimum(x.right); // 如果x没有右孩子。则x有以下两种可能： // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 BSTNode<T> y = x.parent; while ((y!=null) && (x==y.right)) { x = y; y = y.parent; } return y; } /* * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。 */ public BSTNode<T> predecessor(BSTNode<T> x) { // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x.left != null) return maximum(x.left); // 如果x没有左孩子。则x有以下两种可能： // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 BSTNode<T> y = x.parent; while ((y!=null) && (x==y.left)) { x = y; y = y.parent; } return y; } /* * 将结点插入到二叉树中 * * 参数说明： * tree 二叉树的 * z 插入的结点 */ private void insert(BSTree<T> bst, BSTNode<T> z) { int cmp; BSTNode<T> y = null; BSTNode<T> x = bst.mRoot; // 查找z的插入位置 while (x != null) { y = x; cmp = z.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; } z.parent = y; if (y==null) bst.mRoot = z; else { cmp = z.key.compareTo(y.key); if (cmp < 0) y.left = z; else y.right = z; } } /* * 新建结点(key)，并将其插入到二叉树中 * * 参数说明： * tree 二叉树的根结点 * key 插入结点的键值 */ public void insert(T key) { BSTNode<T> z=new BSTNode<T>(key,null,null,null); // 如果新建结点失败，则返回。 if (z != null) insert(this, z); } /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * bst 二叉树 * z 删除的结点 */ private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) { BSTNode<T> x=null; BSTNode<T> y=null; if ((z.left == null) || (z.right == null) ) y = z; else y = successor(z); if (y.left != null) x = y.left; else x = y.right; if (x != null) x.parent = y.parent; if (y.parent == null) bst.mRoot = x; else if (y == y.parent.left) y.parent.left = x; else y.parent.right = x; if (y != z) z.key = y.key; return y; } /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * tree 二叉树的根结点 * z 删除的结点 */ public void remove(T key) { BSTNode<T> z, node; if ((z = search(mRoot, key)) != null) if ( (node = remove(this, z)) != null) node = null; } /* * 销毁二叉树 */ private void destroy(BSTNode<T> tree) { if (tree==null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; } public void clear() { destroy(mRoot); mRoot = null; } /* * 打印"二叉查找树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(BSTNode<T> tree, T key, int direction) { if(tree != null) { if(direction==0) // tree是根节点 System.out.printf("%2d is root\n", tree.key); else // tree是分支节点 System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left"); print(tree.left, tree.key, -1); print(tree.right,tree.key, 1); } } public void print() { if (mRoot != null) print(mRoot, mRoot.key, 0); } } 5.1.2 实现查找二叉查找树中某个节点的后继，前驱节点 /** * 前驱元素 * **/ public BSTreeNode<T> Pred(BSTreeNode<T> node) { if (node.left != null) { return Max(node.left); } BSTreeNode<T> parent = node.parent; while (parent != null && node != parent.right) { node = parent; parent = node.parent; } return parent; } /** * 后继元素 * **/ public BSTreeNode<T> Succ(BSTreeNode<T> node) { if (node.right != null) { return Min(node.right); } BSTreeNode<T> parent = node.parent; while (parent != null && node != parent.left) { node = parent; parent = node.parent; } return parent; } 5.1.3 实现二叉树前，中，后序以及层次遍历 /* *在5.1.1中已经实现 */ 5.1.4 练习：翻转二叉树 class Solution{ public TreeNode invertTree(TreeNode root){ if(root==null) return root; TreeNode temp=root.left; root.left=root.right; root.right=temp; invertTree(root.left); invertTree(root.right); return root; } } 5.1.5 二叉树的最大深度 class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; return 1+Math.max(maxDepth(root.left),maxDepth(root.right)); } 5.1.6 验证二叉查找树 class Solution { private TreeNode pre = null; public boolean isValidBST(TreeNode root) { return helper(root); } private boolean helper(TreeNode root){ if(root == null) return true; if(!helper(root.left)) return false; if(pre != null && pre.val >= root.val) return false; pre = root; return helper(root.right); } } TASK5.2 堆 5.2.1 实现一个小顶堆，大顶堆 public class MaxHeap<T extends Comparable<T>> { private List<T> mHeap; // 存放元素的动态数组 public MaxHeap() { this.mHeap = new ArrayList<>(); } /** * 大顶堆的向上调整算法(添加节点的时候调用) 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。 * * @param start * -- 被上调节点的起始位置(一般为数组中最后一个元素的索引) */ protected void filterup(int start) { int c = start; // 需要调整的节点的初始位置 int p = (c - 1) / 2; // 当前节点的父节点的位置 T tmp = mHeap.get(c); // 被调整节点的值 while (c > 0) { // 父节点的值和被调整节点的值进行比较 int cmp = mHeap.get(p).compareTo(tmp); if (cmp >= 0) { // 父节点大 break; } else { // 被调整节点的值大，交换 mHeap.set(c, mHeap.get(p)); c = p; p = (c - 1) / 2; } } // 找到被调整节点的最终位置了 mHeap.set(c, tmp); } /** * 大顶堆的向下调整算法(删除节点的时候需要调用来调整大顶堆) * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。 * * @param start * -- 被下调节点的起始位置(一般为0，表示从第1个开始) * @param end * -- 截至范围(一般为数组中最后一个元素的索引) */ protected void filterdown(int start, int end) { int c = start; // 被下调节点的初始位置 int l = 2 * c + 1; // 左孩子节点的位置 T tmp = mHeap.get(c); // 当前节点的值(大小) while (l <= end) { // 当前节点的左右节点进行比较 int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // 取大的 if (l < end && cmp < 0) { l++; } // 当前节点和大的那个再比较一下 cmp = tmp.compareTo(mHeap.get(l)); if (cmp >= 0) { // 当前节点大,不用动 break; } else { // 当前节点小,交换 mHeap.set(c, mHeap.get(l)); c = l; // 更新当前节点的位置 l = 2 * c + 1; // 更新当前节点的左孩子位置 } } mHeap.set(c, tmp); } /** * 向大顶堆中插入新元素 * * @param data */ public void insert(T data) { int insertIndex = mHeap.size(); // 获取插入的位置 // 将新元素插入到数组尾部 mHeap.add(data); // 调用filterup函数，调整大顶堆 filterup(insertIndex); } /** * 删除大顶堆中的data节点 * * @param data * @return 返回-1表示出错, 返回0表示删除成功 */ public int remove(T data) { // 大顶堆空 if (mHeap.isEmpty()) { return -1; } // 获取data在数组中的索引 int index = mHeap.indexOf(data); if (index == -1) { return -1; } // 堆中元素的个数 int size = mHeap.size(); // 删除了data元素，需要用最后一个元素填补，然后调用filterdown算法进行调整 mHeap.set(index, mHeap.get(size - 1)); // 用最后一个元素填补 mHeap.remove(size - 1); // 删除最后一个元素 if (mHeap.size() > 1 && index < mHeap.size()) { // 调整成大顶堆 filterdown(index, mHeap.size() - 1); } return 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for(int i = 0; i < mHeap.size(); i++) { sb.append(mHeap.get(i) + " "); } return sb.toString(); } public static void main(String[] args) { int a[] = {10, 40 ,30, 60, 90, 70, 20, 50 ,80}; //大顶堆 MaxHeap<Integer> maxHeap = new MaxHeap<>(); //添加元素 System.out.println("=== 依次添加元素："); for(int i = 0; i < a.length; i++) { System.out.println(a[i]); maxHeap.insert(a[i]); } //生成的大顶堆 System.out.println("=== 生成的大顶堆："); System.out.println(maxHeap); //添加新元素85 int data = 85; maxHeap.insert(data); System.out.println("=== 添加新元素" + data + "之后的大顶堆："); System.out.println(maxHeap); //删除元素90 data = 90; maxHeap.remove(data); System.out.println("=== 删除元素" + data + "之后的大顶堆："); System.out.println(maxHeap); } } 5.2.2 实现优先级队列 /** * 优先队列类（最大优先队列） */ public class PriorityHeap { // ------------------------------ Instance Variables private int[] arr; private int size; // ------------------------------ Constructors /** * 优先队列数组默认大小为64 */ public PriorityHeap() { this(64); } public PriorityHeap(int initSize) { if (initSize <= 0) { initSize = 64; } this.arr = new int[initSize]; this.size = 0; } // ------------------------------ Public methods public int max() { return this.arr[0]; } public int maxAndRemove() { int t = max(); this.arr[0] = this.arr[--size]; sink(0, this.arr[0]); return t; } public void add(int data) { resize(1); this.arr[size++] = data; pop(size - 1, data); } // ------------------------------ Private methods /** * key下沉方法 */ private void sink(int i, int key) { while (2 * i <= this.size - 1) { int child = 2 * i; if (child < this.size - 1 && this.arr[child] < this.arr[child + 1]) { child++; } if (this.arr[i] >= this.arr[child]) { break; } swap(i, child); i = child; } } /** * key上浮方法 */ private void pop(int i, int key) { while (i > 0) { int parent = i / 2; if (this.arr[i] <= this.arr[parent]) { break; } swap(i, parent); i = parent; } } /** * 重新调整数组大小 */ private void resize(int increaseSize) { if ((this.size + increaseSize) > this.arr.length) { int newSize = (this.size + increaseSize) > 2 * this.arr.length ? (this.size + increaseSize) : 2 * this.arr.length; int[] t = this.arr; this.arr = Arrays.copyOf(t, newSize); } } /** * Swaps arr[a] with arr[b]. */ private void swap(int a, int b) { int t = this.arr[a]; this.arr[a] = this.arr[b]; this.arr[b] = t; } } 5.2.3 实现堆排序 /*堆排序分为三个步骤： * 创建最大堆 * 确保最大堆中父节点的值比子节点的值都大 * 将根节点与最后一个叶子节点比较，择其大者剔除出堆，再重复第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); } } } 5.2.4 利用有限集队列合并K个有序数组 class Solution { 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; } } 5.2.5 ：求一组动态数据集合的最大Top K /* *不太明白这道题的具体意思，如果是需要求一组数据的Top K, *那直接，最大堆排序，然后取TopK加入到一个list中返回，就行 */ 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 List 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); } } List list=new ArrayList(); for(int i =0;i<k;i++){ list.add(array[i]) } return list; } 5.2.6 练习：路径总和 class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; int t=sum-root.val; if(root.left==null && root.right==null) return t==0 ? true : false; return hasPathSum(root.left,t) || hasPathSum(root.right,t); } }

发表了文章 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-04-08

sql练习三（DataWhale 系列-最终）

4.1 MySQL 实战学习内容数据导入导出将之前创建的任意一张MySQL表导出,且是CSV格式再将CSV表导入数据库作业项目七: 各部门工资最高的员工（难度：中等）创建 Employee 表，包含所有员工信息，每个员工有其对应的 Id, salary 和 department Id。 Id Name Salary DepartmentId 1 Joe 70000 1 2 Henry 80000 2 3 Sam 60000 2 4 Max 90000 1 创建 Department 表，包含公司所有部门的信息。 Id Name 1 IT 2 Sales 编写一个 SQL 查询，找出每个部门工资最高的员工。例如，根据上述给定的表格，Max 在 IT 部门有最高工资，Henry 在 Sales 部门有最高工资。 Department Employee Salary IT Max 90000 Sales Henry 80000 答案 ---建表--- CREATE TABLE Employee(Id INT, NAME VARCHAR(10), Salary INT, DepartmentId INT); CREATE TABLE Department(Id INT, NAME VARCHAR(10)); ---插值--- INSERT INTO Employee VALUES (1,'Joe',70000,1), (2,'Henry',80000,2), (3,'Sam',60000,2), (4,'Max',90000,1); INSERT INTO Department VALUES(1,'IT'),(2,'Sales'); ---查找--- ---查找部门最高工资--- SELECT d.Name AS Department,e.name AS Employee,e.Salary FROM Employee e LEFT JOIN department d ON e.DepartmentId=d.Id WHERE e.Salary=(SELECT MAX(Salary) FROM Employee WHERE DepartmentId=d.Id); ---查找部门工资最高前三--- SELECT Department.Name AS Department, e1.Name AS Employee, e1.Salary AS Salary FROM Employee e1 JOIN Department ON e1.DepartmentId = Department.Id WHERE 3 > ( SELECT COUNT(DISTINCT e2.Salary) FROM Employee e2 WHERE e2.Salary > e1.Salary AND e1.DepartmentId = e2.DepartmentId ) ORDER BY Department.Name, e1.Salary DESC 项目八: 换座位（难度：中等）小美是一所中学的信息科技老师，她有一张 seat 座位表，平时用来储存学生名字和与他们相对应的座位 id。其中纵列的 id 是连续递增的小美想改变相邻俩学生的座位。你能不能帮她写一个 SQL query 来输出小美想要的结果呢？请创建如下所示 seat 表：示例： id student 1 Abbot 2 Doris 3 Emerson 4 Green 5 Jeames 假如数据输入的是上表，则输出结果如下： id student 1 Doris 2 Abbot 3 Green 4 Emerson 5 Jeames 注意：如果学生人数是奇数，则不需要改变最后一个同学的座位。 ---建表插值--- CREATE TABLE seat(id INT,Student VARCHAR(10)); INSERT INTO seat VALUES(1,'Abbot'), (2,'Doris'), (3,'Emerson'), (4,'Green'), (5,'Jeames'); ---转换座位--- SELECT( CASE WHEN id %2 = 1 AND id!=max_id THEN id+1 WHEN id %2 = 0 THEN id-1 WHEN id = max_id THEN id END) AS id,student FROM(SELECT id, student, (SELECT MAX(id) FROM seat) AS max_id FROM seat) a ORDER BY id; 项目九: 分数排名（难度：中等）编写一个 SQL 查询来实现分数排名。如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。创建以下 score 表： Id Score 1 3.50 2 3.65 3 4.00 4 3.85 5 4.00 6 3.65 例如，根据上述给定的 scores 表，你的查询应该返回（按分数从高到低排列）： Score Rank 4.00 1 4.00 1 3.85 2 3.65 3 3.65 3 3.50 4 答案 ---建表，插值--- CREATE TABLE Scores (Id INT,Score DOUBLE); INSERT INTO Scores VALUES(1,3.50),(2,3.65),(3,4.00), (4,3.85),(5,4.00),(6,3.65); ----查询-- SELECT u.score,a.rank AS Rank FROM Scores u, (SELECT @counter:=@counter+1 AS rank,t.score FROM (SELECT @counter:=0,score FROM Scores GROUP BY score ORDER BY score DESC)AS t)a WHERE u.score=a.score ORDER BY Rank ASC; 4.2 MySQL 实战 - 复杂项目作业项目十：行程和用户（难度：困难） Trips 表中存所有出租车的行程信息。每段行程有唯一键 Id，Client_Id 和 Driver_Id 是 Users 表中 Users_Id 的外键。Status 是枚举类型，枚举成员为 (‘completed’, ‘cancelled_by_driver’, ‘cancelled_by_client’)。 Id Client_Id Driver_Id City_Id Status Request_at 1 1 10 1 completed 2013-10-01 2 2 11 1 cancelled_by_driver 2013-10-01 3 3 12 6 completed 2013-10-01 4 4 13 6 cancelled_by_client 2013-10-01 5 1 10 1 completed 2013-10-02 6 2 11 6 completed 2013-10-02 7 3 12 6 completed 2013-10-02 8 2 12 12 completed 2013-10-03 9 3 10 12 completed 2013-10-03 10 4 13 12 cancelled_by_driver 2013-10-03 Users 表存所有用户。每个用户有唯一键 Users_Id。Banned 表示这个用户是否被禁止，Role 则是一个表示（‘client’, ‘driver’, ‘partner’）的枚举类型。 Users_Id Banned Role 1 No client 2 Yes client 3 No client 4 No client 10 No driver 11 No driver 12 No driver 13 No driver 写一段 SQL 语句查出 2013年10月1日至 2013年10月3日期间非禁止用户的取消率。基于上表，你的 SQL 语句应返回如下结果，取消率（Cancellation Rate）保留两位小数。 Day Cancellation Rate 2013-10-01 0.33 2013-10-02 0.00 2013-10-03 0.50 答案 ---创建插值--- CREATE TABLE Trips(Id INT,Client_Id INT,Driver_id INT,City_Id INT,STATUS VARCHAR(10),Request_at DATETIME); INSERT INTO Trips VALUES(1,1,10,1 ,'completed','2013-10-01'), (2,2,11,1 ,'cancelled_by_driver','2013-10-01'), (3,3,12,6 ,'completed','2013-10-01'), (4,4,13,6 ,'cancelled_by_client','2013-10-01'), (5,1,10,1 ,'completed','2013-10-02'), (6,2,11,6 ,'completed','2013-10-02'), (7,3,12,6 ,'completed','2013-10-02'), (8,2,12,12,'completed','2013-10-03'), (9,3,10,12,'completed','2013-10-03'), (1,4,13,12,'cancelled_by_driver','2013-10-03'); CREATE TABLE Users(Users_Id INT,Banned VARCHAR(3),Role VARCHAR(6)); INSERT INTO Users VALUES (1 ,'No','client'), (2 ,'Yes','client'), (3 ,'No','client'), (4 ,'No','client'), (10,'No','driver'), (11,'No','driver'), (12,'No','driver'), (13,'No','driver'); ---查询--- SELECT T2.DAY,IFNULL(ROUND((T1.num/T2.num),2),0) AS 'Cancellation Rate' FROM (SELECT Request_at as Day,count(*) as num FROM Trips t LEFT JOIN Users u ON t.Client_Id = u.Users_Id WHERE u.Banned != 'Yes' AND t.status != 'completed' AND Request_at >='2013-10-01' AND Request_at <= '2013-10-03' GROUP BY Day) AS T1 RIGHT JOIN (SELECT Request_at as Day,count(*) as num FROM Trips t LEFT JOIN Users u ON t.Client_Id = u.Users_Id WHERE u.Banned != 'Yes' AND Request_at >='2013-10-01' AND Request_at <= '2013-10-03' GROUP BY Day) AS T2 ON T1.DAY = T2.DAY; 项目十一：各部门前3高工资的员工（难度：中等）将项目7中的 employee 表清空，重新插入以下数据（其实是多插入5,6两行）： Id Name Salary DepartmentId 1 Joe 70000 1 2 Henry 80000 2 3 Sam 60000 2 4 Max 90000 1 5 Janet 69000 1 6 Randy 85000 1 编写一个 SQL 查询，找出每个部门工资前三高的员工。例如，根据上述给定的表格，查询结果应返回： Department Employee Salary IT Max 90000 IT Randy 85000 IT Joe 70000 Sales Henry 80000 Sales Sam 60000 此外，请考虑实现各部门前N高工资的员工功能。 ---查找前三--- SELECT Department.Name AS Department, e1.Name AS Employee, e1.Salary AS Salary FROM Employee e1 JOIN Department ON e1.DepartmentId = Department.Id WHERE 3 > ( SELECT COUNT(DISTINCT e2.Salary) FROM Employee e2 WHERE e2.Salary > e1.Salary AND e1.DepartmentId = e2.DepartmentId ) ORDER BY Department.Name, e1.Salary DESC ---查找前N的排名，把where后3改成N就好--- 项目十二分数排名 - （难度：中等）依然是昨天的分数表，实现排名功能，但是排名是非连续的，如下： Score Rank 4.00 1 4.00 1 3.85 3 3.65 4 3.65 4 3.50 6 ---查询--- SELECT s.score,(SELECT COUNT(*)+1 FROM scores AS s1 WHERE s1.score>s.score) AS rank FROM scores s ORDER BY score DESC;

发表了文章 2019-03-31

SQL练习一（Datawhale系列）

SQL练习（一）说明：最近面试，深感sql方面需要强化训练。恰巧，在机缘巧合的情况下（忘记是怎么加入的），一个mysql训练营，每天会发布一定的任务，看起来还不错的样子。那，就一起参加一波呗。任务与解答项目一：查找重复的电子邮箱（难度：简单）创建 email表，并插入如下三行数据 +----+---------+ | Id | Email | +----+---------+ | 1 | a@b.com | | 2 | c@d.com | | 3 | a@b.com | +----+---------+ 编写一个 SQL 查询，查找 email 表中所有重复的电子邮箱。根据以上输入，你的查询应返回以下结果： +---------+ | Email | +---------+ | a@b.com | +---------+ 说明：所有电子邮箱都是小写字母。答案：建表: CREATE TABLE email(id INT PRIMARY KEY,Email VARCHAR(20)); 插入数据： INSERT INTO email(id,Email) VALUES(1,'a@b.com'),(2,'c@d.com'),(3,'a@b.com'); 查找：重复的电子邮箱 SELECT Email FROM email GROUP BY Email HAVING COUNT(id)>1; 项目二：查找大国（难度：简单）创建如下 World 表 +------------+----------+---------+--------------+---------------+ | name | continent| area | population | gdp | +------------+----------+---------+--------------+---------------+ | Afghanistan| Asia | 652230 | 25500100 | 20343000 | | Albania | Europe | 28748 | 2831741 | 12960000 | | Algeria | Africa | 2381741 | 37100000 | 188681000 | | Andorra | Europe | 468 | 78115 | 3712000 | | Angola | Africa | 1246700 | 20609294 | 100990000 | +------------+----------+---------+--------------+---------------+ 如果一个国家的面积超过300万平方公里，或者(人口超过2500万并且gdp超过2000万)，那么这个国家就是大国家。编写一个SQL查询，输出表中所有大国家的名称、人口和面积。例如，根据上表，我们应该输出: +--------------+-------------+--------------+ | name | population | area | +--------------+-------------+--------------+ | Afghanistan | 25500100 | 652230 | | Algeria | 37100000 | 2381741 | +--------------+-------------+--------------+ 解答建表： CREATE TABLE world(NAME VARCHAR(20),continent VARCHAR(20), AREA INT ,population INT,gdp INT ); 插入数据： INSERT INTO World VALUES('Afghanistan','Asia',652230,25500100,20343000), ('Albania','Europe',28748,2831741,12960000), ('Algeria','Africa',2381741,37100000,188681000), ('Andorra','Europe',468,78115,3712000), ('Angola','Africa',1246700,20609294,100990000); 查询： SELECT NAME,population,AREA FROM world WHERE AREA>3000000 OR (population>25000000 AND gdp>20000000);

发表了文章 2019-03-28

mysql优化

sql优化最近面试，在sql优化这块，一直都不是很熟悉，于是有了以下的总结，主要是在鲁玉成先生的笔记基础上，加入自己的理解。原文链接如下：http://www.cnblogs.com/luyucheng/p/6323477.html 1.sql语句的优化 a.使用limit对查询结果的记录进行限定b.避免select * ，将需要查找的字段列出来c.使用连接（join）来代替子查询d.拆分大的delete或者insert语句 1.1子查询 1.1.1mysql的五种查询子句： where:条件查询 group by：按照属性名指定的字段进行分组其他字段如果想出现在select中，则必须包含在聚合函数中： min(),max(),sum(),avg(),count() having：有group by才能有having，满足条件在group by的属性名中输出 order by：按照属性名指定的字段进行排序。排序方式有“asc”,"desc" limit：限制结果集 1.1.2子查询： where 子查询查询每个类别下id最大的商品 select goods_id,goods_name,cat_id,shop_price from goods where goods_id In (select max(goods_id) from goods group by cat_id); from型子查询 select goods_id,goods_name,cat_id,shop_price from (select goods_id,goods_name,cat_id,shop_price from goods order by cat_id asc,goods_id desc)as temp group by cat_id; exists子查询从类别表中取出其类别下有商品的类别(如果该类别下没有商品，则不取出)[使用exists子查询] SELECT c.cat_id,c.cat_name FROM category c WHERE EXISTS (SELECT 1 FROM goods g WHERE g.cat_id = c.cat_id); 1.2连接查询 1、全相乘，做笛卡儿积。（效率低） 2、左连接查询 left join ... on ... 3、右连接查询 right join ... on ... 4、内连接查询 inner join ... on ... 5、全连接查询 full join ... on ... 6、联合查询 6.1、将两张表的数据合并查询出来 SELECT id, content, user FROM comment UNION (SELECT id, msg AS content, user FROM feedback); 6.2、union查询，列名不一致时，以第一条sql语句的列名对齐 6.3、使用union会将重复的行过滤掉 6.4、使用union all 查询所有，重复的行不会被过滤 SELECT content,user FROM comment UNION ALL (SELECT msg, user FROM feedback); 6.5、union查询，如果列数不相等，会报列数不相等错误 6.6、union后的结果集还可以再筛选 SELECT id,content,user FROM comment UNION ALL (SELECT id, msg, user FROM feedback) ORDER BY id DESC; 注意order by放在排序放在内层sql是不起作用的，因为union查出来的结果会自动排序。但是内层，order by 和limit一起使用，就不会被优化掉 2.选择合适的数据类型（1）使用可存下数据的最小的数据类型，整型 < date,time < char,varchar < blob （2）使用简单的数据类型，整型比字符处理开销更小，因为字符串的比较更复杂。如，int类型存储时间类型，bigint类型转ip函数（3）使用合理的字段属性长度，固定长度的表会更快。使用enum、char而不是varchar （4）尽可能使用not null定义字段（5）尽量少用text，非用不可最好分表 3.选择合适的索引列（1）查询频繁的列，在where，group by，order by，on从句中出现的列（2）where条件中<，<=，=，>，>=，between，in，以及like 字符串+通配符（%）出现的列（3）长度小的列，索引字段越小越好，因为数据库的存储单位是页，一页中能存下的数据越多越好（4）离散度大（不同的值多）的列，放在联合索引前面。查看离散度，通过统计不同的列值来实现，count越大，离散程度越高： SELECT COUNT(DISTINCT column_name) FROM table_name; 4.使用命令分析（1）SHOW查看状态 1.显示状态信息 mysql> SHOW [SESSION|GLOBAL] STATUS LIKE '%Status_name%'; session（默认）：取出当前窗口的执行 global：从mysql启动到现在（a）查看查询次数（插入次数com_insert、修改次数com_insert、删除次数com_delete） mysql> SHOW STATUS LIKE 'com_select'; （b）查看连接数(登录次数) mysql> SHOW STATUS LIKE 'connections'; （c）数据库运行时间 mysql> SHOW STATUS LIKE 'uptime'; （d）查看慢查询次数 mysql> SHOW STATUS LIKE 'slow_queries'; （e）查看索引使用的情况： mysql> SHOW STATUS LIKE 'handler_read%'; handler_read_key：这个值越高越好，越高表示使用索引查询到的次数。 handler_read_rnd_next：这个值越高，说明查询低效。 2.显示系统变量 mysql> SHOW VARIABLES LIKE '%Variables_name%'; 3.显示InnoDB存储引擎的状态 mysql> SHOW ENGINE INNODB STATUS; （2）EXPLAIN分析查询 mysql> EXPLAIN SELECT column_name FROM table_name; explain查询sql执行计划，各列含义： table：表名； type：连接的类型 -const：主键、索引； -eq_reg：主键、索引的范围查找； -ref：连接的查找（join） -range：索引的范围查找； -index：索引的扫描； -all：全表扫描； possible_keys：可能用到的索引； key：实际使用的索引； key_len：索引的长度，越短越好； ref：索引的哪一列被使用了，常数较好； rows：mysql认为必须检查的用来返回请求数据的行数； extra：using filesort、using temporary（常出现在使用order by时）时需要优化。 -Using filesort 额外排序。看到这个的时候，查询就需要优化了 -Using temporary 使用了临时表。看到这个的时候，也需要优化（3）PROFILING分析SQL语句 1.开启profile。查看当前SQL执行时间 mysql> SET PROFILING=ON; mysql> SHOW profiles; 2.查看所有用户的当前连接。包括执行状态、是否锁表等 mysql> SHOW processlist; （4）PROCEDURE ANALYSE()取得建议通过分析select查询结果对现有的表的每一列给出优化的建议 mysql> SELECT column_name FROM table_name PROCEDURE ANALYSE(); （5）OPTIMIZE TABLE回收闲置的数据库空间 mysql> OPTIMIZE TABLE table_name; 对于MyISAM表，当表上的数据行被删除时，所占据的磁盘空间并没有立即被回收，使用命令后这些空间将被回收，并且对磁盘上的数据行进行重排（注意：是磁盘上，而非数据库）。对于InnoDB表，OPTIMIZE TABLE被映射到ALTER TABLE上，这会重建表。重建操作能更新索引统计数据并释放成簇索引中的未使用的空间。只需在批量删除数据行之后，或定期（每周一次或每月一次）进行一次数据表优化操作即可，只对那些特定的表运行。（6）REPAIR TABLE修复被破坏的表 mysql> REPAIR TABLE table_name; （7）CHECK TABLE检查表是否有错误 mysql> CHECK TABLE table_name;

提交了问题 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]离线地图加载问题高德地图

提交了问题 2018-12-14

[@炯轩][¥20]Android APP选择本地照片或者拍照上传到服务器后，程序竟然卡死了，求帮助

提交了问题 2018-12-14

[@炯轩][¥20]开发中遇到一种较难扫描识别出来的二维码，求帮助

提交了问题 2018-12-14

[@炯轩][¥20]移动通信安全问题，像android这种容易破解的通信问题

提交了问题 2018-12-14

[@炯轩][¥20]Android 4.0 怎么调用Webservice 还有就是怎么调用带SoapHeader的Webservice

提交了问题 2018-12-14

[@炯轩][¥20]群发信息后的短信息状态怎样掌握

提交了问题 2018-12-14

[@炯轩][¥20]请问后台和APP之间的接口通信怎么实现用户身份验证

提交了问题 2018-12-14

[@炯轩][¥20]在前端开发中：WebAssembly这个对象在JavaScript中，能够被PC端和安卓端的浏览器识别，但是在IOS端的Safari不识别这个对象

提交了问题 2018-12-14

[@wangccsy][¥20]linux 下Tomcat 8 配置https 访问不了

提交了问题 2018-12-14

[@小川游鱼][¥20]kafka的消费者stream iterator block，读不出消息？

提交了问题 2018-12-14

[@小川游鱼][¥20]java关键词联想技术

提交了问题 2018-12-14

[@小川游鱼][¥20]apache如何配置SSL双向验证？

提交了问题 2018-12-14

[@小川游鱼][¥20]HBASE数据导入问题

提交了问题 2018-12-14

[@小川游鱼][¥20]大数据环境中，根据一张表（idList）的数据去修改另一张表的数据(id_label),有没有比较高效的方法？

提交了问题 2018-12-14

[@小川游鱼][¥20]项目上线三个月，每天过亿的数据量....如何处理是好？

提交了问题 2018-12-14

[@小川游鱼][¥20]我用hue执行hive SQL的时候 hbase报connectionException

提交了问题 2018-12-14

[@小川游鱼][¥20]基于hive建设数据仓库的问题？

提交了问题 2018-12-14

[@小川游鱼][¥20]hive 或者 presto 有没有类似于mybatis 能把表给结构化并把sql语句提取出来的框架

提交了问题 2018-12-14

[@小川游鱼][¥20]Apache FTPClient 登录和文件下载问题

提交了问题 2018-12-14

[@talishboy][¥20]nginx tomcat请求分发

提交了问题 2018-12-14

晓生寒_个人页

个人介绍

擅长的技术

数据结构七：递归+动规+分治+回溯

数据结构六：图（DataWhale系列）

数据结构五：树+堆（DataWhale系列）

数据结构四：散列表+字符串（DataWhale系列）

数据结构三：排序+二分查找（DataWhale系列）

数据结构二：栈+队列+递归（DataWhale系列）

数据结构一：数据+链表 （Datawhale 系列）

sql练习三（DataWhale 系列-最终）

SQL练习一（Datawhale系列）

mysql优化

[@徐雷frank][¥20]ThreadLocal 这个为啥理解起来迷迷糊糊得?

[@徐雷frank][¥20]java如何优化上万条数据修改

[@徐雷frank][¥20]有没有好用的代码生成器，可以生成controller 的 （Java）

[@徐雷frank][¥20]springboot+mybatis企业开发模版

[@徐雷frank][¥20]SpringCloud 隔一段时间去调用服务就返回 read time out

[@炯轩][¥20]JAVA中如何生成多标题结构的word？？

[@倚贤][¥20]小程序商品列表加载图特别的慢怎么解决？

[@倚贤][¥20]数据库设计

[@徐雷frank][¥20]centos7设置mysql自启动的配置文件中[Service] User=mysql Group=mysql，user和group这边的mysql是指的什么？centos的登录用户名？

[@炯轩][¥20]通过mybatis插入mysql上万条数据，代码停在插入方法不继续往下运行

[@徐雷frank][¥20]vmware 使用docker部署的mysql 在vmware挂起在运行后无法连接

[@炯轩][¥20]请问后台和APP之间的接口通信怎么实现用户身份验证

[@炯轩][¥20]Android多进程能否单独开辟一个进程进行图片处理

[@炯轩][¥20]安卓的通话记录究竟是存放在哪个数据库表里面？

[@炯轩][¥20]android 双摄像头开发

[@炯轩][¥20]Android使用zxing二维码框架时候构建apk文件出现的错误

[@炯轩][¥20]移动跨平台APP开发，什么框架比较好？

[@炯轩][¥20]请问，从Android开发到线上过程是什么，比如有了好的安装包后怎么放到阿里云，怎么审核等

[@炯轩][¥20]如何通过基站定位获取地址候选集？

[@炯轩][¥20]离线地图加载问题 高德地图

[@炯轩][¥20]Android APP选择本地照片或者拍照上传到服务器后，程序竟然卡死了，求帮助

[@炯轩][¥20]开发中遇到一种较难扫描识别出来的二维码，求帮助

[@炯轩][¥20]移动通信安全问题，像android这种容易破解的通信问题

[@炯轩][¥20]Android 4.0 怎么调用Webservice 还有就是怎么调用带SoapHeader的Webservice

[@炯轩][¥20]群发信息后的短信息状态怎样掌握

[@炯轩][¥20]请问后台和APP之间的接口通信怎么实现用户身份验证

[@炯轩][¥20]在前端开发中：WebAssembly这个对象在JavaScript中，能够被PC端和安卓端的浏览器识别，但是在IOS端的Safari不识别这个对象

[@wangccsy][¥20]linux 下Tomcat 8 配置https 访问不了

[@小川游鱼][¥20]kafka的消费者stream iterator block，读不出消息？

[@小川游鱼][¥20]java关键词联想技术

[@小川游鱼][¥20]apache如何配置SSL双向验证？

[@小川游鱼][¥20]HBASE数据导入问题

[@小川游鱼][¥20]大数据环境中，根据一张表（idList）的数据去修改另一张表的数据(id_label),有没有比较高效的方法？

[@小川游鱼][¥20]项目上线三个月，每天过亿的数据量....如何处理是好？

[@小川游鱼][¥20]我用hue执行hive SQL的时候 hbase报connectionException

[@小川游鱼][¥20]基于hive建设数据仓库的问题？

[@小川游鱼][¥20]hive 或者 presto 有没有类似于mybatis 能把表给结构化 并把sql语句提取出来的框架

[@小川游鱼][¥20]Apache FTPClient 登录和文件下载问题

[@talishboy][¥20]nginx tomcat请求分发

[@talishboy][¥20]nginx+tocmat 负载均衡时，一台tomcat宕机时的问题

数据结构七：递归+动规+分治+回溯

数据结构六：图（DataWhale系列）

数据结构五：树+堆（DataWhale系列）

数据结构四：散列表+字符串（DataWhale系列）

数据结构三：排序+二分查找（DataWhale系列）

数据结构二：栈+队列+递归（DataWhale系列）

数据结构一：数据+链表 （Datawhale 系列）

sql练习三（DataWhale 系列-最终）

SQL练习一（Datawhale系列）

mysql优化

Java学习----Collection总结

[@徐雷frank][¥20]ThreadLocal 这个为啥理解起来迷迷糊糊得?

[@徐雷frank][¥20]java如何优化上万条数据修改

[@徐雷frank][¥20]有没有好用的代码生成器，可以生成controller 的 （Java）

[@徐雷frank][¥20]springboot+mybatis企业开发模版

[@徐雷frank][¥20]SpringCloud 隔一段时间去调用服务就返回 read time out

[@炯轩][¥20]JAVA中如何生成多标题结构的word？？

[@倚贤][¥20]小程序商品列表加载图特别的慢怎么解决？

[@倚贤][¥20]数据库设计

[@徐雷frank][¥20]centos7设置mysql自启动的配置文件中[Service] User=mysql Group=mysql，user和group这边的mysql是指的什么？centos的登录用户名？

[@炯轩][¥20]通过mybatis插入mysql上万条数据，代码停在插入方法不继续往下运行

[@徐雷frank][¥20]vmware 使用docker部署的mysql 在vmware挂起在运行后无法连接

[@炯轩][¥20]请问后台和APP之间的接口通信怎么实现用户身份验证

[@炯轩][¥20]Android多进程能否单独开辟一个进程进行图片处理

[@炯轩][¥20]安卓的通话记录究竟是存放在哪个数据库表里面？

[@炯轩][¥20]android 双摄像头开发

[@炯轩][¥20]Android使用zxing二维码框架时候构建apk文件出现的错误

数据结构一：数据+链表（Datawhale 系列）

[@徐雷frank][¥20]有没有好用的代码生成器，可以生成controller 的（Java）

[@炯轩][¥20]离线地图加载问题高德地图

[@小川游鱼][¥20]hive 或者 presto 有没有类似于mybatis 能把表给结构化并把sql语句提取出来的框架

数据结构一：数据+链表（Datawhale 系列）

[@徐雷frank][¥20]有没有好用的代码生成器，可以生成controller 的（Java）

[@炯轩][¥20]离线地图加载问题高德地图