英文:
priority queue as max priority queue not working as expected
问题
我正在处理一个leetcode问题，我们需要设计基本的推特功能，例如关注和取消关注、发推文以及新闻源，该新闻源会为用户提供最近的10条推文。
postTweet(userId, tweetId): 发布一条新推文。
getNewsFeed(userId): 获取用户新闻源中最近的10条推文ID。新闻源中的每个项目必须由用户关注的用户或用户本人发布。推文必须按照从最近到最旧的顺序排序。
follow(followerId, followeeId): 关注者关注一个被关注者。
unfollow(followerId, followeeId): 关注者取消关注一个被关注者。
import java.time.Instant;
import java.util.*;
class Twitter {
Map<Integer, List<Integer>> followMap = new HashMap<Integer, List<Integer>>();
Queue<Tweet> pQueue = new PriorityQueue<Tweet>((a, b) -> (int)(b.createdOn - a.createdOn));
public Twitter() {
}
public void postTweet(int userId, int tweetId) {
Tweet tweet = new Tweet(userId, tweetId, System.nanoTime());
pQueue.add(tweet);
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> newsFeed = new ArrayList<Integer>();
List<Integer> followedList = followMap.get(userId);
List<Tweet> tempList = new ArrayList<Tweet>();
while (pQueue.peek() != null) {
Tweet element = pQueue.poll();
if (newsFeed.size() == 10) {
pQueue.addAll(tempList);
return newsFeed;
}
if (element.userId == userId || (followedList != null && followedList.contains(element.userId))) {
newsFeed.add(element.tweetId);
}
tempList.add(element);
}
pQueue.addAll(tempList);
return newsFeed;
}
public void follow(int followerId, int followeeId) {
if (followMap.get(followerId) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(followeeId);
followMap.put(followerId, list);
} else {
followMap.get(followerId).add(followeeId);
}
}
public void unfollow(int followerId, int followeeId) {
if (followMap.get(followerId) != null) {
followMap.get(followerId).removeIf(id -> id == followeeId);
}
}
}
class Tweet {
int tweetId;
int userId;
long createdOn;
Tweet(int userId, int tweetId, long createdOn) {
this.tweetId = tweetId;
this.userId = userId;
this.createdOn = createdOn;
}
}
代码在大多数测试用例中都能正常工作，除了一个测试用例。预期输出结果中最后一个新闻源存在错误，对我来说，推文ID 205没有被包括在内，但是按设计我期望它在结果中，不确定为什么会出现这种情况。
英文:
I was working on a leetcode question where we need to design the basic twitter functionality ,
such as follow and unfollow , post a tweet and newsfeed which will give the most recent 10 tweets for a user
postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): 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.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
import java.time.Instant;
import java.util.*;
class Twitter {
Map<Integer, List<Integer>> followMap = new HashMap<Integer,List<Integer>>();
Queue<Tweet> pQueue = new PriorityQueue<Tweet>((a, b)-> (int)(b.createdOn-a.createdOn));
/** Initialize your data structure here. */
public Twitter() {
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
Tweet tweet = new Tweet(userId,tweetId, System.nanoTime());
pQueue.add(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> newsFeed = new ArrayList<Integer>();
List<Integer> follwedList = followMap.get(userId);
List<Tweet> la = new ArrayList<Tweet>();
while(pQueue.peek()!=null){
Tweet element = pQueue.poll();
if(newsFeed.size()==10){
pQueue.addAll(la);
return newsFeed;
}
if(element.userId == userId || (follwedList!=null && follwedList.contains(element.userId))){
newsFeed.add(element.tweetId);
}
la.add(element);
}
pQueue.addAll(la);
return newsFeed;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if(followMap.get(followerId)==null){
List<Integer> a = new ArrayList<Integer>();
a.add(followeeId);
followMap.put(followerId,a);
}else{
followMap.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(followMap.get(followerId)!=null){
for(int i=0;i<followMap.get(followerId).size();i++){
if(followMap.get(followerId).get(i)==followeeId){
followMap.get(followerId).remove(i);
break;
}
}
}
}
}
class Tweet {
int tweetId;
int userId;
long createdOn;
Tweet(int userId, int tweetId, long createdOn){
this.tweetId = tweetId;
this.userId = userId;
this.createdOn = createdOn;
}
}
the code work as expected for most of the test cases except one
["Twitter","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","getNewsFeed","follow","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[2,3],[1,101],[2,13],[2,10],[1,2],[1,94],[2,505],[1,333],[2,22],[1,11],[1,205],[2,203],[1,201],[2,213],[1,200],[2,202],[1,204],[2,208],[2,233],[1,222],[2,211],1,[1,2],1,[1,2],1]
My answer
[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,[222,204,200,201,205,11,333,94,2,101],null,[211,222,233,208,204,202,200,213,201,203],null,[222,204,200,201,11,333,94,2,101,5]]
Expected answer
[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,[222,204,200,201,205,11,333,94,2,101],null,[211,222,233,208,204,202,200,213,201,203],null,[222,204,200,201,205,11,333,94,2,101]]
in the last news feed there is an error , for me 205 in not coming , but by design I expect it to be in the result , not sure why it is happening
答案1
得分: 0
如果我正确理解你的策略：
Tweet element = pQueue.poll();
if(newsFeed.size()==10){
pQueue.addAll(la);
return newsFeed;
}
if(element.userId == userId || (follwedList!=null && follwedList.contains(element.userId))){
newsFeed.add(element.tweetId);
}
la.add(element);
你将所有推文放在 pQueue 中，你的 la 列表跟踪你（暂时）移除的推文，一旦循环完成，你会将所有这些推文重新添加到 pQueue 中。
如果是这样的话，在你达到 newsFeed.size()==10 的情况下，la 并不包含所有已移除的推文，因为你提前进行了 return。
要修复这个问题，你应该将 la.add(element) 放在 .poll() 之后。
英文:
If I understand your strategy correctly:
Tweet element = pQueue.poll();
if(newsFeed.size()==10){
pQueue.addAll(la);
return newsFeed;
}
if(element.userId == userId || (follwedList!=null && follwedList.contains(element.userId))){
newsFeed.add(element.tweetId);
}
la.add(element);
you have all tweets in pQueue and your la list keeps track of tweets that you have (temporarily) removed, and once your loop is complete, you add all those tweets in la back to the pQueue.
If so, then la does not contain all your removed tweets in the case that you reach newsFeed.size()==10. since you return early.
To fix this, you should probably have your la.add(element) right up where you .poll()
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论