这几天笔试常考算法

快来打我* 2024-02-17 16:15 31阅读 0赞

1.求两个数公约数

public class Gongyue {
        public static void main(String args[]){
            int max = getMaxGongyue(11,12);
            System.out.println(max);
        }
    
        public static int getMaxGongyue(int a, int n) {
            if (a < n) {
                int temp = a;
                a = n;
                n = temp;
            }
            while(a%n!=0){
                int temp = a%n;
                a = n;
                n = temp;
            }
            return n;
        }
    }

2.快速排序

public class Kuaipai {
    
        public int[] sortQ(int[] temp, int low, int high) {
            int pos;
            if (low < high) {
                pos = trans(temp, low, high);
                sortQ(temp, low, pos - 1);
                sortQ(temp, pos + 1, high);
    
            }
            return temp;
        }
    
        public int trans(int[] temp, int left, int right) {
    
            int prvotkey = temp[left];
    
            while (left < right) {
                while (temp[right] >= prvotkey && left < right) {
                    right--;
                }
                temp[left] = temp[right];
                while (temp[left] <= prvotkey && left < right) {
                    left++;
                }
                temp[right] = temp[left];
            }
            temp[left] = prvotkey;
    
            return left;
        }
    
        public static void main(String args[]) {
            int[] temp = { 6, 1, 9, 4, 10, 13 };
            int[] sorts = new Kuaipai().sortQ(temp, 0, 5);
            for (int i = 0; i < sorts.length; i++) {
                System.out.println(sorts[i]);
            }
        }
    }

3.字母全排列，例如abc这3字母，可以排列成：abc，bac，cba等

public class QuanPai {
        public static void permutation(char[] buf, int start, int end) {
            if (start == end) {// 当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
                for (int i = 0; i <= end; i++) {
                    System.out.print(buf[i]);
                }
                System.out.println();
            } else {// 多个字母全排列
                for (int i = start; i <= end; i++) {
                    char temp = buf[start];// 交换数组第一个元素与后续的元素
                    buf[start] = buf[i];
                    buf[i] = temp;
    
                    permutation(buf, start + 1, end);// 后续元素递归全排列
    
                    temp = buf[start];// 将交换后的数组还原
                    buf[start] = buf[i];
                    buf[i] = temp;
                }
            }
        }
        public static void main(String args[]){
            char[] buf = {'a','b','c','d'};
            permutation(buf,0,3);
        }
    }

4.十进制转2进制，倒序2进制数，再输出对应的10进制

public class Ten2Two {
        public static void main(String args[]){
            String s = getTwo(23);
            char[] cs = s.toCharArray();
            System.out.println(cs);
            for(int i=0;i<cs.length/2;i++){
                char temp = cs[i];
                cs[i] = cs[cs.length-1-i];
                cs[cs.length-1-i] = temp;
            }
            System.out.println(cs);
            int sum = 0;
            for(int i=0;i<cs.length;i++){
                sum = 2*sum+Integer.parseInt(cs[i]+"");
            }
            System.out.println(sum);
        }
    
        public static String getTwo(int t){
            StringBuffer sb = new StringBuffer();
            while(t!=0){
                sb.insert(0, t % 2);
                t = t/2;
            }
            return sb.toString();
        }
    }

5.给你一个数字序列，要求找到最大的数放中间，其余数按大小顺序依次放该数的左边和右边

public class SpaTestOne {
        public static void main(String args[]) {
            int[] a = { 1, 45, 23, 74, 4, 32, 55,66 };
            maoPao(a);
            printAll(a);
        }
    
        /**
         * 输出所有数组元素
         * @param array
         */
        public static void printArray(int[] array) {
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    
        /**
         * 按题目条件输出数据
         * @param array  已从小到大排好序数组
         */
        public static void printAll(int[] array) {
            int[] temp = new int[array.length];
            int tempindex = 0;
            for (int i = 0; i < array.length / 2;i++) {
                temp[i] = array[tempindex];
                temp[array.length - i-1] = array[tempindex + 1];
                tempindex=tempindex+2;
            }
            temp[array.length / 2] = array[array.length - 1];
            printArray(temp);
        }
    
        //冒泡进行排序
        public static void maoPao(int[] array) {
            for (int i = 0; i < array.length; i++) {
                for (int j = 1; j < array.length - i; j++) {
                    //比较相邻数大小
                    if (array[j - 1] > array[j]) {
                        //交换
                        int temp = array[j - 1];
                        array[j - 1] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
    }