记录一些其他算法题

一些其他的算法题

• 给定一个 0-4随机数生成器 如何生成0-6随机数

  这个实在没想明白怎么做，只能抄写在这里，记一记，背一背。

  public int rand7(){
      while(true){
          int a = 5*rand4() + rand4();  // 大于1 相乘
          if(a < 21){					  // 算出理论范围，然后确定边界
  			return a % 7;
          }
      }
  }
  
  //变形：如果用0-6随机生成器生成0-9随机数
  public int rand10(){
      while(true){
          int a = 7*rand6() + rand6();
          if(a < 41){ //排除41-48，因为他们不能生成9，会造成各个数字出现的概率不同
  			return a % 10;
          }
      }
  }
  

• 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3

  public int canCompleteCircuit(int[] gas, int[] cost) {
          int n = gas.length;
          int sumTank = 0;//总油量
          int curTank = 0;//当前油箱内的油量
          int startStation = 0;
          for(int i = 0; i < n;i++){
              sumTank += gas[i] - cost[i];
              curTank += gas[i] - cost[i];
              if(curTank < 0){
                  startStation = i + 1;
                  curTank = 0;
              }
          }
          return sumTank >= 0 ? startStation : -1; // 这个是整个需要的油耗量，如果你要绕行一周，那么这个中耗油量一定要大于等于0，不然是没有办法环绕一周的。用这个来标志，
      }
  

• 剑指offer62:圆圈剩下的数字（约瑟夫环问题）

  不写了，用数组来模拟链表，注意下标的循环

• 🌹 给出一个区间的集合，请合并所有重叠的区间。 leetcode056

  ​ 示例 1:

  ​ 输入: [[1,3],[2,6],[8,10],[15,18]]

  ​ 输出: [[1,6],[8,10],[15,18]]

  ​ 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

  	public static int[][] merge(int[][] intervals) {
          // 先按照区间起始位置排序
          Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
          // 遍历区间
          int[][] res = new int[intervals.length][2];
          int idx = -1;
          for (int[] interval: intervals) {
              // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
              // 则不合并，直接将当前区间加入结果数组。
              if (idx == -1 || interval[0] > res[idx][1]) {
                  res[++idx] = interval;
              } else {
                  // 反之将当前区间合并至结果数组的最后区间
                  res[idx][1] = Math.max(res[idx][1], interval[1]);
              }
          }
          return Arrays.copyOf(res, idx + 1);
      }
  

• 不是算法题：三个线程循环打印ABC 30次

  // synchronized wait notifyAll
  public Mythread implements Runnale(){
      private static Object obj = new Object();
  	private static int count = 0;
  	private String value;
  	private int flag; // 0 
  	public ABCdemo1(String value,int flag) {
  		this.value = value;
  		this.flag = flag;
  	}
      
      @override
      public void run(){
      	for(int i = 0; i < 10; i++){
              synchronized(obj){
                  while(count % 3 != flag){
                      try{
                          obj.wait();
                      } catch (Exception e){
                          e.printStackTrace()
                      }
                  }
                  syso(value);
                  count++;
                  obj.notifyAll();
              }
          }    
      }
      
      public static void main(String[] args) {
  		new Thread(new ABCdemo1("A", 0)).start();
  		new Thread(new ABCdemo1("B", 1)).start();
  		new Thread(new ABCdemo1("C", 2)).start();
  	}
  }
  

  // lock condition await singalAll
  public Mythread implements Runnale(){
  private static int currentCount; // 线程共有，判断所有的打印状态
  	private static Lock lock = new ReentrantLock(); // 线程共有，线程锁对象
  	private static Condition condition = lock.newCondition();
  	private int flag; // 0：打印A；1：打印B；2：打印C
  	private String value;
  	public ABCdemo1(String value,int flag) {
  		this.value = value;
  		this.flag = flag;
  	}
      
      @override
      public void run(){
      	for(int i = 0; i < 10; i++){
              try{
  				lock.lock();
                  while(count % 3 != flag){
                      try{
                          condition.await();
                      } catch (Exception e){
                          e.printStackTrace()
                      }
                  }
                  syso(value);
                  count++;
                  obj.singalAll();
              }finally{
                  lock.unlock();
              }
          }    
      }
      
      public static void main(String[] args) {
  		new Thread(new ABCdemo1("A", 0)).start();
  		new Thread(new ABCdemo1("B", 1)).start();
  		new Thread(new ABCdemo1("C", 2)).start();
  	}
  }
  

• 1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度

  这个题目是就是用位图来做的，下面的方式其实和桶排序一样，包括了确定位置，和桶的数量方法都是一样的。也叫做位图

  	public static void method(int[] a) {
  		int max = 0;
  		int min = 0;
  		for (int i = 0; i < a.length; i++) {
  			max = Math.max(max, a[i]);
  			min = Math.min(min, a[i]);
  		}
  		
  		int length = max / 8 - min / 8 + 1;
  		byte[] arry = new byte[length];
  		for (int i = 0; i < a.length; i++) {
  			int num = a[i];
  			int index = num / 8 - min / 8;
  			int k = (num - min) % 8;
  			if((arry[index] & 1<<k) > 0) {  // 是左移
  				System.out.println(num + "重复了");
  			}else {
  				arry[index] |= (1<<k);
  			}
  		}
  	}
  	
  	public static void main(String[] args) {
  		int[] a = new int[] {1,7,2,3,4,5,6,6};
  		method(a);
  	}