leetcode 355. 设计推特-https://leetcode.cn/problems/design-twitter/

class Twitter {

    public Twitter() {

    }
    
    public void postTweet(int userId, int tweetId) {

    }
    
    public List<Integer> getNewsFeed(int userId) {

    }
    
    public void follow(int followerId, int followeeId) {

    }
    
    public void unfollow(int followerId, int followeeId) {

    }
}

方法一

class Twitter0
{

    public static void main(String[] args) {
        Twitter0 Twitter0 = new Twitter0();
        Twitter0.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
        System.out.println(Twitter0.getNewsFeed(1)); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
        Twitter0.follow(1, 2);    // 用户 1 关注了用户 2
        Twitter0.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
        System.out.println(Twitter0.getNewsFeed(1)); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
        Twitter0.unfollow(1, 2);  // 用户 1 取消关注了用户 2
        System.out.println(Twitter0.getNewsFeed(1)); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
    }

    static Map<Integer, MyInfo> peopleMap;

    static int time;

    public Twitter0() {
        peopleMap = new HashMap<>();
        time = 0;
    }

    public void postTweet(int userId, int tweetId) {
        //推文和时间
        TidAndTime tidAndTime = new TidAndTime(tweetId, getNowTime());
        if (peopleMap.containsKey(userId)) {
            MyInfo myInfo = peopleMap.get(userId);
            myInfo.getTidAndTimeList().add(tidAndTime);
        }
        else {
            //我的信息
            MyInfo myInfo = new MyInfo();
            ArrayList<TidAndTime> tidAndTimeList = new ArrayList<>();
            tidAndTimeList.add(tidAndTime);
            myInfo.setTidAndTimeList(tidAndTimeList);
            peopleMap.put(userId, myInfo);
        }

    }

    //获得最新的推文
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> rtnList = new ArrayList<>();
        if (!peopleMap.containsKey(userId)) {
            return rtnList;
        }

        List<TidAndTime> lastList = new ArrayList<>();
        MyInfo myInfo = peopleMap.get(userId);
        //我的推文和时间
        List<TidAndTime> tidAndTimeList = myInfo.getTidAndTimeList();
        lastList.addAll(tidAndTimeList);
        //我关注的人
        List<Integer> focksList = myInfo.getFocksList();
        //获取我关注人的推文和时间
        List<TidAndTime> focksTidAndTimeList = getfocksFeed(focksList);
        lastList.addAll(focksTidAndTimeList);

        //排序，根据时间获取最新的10条
        boolean change = false;
        for (int i = 0, len = lastList.size(); i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                TidAndTime tidAndTime = lastList.get(j);
                TidAndTime tidAndTime2 = lastList.get(j + 1);
                if (tidAndTime.getTime() < tidAndTime2.getTime()) {
                    lastList.set(j, tidAndTime2);
                    lastList.set(j + 1, tidAndTime);
                    change = true;
                }
            }

            if (!change) {
                break;
            }
        }

        int size = lastList.size();
        if (size > 10) {
            size = 10;
        }

        for (int i = 0; i < size; i++) {
            rtnList.add(lastList.get(i).getTweetId());
        }

        return rtnList;
    }

    public void follow(int followerId, int followeeId) {
        //谁 关注了 谁
        if (peopleMap.containsKey(followerId)) {
            MyInfo myInfo = peopleMap.get(followerId);
            if (!myInfo.getFocksList().contains(followeeId)) {
                myInfo.getFocksList().add(followeeId);
            }
        }
        else {
            MyInfo myInfo = new MyInfo();
            ArrayList<Integer> focksList = new ArrayList<>();
            focksList.add(followeeId);
            myInfo.setFocksList(focksList);
            peopleMap.put(followerId, myInfo);
        }
    }

    public void unfollow(int followerId, int followeeId) {
        //谁 关注了 谁
        if (peopleMap.containsKey(followerId)) {
            MyInfo myInfo = peopleMap.get(followerId);
            List<Integer> focksList = myInfo.getFocksList();
            if (focksList.contains(followeeId)) {
                List<Integer> newForks = new ArrayList<>();
                for (Integer integer : focksList) {
                    if (!integer.equals(followeeId)) {
                        newForks.add(integer);
                    }
                }
                myInfo.setFocksList(newForks);
            }
        }
    }

    //获得关注人的的推文
    public static List<TidAndTime> getfocksFeed(List<Integer> userIdList) {
        List<TidAndTime> rtnList = new ArrayList<>();

        if (userIdList == null || userIdList.isEmpty()) {
            return rtnList;
        }

        for (Integer userId : userIdList) {
            if (!peopleMap.containsKey(userId)) {
                continue;
            }

            MyInfo myInfo = peopleMap.get(userId);
            //我的推文和时间
            rtnList.addAll(myInfo.getTidAndTimeList());
        }
        return rtnList;
    }

    public static long getNowTime() {
        return time++;
    }

    class MyInfo
    {
        //我的发布
        private List<TidAndTime> tidAndTimeList;

        //关注的人
        private List<Integer> focksList;

        public MyInfo() {
            tidAndTimeList = new ArrayList<>();
            focksList = new ArrayList<>();
        }

        public List<TidAndTime> getTidAndTimeList() {
            return tidAndTimeList;
        }

        public void setTidAndTimeList(List<TidAndTime> tidAndTimeList) {
            this.tidAndTimeList = tidAndTimeList;
        }

        public List<Integer> getFocksList() {
            return focksList;
        }

        public void setFocksList(List<Integer> focksList) {
            this.focksList = focksList;
        }
    }

    //tid和发布时间
    class TidAndTime
    {

        private int tweetId;
        private long time;

        public TidAndTime(int tweetId, long time) {
            this.tweetId = tweetId;
            this.time = time;
        }

        public int getTweetId() {
            return tweetId;
        }

        public void setTweetId(int tweetId) {
            this.tweetId = tweetId;
        }

        public long getTime() {
            return time;
        }

        public void setTime(long time) {
            this.time = time;
        }
    }
}

方法2-优先级队列

class Twitter2
{

    public static void main(String[] args) {
        Twitter2 Twitter2 = new Twitter2();
        Twitter2.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
        System.out.println(Twitter2.getNewsFeed(1)); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
        Twitter2.follow(1, 2);    // 用户 1 关注了用户 2
        Twitter2.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
        System.out.println(Twitter2.getNewsFeed(1)); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
        Twitter2.unfollow(1, 2);  // 用户 1 取消关注了用户 2
        System.out.println(Twitter2.getNewsFeed(1)); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
    }

    static Map<Integer, MyInfo> peopleMap;

    static int time;

    public Twitter2() {
        peopleMap = new HashMap<>();
        time = 0;
    }

    public void postTweet(int userId, int tweetId) {
        //推文和时间
        TidAndTime tidAndTime = new TidAndTime(tweetId, getNowTime());
        MyInfo myInfo = peopleMap.getOrDefault(userId, new MyInfo());
        myInfo.getTidAndTimeList().add(tidAndTime);
        peopleMap.putIfAbsent(userId, myInfo);
    }

    //获得最新的推文
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> rtnList = new ArrayList<>();
        if (!peopleMap.containsKey(userId)) {
            return rtnList;
        }
        PriorityQueue<TidAndTime> queue = new PriorityQueue<>((o1, o2) -> -(o1.getTime() - o2.getTime()));
        MyInfo myInfo = peopleMap.get(userId);
        //我的推文和时间
        List<TidAndTime> tidAndTimeList = myInfo.getTidAndTimeList();
        for (TidAndTime tidAndTime : tidAndTimeList) {
            queue.offer(tidAndTime);
        }
        //我关注的人
        Set<Integer> focksSet = myInfo.getFocksSet();
        //获取我关注人的推文和时间
        List<TidAndTime> focksTidAndTimeList = getfocksFeed(focksSet);
        for (TidAndTime tidAndTime : focksTidAndTimeList) {
            queue.offer(tidAndTime);
        }
        while (!queue.isEmpty() && rtnList.size() < 10) {
            rtnList.add(queue.poll().getTweetId());
        }
        return rtnList;
    }

    public void follow(int followerId, int followeeId) {
        //谁 关注了 谁
        MyInfo myInfo = peopleMap.getOrDefault(followerId, new MyInfo());
        myInfo.getFocksSet().add(followeeId);
        peopleMap.putIfAbsent(followerId, myInfo);
    }

    public void unfollow(int followerId, int followeeId) {
        //谁 关注了 谁
        MyInfo myInfo = peopleMap.get(followerId);
        if (myInfo != null) {
            myInfo.getFocksSet().remove(followeeId);
        }
    }

    //获得关注人的的推文
    public static List<TidAndTime> getfocksFeed(Set<Integer> userIdSet) {
        List<TidAndTime> rtnList = new ArrayList<>();

        if (userIdSet == null || userIdSet.isEmpty()) {
            return rtnList;
        }

        for (Integer userId : userIdSet) {
            if (!peopleMap.containsKey(userId)) {
                continue;
            }

            MyInfo myInfo = peopleMap.get(userId);
            //我的推文和时间
            rtnList.addAll(myInfo.getTidAndTimeList());
        }
        return rtnList;
    }

    public static int getNowTime() {
        return time++;
    }

    class MyInfo
    {
        //我的发布
        private List<TidAndTime> tidAndTimeList;

        //关注的人
        private Set<Integer> focksSet;

        public MyInfo() {
            tidAndTimeList = new ArrayList<>();
            focksSet = new HashSet<>();
        }

        public List<TidAndTime> getTidAndTimeList() {
            return tidAndTimeList;
        }

        public void setTidAndTimeList(List<TidAndTime> tidAndTimeList) {
            this.tidAndTimeList = tidAndTimeList;
        }

        public Set<Integer> getFocksSet() {
            return focksSet;
        }

        public void setFocksSet(Set<Integer> focksSet) {
            this.focksSet = focksSet;
        }
    }

    //tid和发布时间
    class TidAndTime
    {

        private int tweetId;
        private int time;

        public TidAndTime(int tweetId, int time) {
            this.tweetId = tweetId;
            this.time = time;
        }

        public int getTweetId() {
            return tweetId;
        }

        public void setTweetId(int tweetId) {
            this.tweetId = tweetId;
        }

        public int getTime() {
            return time;
        }

        public void setTime(int time) {
            this.time = time;
        }
    }
}

方法三-集合排序，比较器

class Twitter3
{

   static Map<Integer, MyInfo> peopleMap;

    static int time;

    public Twitter3() {
        peopleMap = new HashMap<>();
        time = 0;
    }

    public void postTweet(int userId, int tweetId) {
        //推文和时间
        TidAndTime tidAndTime = new TidAndTime(tweetId, getNowTime());
        MyInfo myInfo = peopleMap.getOrDefault(userId, new MyInfo());
        myInfo.getTidAndTimeList().add(tidAndTime);
        peopleMap.putIfAbsent(userId, myInfo);
    }

    //获得最新的推文
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> rtnList = new ArrayList<>();
        if (!peopleMap.containsKey(userId)) {
            return rtnList;
        }

        List<TidAndTime> lastList = new ArrayList<>();
        MyInfo myInfo = peopleMap.get(userId);
        //我的推文和时间
        List<TidAndTime> tidAndTimeList = myInfo.getTidAndTimeList();
        lastList.addAll(tidAndTimeList);
        //我关注的人
        Set<Integer> focksSet = myInfo.getFocksSet();
        //获取我关注人的推文和时间
        List<TidAndTime> focksTidAndTimeList = getfocksFeed(focksSet);
        lastList.addAll(focksTidAndTimeList);

        Collections.sort(lastList, new Comparator<TidAndTime>()
        {
            @Override
            public int compare(TidAndTime o1, TidAndTime o2) {
                return -(o1.getTime() - o2.getTime());
            }
        });

        int size = lastList.size();
        if (size > 10) {
            size = 10;
        }

        for (int i = 0; i < size; i++) {
            rtnList.add(lastList.get(i).getTweetId());
        }

        return rtnList;
    }

    public void follow(int followerId, int followeeId) {
        //谁 关注了 谁
        MyInfo myInfo = peopleMap.getOrDefault(followerId, new MyInfo());
        myInfo.getFocksSet().add(followeeId);
        peopleMap.putIfAbsent(followerId, myInfo);
    }

    public void unfollow(int followerId, int followeeId) {
        //谁 关注了 谁
        MyInfo myInfo = peopleMap.get(followerId);
        if (myInfo != null) {
            myInfo.getFocksSet().remove(followeeId);
        }
    }

    //获得关注人的的推文
    public static List<TidAndTime> getfocksFeed(Set<Integer> userIdSet) {
        List<TidAndTime> rtnList = new ArrayList<>();

        if (userIdSet == null || userIdSet.isEmpty()) {
            return rtnList;
        }

        for (Integer userId : userIdSet) {
            if (!peopleMap.containsKey(userId)) {
                continue;
            }

            MyInfo myInfo = peopleMap.get(userId);
            //我的推文和时间
            rtnList.addAll(myInfo.getTidAndTimeList());
        }
        return rtnList;
    }

    public static int getNowTime() {
        return time++;
    }

    class MyInfo
    {
        //我的发布
        private List<TidAndTime> tidAndTimeList;

        //关注的人
        private Set<Integer> focksSet;

        public MyInfo() {
            tidAndTimeList = new ArrayList<>();
            focksSet = new HashSet<>();
        }

        public List<TidAndTime> getTidAndTimeList() {
            return tidAndTimeList;
        }

        public void setTidAndTimeList(List<TidAndTime> tidAndTimeList) {
            this.tidAndTimeList = tidAndTimeList;
        }

        public Set<Integer> getFocksSet() {
            return focksSet;
        }

        public void setFocksSet(Set<Integer> focksSet) {
            this.focksSet = focksSet;
        }
    }

    //tid和发布时间
    class TidAndTime
    {

        private int tweetId;
        private int time;

        public TidAndTime(int tweetId, int time) {
            this.tweetId = tweetId;
            this.time = time;
        }

        public int getTweetId() {
            return tweetId;
        }

        public void setTweetId(int tweetId) {
            this.tweetId = tweetId;
        }

        public int getTime() {
            return time;
        }

        public void setTime(int time) {
            this.time = time;
        }
    }
}