蓝桥杯备赛算法（java）

导学

蓝桥杯课程安排：

参考书籍：

学习⽅法：

位运算

1-1000这1000个数放在含有1001个元素的数组中，只有唯⼀的⼀个元素值重复，其它均只出现⼀次。每个数组元素只能访问⼀次，设计⼀个算法，将它找出来；不⽤辅助存储空间，能否设计⼀个算法实现？

1 package 算法基础;

2 import 算法基础.数组随机排序; 3 import java.util.Random; 4 5 /**

6 * @Auther:zhushen 7 * @Date:2021/1/13 8 * @Description:位运算

9 * @version:1.010 */

11 public class 唯⼀成对的数 {12 /*

13 1-1000这1000个数放在含有1001个元素的数组中，只有唯⼀的⼀个元素值重复，其它均只出现⼀次。14 每个数组元素只能访问⼀次，设计⼀个算法，将它找出来；不⽤辅助存储空间，能否设计⼀个算法实现？15 */

16 public static void main(String[]args){

17 System.out.println(\"============⽅法⼀============\");18 //不使⽤辅助存储空间

19 //思路：将数组元素与正常⽆重复数组元素进⾏异或（数组元素为0—10中的整数）　　　　　　 //20 //代码实现参考：两个数交换值21 //num1 = num1^num2;22 //num2 = num1^num2;23 //num1 = num1^num2;24 int N = 11;

25 int[]arr = new int[N];26 //填充整数

27 for (int i =0;i30 //最后⼀个数，是随机数

31 arr[arr.length-1]= new Random().nextInt(N-1)+1;32 //随机下标

33 数组随机排序.shuffle(arr);34 int x1 = 0;

35 for(int i = 1;i<=N-1;i++){36 x1 = (x1^i);37 }

38 for(int i = 0;i41 for (int value : arr) {

42 System.out.print(value);43 }

44 System.out.println(\"\\n\"+x1);45

46 System.out.println(\"============⽅法⼆============\");47 //使⽤辅助存储空间

48 //思路：使⽤数组下标查出重复元素

49 //代码实现：使⽤辅助存储空间，将该数组的值作为辅助存储空间（数组）的下标。50 int[]helper = new int[N];51 for (int i=0;i52 helper[arr[i]]++;//上⼀个数组的值作为该数组元素的下标53 }

54 for (int i=0;i56 System.out.println(i);57 break;58 }59 }60 }61 }

1 package 算法基础;

2 import java.util.Random; 3 4 /**

5 * @Auther:zhushen 6 * @Date:2021/1/13 7 * @Description:tools 8 * @version:1.0 9 */

10 public class 数组随机排序 {11 12

13 /**

14 * 随机排序15 */16

17 private static Random rand = new Random();18

19 public static void swap(int[] a, int i, int j) {20 int temp = a[i];21 a[i] = a[j];22 a[j] = temp;23 }24

25 public static void shuffle(int[] arr) {26 int length = arr.length;

27 for (int i = length; i > 0; i--) {28 int randInd = rand.nextInt(i);29 swap(arr, randInd, i - 1);30 }31 }32 }

⼀个数组⾥除了某⼀个数字之外，其他的数字都出现了两次。请写程序找出这个只出现⼀次的数字。

1 package 算法基础; 2

3 import java.util.Random; 4 5 /**

6 * @Auther:zhushen 7 * @Date:2021/1/13 8 * @Description:位运算 9 * @version:1.010 */

11 public class 找出落单的数 {

12 public static void main(String[] args) {

13 System.out.println(\"============⽅法⼀============\");14 //不使⽤辅助存储空间

15 //思路：直接异或，A^A=0、A^0=A16 //代码实现参考：两个数交换值17 //num1 = num1^num2;18 //num2 = num1^num2;19 //num1 = num1^num2;20 int N = 11;

21 int[]arr = new int[N];22 //填充整数

23 for (int i =0;i26 //最后⼀个数，是随机数

27 arr[arr.length-1]= new Random().nextInt(N-1)+1;28 //随机下标

29 数组随机排序.shuffle(arr);30 int x1 = 0;

31 for(int i = 0;i34 for (int value : arr) {

35 System.out.print(value);36 }

37 System.out.println(\"\\n\"+x1);38

39 System.out.println(\"============⽅法⼆============\");40 //使⽤辅助存储空间

41 //思路：使⽤数组下标查出不重复元素

42 //代码实现：使⽤辅助存储空间，将该数组的值作为辅助存储空间（数组）的下标。43 int[]helper = new int[N];44 for (int i=0;i45 helper[arr[i]]++;//上⼀个数组的值作为该数组元素的下标46 }

47 for (int i=0;i49 System.out.println(i);50 break;

51 }52 }53 }54 }

请实现⼀个函数，输⼊⼀个整数，输出该数⼆进制表⽰中1的个数。例：9的⼆进制表⽰为1001,有2位是1

1 package 算法基础; 2

3 import java.util.Scanner; 4 5 /**

6 * @Auther:zhushen 7 * @Date:2021/1/13 8 * @Description:位运算 9 * @version:1.010 */

11 public class ⼆进制中1的个数 {

12 public static void main(String[] args) {

13 System.out.println(\"请输⼊要求的数：\");14 Scanner sc = new Scanner(System.in);15 int N = sc.nextInt();

16 System.out.println(Integer.toString(N, 2));17 //⽅法⼀：

18 //拿1从右向左与原数字做&运算19 int count = 0;20 //对⽐每⼀位

21 for (int i = 0; i < 32; i++) {

22 if ((N & (1 << i)) == (1 << i)) {23 count++;24 }25 }

26 System.out.println(count);27

28 //⽅法⼆：把原数字往右移与1做&运算29 count = 0;

30 for(int i = 0;i<32;i++){31 if(((N>>>i)&1)==1)32 count++;33 }

34 System.out.println(count);35

36 //⽅法三：原数字-1，每次可消除⼀个1，然后原数字与-1后的数字做与运算。37 //现象（1）：1000-1=011138 //现象（2）：1000&0111=000039 count = 0;40 while(N!=0){

41 N = ((N-1)&N);42 count++;43 }

44 System.out.println(count);45 }46 }

⽤⼀条语句判断⼀个整数是不是2的整数次⽅。

1 int N = 18;

2 System.out.println(Integer.toString(N, 2));3 if(((N-1)&N)==0){

4 System.out.println(\"是\");6 }else{

7 System.out.println(\"不是\");8 }

1 package 算法基础; 2

3 import org.junit.Assert; 4 5 /**

6 * @Auther:zhushen 7 * @Date:2021/2/5

8 * @Description:位运算，见⼀个记⼀个。 9 * @version:1.010 */

11 public class 整数的奇偶位互换 {

12 public static void main(String[] args) {

13 int a = 0b01000000_00000000_00000000_00000000;14 int b =m(a);

15 Assert.assertEquals(b,0b10000000_00000000_00000000_00000000);16 }

17 private static int m(int i){

18 int ou = i&0xaaaaaaaa;//原数字和1010 1010 1010....(偶数位为1，奇数位为0)做与运算取出偶数位19 int ji = i&0x55555555;//原数字和0101 0101 0101....(偶数位为0，奇数位为1)做与运算取出奇数位20 return (ou>>1)^(ji<<1);//连起来21 }22 }

(1)给定⼀个介于0和1之间的实数，(如0.625),类型为double,打印它的⼆进制表⽰（0.101,因为⼩数点后的⼆进制分别表⽰0.5,0.25.0.125......)。

(2)如果该数字⽆法精确地⽤32位以内的⼆进制表⽰，则打印“ERROR\"

1 package 算法基础; 2

3 import com.sun.org.apache.bcel.internal.generic.RETURN; 4 5 /**

6 * @Auther:zhushen 7 * @Date:2021/2/5

8 * @Description:位运算，见⼀个记⼀个 9 * @version:1.010 */

11 public class ⼆进制表⽰浮点实数 {

12 public static void main(String[] args) {13 double num = 0.625;

14 StringBuilder sb = new StringBuilder(\"0.\");15 while(num>0){16 //乘2挪整

17 double r = num*2;18 //判断整数部分19 if(r>=1){

20 sb.append(\"1\");21 //消除整数部分22 num=r-1;23 }else{

24 sb.append(\"0\");25 num = r;26 }

27 if(sb.length()>34){

28 System.out.println(\"ERROR\");29 return;30 }31 }

32 System.out.println(sb.toString());33 }34 }

1 package 算法基础; 2 3 /**

4 * @Auther:zhushen 5 * @Date:2021/2/6 6 * @Description: 7 * @version:1.0 8 */

9 public class 出现k次与1次 {

10 public static void main(String[] args) {

11 int[]arr = {2,2,2,9,7,7,7,3,3,3,6,6,6,0,0,0};12 int len = arr.length;

13 char[][]kRadix = new char[len][];14 int k = 3;

15 //转成k进制字符数组16 int maxLen = 0;

17 for(int i=0;i18 //求每个数字的三进制字符串并翻转，然后转为字符数组

19 kRadix[i] = new StringBuffer(Integer.toString(arr[i],k)).reverse().toString().toCharArray();20 if(kRadix[i].length>maxLen){21 maxLen = kRadix[i].length;22 }23 }

24 int[] resArr = new int[maxLen];25 for(int i =0;i27 for(int j = 0;j=kRadix[i].length){29 resArr[j]+=0;30 }else{

31 resArr[j] +=(kRadix[i][j]-'0');32 }33 }34 35

36 }

37 int res = 0;

38 for(int i = 0;i39 res+=(resArr[i]%k)*(int)(Math.pow(k,i));//8%3=240 }

41 System.out.println(res);42 }43 }