public class Logger {
HashMap<String, Integer> map;
/** Initialize your data structure here. */
public Logger() {
map = new HashMap<String, Integer>();
}
/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity. */
public boolean shouldPrintMessage(int timestamp, String message) {
boolean rst = false;
if(!map.containsKey(message) || timestamp - map.get(message) >= 10) rst = true;
if(rst) map.put(message, timestamp);
return rst;
}
}
What if the number of hits per second could be very large? Does your design scale?
建 int[] array 显然就不现实了，不如 deque !
public class HitCounter {
Deque<Integer> deque;
/** Initialize your data structure here. */
public HitCounter() {
deque = new LinkedList<Integer>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
deque.offerFirst(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
if(timestamp <= 300) return deque.size();
int startTime = timestamp - 300;
while(!deque.isEmpty() && deque.peekLast() <= startTime) deque.pollLast();
return deque.size();
}
}
public class TicTacToe {
// array[][index]
// index 0 : # of player 1's pieces
// index 1 : # of player 2's pieces
private int[] leftDiag;
private int[] rightDiag;
private int[][] rows;
private int[][] cols;
private int n;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
leftDiag = new int[2];
rightDiag = new int[2];
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) {
rows[row][player - 1] ++;
cols[col][player - 1] ++;
if(row == col) leftDiag[player - 1] ++;
if(row + col == n - 1) rightDiag[player - 1]++;
if(rows[row][player - 1] == n || cols[col][player - 1] == n ||
leftDiag[player - 1] == n || rightDiag[player - 1] == n){
return player;
} else {
return 0;
}
}
}
看了下论坛，这题还可以进一步做空间优化，利用只有两个玩家的特点省掉一半空间。
public class TicTacToe {
// array[][index]
// index 0 : # of player 1's pieces
// index 1 : # of player 2's pieces
private int leftDiag;
private int rightDiag;
private int[] rows;
private int[] cols;
private int n;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
leftDiag = 0;
rightDiag = 0;
rows = new int[n];
cols = new int[n];
}
/** 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 delta = (player == 1) ? 1: -1;
rows[row] += delta;
cols[col] += delta;
if(row == col) leftDiag += delta;
if(row + col == n - 1) rightDiag += delta;
if(Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
Math.abs(leftDiag) == n || Math.abs(rightDiag) == n){
return player;
} else {
return 0;
}
}
}
用了另外一个 deque 存 body index 速度就快多了超过 54%， 但是没什么大改动就不贴代码了。另外一个小改动是，其实用不着存 score 变量，因为 score = 蛇长度 - 1
public class SnakeGame {
int[][] food;
int foodIndex;
// deque of String "x y" representing positions of snake
Deque<String> snake;
int score;
int rows;
int cols;
/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
this.rows = height;
this.cols = width;
this.food = food;
this.foodIndex = 0;
this.score = 0;
this.snake = new LinkedList<String>();
snake.offerFirst("0,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) {
String[] coordinates = snake.peekFirst().split(",");
int headX = Integer.parseInt(coordinates[0]);
int headY = Integer.parseInt(coordinates[1]);
if(direction.equals("U")) headX--;
if(direction.equals("L")) headY--;
if(direction.equals("R")) headY++;
if(direction.equals("D")) headX++;
// Hit wall
if(headX < 0 || headX >= rows) return -1;
if(headY < 0 || headY >= cols) return -1;
// Hit itself
String newPos = headX + "," + headY;
// It's ok if you bite the tail
if(snake.contains(newPos) && !snake.peekLast().equals(newPos)) return -1;
// No food, just move
if(foodIndex >= food.length){
snake.offerFirst(newPos);
snake.pollLast();
return score;
}
int foodX = food[foodIndex][0];
int foodY = food[foodIndex][1];
// Got food !
if(headX == foodX && headY == foodY){
snake.offerFirst(newPos);
score ++;
foodIndex ++;
return score;
} else {
snake.offerFirst(newPos);
snake.pollLast();
return score;
}
}
}
除此之外就是比较直观的 merge k sorted list 问题了，为了方便处理，我们维护了一个 Tweet object 的 LinkedList，但同时 Tweet 存了一个自己的 prev 指针，方便进行多路归并的时候正确找到下一个元素。
其他需要注意的就是各种 corner case : 关注自己，取关不存在的人，取关自己本来就没关注的人，自己或者自己的关注用户没有任何 post，等等。
public class Twitter {
// Key : user
// Value : list of tweets
HashMap<Integer, LinkedList<Tweet>> tweetsMap;
// Key : user
// Value : list of userId's the user has been following
HashMap<Integer, Set<Integer>> follows;
int timestamp;
private class Tweet implements Comparable<Tweet>{
int timestamp;
int tweetId;
Tweet prev;
public Tweet(int timestamp, int tweetId, Tweet prev){
this.timestamp = timestamp;
this.tweetId = tweetId;
this.prev = prev;
}
public int compareTo(Tweet a){
return a.timestamp - this.timestamp;
}
}
/** Initialize your data structure here. */
public Twitter() {
tweetsMap = new HashMap<Integer, LinkedList<Tweet>>();
follows = new HashMap<Integer, Set<Integer>>();
timestamp = 0;
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if(!tweetsMap.containsKey(userId)) tweetsMap.put(userId, new LinkedList<Tweet>());
Tweet prev = (tweetsMap.get(userId).size() == 0) ? null: tweetsMap.get(userId).peekFirst();
tweetsMap.get(userId).offerFirst(new Tweet(timestamp, tweetId, prev));
timestamp++;
}
/** 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> list = new ArrayList<>();
PriorityQueue<Tweet> maxHeap = new PriorityQueue<Tweet>();
if(tweetsMap.containsKey(userId) && tweetsMap.get(userId).size() > 0)
maxHeap.offer(tweetsMap.get(userId).peekFirst());
if(follows.containsKey(userId)){
for(int followee : follows.get(userId)){
if(tweetsMap.containsKey(followee) && tweetsMap.get(followee).size() > 0)
maxHeap.offer(tweetsMap.get(followee).peekFirst());
}
}
for(int i = 0; i < 10 && !maxHeap.isEmpty(); i++){
Tweet tweet = maxHeap.poll();
list.add(tweet.tweetId);
if(tweet.prev != null) maxHeap.offer(tweet.prev);
}
return list;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
// Can't follow yourself
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(!follows.containsKey(followerId) || !follows.get(followerId).contains(followeeId)) return;
follows.get(followerId).remove(followeeId);
}
}
我还以为要写个 trie 什么的。。这题是什么鬼。。写个 boolean[] 都能 AC.... 697 ms 好么。。
下面这个代码的 get 时间复杂度为 O(maxNumber)，显然太高了。
public class PhoneDirectory {
boolean[] phoneBook;
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
phoneBook = new boolean[maxNumbers];
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
for(int i = 0; i < phoneBook.length; i++){
if(!phoneBook[i]){
phoneBook[i] = true;
return i;
}
}
return -1;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return !phoneBook[number];
}
/** Recycle or release a number. */
public void release(int number) {
phoneBook[number] = false;
}
}
public class PhoneDirectory {
Set<Integer> set;
Queue<Integer> available;
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
set = new HashSet<>();
available = new LinkedList<>();
for(int i = 0; i < maxNumbers; i++){
available.offer(i);
}
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
if(available.size() == 0) return -1;
int num = available.poll();
set.add(num);
return num;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return !set.contains(number);
}
/** Recycle or release a number. */
public void release(int number) {
if(!set.contains(number)) return;
available.offer(number);
// Amortized O(1) to remove in hashmap / hashset
set.remove(number);
}
}