2023-12-17 周记 0x002
· Life
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
快速选择思想类似快速排序
[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);
}
}
}