java简单算法 | 刘民锴的个人博客

无标签

发布日期: 2020-10-21

更新日期: 2020-10-21

文章字数: 2.7k

阅读时长: 14 分

阅读次数:

java简单算法.

1.交换两数.

int a = 1;
int b = 2;
System.out.println("原 a = " + a + "; b = " + b);

//方法一：定义临时变量
//好处：①对于任何类型都可以
int tmp = a;
a = b;
b = tmp;
System.out.println("方法一 a = " + a + "; b = " + b);

//方法二： 先加，后减
//好处：无需定义临时变量
//弊端：①相加可能会超出数的存储范围 ②只适用于 数值类型
a = a + b;
b = a - b;
a = a - b;
System.out.println("方法二 a = " + a + "; b = " + b);

//方法三： 异或
//好处：无需定义临时变量
//弊端：①只适用于 数值类型
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("方法三 a = " + a + "; b = " + b);

2.获取三数中的最大值.

int a = 1;
int b = 3;
int c = 2

//三元运算符
int tmp = (a > b) ? a : b;
int sum = (tmp > c) ? tmp : c;
System.out.println("最值 " + sum);

//条件判断语句
int max = 0;
if(a > b){
    max = a;
}else{
    max = b;
}
if(max < c){
    max = c;
}

3.输入年份判断是否是闰年.

能被4整除，但不能被100整除或能被400整除

// 条件判断
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0){
    System.out.println("这一年是闰年");
}else{
    System.out.println("这一年不是闰年");
}

4.这个月底最后一天，是今年的第几天.

//使用switch
int year = 2000;//闰年
int month = 3;//三月份
int totalDay = 0;

switch(month){

case 12:
    totalDay+=30;
case 11:
    totalDay+=31;
case 10:
    totalDay+=30;
case 9:
    totalDay+=31;
case 8:
    totalDay+=30;
case 7:
    totalDay+=31;
case 6:
    totalDay+=30;
case 5:
    totalDay+=31;
case 4:
    totalDay+=30;
case 3:
    totalDay+=31;
case 2:
    if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0){
        totalDay+=29;
    }else{
        totalDay+=28;
    }
case 1:
    totalDay+=31;
    System.out.println(month+"月最后一天是"+year+"年的第"+ totalDay + "天");
}

5.输入两个正整数，求其最大公约数和最小公倍数.

int m = 12;
int n = 15;

//方法一 ： 暴力破解法（枚举）

//最大公约数
int min = (m > n) ? n : m;
for(int i = min; i >= 1; i--){
    if(m % i == 0 && n % i == 0){
        System.out.println("最大公约数是"+i);
        break;
    }   
}

//最小公倍数
int max = (m > n) ? m : n;
for(int i = max;  ;i++){
    if(i % m == 0 && i % n == 0){
        System.out.println("最小公倍数是"+i);
        break;
    }
}

//辗转相除法

//辗转相减法

6.水仙花数（输出所有）.

一个三位数，各位上的立方之和等于其本身
如153 = 1³ + 5³ + 3³
153 370 371 407

//暴力破解法
for(int i = 100; i < 1000; i++){
    int g = i % 10;//个位
    int s = i % 100 / 10;//十位 s = i / 10 % 10
    int b = i / 100;//百位
    int sum = g*g*g + s*s*s + b*b*b;
    if(sum == i){
        System.out.println(sum);
    }
}

7.打印三角 *.

*
**
***
****
***
**
*

for(int i = 1; i <= 7; i++){
    if(i <= 4){
        for(int j = 1; j <= i; j++){
            System.out.print("*");
        }
    }else{
        for(int j = i ; j <= 7; j++){
            System.out.print("*");
        }
    }
    System.out.println("");
}

8.打印菱形 *.

    *
   * *
  * * *
 * * * *
  * * * 
   * *
    *

for(int i = 1; i <= 7; i++){
    //控制空格
    if(i <= 4){
        for(int j = 4; j > i; j--){
               System.out.print(" ");
        }
    }else{
        for(int j = 4; j < i; j++){
                System.out.print(" ");
        }
    }
    // * 号
    if(i <= 4){
        for(int j = 1; j <= i; j++){
            System.out.print("* ");
        }
    }else{
        for(int j = 1 ; j <= 8 - i; j++){
            System.out.print("* ");
        }
    }
    System.out.println("");
}

9.九九乘法表.

1 * 1 = 1    

2 * 1 = 2    2 * 2 = 4    

3 * 1 = 3    3 * 2 = 6    3 * 3 = 9    

4 * 1 = 4    4 * 2 = 8    4 * 3 = 12    4 * 4 = 16    

5 * 1 = 5    5 * 2 = 10    5 * 3 = 15    5 * 4 = 20    5 * 5 = 25    

6 * 1 = 6    6 * 2 = 12    6 * 3 = 18    6 * 4 = 24    6 * 5 = 30    6 * 6 = 36    

7 * 1 = 7    7 * 2 = 14    7 * 3 = 21    7 * 4 = 28    7 * 5 = 35    7 * 6 = 42    7 * 7 = 49    

8 * 1 = 8    8 * 2 = 16    8 * 3 = 24    8 * 4 = 32    8 * 5 = 40    8 * 6 = 48    8 * 7 = 56    8 * 8 = 64    

9 * 1 = 9    9 * 2 = 18    9 * 3 = 27    9 * 4 = 36    9 * 5 = 45    9 * 6 = 54    9 * 7 = 63    9 * 8 = 72    9 * 9 = 81

for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= i; j++){
        System.out.print(i + " * " + j + " = "+ i*j + "\t");
    }
    System.out.println("\n");
}

10.100以内的所有质数（素数）.

只能被本身和1整除的自然数(除了1)

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

for(int i = 2; i <= 100; i++){
    boolean isPrime = true;
    for(int j = 2; j <= i/2 ; j++){
        if(i % j == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime) {
        System.out.print(i + " ");
    }
}

//优化 使用 sqrt(i)
/*
原因    首先，约数是成对出现的。比如24,你找到个约数3,那么一定有个约数8,因为24/3=8。
然后，这对约数必须一个在根号n之前，一个在根号n之后。因为都在根号n之前的话，乘积一定小于n（根号nX根号n=n）。同样，都在根号n之后的话，乘积一定大于n。
所以，如果你在根号n之前都找不到约数的话，那么根号n之后就不会有了。
*/
for(int i = 2; i <= 100; i++){
    boolean isPrime = true;
    for(int j = 2; j <= Math.sqrt(i) ; j++){
        if(i % j == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime) {
        System.out.print(i + " ");
    }
}

// 带标签的
label:for(int i = 2; i <= 100; i++){
    for(int j = 2; j <= Math.sqrt(i) ; j++){
        if(i % j == 0){
            continue label;
        }
    }
    if(isPrime) {
        System.out.print(i + " ");
    }
}

11.1000以内的所有完数.

一个数等于它的因子之和
如 6 = 1 + 2 + 3
因子：除去这个数本身的其他约数

6 28 496

int sum = 0;
for(int i = 1; i <= 1000; i++){
    for(int j = 1; j <= i/2; j++){
        if(i % j == 0){
               sum += j;     
        }
    }
    if(sum == i){
        System.out.print(i + " ");
    }
    sum = 0;
}

12.二维数组打印十行杨辉三角.

上面两数之和等于下面的数
第一行1个元素，第n行n个元素
每一行第一个和最后一个都是1
从第三行开始，对于非第一个元素和最后一个元素的元素有：arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];

    1              |\       1
   1 1       |-----| \      1 1
  1 2 1      |-----| /      1 2 1
 1 3 3 1           |/       1 3 3 1
1 4 6 4 1                   1 4 6 4 1
..........                  .......... 



arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];

int[][] arr = new int[10][];
for(int i = 0; i < arr.length; i++){
    //
    arr[i] = new int[i+1];
    arr[i][0] = 1;//第一个
    arr[i][i] = 1;//最后一个
    for(int j = 1; j < arr[i].length - 1; j++){//第三行开始,第2个元素到倒数第2个元素
        arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
    }
    for(int j = 0; j < arr[i].length; j++){
        System.out.print(arr[i][j] + " ");
    }
    System.out.println();
}

13.二维数组打印回形数.

输入n打印n阶回形数矩阵

1   1 2   1 2 3    1  2  3  4   ....
    4 3   8 9 4   12 13 14  5   ....
          7 6 5   11 16 15  6   ....
                  10  9  8  7   ....
                                ....

int[][] arr = new int[n][n];
for(int i = 0; i < n;  i++){
    for(int j = 0; i < n; j++){
        arr[i][j] = j+1;
    }

}

class RectangleTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入一个数字");
        int len = scanner.nextInt();
        int[][] arr = new int[len][len];

        int s = len * len;
        /*
         * k = 1:向右 k = 2:向下 k = 3:向左 k = 4:向上
         */
        int k = 1;
        int i = 0, j = 0;
        for (int m = 1; m <= s; m++) {
            if (k == 1) {
                if (j < len && arr[i][j] == 0) {
                    arr[i][j++] = m;
                } else {
                    k = 2;
                    i++;
                    j--;
                    m--;
                }
            } else if (k == 2) {
                if (i < len && arr[i][j] == 0) {
                    arr[i++][j] = m;
                } else {
                    k = 3;
                    i--;
                    j--;
                    m--;
                }
            } else if (k == 3) {
                if (j >= 0 && arr[i][j] == 0) {
                    arr[i][j--] = m;
                } else {
                    k = 4;
                    i--;
                    j++;
                    m--;
                }
            } else if (k == 4) {
                if (i >= 0 && arr[i][j] == 0) {
                    arr[i--][j] = m;
                } else {
                    k = 1;
                    i++;
                    j++;
                    m--;
                }
            }
        }

        // 遍历
        for (int m = 0; m < arr.length; m++) {
            for (int n = 0; n < arr[m].length; n++) {
                System.out.print(arr[m][n] + "\t");
            }
            System.out.println();
        }
    }
}

14、数组中的最大值.

int[] arr = {1,5,2,3,10,9,12,98,14,29,25};

int max = arr[0];
for(int i = 1; i < arr.length; i++){
    if(max < arr[i]){
        max = arr[i];
    }
}

System.out.println(max);

15.数组的复制，反转.

arr1 = arr2 属于赋值，不是复制

int[] arr1 = {1,2,3,5};

int[] arr2 = new int[arr1.length];
for(int i = 0; i < arr1.length; i++){
    arr2[i] = arr1[i];
}

反转

int[] arr = {1,2,3,4,5,6};
int len = arr.length;
for(int i = 0; i < len/2; i++){
    int tmp = arr[i];
    arr[i] = arr[len - 1 - i];
    arr[len - 1 - i] = tmp;
}

Arrays.stream(arr).forEach(System.out::println);

int[] arr = {1,2,3,4,5,6};
int len = arr.length;
for(int i = 0,j = len - 1; i < j ; i++,j--){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Arrays.stream(arr).forEach(System.out::println);

16.数组的查找.

线性查找.

int target = 43;
int[] arr = {1,2,3,4,5,192,43,23,1000,67,33,45,7};

for(int i = 0; i < arr.length; i++){
    if(target == arr[i]){//String使用equals, 浮点数使用bigDecimal或精确值，
        System.out.println("存在" + i);
    }
}

二分查找.

前提：有序
只适用于数值型

int[] arr = {2,4,10,34,65,89,100,302,432};
int target = 32;

int len = arr.length;
int min = 0;
int max = len - 1;
int mid = 0;
while(true){
    mid = (max + min) / 2;
    if(max >= min) {
        if(target > arr[mid]){
            min = mid + 1; 
        }else if(target < arr[mid]){
            max = mid - 1;
        }else{
            System.out.println("存在"+mid);
            break;
        }
    }else {
        System.out.println("不存在");
        break;
    }
}

17.数组的排序算法.

时间复杂度：分析关键字的比较次数和记录的移动次数
空间复杂度：分析排序算法中需要多少辅助内存
稳定性：若两个记录A、B，A = B，如果排序后的A、B先后顺序不变 —- 排序是稳定的

十大内部排序算法

选择排序
- 直接选择排序
- 堆排序

交换排序

冒泡排序

int[] arr = {4,5,6,1,2,3};

for(int i = 0; i < arr.length - 1; i++){//
    for(int j = 0; j < arr.length - 1 - i; j++){
        if(arr[j+1] < arr[j]){
            int tmp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = tmp;
        }
    }
}

快速排序

插入排序
- 直接插入排序
- 折半插入排序
- Shell排序
归并排序
桶式排序
基数排序

18.拓展笔试题-1.

创建一个长度为6的int型数组，要求数组元素的值都在1-30之间，且是随机赋值，同时，要求元素的值不同

int[] arr = new int[6];
int min = 1;
int max = 30;
// [min,max] = Math.random()*(max - min + 1) + min;
// [min,max) = Math.random()*(max - min) + min;

for(int i = 0; i < arr.length; i++){
    arr[i] = (int)(Math.random()*(max - min + 1) + min);//[1,30]
    for(int j = 0; j < i; ){
        if(arr[i] == arr[j]){//如果相等 就 跳到内层 开头j = 0
            arr[i] = (int)(Math.random()*(max - min + 1) + min;);//[1,30]
            j = 0;
        }
        j++;//必须拿出来，不然 进入 if 后 j=0 每次都会加 1 --> j = 1
    }
    System.out.println(arr[i]);
}

//方式二：
int[] arr = new int[6];
for (int i = 0; i < arr.length; i++) {
    arr[i] = (int) (Math.random() * 30) + 1;

    for (int j = 0; j < i; j++) {
        if (arr[i] == arr[j]) {//如果相等 就跳到外层的上一次 --i
            i--;
            break;
        }
    }
}

for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

19.拓展笔试题-2.

public class Test{
    public static void main(String[] args){
        int a = 10;
        int b = 20;
        method(a,b);//需要在method方法被调用之后，仅打印出a=100，b=200，请写出method方法的代码
        System.out.println("a="+a);
        System.out.println("b="+b);
    }
//代码编写出

}

看题目好像是在考参数传递，实际上不可能是

解答

public static void method(int a,int b){
    a *= 10;
    b *= 10;

    System.out.println("a="+ a + "\n" + "b=" + b);

    System.exit(1);
}

public static void method(){
    PrintStream ps = new PrintStream(System.out){
        @override
        public void println(String x){
            if("a=10".equals(x)){
                x="a=100";
            }else if("b=20".equals(x)){
                x="b=200";
            }
            super.println(x);
        }
    };
}

20.拓展笔试题-3.

char[] ch = new char[]{'c','h','a','r'};
int[] i = new int[]{1,2,3,4};
System.out.prinln(i);//地址值 println(Object x)
System.out.prinln(ch);// char 由于println重载方法为prinln(char4 g  x[])