java,Code片段,代码实例,代码示例,代码片段库

java 将零移动到结束 - 将0移动到数组最后同时保证原非0的相对顺序

move zero to end

public static void moveZerosToEnd(int[] nums){
    int k=0;
    for(int i = 0 ; i<nums.length; i++){
        if(nums[i]!=0){
            nums[k]=nums[i];
            k++;
        }
    }
    while(k < nums.length){
        nums[k++]=0;
    }
}

java 荷兰三色旗或者红白蓝排序问题

给定一个无序数组，里面的数字有0/1/2，将其排列成为0 .... .... 1 2 ....，只允许遍历一次

three colors flags

//三指针问题
public void sortThreeColors(int [] nums){
  int left= 0 ; 
  int right = nums.length-1;
  for(int k = 0 ; k <= right;){
    if(nums[k]==1) k++;
    else if(nums[k]==0){
      //如果k对应的是0应该和左边的left指针交换并均加1，因为k是往右走的
      int temp = nums[k];
      nums[k]=nums[left];
      nums[left]=temp;
      left++;k++;
    }else{
      //如果k对应的是2则要和右边的right指针交换，但是只有right--，k不变
      int temp = nums[k];
      nums[k] = nums[right];
      nums[right] = temp;
      right--;
    }
  }
}

java 合并排序数组 - 合并两个排序的数组

假设两个递增排序的数组合并成为一个递增排序的数组，并且一个数组的长度M，B数组的长度N，同时一个数组的容量大于等于M + N，所以不要额外申请数组来实现，直接在一个数组中操作。思路是从后往前循环，把最大的数字放在最后面，这样可以直接在一个数组上操作。

merge sorted array

	public static void mergedTwoSortedArray(int [] a,int m,int [] b,int n){
	  int k = m+n-1;
	  int i = m-1;
	  int j = n-1;
	  while(i >=0 && j >= 0){
	    if(a[i]>=b[j])
	      a[k--]=a[i--];
	    else
	      a[k--] = b[j--];
	  }
	  while(j>=0)
	    a[k--]=b[j--];
	  while(i>=0)
	    a[k--]=a[i--];
	  return;
	}

java 缺失的区间和总结区间

缺失的区间：0,1,5,6,7,10,16,17,18,20,21,98,99则输出[2-> 4,8-> 9,11-> 15,19,22 - > 97] <br/>总结区间：1,2,3,10,11,13,14,23则输出[4-> 9,12,15-> 22]

missing ranges

//缺失的区间问题。
public static  List<String> lostRanges(int [] nums){
    List<String> res = new ArrayList<String>();
    if(nums==null || nums.length==0) return res;

    int start = 0,end = 0;
    if(nums[0]!=0){
        if(nums[0]==1) res.add(Integer.toString(0));
        else res.add(Interger.toString(0)+"->"+Integer.toString(nums[0]-1));
    }
    while(end < nums.length){
       while(end+1<nums.length && nums[end+1]==nums[end]+1)  end++;
       int left=nums[end]+1;
       if(left==100) break;  //如果最后一个数是99那就不要再加了
       int right = 99;
       if(end+1<nums.length) right = nums[end+1]-1;
       if(left==right) res.add(Integer.toString(left));
       else res.add(Integer.toString(left)+"->"+Integer.toString(right));
       start = end+1;
       end=start;
    }
    return res;
}

summary ranges

//Summary ranges
public List<String> summaryRanges(int [] nums){
    List<Sttring> res = new ArrayList<>();
    if(nums==null || nums.length==0) return res;
    int s = 0,e = 0 ;
    while (e < nums.length){
        if(e+1<nums.length && nums[e+1]==nums[e]+1)
            e++;
        else{
            if(s==e)
                res.add(Integer.toString(nums[s]));
            else{
                String str = nums[s]+"->"+nums[e];
                res.add(str);
            }
        }
        
    }
    return res;
}

java 求数组中除了自己之外其他数的乘积，不用除法

double array

public int[] productExceptSelf(int [] nums){
    int [] res = new int[nums.length];
    int [] left = new int [nums.length];
    left[0]=1;
    int[] right = new int[nums.length];
    right[nums.length-1] = 1;
    for(int i = 1; i < nums.length; i++){
        left[i] = left[i-1]*nums[i];
    }
    for(int i = nums.legnth-2; i >= 0; i--){
        right[i] = right[i+1]*nums[i];
    }
    for(int i  = 0; i < nums.length; i++){
        res [i] = left[i]*right[i];
    }
    return res;
}

no extra space

public int productExceptSelf_WithConstantSpace(int [] nums){
    int [] res = new int [nums.length];
    int temp = 1;
    res[0] = 1;
    for(int i = 1 ; i < nums.length; i++){
        res[i] = res[i-1]*nums[i];
    }
    temp = nums[nums.length-1];
    for(int i = nums.length-2; i >= 0 ; i--){
        res[i] = res[i]*temp;
        temp *= nums[i];
    }
    return res;
}

java 求数组中除了自己之外其他数的乘积，不用除法

double array

public int[] productExceptSelf(int [] nums){
    int [] res = new int[nums.length];
    int [] left = new int [nums.length];
    left[0]=1;
    int[] right = new int[nums.length];
    right[nums.length-1] = 1;
    for(int i = 1; i < nums.length; i++){
        left[i] = left[i-1]*nums[i];
    }
    for(int i = nums.legnth-2; i >= 0; i--){
        right[i] = right[i+1]*nums[i];
    }
    for(int i  = 0; i < nums.length; i++){
        res [i] = left[i]*right[i];
    }
    return res;
}

no extra space

public int productExceptSelf_WithConstantSpace(int [] nums){
    int [] res = new int [nums.length];
    int temp = 1;
    res[0] = 1;
    for(int i = 1 ; i < nums.length; i++){
        res[i] = res[i-1]*nums[i];
    }
    temp = nums[nums.length-1];
    for(int i = nums.length-2; i >= 0 ; i--){
        res[i] = res[i]*temp;
        temp *= nums[i];
    }
    return res;
}

java 大于等于ķ的最短子数组长度

这里的子数组是连续子数组，数组中所有的数都是正数

shortest sub array

//O(n)的方法，其实有两种方法。一个是用两个指针从左往右扫描，left和right记录满足要求的连续子数组左边界和右边界，先移动right直到期间的和大于等于k，然后再把left往右移动来缩小子数组的长度，并且更新最短子数组长度。
//第二种借用HashMap，存储累加值和索引的对应关系。先将数组从左往右累加，然后再类似于“连续子数组之和大于k的最大长度”来实现
public int minSubArrMoreK(int[] nums,int k){
  if(nums==null || nums.length==0) return 0;
  int left=0,right=0,sum=0;
  int res = nums.length+1; ;
  while(right < nums.length){
    while(sum < k && right < nums.length) sum += nums[right++];
    while(sum >= k){
      res = Math.min(res,right-left);
      sum -= nums[left++];
    }
  }
  return res==nums.length+1?0:res;
}

divide and conquer

//分治法,Divide and Conquer

java 最大尺寸子阵列和等于k（和为k的最长连续子数组）

这里的子数组是连续的，给定一个数组ARR和目标值K，求解数组中所有连续子数组之和等于ķ的最大长度的子数组的长度，时间复杂度是O（n）的

public int maxLenSumToK_NoMap(int [] nums,int k){
    int len = nums.length;
    int [] sums = new int[len];
    sums[0] = nums[0];
    for(int i=1; i < len; i++){
        sums[i] = sums[i-1]+nums[i];  //先从第一个往后累加
    }
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < len; i++){
        for(int j = i; j < len; j++){
            if(sums[j]-sums[i]==k) max = Math.max(max,j-i); //判断所有的子数组之和等不等于k，并记录最大长度子数组
        }
    }
}

public int maxLenSumToK_WithMap(int [] nums,int k){
    int len = nums.length;
    int [] sums = new int[len];
    sums[0]=nums[0];
    int max = Integer.MIN_VALUE;
    for(int i = 1 ; i < len; i++){
        sums[i] = sums[i-1]+nums[i];
    }
    Map<Integer,Integer> map = new HashMap<>();  //用map来保存累加值和下表索引之间的对应关系
    for(int i = 0; i < len; i++){
        int dis = sums[i]-k;//求当前累加值和k之间的差距
        int j = map.get(dis);  //去map中查找有没有已经放入了这个期待的差距值，有的话拿到其索引值用于更新max值
        if(j!=null) max = Math.max(max,j-i);  //更新max
        if(!map.get(sums[i])) map.put(sums[i],i); //如果没有该累加值则加入，如果有的话放入的是前面的因为这样可以max更大。
    }
    return max;
}

java 寻找流数据中的中位数

采用大顶堆和小顶堆的方法来实现。例如已有数据为Ñ个，如果N％2 == 1则返回小顶堆的PEEK（），否则返回大顶堆和小顶堆堆顶元素之平均值。奇数位数的数存如小顶堆，偶数位的数存入大顶堆（当然也可以反过来，不过后面就要反过来）。大顶堆永远存储的是见过的最小的n / 2个个数，而小顶堆存储见过的最大的n / 2个个数。两个堆对于新加入的数据需要先加入再调整，再判断如果小顶堆的堆顶元素小于大顶堆的堆顶元素则交换两者的堆顶元素然后再调整。

min-max-heap

java LeetCode - 滑动窗口maxmum滑动窗口最大值

给定一个数组以及一个窗口值K，求每次窗口滑动过程中窗口中的最大值。

Deque

//利用双端队列来实现，其中保存的是数字下标而非数字本身，双端队列中需要是从大到小有序的数字，那么每次窗口中最大值就是队列头部的元素。保持每次插入都将带插入数字从后前遍历插入到合适的位置并且去掉所有小于该数字的队列中其他数字
public List<Integer> maxSlidingWindow(int[] nums,int k){
  List<Integer> res = new ArrayList<Integer>();
  Deque<Integer> q = new Deque<>();
  for(int i = 0 ; i < nums.length; i++){
    if(!q.isEmpty() && q.getFirst()<=(i-k)) q.removeFirst();
    while(!q.isEmpty() && nums[q.getLast()] <nums[i]) q.removeLast();
    q.addLast(i);
    if(i>=k-1) res.add(nums[q.getFirst()]);//之所以要有i>=k-1限制是因为保证是已经处理完前k个元素才开始往结果集里加的。
  }
  return res;
}

max heap

//利用大顶堆实现，先利用最前面k个元素建堆然后每次窗口中最大值都是插入新的元素之后堆顶元素。对于新的元素如果大于堆顶元素就是插入堆，如果小于就直接排除。
//堆中存储的还是位置索引而非真实值，因为需要比较堆顶的元素是否需要移除了.
public List<Integer> maxSlidingWindow(int[] nums,int k){
  List<Integer> res = new ArrayList<>();
  PriorityQueue<Integer> q = new PriorityQueue<>();
  for(int i = 0 ; i < nums.length ; i++){
    while(!q.isEmpty() && i-k>=q.peek()) q.remove();
    q.add(i);
    if(i>=k-1) res.add(nums[q.peek()]);
  }
  return res;
}