Java编程题收集

reference-site-list

steps

生成1-9的随机不重复数组

• 这个题是我自己编的，在以前写数独的时候经常写这种1到9的不重复随机数组

public static int[] getRandomArray() {
    int[] arr = new int[9];
    int[] temp = new int[9];
    // 初始化临时数组
    for (int i = 0; i < temp.length; i++) {
        temp[i] = i + 1;
    }
    for (int i = 0; i < arr.length; i++) {
        int random = new Random().nextInt(temp.length);
        if (temp[random] == 0) {
            i--;
            continue;
        }
        arr[i] = temp[random];
        temp[random] = 0;
    }
    return arr;
}

解释：

• 难点：在于实现不重复，使用两个数组，临时数组是为了生成1到9的数字，然后生成随机数，将随机数存入结果数组，然后将临时数组上该位置的数变成0，下次取到临时数组中的0就代表这个随机数已经存在了，重新生成随机数，这样就实现了不重复。
• 缺点: 这样实现不重复的效果，效率不高，只是现在CUP的速度太快了，感觉不出来很慢。

两个数交换位置

• 很多地方都会用到，记得大学那会儿的教数据结构的美女老师教的空间换时间，时间换空间

• 最常见的空间换时间

int a = 3;
int b = 2;

int temp = a;
a = b;
b = temp;

• 时间换空间

int a = 3;
int b = 2;

a = a + b;
b = a - b;
a = a - b;

解释：用一个变量缓存两个数的和，然后用和减去原来的一个数b得到了a再赋值给b，只要将结果算出来再看代码，其实也很简单。

• 利用异或

int a = 3;
int b = 2;

a = a ^ b;
b = a ^ b;
a = a ^ b;

解释：异或的神奇特性，二进制数a,b; a = 11, b = 10, c = a ^ b = 01, c ^ a = 01 ^ 11 = 10 = b;看懂了没，异或的结果C再和之前的一个数a进行异或就会得到另外一个数b，注意：异或是二进制数的运算哦。

冒泡排序

• 冒泡排序，大学时学C语言的时候第一个算法题，经典

public static void bubbleSort(int[] arr) {
    for (int i = arr.length; i > 0; i--) {
        for (int j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                arr[j] = arr[j] + arr[j + 1];
                arr[j + 1] = arr[j] - arr[j + 1];
                arr[j] = arr[j] - arr[j + 1];
            }
        }
    }
}

解释：

• 假设是4, 1, 7, 9 这四个数，用冒泡排序，由小到大排序，相邻两个数比较，将最大的数移动到右边，模型想清楚了，然后就知道该怎么写代码了。
• 第一次比较是从第一个数字开始，和它后面的一个数比较，然后第2个数和它后面的第3个数比较，只掉第n-1个数和第n个数比较。这就是内部循环要做的事，
• 找出一个最大数算一次大循环，然后就知道外部循环要怎么写，次数是递减的。
• 总之就是外部循环控制内部循环的最大循环次数是递减的，内部循环从0递增。

选择排序

• 选择排序，我做冒泡排序时候自己就想出来过这种更直接简单的排序，个人觉得比冒泡直观，反而觉得冒泡比较绕

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }
        }
    }
}

• 选择排序就是将第一个数依次后他后面的其他数进行比较，然后把最小的数放在第一位，这样就找到了第一个最小的数，然后就从第二个数开始依次后它后面的其他数比较，这种思考明显比冒泡那种每次都进行相邻比较要简单清晰
• 外层循环的变量就是控制当前是第几个数和它后面的数在进行比较，里面的数就是外面的数的后面一个递增，模型简单代码看着也简单。

递归实现1 + 2 + 3 + … + 100

• 递增相加是递归最原始的题目,然后是求阶乘，然后是斐波拉契数列，兔子问题，走楼梯，汉诺塔

public static int recurse(int num) {
    if (num <= 1) {
        return 1;
    }
    return num + recurse(num - 1);
}

• 递归，就是两个点，最底层的一个停止标志，然后就是变化的规则，先只想它和它挨着的一种情况，然后就套进来，思路就清晰了，递归就像是俄罗斯套娃。

生成100个1到100的随机数，去重后并进行从小到大的排序

• 去重问题

public static void deduplicateAndSort() {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        int random = new Random().nextInt(100) + 1;
        list.add(random);
    }
    System.out.println("randomList: " + Arrays.toString(list.toArray()));
    // 不使用set进行去重,新创建一个list，新list中只保留和旧list对比后，新list中不存在的数
    List<Integer> newList = new ArrayList<>();
    for (Integer item : list) {
        if (!newList.contains(item)) {
            newList.add(item);
        }
    }
    // 使用sort去排序
    /*
    newList.sort(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
    */
    // 不使用sort排序
    for (int i = 0; i < newList.size() - 1; i++) {
        for (int j = i + 1; j < newList.size(); j++) {
            int valI = newList.get(i);
            int valJ = newList.get(j);
            if (valI > valJ) {
                newList.set(i, valJ);
                newList.set(j, valI);
            }
        }
    }
    System.out.println("result: " + Arrays.toString(newList.toArray()));
}

去重，核心在于比较，

• 方案1：不添加另外的集合来存储的话，就是类似选择排序一样，挨着和后面的数进行比较，找到和当前的参照数相同的数，把后那个数去掉，然后集合长度变化，注意循环变量此时要自减1。
• 方案2：添加另外一个集合来存储不重复的数，遍历原集合，每个数判断一下是否在新集合中，如果在就不存，就保证了新集合中的数没有重复，就是原集合去重后的结果了。
  方案1是不添加新的内存空间，省空间。方案2是添加空间。有点类似空间换时间，时间换空间那味了。