Life

今年冬天有点冷啊，慢慢恢复跑步吧，戒掉不良习惯。

技术太菜了，基础也不是很好，英语烂。

继续努力学习啊！

松懈了一断时间！

多写代码，读代码。

多总结、思考，必要记录笔记。

闲暇之余也要找点心情愉快的事情做，看看动漫、小说。

  • Rick and Morty
  • 朋友的游戏

Share

研究下了迷宫算法，下面两个很好的资料。

Randomized Prime Alogirthm 实现

用一个 2D array，最好是奇数长和宽，使用任意算法(DFS、Prime 等)遍历奇数坐标，过程中并把朝向的偶数位置设置成路。


    public TETile[][] generate() {
        world[0][HEIGHT - 2] = Tileset.NOTHING;
        world[WIDTH - 1][1] = Tileset.NOTHING;

        List<Cell> V = new ArrayList<>();
        Cell start = new Cell(0, 0);

        do {
            start.x = r.nextInt(HEIGHT);
        } while (start.x % 2 == 0);

        do {
            start.y = r.nextInt(WIDTH);
        } while (start.y % 2 == 0);

        V.add(start);

        while (!V.isEmpty()) {
            int idx = r.nextInt(V.size());
            Cell randomCell = V.get(idx);
            List<Cell> neighbors = randomCell.neighbors();
            if (neighbors.isEmpty()) {
                V.remove(idx);
            } else {
                Cell neiCell = neighbors.get(r.nextInt(neighbors.size()));
                V.add(neiCell);

                world[neiCell.y][neiCell.x] = Tileset.NOTHING;
                world[(neiCell.y + randomCell.y) / 2][(neiCell.x + randomCell.x) / 2] = Tileset.NOTHING;
            }
        }

        return world;
    }

    private class Cell {
        public int x;
        public int y;

        public Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public List<Cell> neighbors() {
            List<Cell> res = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                int nx = x + directions[i][0], ny = y + directions[i][1];
                if (nx < 0 || ny < 0 || nx >= HEIGHT || ny >= WIDTH) {
                    continue;
                }
                if (world[ny][nx].equals(Tileset.WALL)) {
                    res.add(new Cell(nx, ny));
                }
            }
            return res;
        }
    }

Algorithm

LC 215. 数组中的第 K 个最大元素

快速选择思想类似快速排序
        [3,2,1,5,6,4], k = 2
将数组分割成两部分, <= x, >= x  x为数组里的随机数(x = 3)
        1 2 3      5 6 4
        统计一别的元数个数，用k判断下轮遍历是在左边，还是右边

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    int quickSelect(vector<int> &nums, int lo, int hi, int k) {
        if (lo >= hi) return nums[hi];

        int i = lo - 1, j = hi + 1;
        // 可以随机选取,避免有序数组
        int x = nums[rand() % (hi - lo + 1) + lo];
        // int x = nums[(lo + hi) >> 1];
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(nums[i], nums[j]);
        }
        int cnt = hi - j;
        if (k <= cnt) {
            return quickSelect(nums, j + 1, hi, k);
        } else {
            return quickSelect(nums, lo, j, k - cnt);
        }
    }
}