蔚来，深信服，许愿能进HR面

public int NumberOf1Between1AndN_Solution(int n) { //出现的总数其实就是各个位置上的1的个数的和 //当前位，n(i),cur //高位n(N)....n(i+1)，high //低位n(i-1)...n(1),low //注意当前位出现1的个数其实是和当前位的digital是挂钩的，比如是十分位，那么可能有10...19出现1，有10个 //而百分位就成了100...199出现1，有100个数，以此类推 //而像是10分位的1，有几个10...19出现呢？这就看高位了，至少会有0~high-1共有high个 //不管是当前位是什么，总会有(...

将后序序列看成树，在数组上玩树的深度遍历，关键点在于找到左子树和右子树的切分点，可以使用二分来加速 public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence==null||sequence.length==0) return false; int N = sequence.length; int[] res = process(sequence,0,N-1); return res[0] == 1;//0为false,1为true } //返回结果中0:isBST,1:min...

这题使用模拟法，也就是我们脑子咋分辨是否能够作为弹出序列的？就是看看照着弹出序列能不能弹完，其实我觉得不管是有没有重复值这种模拟的方法都能正确的，比如下面这种，老实说其实不在意到底哪个4先弹出来。1 4 2 3 5 44 5 3 2 4 1 import java.util.*; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { Stack<Integer> stack = new Stack<>(); int b = 0; for(int a:pushA){ st...

public int GetNumberOfK(int [] array , int k) { if(array==null||array.length==0) return 0; //有序，想到二分，如何用二分来优化？ //这是数组，如何确定某个数的个数？ //由于有序，所以这个数出现的位置肯定是连续的，数组的好处在于下标，所以找到上下边界就可以使用下标 //直接算出个数 //上界:>=k的最左边,同样也是<k的最右边+1 //下界:<=k的最右边 //所以整一个函数，求<=k的最右边(leftEqlMaxRight)就可以了 int res = leftEqlMax...

这题通过找规律可以发现是一个类似斐波那契数列的二阶问题，常规解法就是使用递归或者改迭代，但是这个复杂度就是O(N)的。可以有一种矩阵快速幂乘来优化的算法。  public int rectCover(int target) { if(target==0||target==1||target==2) return target; /*int preTwo = 1; int preOne = 2; int temp; for(int n = 3;n<=target;n++){ temp = preOne+preTwo; preTwo = preOne; preOne = temp; } re...

两个重要点  1.每一行都按照从左到右递增的顺序排序 2.每一列都按照从上到下递增的顺序排序 那么起始点a选择右上角* 1.如果a下方位置b小于等于target，由于b>=a,很明显a所在这行就直接淘汰了 2.如果b位置大于target了，说明这一列就淘汰了，再往下走都是大于target的,该往左走找新列了 3.拢共m行n列，每次必定淘汰一行或者淘汰一列，时间复杂度O(m+n)   //判断数组中是否含有该整数target public boolean Find(int target, int [][] array) { if(array==null||array.length==0||...

矩阵类题目关键点在于将问题进行拆分，这里就可以拆分成一层一层的矩阵，只要规定好每个矩阵如何螺旋收集外围数字就好了。  public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> res = new ArrayList<>(); if(matrix==null||matrix.length==0) return res; //左上角和右下角定下一个矩阵，每个矩阵的遍历规定好 int[] leftTop = {0,0}; int[] rightBottom = {matri...

芜湖，今天又全A了一个笔试。  1.题目一:找数对  //1.用set记一下已经有过的数 //2.已经有过数对的开始放入set public int get_pair_count (int[] arr) { if(arr==null||arr.length<2) return 0; HashSet<Integer> found = new HashSet<>(); HashSet<Integer> collected = new HashSet<>(); for(int a:arr){ if(found.contains(a-1)){ co...

记录一下少有的全A笔试  题目一:给个数组，计算每个位置右边最近比它大，左边最近比它小的差值。  //i是下标 nums[i]>0 //对i找到其最近的两个位置x,y，满足x<i且nums[x]<nums[i],y>i且nums[y]>nums[i] //单调栈的概念题 //输出结果是nums[y]-nums[x]右-左,找不到x,y则认为nums[x]=0,nums[y]=0 //注意元素可能重复[9,3,3,6] public int[] nearestDiff (int[] nums) { if(nums==null||nums.length==0) ret...

就是利用前序序列找到头，然后在中序序列中找到这个头的位置h，h左边就是左子树，h右边就是右子树，然后递归就可以了  public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { if(pre==null||vin==null||pre.length==0||pre.length!=vin.length) return null; return reBuildTree(pre,0,pre.length-1,vin,0,pre.length-1); } public TreeNode reBuildTree(int[] pre,int...

借鉴这个老哥的解题思想https://blog.nowcoder.net/n/1b4531b1265d4fe1b9e4ca31c3c66da1这是我的实现方法  //想要取得中位数O(1) //中位数怎么求？数据排好序后 //1.奇数下 //就是中间那个 //2.偶数下 //就是中间两个的平均值 //可以将这些数据看成左右两半，约定左边的数目容许比右边多1 //这下好了，奇数下，中位数就是max(left) // 偶数下，中位数就是(max(left)+min(left))>>1 //什么结构能简单获取最值？堆，其中左边用大根堆，右边用小根堆 //巧妙的数据流动思想: //插入一个...