自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。
“计划”的主要目的:
1、想通过这样的方式监督自己更努力的学习算法。
2、想和小伙伴们“组团”一起来学习交流学习算法过程中的点点滴滴。
“计划”的主要内容:
1、数据结构和算法的基础知识巩固。
2、逐步进阶的oj算法训练。
“计划”的时间安排:每周三和周六
——说在前面
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”计划01打卡:
问题描述
对于长度为5位的一个01串,每一位都可能是0或1,一共有32种可能。它们的前几个是:
00000
00001
00010
00011
00100
请按从小到大的顺序输出这32种01串。
输入格式
本试题没有输入。
输出格式
输出32行,按从小到大的顺序每行一个长度为5的01串。
样例输出
00000
00001
00010
00011
<以下部分省略>
解题思路与实现
如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。
1System.out.println("00000")
2..........
3System.out.println("11111")
这种方式是不是也能够得到最后的结果,没错,当然没问题,但是,我们在思考的时候可以一步一步来,尝试多种方法,找到最优解。
这种方法看来不太好,一是不够灵活,二是敲代码很累,所以,改进一下。
这里写图片描述
这种方式是不是能够更加灵活的解决这个问题,这个解决的方式就是我们常说的“暴力破解”,全部用for循环来遍历所有的情况,如果找到符合的情况就输出,但是我们会发现,这个算法的时间复杂度是:O(n^5)
,这个方法比前一种方法更好了,但是还不是最好的答案。
1public static void main(String[] args) {
2 for (int i = 0; i < 32; i++) {
3 String result = Integer.toBinaryString(i);
4 int num = result.length();
5 for (int j = 0; j < 5 - num; j++) {
6 result = "0" + result;
7 }
8 System.out.println(result);
再来看看这种方法,这种方法的思路:通过jdk的方法Integer.toBinaryString()
获取到每个数字的二进制,因为要求输出的是形如“11111”
的五位数字,所以,我们还需要根据得到的二进制的数字的长度,在这个字符串的前面加上5 - num
个“0”
,比如,得到的二进制是1
(长度为1),所以在1
的前面要加上5-(num=1)
等于4个0
。
是不是特别的简洁,而且这种方法的效率应该也是不错的:O(n)
,因为这个是jdk提供的方法,在底层是用位移的方法来实现的(注:我们不推荐用jdk的方法来解决,我们尽量用自己思考的方法来解决,就算这个方法“笨”,但是也是自己思考了)。
当然,如果我们换个角度,也可以的到另一种解法。
1public static void main(String args[]){
2 for(int i=0;i<32;i++){
3 String str = Integer.toBinaryString(i);
4 switch (str.length()) {
5 case 1:
6 str = "0000"+str;
7 break;
8 case 2:
9 str = "000"+str;
10 break;
11 case 3:
12 str = "00"+str;
13 break;
14 case 4:
15 str = "0"+str;
16 break;
17 }
18 System.out.println(str);
这种解法只是用switch-case的方式来解决而已,思路和上面一样。
最后再来一种不用jdk的方法来解决:
1package sihai;
2public class Test {
3 public static void main(String[] args) {
4 for(int i=0; i<32; ++i)
5 {
6 int a[] = new int[5];
7 int temp = i;
8 int index = 4;
9 while (temp >= 1)
10 {
11 a[index--] = temp % 2;
12 temp = temp/2;
13 }
14 for (int idx = 0; idx < 5; ++idx)
15 {
16 System.out.print(a[idx]);
17 }
18 System.out.println();
19 }
20 }
21}
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”计划02打卡: 问题描述 十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号,分别表示十进制数的0至15。十六进制的计数方法是满16进1,所以十进制数16在十六进制中是10,而十进制的17在十六进制中是11,以此类推,十进制的30在十六进制中是1E。 给出一个非负整数,将它表示成十六进制的形式。 输入格式 输入包含一个非负整数a,表示要转换的数。0<=a<=2147483647 输出格式 输出这个整数的16进制表示 样例输入 30 样例输出 1E
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Integer n = in.nextInt();
in.close();
System.out.println(Integer.toHexString(n).toUpperCase());
}
}
上面是api,下面看看其他:
这道题本身是没什么难度的,只要用递归处理,当输入的数字大于等于16时,则递归处理该数整除16的值,然后再输出最后一位即可。
但是,我在做的时候,一开始没有考虑到整除16后的值大于9的情况和整除16的次数大于9的情况,结,如下图这里写图片描述
以后要注意考虑全方面和一定要注意数据范围!
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int[] b=new int[8];
//数组b的元素个数由a决定,由于a<=2^32,即a<=16^8
char[] s={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
if(a>=0&&a<16){
for(int i=0;i<16;i++){
int m=a%16;
if(m==i)
System.out.println(s[i]);
}
}
else{
int i=0;
while(a!=0){
b[i]=a%16;
a=a/16;
i++;
}
for(int j=i-1;j>=0;j--){
if(b[j]==10)
System.out.print("A");
else if(b[j]==11)
System.out.print("B");
else if(b[j]==12)
System.out.print("C");
else if(b[j]==13)
System.out.print("D");
else if(b[j]==14)
System.out.print("E");
else if(b[j]==15)
System.out.print("F");
else
System.out.print(b[j]);
}
}
}
}
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”计划03打卡: 问题描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 输入格式 每个测试案例包括2行: 第一行输入一个整数n(1<=n<=100000),表示数组中元素的个数。 第二行输入n个整数,表示数组中的每个元素,这n个整数的范围是[1,1000000000]。 输出格式 对应每个测试案例,输出出现的次数超过数组长度的一半的数,如果没有输出-1。 样例输入 9 1 2 3 2 2 2 5 4 2 9 1 1 1 2 2 2 3 3 3 样例输出 2 -1
/**
* 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
* 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
* 由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
*/
public int findMoreThanHalfNum(int[] numbers) {
int length = numbers.length;
if (length == 0) return 0;
int num = numbers[0], count = 1;
for (int i = 1; i < length; i++) {
if (numbers[i] == num) count++;
else count--;
if (count == 0) {
num = numbers[i];
count = 1;
}
}
// Verifying
count = 0;
for (int i = 0; i < length; i++) {
if (numbers[i] == num) count++;
}
if (count * 2 > length) return num;
return 0;
}
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”计划04打卡: 问题描述 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 输入 输入可能包含多个测试样例,对于每个测试案例, 输入的第一行为两个整数m和n(1<=m,n<=1000):代表将要输入的矩阵的行数和列数。 输入的第二行包括一个整数t(1<=t<=1000000):代表要查找的数字。 接下来的m行,每行有n个数,代表题目所给出的m行n列的矩阵(矩阵如题目描述所示,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 输出 对应每个测试案例, 输出”Yes”代表在二维数组中找到了数字t。 输出”No”代表在二维数组中没有找到数字t。 样例输入 3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 8 9 10 样例输出 YES NO
public class Main {
public boolean Find(int target, int [][] array) {
int rowCount = array.length;//获取数据的行数
int colCount = array[0].length; //获取数据的列数
int i,j;
i=rowCount-1;
j=0;
while((i >=0 )&&(j<colCount)) {
if (target == array[i][j]) {
return true;
}
else if (target<array[i][j]) {
i--;
}else {
j++;
}
}
return false;
}
}
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”计划05打卡: 问题描述 理论知识学习,算法基础,理解时间复杂度,理解空间复杂度。 输入 无 输出 无
参考答案:https://blog.csdn.net/halotrriger/article/details/78994122