小挑战
本小节与大家分享一些适合启发新手学习算法的小题目，希望能启发你的斗志！
题目1
在java中你能输出一个int类型整数的二进制表示吗？
例如：
int 类型的整数1，输出为 0000 0000 0000 0000 0000 0000 0000 0001
int 类型的整数2，输出为 0000 0000 0000 0000 0000 0000 0000 0010
题目2
你能创造一个随机生成 0~5 等概率整数的方法（函数）吗？
提示：
利用 Math.random()
题目3
题目2获取到数值大小在0~5范围的概率是线性的，你能创造一个取到数值大小 在0~5范围的概率为 x平方的函数吗？
提示：
题目二获得的数字，在 0 ~ 5的范围内的概率是100%，0 ~ 4 范围内的概率是80% ...，概率曲线是线性的；现在期望把这个概率改成 x的平方
利用 Math.random()
题目4
你可以使用选择排序给指定整数数组排序吗？
题目5
你可以使用冒泡排序给指定整数数组排序吗？
题目6
你可以使用插入排序给指定整数数组排序吗？
题目7
已知可以获取 1 ~ 5 范围内的等概率随机函数，你可以构建一个 1 ~ 7 范围的等概率随机函数吗？
题目8
已知可以获取 0 ~ 1 范围内的不等概率随机函数，你可以构建一个 1 ~ 7 范围的等概率随机函数吗？
题目9
你可以使用归并排序给指定整数数组排序吗？
题目10
你可以使用快速排序给指定整数数组排序吗？
。。。。。。。。。。。。。我是优美的分割线。。。。。。。。。。。。。
题目1
在java中你能输出一个int类型整数的二进制表示吗？
参考题解：
public static void printBinary(int num) {
int bitLen = 32;
for (int i = bitLen - 1; i >= 0; i--) {
System.out.print((num & 1 << i) == 0 ? 0 : 1);
}
System.out.println();
}
知识点：
&运算，可以快速定位某个数字的二进制位中某一位是 0还是1 ，
特性： 0&1=0； 1&1=1
易错点：
注意运算符的优先级 << 的优先级高于 &
== 的 优先级高于 & ，所以需要用括号包裹。
题目2
你能创造一个随机生成 0~5 等概率整数的方法（函数）吗？
参考题解：
public static int random() {
return (int) (Math.random() * 5 + 1);
}
知识点：
Math.random() 返回的是[0,1)的double 类型的浮点数，
Math.random()*5 返回的是[0,5)的double 类型的浮点数，
Math.random()*5+1 返回的是[0,6)的double 类型的浮点数，
强转类型：(int) (Math.random() * 5 + 1)
所以此处就可以获取到 [0,5]的等概率的随机数；
常见错误写法：
(int) Math.random() * 5 + 1;
(int) Math.random() 返回的结果是整数类型的 0，因为[0,1)
(int) Math.random()*5 结果还是整数类型的 0
(int) Math.random() * 5 + 1; 的结果永远是 1
题目3
题目2获取到数值大小在0~5范围的概率是线性的，你能创造一个取到数值大小 在0~5范围的概率为 x平方的函数吗？
提示：
题目二获得的数字，在 0 ~ 5的范围内的概率是100%，0 ~ 4 范围内的概率是80% ...，概率曲线是线性的；现在期望把这个概率改成 x的平方
利用 Math.random()
参考题解：
public static int changePower2() {
return Math.max((int) (Math.random() * 5 + 1),(int) (Math.random() * 5 + 1));
// return Math.max(random(),random());
}
思路：
假设：
小于等于n的概率为x，那么大于n的概率是(1-x);
执行两次的概率就变成了 x的平方
题目4
你可以使用选择排序给指定整数数组排序吗？
public static void selectorSort(int[] array){
if(array==null|| array.length<2){
return;
}
int len = array.length;
for(int i=0; i<len; i++){
int minIndex = i;
for(int j=i+1; j<len; j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
swap(array,i,minIndex);
}
}
public static void swap(int[] array,int i1,int i2){
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
思路：
每一次内存循环找到最小值的下标，内存循环结束交换位置；一直到全部执行完毕
第1轮 从下标0开始，结束后找到的最小值下标，与0下标为数字交换位置
第2轮 从下标1开始，结束后找到的最小值下标，与1下标为数字交换位置
第i轮 从下标i-1开始，结束后找到最小值下标，与i-1下标为数字交换位置
.....
题目5
你可以使用冒泡排序给指定整数数组排序吗？
public static void popSort(int[] array){
if(array==null|| array.length<2){
return;
}
int len = array.length;
for(int i=len-1; i>=0; i--){
for(int j=1; j<=i; j++){
if(array[j-1]>array[j]){
swap(array,j-1,j);
}
}
}
}
public static void swap(int[] array,int i1,int i2){
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
思路：
两两比较，大的往后移动;
第1轮结束后的最大值处于N-1的位置
第2轮结束后的最大值处于N-2的位置
第i轮结束后的最大值处于N-i的位置
.....
题目6
你可以使用插入排序给指定整数数组排序吗？
public static void insertSort(int[] array){
if(array==null|| array.length<2){
return;
}
int len = array.length;
for(int i=0; i<len; i++){
for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {
swap(array,j-1,j);
}
}
}
}
public static void swap(int[] array,int i1,int i2){
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
思路：
构建局部有序;
第1轮结束[0,1]的区间有序
第1轮结束[0,2]的区间有序
第i轮结束[0,i]的区间有序
.....
题目7
已知可以获取 1 ~ 5 范围内的等概率随机函数f()，你可以构建一个 1 ~ 7 范围的等概率随机函数r()吗？
//此函数尽可使用，不可编辑
public static int f() {
return (int) (Math.random() * 5 + 1);
}
//构建0，1发生器
public static int random() {
int num=0;
do{
num=f();
}while(num==3);
return num>3?1:0;
}
//构建0，7的随机函数，如遇到7则抛弃重新做，只保留[0，6]的区间
//构建[1，7]的随机函数
public static int r() {
int num=0;
do{
num=(random()<<2)+(random()<<1)+random();
}while(num==7);
return num+1;
}
思路：
1.首先利用已知的信息，构建0,1发生器
2.利用0,1发生器，通过移位运算，获得接近区间[0,7]的值
3.遇7重新做，修改区间为[0,6]，结果+1，移动区间为[1,7]
题目8
已知可以获取 0 ~ 1 范围内的不等概率随机函数f2()，你可以构建一个 1 ~ 7 范围的等概率随机函数r2()吗？
//此函数仅可使用，不可编辑
public static int f2() {
return Math.random()>0.85? 0: 1;
}
//构建0，1发生器
public static int random2() {
int num=0;
do{
num=f2();
}while(num==f2());
return num;
}
//构建0，7的随机函数，如遇到7则抛弃重新做，只保留[0，6]的区间
//构建[1，7]的随机函数
public static int r2() {
int num=0;
do{
num=(random2()<<2)+(random2()<<1)+random2();
}while(num==7);
return num+1;
}
思路：
1.首先利用已知的信息，构建0,1发生器
假如：获得0的概率为x，那么非零的概率就是(1-x),所以结果数的概率为
2.利用0,1发生器，通过移位运算，获得接近区间[0,7]的值
3.遇7重新做，修改区间为[0,6]，结果+1，移动区间为[1,7]
题目9
你可以使用归并排序给指定整数数组排序吗？
参考题解：递归解法
public static void mergeSort(int[] array){
if( array==null || array.length<2 ){
return;
}
process(array, 0, array.length-1);
}
public static void process(int[] array,int l,int r){
if(l >= r){
return;
}
int mid = l+ ((r-l)>>1);
process(array, l, mid);
process(array, mid+1, r);
merge(array, l, mid, r);
}
public static void merge(int[] array,int l,int m,int r){
int [] help = new int[r-l];
int i = 0;
int l1 = l;
int l2 = m+1;
while(l1<=m&& l2<=r){
help[i++] = array[l1]<=array[l2]?array[l1++]:array[l2++];
}
while(l<=m){
help[i++] = array[l1++];
}
while(l2<=r){
help[i++] = array[l2++];
}
for(i=0;i<help.length;i++){
array[l+i] =help[i];
}
}
题目10
你可以使用快速排序给指定整数数组排序吗？
参考题解: 递归解法
public static void quickSort(int[] array){
if( array==null || array.length<2 ){
return;
}
process(array, 0, array.length-1);
}
public static void process(int[] array,int l,int r){
if(l >= r){
return;
}
int[] partition = partition(array, l, r);
process(array, l, partition[0]);
process(array, partition[1], r);
}
public static int[] partition(int[] array, int l, int r){
int less = l-1;
int more = r;
int index = l;
while(index < more){
if(array[index] < array[r]){
swap(array, ++less, index++);
}else if(array[index] > array[r]){
swap(array, --more, index);
}else {
index++;
}
}
swap(array,index,r);
return new int[]{less,more};
}
public static void swap(int[] array, int i1, int i2){
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
- 本文链接： https://www.sunce.wang/archives/算法小练习之新手挑战赛
- 版权声明： 本博客所有文章除特别声明外，均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处！