本文主要是介绍ProblemSet of Random，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
470. Implement Rand10() Using Rand7()
解法一：
这个问题腾讯二面问的，我竟然一点思路没有，说实话没刷过类似题目真的很难想到。
/*** The rand7() API is already defined in the parent class SolBase.* public int rand7();* @return a random integer in the range 1 to 7*/
class Solution extends SolBase {public int rand10() {int idx=40;while(idx>=40){int a=rand7();int b=rand7();idx=(a-1)*7+b-1;}return 1+idx%10;}
}
解法二：
/*** The rand7() API is already defined in the parent class SolBase.* public int rand7();* @return a random integer in the range 1 to 7*/
class Solution extends SolBase {public int rand10() {int idx;while(true){int a=rand7();int b=rand7();idx=(a-1)*7+b;if(idx<=40)return 1+(idx-1)%10;//distribute a=idx-40;b=rand7();idx=(a-1)*7+b;if(idx<=60)return 1+(idx-1)%10;a=idx-60;b=rand7();idx=(a-1)*7+b;if(idx<=20)return 1+(idx-1)%10;}}
}
519. Random Flip Matrix
class Solution {public HashSet<Integer> set;public int n_row;public int n_col;public Solution(int n_rows, int n_cols) {set=new HashSet<>();n_row=n_rows;n_col=n_cols;}/*3 40 1 2 34 5 6 78 9 10 11*/public int[] flip() {int[] ret=new int[2];if(n_col==0 || n_row==0)return ret;int rand;while(true){rand=(int)(Math.random()*(double)this.n_row*this.n_col);if(!set.contains(rand))break;}ret[0]=rand/n_col;ret[1]=rand%n_col;set.add(rand);return ret;}public void reset() {this.set=new HashSet<>();}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(n_rows, n_cols);* int[] param_1 = obj.flip();* obj.reset();*/
528. Random Pick with Weight
class Solution {public int[] right;public int sum;public Solution(int[] w) {sum=0;right=new int[w.length];for(int i=0;i<w.length;i++){sum+=w[i];right[i]=sum;}}public int pickIndex() {double target=Math.random()*sum;int i=0;for(;i<right.length;i++){if(target<=right[i])break;}return i;}}
497. Random Point in Non-overlapping Rectangles
因为要返回被矩形区域覆盖的整数坐标点，累计计算的不是矩形的面积，而应该是点的数量（包括矩形边上的点），另外生成的随机数范围因该注意
class Solution {public int[] areas;public int[][] rects;public Solution(int[][] rects) {this.areas=new int[rects.length];this.rects=rects;for(int i=0;i<rects.length;i++){int[] rect=rects[i];areas[i]=(rect[2]-rect[0]+1)*(rect[3]-rect[1]+1);}for(int i=1;i<areas.length;i++)areas[i]+=areas[i-1];}public int[] pick() {int target=(int)(Math.random()*(this.areas[this.rects.length-1]+1));int[] ret=new int[2];if(rects.length==0)return ret;int i=0;for(;i<this.rects.length;i++){if(target<=this.areas[i])break;}int[] rect=this.rects[i];ret[0]=rect[0]+(int)(Math.random()*(rect[2]-rect[0]+1));ret[1]=rect[1]+(int)(Math.random()*(rect[3]-rect[1]+1));return ret;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(rects);* int[] param_1 = obj.pick();*/
解法二：
基本思路一样，但是在搜索步骤采用了TreeMap来降低查询时间复杂度，当然也可以使用二分法。
class Solution {TreeMap<Integer, Integer> map; //将累积点数（key）与矩形的索引(value)存储在map中int[][] arrays;int sum;Random rnd= new Random();public Solution(int[][] rects) {arrays = rects;map = new TreeMap<>();sum = 0;for(int i = 0; i < rects.length; i++) {int[] rect = rects[i];// the right part means the number of points can be picked in this rectanglesum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);map.put(sum, i);}}public int[] pick() {// nextInt(sum) returns a num in [0, sum -1]. After added by 1, it becomes [1, sum]int c = map.ceilingKey( rnd.nextInt(sum) + 1);return pickInRect(arrays[map.get(c)]);}private int[] pickInRect(int[] rect) {int left = rect[0], right = rect[2], bot = rect[1], top = rect[3];return new int[]{left + rnd.nextInt(right - left + 1), bot + rnd.nextInt(top - bot + 1) };}
}
478. Generate Random Point in a Circle
采用reject sampling算法
class Solution {public double x;public double y;public double r;public Solution(double radius, double x_center, double y_center) {x=x_center;y=y_center;r=radius;}public double[] randPoint() {double dx,dy;do{dx=(2*Math.random()-1)*this.r;dy=(2*Math.random()-1)*this.r;}while(dx*dx+dy*dy>r*r);double[] ret=new double[2];ret[0]=x+dx;ret[1]=y+dy;return ret;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(radius, x_center, y_center);* double[] param_1 = obj.randPoint();*/
极坐标法：
class Solution {public double x;public double y;public double r;public Solution(double radius, double x_center, double y_center) {x=x_center;y=y_center;r=radius;}public double[] randPoint() {double angle=Math.random()*360;double radius=Math.sqrt(Math.random())*this.r;double dx=radius*Math.cos(angle*Math.PI/180);double dy=radius*Math.sin(angle*Math.PI/180);double[] ret=new double[2];ret[0]=x+dx;ret[1]=y+dy;return ret;}
}
710. Random Pick with Blacklist
算法一：
lass Solution {ArrayList<Interval> arr;TreeMap<Integer,Interval> map;int acc;public static Random random = new Random();class Interval{int left;int right; //left bound and right bount are both includedpublic Interval(int left,int right){this.left=left;this.right=right;}public int getNum(){ //return the length of the Intervalreturn right-left+1;}public int pickInInterval(int rand){ //pick randomly in IntervalSystem.out.println(right+" xixi "+getNum()+" xixi "+rand);System.out.println("hehe "+(right-getNum()+rand));return right-getNum()+rand;}public String toString(){String s="[";s+=left+","+right+"]";return s;}}public Solution(int N, int[] blacklist) {Arrays.sort(blacklist);arr=new ArrayList<>();map=new TreeMap<>();acc=0;int start=0;for(int i=0;i<blacklist.length;i++){if(start==blacklist[i]){start++;continue;}Interval tmp=new Interval(start,blacklist[i]-1);arr.add(tmp);start=blacklist[i]+1;acc+=tmp.getNum();map.put(acc,tmp);}if(start<N){Interval in=new Interval(start,N-1);arr.add(in);acc+=N-start;map.put(acc,in);}/*System.out.println(acc); for(int i:map.keySet())System.out.println(i+":"+map.get(i).toString());*/}public int pick() {int rand=random.nextInt(acc);int target=rand+1;//System.out.println("target:"+target);Integer lastAccum=map.floorKey(target);if(lastAccum==null)lastAccum=-1;int curAccum =map.ceilingKey(target);int ans;if(target>lastAccum)ans=map.get(curAccum).right-curAccum+target;elseans=map.get(lastAccum).right;//System.out.println(target+" xixi "+ans);return ans;}
}
算法二：
class Solution {Map<Integer, Integer> map;Random random = new Random();int bound;public Solution(int N, int[] blacklist) {map = new HashMap<Integer, Integer>();bound = N-blacklist.length;Set<Integer> set = new HashSet<>();for (int i: blacklist){set.add(i);}int idx = N-1;for (int i: blacklist){if (i < N-blacklist.length){while(set.contains(idx)){idx--;}map.put(i, idx);idx--;}}}public int pick() {int r = random.nextInt(bound);return map.getOrDefault(r, r);}
}
这篇关于ProblemSet of Random的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
