脚踏实地

public class MyTest {

    public static void main(String[] args) {
        Mazeback mazeback = new Mazeback();

        int[][] map = mazeback.createMap();
        mazeback.list(map);

        System.out.println("自动寻找路线：");

        mazeback.setWay(map, 1, 1);
        mazeback.list(map);
    }

}


class Mazeback {

    // 创建地图
    public int[][] createMap() {
        // 地图
        int[][] map = new int[7][8];

        for (int i = 0; i < 7; i++) {
            map[i][0] = 1;
            map[i][7] = 1;
            map[6][i] = 1;
            map[0][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        return map;
    }

    // 遍历地图
    public void list(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");
            }
            System.out.println();
        }
    }

    // 寻找路径
    // 1：墙；2：通路，3：死路
    public boolean setWay(int[][] map, int row, int column) {
        if (map[5][6] == 2) {
            return true;
        }
        if (map[row][column] == 0) {

            // 先假设是通路
            map[row][column] = 2;

            // 寻找路径顺序：下，右，上，左
            if (setWay(map, row + 1, column)) {
                return true;
            } else if (setWay(map, row, column + 1)) {
                return true;
            } else if (setWay(map, row - 1, column)) {
                return true;
            } else if (setWay(map, row, column - 1)) {
                return true;
            } else {
                // 当标记为3时，说明是死路走不通
                map[row][column] = 3;
                return false;
            }
        }
        return false;
    }

}

public class MyTest {

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.exec(0);
    }

}


class EightQueens {

    private int[] arr;

    private int max;

    public EightQueens() {
        this.max = 8;
        this.arr = new int[max];
    }


    // 算法
    public void exec(int position) {
        // 如果当前位置等于max说明解法成立，需要回溯
        if (position == max) {
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            arr[position] = i;
            if (check(position)){
                exec(position + 1);
            }
        }
    }


    // 判断皇后位置是否冲突
    private boolean check(int position) {
        for (int j = 0; j < position; j++) {
            // 判断是否在同一列或在同一斜线上
            if (arr[position] == arr[j] || Math.abs(position - j) == Math.abs(arr[position] - arr[j])) {
               return false;
            }
        }
        return true;
    }


    // 打印数组
    private void print() {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "");
        }
        System.out.println();
    }

}

public class HouseChessBoardDemo {
    public static void main(String[] args) {
        HouseChessBoard houseChessBoard = new HouseChessBoard(7, 7, 2, 4);
        houseChessBoard.showChessBoard();
    }
}

class HouseChessBoard {

    /**
     * 表示棋盘的列
     */
    private int x;
    /**
     * 表示棋盘的行
     */
    private int y;
    /**
     * 创建一个数组，标记棋盘的各个位置是否被访问过，true表示已经访问过
     */
    private boolean visited[];
    /**
     * 使用一个属性，标记是否棋盘的所有位置都被访问 如果为true,表示成功
     */
    private boolean finished;

    private int[][] chessboard;

    public HouseChessBoard(int x, int y, int row, int column) {
        this.x = x;
        this.y = y;
        this.visited = new boolean[x * y];
        this.chessboard = new int[x][y];
        traversalChess(this.chessboard, row-1, column-1, 1);
    }

    public void showChessBoard(){
        for (int[] ints : this.chessboard) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }

    public void traversalChess(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;

        // 将当前位置标记为已经访问过
        visited[row * x + column] = true;

        // 获取当前位置的下一个可走通的位置的集合
        ArrayList<Point> nextPos = getNext(new Point(column, row));

        sort(nextPos);

        while (nextPos.size() > 0) {
            // 获取当前可走通的位置
            Point current = nextPos.remove(0);
            // 判断当前该点是否被访问过,如果没有被访问过则继续向下访问
            if (!visited[current.y * x + current.x]) {
                traversalChess(chessboard, current.y, current.x, step + 1);
            }
        }

        // 当遍历完可走的位置集合后，如果发现该路不通，则进行回溯，否则标记为完成
        if (step < x * y && !finished) {
            chessboard[row][column] = 0;
            visited[row * x + column] = false;
        } else {
            finished = true;
        }
    }

    // 将可走通路根据回溯次数进行从小到大排序
    public void sort(ArrayList<Point> points){
        points.sort((o1, o2) -> {
            int next1 = getNext(o1).size();
            int next2 = getNext(o2).size();
            return next1 - next2;
        });
    }



    // 获取下一个可走的位置
    public ArrayList<Point> getNext(Point current) {
        ArrayList<Point> ps = new ArrayList<Point>();
        Point p1 = new Point();
        // 表示马儿可以走5这个位置
        if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走6这个位置
        if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走7这个位置
        if ((p1.x = current.x + 1) < x && (p1.y = current.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走0这个位置
        if ((p1.x = current.x + 2) < x && (p1.y = current.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走1这个位置
        if ((p1.x = current.x + 2) < x && (p1.y = current.y + 1) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走2这个位置
        if ((p1.x = current.x + 1) < x && (p1.y = current.y + 2) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走3这个位置
        if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走4这个位置
        if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

}

class BubbleSorting {

    public int[] sort(int[] data) {
        int len = data.length - 1;
        int tmp;
        boolean flag = false;

        for (int i = 0; i <len; i++){
            for (int j = 0; j < len - i; j++) {
                // 将当前值与next值进行比较，如果当前值大于next值则交换两者之间的位置
                if (data[j] > data[j+1]){
                    flag = true;
                    tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;
                }
            }

            // 加入标志为进行判断，如果整个循环下啦都没有交换位置，说明该数组是有序的，所以直接退出循环
            if (!flag){
                break;
            }else {
                flag = false;
            }
        }
        return data;
    }
}

class SelectSorting{

    public int[] sort(int[] data) {
        for (int i = 0; i < data.length; i++){

            int min = i;

            for (int j = i+1; j < data.length; j++) {
                // 如果next值大于当前值，则记录该值和该值的位置，等全部比较完毕后，将最大的一个与数据的末尾进行替换
                if (data[i] > data[j]){
                    min = j;
                }
            }

            // 将每次循环中的最小的值，调整到最前面
            if (min != i){
                int tmp = data[i];
                data[i] = data[min];
                data[min] = tmp;
            }
        }
        return data;
    }
}

class InsertSorting{

    public int[] sort(int[] data) {
        for (int i = 1; i < data.length; i++){
            // 如果当前要插入的值 data[i] > 有序队列中最后一个，则将其直接插入到最后一个
            if (data[i] > data[i - 1]){
                continue;
            }

            int tmp = data[i];
            int index = i - 1;
            // 如果当前位置的值【tmp】小于 上一个位置的值【data[index]】说明当前值需要插入到有序队列中
            while (index >= 0 && tmp < data[index]){
                data[index + 1] = data[index];
                index--;
            }
            data[index + 1] = tmp;
        }
        return data;
    }

}

class MergeSorting {

    // 递归拆分算法
    public void divide(int[] arr, int start, int end, int[] tmpArr) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) >> 1;

        // 分别向左向右递归
        divide(arr, start, mid, tmpArr);
        divide(arr, mid + 1, end, tmpArr);

        // 拆分一次合并一次
        merge(arr, start, mid, end, tmpArr);

    }

    // 合并算法
    public void merge(int[] arr, int start, int mid, int end, int[] tmpArr) {
        int leftIndex = start;
        int rightIndex = mid + 1;
        int tmpArrIndex = 0;

        // 判断是否超出范围
        while (leftIndex <= mid && rightIndex <= end) {

            // 将两组数据进行比较，按照从小到大的顺序将两组数据填入 tmpArr 中
            if (arr[leftIndex] <= arr[rightIndex]) {
                tmpArr[tmpArrIndex] = arr[leftIndex];
                ++leftIndex;
            } else {
                tmpArr[tmpArrIndex] = arr[rightIndex];
                ++rightIndex;
            }
            ++tmpArrIndex;
        }

        // 判断两组数据是否还有剩余，如果有剩余数据，则直接将数据追加到 tmpArr 数组后边
        while (leftIndex <= mid) {
            tmpArr[tmpArrIndex] = arr[leftIndex];
            ++leftIndex;
            ++tmpArrIndex;
        }

        while (rightIndex <= end) {
            tmpArr[tmpArrIndex] = arr[rightIndex];
            ++rightIndex;
            ++tmpArrIndex;
        }

        // 将两组数据进行合并
        tmpArrIndex = 0;
        int tmpLeftIndex = leftIndex;
        while (tmpLeftIndex <= end) {
            arr[tmpLeftIndex] = tmpArr[tmpArrIndex];
            ++tmpLeftIndex;
            ++tmpArrIndex;
        }
    }
    
}

class QuickSorting {

    public void sort(int[] data, int l, int r) {

        // 如果开始的位置大于等于结束的位置则不用进行比较直接退出
        if (l >= r){
            return;
        }

        int left = l;
        int right = r;

        // 基准数值，将小于该数值的放在该数字的左边，大于该数值的放在右边
        int pivot = data[left];

        while (left < right) {

            // 从右向左开始比较，如果此数大于等于基准数则将right索引向前移动，否则，将该值覆盖到对应的 data[left] 中
            while (left < right && data[right] >= pivot) {
                --right;
            }
            data[left] = data[right];

            // 从左向右开始比较，如果此数小于等于基准数则将left索引向后移动，否则，将该值覆盖到对应的 data[right] 中
            while (left < right && data[left] <= pivot) {
                ++left;
            }
            data[right] = data[left];
        }

        // 此时left与right指向重合的位置为基准所在的位置，需要将该位置覆盖掉为基准的值
        data[left] = pivot;

        // 递归排序
        sort(data, l, left);
        sort(data, right+1,r);
    }
} 

class ShellSorting{

    // 希尔排序，交换法
    public void sortSwap(int[] data){
        int size = data.length;
        int tmp = 0;

        // 将数据分组，分组数量：data.length/2
        for (int gap = size >> 1; gap > 0; gap >>= 1){

            for (int i = gap; i < size; i++) {
                // 遍历每组中的元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 将每组中的元素进行排序（交换元素）
                    if (data[j] > data[j + gap]){
                        tmp = data[j];
                        data[j] = data[j+gap];
                        data[j+gap] = tmp;
                    }
                }
            }
        }
    }

    // 插入法，融入 插入排序 思想
    public void sort(int[] data){
        int size = data.length;
        int tmp = 0;

        // 将数据分组，分组数量：data.length/2
        for (int gap = size >> 1; gap > 0; gap >>= 1) {
            for (int i = gap; i < size; i++) {

                tmp = data[i];
                int index = i;

                // 如果当前位置的值【tmp】小于 上一个位置的值【data[index]】说明当前值需要插入到有序队列中
                while (index - gap >= 0 && tmp < data[index - gap]){
                    data[index] = data[index - gap];
                    index -= gap;
                }
                data[index] = tmp;
            }
        }
    }
    
}

class HeapSorting {

    public void sort(int[] arr) {
        // 计算树中的叶子结点位置
        int leafNode = (arr.length >> 1) - 1;

        // 构建大顶堆，此处需要注意 i >= 0 需要算根结点
        for (int i = leafNode; i >= 0; i--) {
            buildMaxHeap(arr, i, arr.length);
        }

        // 构建大顶堆后，将根元素与树中的最后一个进行交换，再循环构建大顶堆
        int tmp;
        for (int i = arr.length - 1; i > 0; i--) {
            tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            buildMaxHeap(arr, 0, i);
        }
    }

    /**
     * 堆排序核心代码 构建大顶堆
     *
     * @param arr 需要调整的数组
     * @param i   非叶子结点的索引位置
     * @param len 每次调整的长度
     */
    public void buildMaxHeap(int[] arr, int i, int len) {
        // 保存非叶子结点的位置如果该结点的值小于子结点的值，则需要进行交换
        int tmp = arr[i];

        // 从上至下，从左至右 遍历. 从第一个左子结点开始遍历
        for (int n = (i << 1) + 1; n < len; n = (n << 1) + 1) {
            // 如果左子结点 < 右结点，则需要将 n 指向右结点，即后移
            if (n + 1 < len && arr[n] < arr[n + 1]) {
                n++;
            }
            // 当前非叶子结点 < 当前子结点
            if (arr[n] > tmp) {
                // 将当前非叶子结点指向叶子结点
                arr[i] = arr[n];
                // 将i指向当前叶子结点，待最后将其变为 非叶子结点的值 即tmp的值
                i = n;
            } else {
                break;
            }
        }
        // 与前面互相呼应
        arr[i] = tmp;
    }
}

class BucketSorting {

    public void sort(int[] arr) {
        // 求数组中最大数的长度
        int maxNum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        int maxNumLen = String.valueOf(maxNum).length();

        // 桶，用于保存数据
        int[][] buckets = new int[10][arr.length];

        // 存放每个桶的保存数据的索引
        int[] bucketElementIndex = new int[10];

        // 将数组中的元素 按照 个、十、百、千 …… 的顺序依次放入桶中
        for (int i = 0, n = 1; i < maxNumLen; i++, n *= 10) {

            // 遍历二维数组
            for (int j = 0; j < arr.length; j++) {
                // 计算放入的桶的下标
                int index = arr[j] / n % 10;
                buckets[index][bucketElementIndex[index]] = arr[j];
                bucketElementIndex[index]++;
            }

            // 从桶中依次取出元素并放入原数组中
            int index = 0;
            for (int f = 0; f < bucketElementIndex.length; f++) {
                // 判断桶中是否保存数据
                if (bucketElementIndex[f] == 0) {
                    continue;
                }
                for (int h = 0; h < bucketElementIndex[f]; h++) {
                    arr[index] = buckets[f][h];
                    index++;
                }
                bucketElementIndex[f] = 0;
            }
        }

    }
}

class LinearSearch{

    public int search(int[] arr, int value){
        for (int i = 0; i < arr.length; i++){
            if (arr[i] == value) {
                return i;
            }
        }
        return - 1;
    }

}

class BinarySearch {

    // 使用二分查找时，arr必须为有序列表
    public int search(int start, int end, int[] arr, int value) {
        // 在 {@param arr} 中 没有查到 {@param value}
        if (start > end || value > arr[end] || value < arr[start]) {
            return -1;
        }

        // 获取中间值，用于分割列表
        int mid = (start + end) >> 1;
        int midVal = arr[mid];

        // 如果 查找的值< 中间值，说明该值可能在mid的左边
        if (value < midVal) {
            return search(start, mid - 1, arr, value);
        }

        // 相反如果 查找的值 > 中间值，说明该值可能在mid的右边
        if (value > midVal) {
            return search(mid + 1, end, arr, value);
        }

        // 使用递归不停的向下细分，当 value == arr[mid] 时 返回该值，说明此时已经找到了
        return mid;
    }
}

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(new BinarySearch().search(arr, 3));
    }
}

class BinarySearch {

    // 使用二分查找时，arr必须为有序列表
    public int search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (arr[mid] == target) {
                return mid;
            }
            // 如果目标值小于中间值则向左边找，反之向右边找
            if (target < arr[mid]) {
                right = mid - 1;
            }

            if (target > arr[mid]) {
                left = mid + 1;
            }
        }
        return -1;
    }

}

class InsertValueSearch {

    // 与二分查找基本相同，只是查找 mid 值发生了变动
    public int search(int start, int end, int[] arr, int value) {
        // 在 {@param arr} 中 没有查到 {@param value}
        if (start > end || value > arr[end] || value < arr[start]) {
            return -1;
        }

        int mid = start + (value - arr[start]) / (arr[end] - arr[start]) * (end - start);
        int midVal = arr[mid];

        if (value < midVal) {
            return search(start, mid - 1, arr, value);
        }

        if (value > midVal) {
            return search(mid + 1, end, arr, value);
        }
        return mid;
    }

}

class FibonacciSearch{
    // lookupTable,需要传入斐波那契数列,例如：{1,1,2,3,5,8,13,21,34,55};
    public static int search(int[] lookupTable,int[] f,int target){

        int low = 0;
        int high = lookupTable.length - 1;

        // k 是 Fibonacci 分割数组下标
        int k = 0;
        int middle = 0;

        while (f[k] < high){
            k ++;
        }

        //利用 java 工具类构造 f[k] 长度的查找表，解决原有查找表元素不够的问题
        int[] temp = Arrays.copyOf(lookupTable,f[k]);
        while (low <= high){
            middle = low + f[k - 1];
            if (target < lookupTable[middle]){
                high = middle -1;
                k --;
            }else if (target > lookupTable[middle]){
                low = middle + 1;
                k -= 2;
            }else{
                return Math.min(middle,high);
            }
        }
        return -1;
    }
}

public class HashTable<K, V> {
    private static final int SIZE = 10; // 哈希表大小
    private LinkedList<Entry<K, V>>[] table; // 链地址法存储

    // 构造方法
    @SuppressWarnings("unchecked")
    public HashTable() {
        table = new LinkedList[SIZE];
        for (int i = 0; i < SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 哈希函数
    private int hash(K key) {
        return Math.abs(key.hashCode()) % SIZE;
    }

    // 插入键值对
    public void put(K key, V value) {
        int index = hash(key);
        LinkedList<Entry<K, V>> bucket = table[index];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value; // 如果键已存在，更新值
                return;
            }
        }

        bucket.add(new Entry<>(key, value)); // 插入新键值对
    }

    // 查找值
    public V get(K key) {
        int index = hash(key);
        LinkedList<Entry<K, V>> bucket = table[index];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null; // 未找到
    }

    // 删除键值对
    public void remove(K key) {
        int index = hash(key);
        LinkedList<Entry<K, V>> bucket = table[index];

        bucket.removeIf(entry -> entry.key.equals(key));
    }

    // 哈希表中的键值对
    private static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 打印哈希表内容
    public void printHashTable() {
        for (int i = 0; i < SIZE; i++) {
            System.out.print("Bucket " + i + ": ");
            for (Entry<K, V> entry : table[i]) {
                System.out.print("[" + entry.key + ": " + entry.value + "] ");
            }
            System.out.println();
        }
    }

    // 测试
    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>();
        hashTable.put("Alice", 25);
        hashTable.put("Bob", 30);
        hashTable.put("Charlie", 35);

        System.out.println("Alice's age: " + hashTable.get("Alice")); // 输出: Alice's age: 25
        System.out.println("Bob's age: " + hashTable.get("Bob"));     // 输出: Bob's age: 30

        hashTable.remove("Alice");
        System.out.println("After removal, Alice's age: " + hashTable.get("Alice")); // 输出: After removal, Alice's age: null

        hashTable.printHashTable();
    }
}