Design
Design Tic-Tac-Toe
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
we can record the marks of rows, cols and diagnoal by a array.
so the question is easy to solve.
rows[row][id]cols[col][id]leftDiag[id]
public class TicTacToe {
int[] leftDiag = new int[2];
int[] rightDiag = new int[2];
int[][] rows;
int[][] cols;
int n;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
rows = new int[n][2];
cols = new int[n][2];
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int id = player - 1;
rows[row][id]++;
cols[col][id]++;
if(row == col) {
leftDiag[id]++;
}
// error-prone 这两个有一个重叠的点
if(row + col == n - 1) {
rightDiag[id]++;
}
if(rows[row][id] == n || cols[col][id] == n || leftDiag[id] == n || rightDiag[id] == n) {
return player;
} else {
//System.out.println(id + " " + rightDiag[id]);
return 0;
}
}
}
Design Snake Game
有几个问题：
- 用什么来表示snake，需要不断的从尾部插入新的数，可以用queue来表示
- 保证不会越界，每次move之后，需要判断越界情况
- 吃到自己的身体会gameover
如何来表示移动？ 在头部加入新的位置，在尾部移除老的位置。 所以queue是不够的，需要deque。
如何在deque里面表示坐标？
两个deque，一个存x，一个存y, 不行，不能组成配对- 新建一个object存坐标
- 把二维坐标转换成一维(x * col + y)
因为food是一个接一个的出现的，所以我们需要一个index来指示我们当前吃到哪个food了。
public class SnakeGame {
Deque<Integer> q = new LinkedList<>();
int[][] food;
int row;
int col;
int foodIndex; // if it's the last food
public SnakeGame(int width, int height, int[][] food) {
this.food = food;
this.row = height;
this.col = width;
foodIndex = 0;
q.offerFirst(0);
}
/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */
public int move(String direction) {
int x = q.peekFirst() / col;
int y = q.peekFirst() % col;
if(direction.equals("U")) x--;
if(direction.equals("D")) x++;
if(direction.equals("L")) y--;
if(direction.equals("R")) y++;
// overstep the boundary
if(x < 0 || y < 0 || x >= row || y >= col) {
//System.out.println("overstep the boundary: " + x + " " + y);
return -1;
}
// hit itself, except its tail
// x 和 y要配对
if(q.contains(x * col + y) && q.peekLast() != (x * col + y)) {
//System.out.println("hit itself: " + x + " " + y);
return -1;
}
// no food anymore
if(foodIndex >= food.length) {
q.offerFirst(x * col + y);
q.pollLast();
return q.size() - 1;
}
// find food
if(food[foodIndex][0] == x && food[foodIndex][1] == y) {
q.offerFirst(x * col + y);
foodIndex++;
return q.size() - 1;
} else {
q.offerFirst(x * col + y);
q.pollLast();
return q.size() - 1;
}
}
}
Design Twitter
一个典型的 Observer pattern，
为了降低耦合度，每个 user 维护自己的 tweet list 和 follow list，而 post tweet 只是负责自行生产，而不主动执行 push; 每次刷新的时候自己从 follow 列表抓 tweets 就好了。
这题一个需要注意的细节是，排序顺序是按照 timestamp，接口里给的 tweetId ，和时间顺序没有必然的联系，所以要自行维护全局时间戳。
除此之外就是比较直观的 merge k sorted list 问题了，为了方便处理，我们维护了一个 Tweet object 的 LinkedList，但同时 Tweet 存了一个自己的 prev 指针，方便进行多路归并的时候正确找到下一个元素。
其他需要注意的就是各种 corner case : 关注自己，取关不存在的人，取关自己本来就没关注的人，自己或者自己的关注用户没有任何 post，等等。
这种代码比较长，比较复杂的题目，怎么样让自己写的尽量对呢？
多写注释！思路清晰
public class Twitter {
HashMap<Integer, Deque<Tweet>> posts;
HashMap<Integer, Set<Integer>> follows;
int time;
public class Tweet implements Comparable<Tweet> {
int tweetId;
int timestamp;
Tweet prev;
public Tweet(int tweetId, int timestamp) {
this.tweetId = tweetId;
this.timestamp = timestamp;
prev = null;
}
public int compareTo(Tweet a) {
// reverseOrder
return a.timestamp - this.timestamp;
}
}
/** Initialize your data structure here. */
public Twitter() {
posts = new HashMap<>();
follows = new HashMap<>();
time = 0;
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
Tweet tweet = new Tweet(tweetId, time++);
// if valid
if(!posts.containsKey(userId)) {
posts.put(userId, new LinkedList<Tweet>());
}
// connect to prev tweet
if(posts.get(userId).size() == 0) {
tweet.prev = null;
} else {
tweet.prev = posts.get(userId).peekFirst();
}
// add to list
posts.get(userId).offerFirst(tweet);
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
public List<Integer> getNewsFeed(int userId) {
List<Integer> result = new ArrayList<>();
PriorityQueue<Tweet> pq = new PriorityQueue<>();
// add user posts
if(posts.containsKey(userId) && posts.get(userId).size() > 0) {
pq.offer(posts.get(userId).peekFirst());
}
if(follows.containsKey(userId)) {
for(int follower : follows.get(userId)) {
if(posts.containsKey(follower) && posts.get(follower).size() > 0) {
pq.offer(posts.get(follower).peekFirst());
}
}
}
// error-prone pq.isEmpty
for(int i = 0; i < 10 && !pq.isEmpty(); i++) {
Tweet tweet = pq.poll();
if(tweet.prev != null) {
pq.offer(tweet.prev);
}
result.add(tweet.tweetId);
}
return result;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if(followerId == followeeId) return;
if(!follows.containsKey(followerId)) {
follows.put(followerId, new HashSet<Integer>());
}
follows.get(followerId).add(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if(followerId == followeeId) return;
if(follows.containsKey(followerId)) {
if(follows.get(followerId).contains(followeeId)) {
// error-prone
// remove element in set
follows.get(followerId).remove(followeeId);
}
}
}
}
Insert Delete GetRandom O(1)
为了same probability，需要一个序号连续的list。 为了方便查询，需要一个map，map映射了插入数字和位置的关系。
当需要删除一个数的时候，我们就把它和最后一个数互换位置，然后把list的最后一个数删掉就可以了，注意要更新map。
Zigzag Iterator
难点：如何设计一个高效的循环方式，如何去设计你要维护的变量。
该题实际上就是轮流取两个列表的下一个元素。我们存下两个列表的迭代器，然后用一个递增的turns变量和取模的方法来判断该取哪一个列表的元素。
学会使用Iterator。
follow up
what if you are given k 1d vectors?
用一个迭代器列表来维护这些迭代器，如果这个迭代器为空那么就要移出列表，同时将当前的位置-1.
public class ZigzagIterator implements Iterator<Integer> {
List<Iterator<Integer>> itlist;
int turns;
public ZigzagIterator(List<Iterator<Integer>> list) {
this.itlist = new LinkedList<Iterator<Integer>>;
// 剔除空的iterator
for(Iterator<Integer> it : list) {
if(it.hasNext()) {
itlist.add(it);
}
}
turns = 0;
}
public int next() {
if(!hasNext()) {
return 0;
}
int res = 0;
int pos = turns % itlist.size();
Iterator<Integer> curr = itlist.get(pos);
int res = curr.next();
if(!curr.hasNext()) {
itlist.remove(curr);
turns = pos - 1;
}
turns++;
return res;
}
public boolean hasNext() {
return itlist.size() > 0;
}
}
Design Phone Directory
需要什么数据结构 实现check， HashSet，已经用过的数放进去。 有序的release， Queue check是否在有效范围， max
Moving Average from Data Stream
这题很简单用一个ArrayDeque 就可以很轻松的实现。
易错点：当windows的大小等于设计大小的时候如何处理，这个case折腾了自己半天。
Peeking Iterator
考点是什么？
为了能peek后下次next还得到同样的数字，我们要用一个缓存保存下一个数字。这样当peek时候，返回缓存就行了，迭代器位置也不会变。
当next的时候除了要返回缓存，还要将缓存更新为下一个数字，如果没有下一个就将缓存更新为null。
如果是int的情况，我们可以维护一个hasPeeked的boolean 变量，如果true 就不用弹出下一个数字。直接返回缓存的数据。
Q：如何支持任意类型的迭代器？ A：使用Generic的方式，代码中已经将Integer替换为Generic的T