leetcode解题思路分析（四十二）355

设计推特
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。

int global_Time = 0;//发表推文的时间全局的
//推文类
class Tweet {
public:

int id;
int time;
Tweet *next;
Tweet(int id) { 
    this->id = id;
    this->time = global_Time++;
    next = nullptr;
}

};

//用户类
class User {
public:

int id;
Tweet *tweet; //该用户发送的推文 是个链表
unordered_set<int> follows; //该用户关注的用户
User(int id) { 
    this->id = id;
    tweet = nullptr;
}
void follow(int followeeId) { 
    //不能关注自己
    if (followeeId == id) return;
    follows.insert(followeeId);
}
void unfollow(int followeeId) { 
    //没有关注 或者 不能取关自己
    if (!follows.count(followeeId) || followeeId == id) return;
    follows.erase(followeeId);
}
void post(int tweetId) { 
    Tweet *newTweet = new Tweet(tweetId);
    //链表 采用头插法 新发表插在前面
    newTweet->next = tweet;
    //新的链表
    tweet = newTweet;
}

};

class Twitter {
private:

unordered_map<int, User*> user_map;  //所有的用户
bool contain(int id) { 
    return user_map.find(id) != user_map.end();
}

public:

Twitter() { 
    user_map.clear();
}
void postTweet(int userId, int tweetId) { 
    if (!contain(userId)) { 
        user_map[userId] = new User(userId);
    }
    //用户 发表 推文 面向对象
    user_map[userId]->post(tweetId);
}
vector<int> getNewsFeed(int userId) { 
    //用户不存在
    if (!contain(userId)) return { };
    struct cmp { 
        bool operator()(const Tweet *a, const Tweet *b) { 
            return a->time < b->time;
        }
    };
    //构造大顶堆 时间最大的排在最上面
    priority_queue<Tweet*, vector<Tweet*>, cmp> q;
    //自己的推文链表
    if (user_map[userId]->tweet) { 
        q.push(user_map[userId]->tweet);
    }
    //关注的推文链表
    for (int followeeId : user_map[userId]->follows) { 
        if (!contain(followeeId)) { 
            continue;
        }
        Tweet *head = user_map[followeeId]->tweet;
        if (head == nullptr) continue;
        q.push(head);
    }
    vector<int> rs;
    while (!q.empty()) { 
        Tweet *t = q.top(); 
        q.pop();
        rs.push_back(t->id);
        if (rs.size() == 10) return rs;
        if (t->next) { 
            q.push(t->next);
        }
    }
    return rs;
}
// 用户followerId 关注 用户followeeId.
void follow(int followerId, int followeeId) { 
    if (!contain(followerId)) { 
        user_map[followerId] = new User(followerId);
    }
    //面向对象
    user_map[followerId]->follow(followeeId);
}
// 用户followerId 取关 用户followeeId.
void unfollow(int followerId, int followeeId) { 
    if (!contain(followerId)) return;
    //面向对象
    user_map[followerId]->unfollow(followeeId);
}

};

计算各个位数不同的数字个数
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

dp[i]表示有i位数的满足条件的数字一共有多少，那么dp[i+1]只能在这些数字添加非重复的数字。前面已经占用了i位数字了，那么只剩10-i位了。注意要取dp[1] = 9, 表示第一位不能取0。

class Solution 
{ 
public:
    int countNumbersWithUniqueDigits(int n) 
    { 
        if (n == 0) return 1;
        if (n == 1) return 10;
        int dp = 9, sum = 10;
        for (int i = 2; i <= min(n, 10); i++) 
        { 
            dp = dp * (11 - i);
            sum += dp;
        }
        return sum;
    }
};

矩形区域不超过K的最大数值和
给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

本题由于列的数量远远小于行的数量，因此应该转化思维，固定起始列，不断增大终止列号，然后计算起始列和终止列之间的某行的累计和，从而解决问题

class Solution { 
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { 
        int m = matrix.size();
        if(m == 0 || matrix[0].size() == 0) return 0;
        int n = matrix[0].size();
        // i 代表矩形的起始行
        int ans = INT_MIN;
        // 起始列
        for(int i = 0; i < n; i++){ 
            // 终止列
            vector<int> rowCums(m, 0);
            for(int j = i; j < n; j++){ 
                set<int> pres;
                int preSum = 0;
                for(int r = 0; r < m; r++){ 
                    rowCums[r] += matrix[r][j];
                    preSum += rowCums[r];
                    if(preSum <= k) ans = max(ans, preSum);
                    auto it = pres.lower_bound(preSum - k);
                    if(it != pres.end() ){  ans = max(ans, preSum - *it); }
                    pres.insert(preSum);
                }
            }
        }
        return ans;
    }
};

水壶问题
有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, ba,b，使得ax+by=z。而贝祖定理告诉我们，ax+by=zax+by=z 有解当且仅当 zz 是 x, yx,y 的最大公约数的倍数。因此我们只需要找到 x, yx,y 的最大公约数并判断 zz 是否是它的倍数即可。

class Solution { 
public:
    bool canMeasureWater(int x, int y, int z) { 
        if (x + y < z) return false;
        if (x == 0 || y == 0) return z == 0 || x + y == z;
        return z % gcd(x, y) == 0;
    }
};

有效的完全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

很简单的一道题，最简单的做法是遍历到1/2的位置，一路检查。更优的做法是判断是否由1357一系列基数构成。因为(n+1)2-n2=2n+1

class Solution { 
public:
    bool isPerfectSquare(int num) { 
        if (num == 1) return true;
        for (int i = 1; i <= num / 2; i++)
        { 
            int tmp = num / i;
            int remain = num % i;
            if (i > tmp) 
                return false;
            else if (i == tmp && remain == 0)
                return true;
        }
        return false;
    }
};
class Solution 
{ 
public:
    bool isPerfectSquare(int num) 
    { 
        int num1 = 1;
        while(num > 0) 
        { 
            num -= num1;
            num1 += 2;
        }
        return num == 0;
    }
};

最大整数子集
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

本题的解法建立在数学推导上：对现有集合加入一个新元素，如果是最大元素的倍数或者最小元素的约数则加入后依然可以保证这个性质，知道了这个就可以用动态规划求解

class Solution { 
public:
    static const int N = 1e3 + 5;
    int dp[N], ans_len = 1, ans_index = 0;
    std::vector<int> ans;
    void print(int index, vector<int>& nums) { 
        if (dp[index] == 1) { 
            ans.push_back(nums[index]);
            return;
        }
        for (int j = 0; j < index; ++j) { 
            if (nums[index] % nums[j] == 0 && dp[j] + 1 == dp[index]) { 
                ans.push_back(nums[index]);
                print(j, nums);
                break;
            }
        }
    }
    vector<int> largestDivisibleSubset(vector<int>& nums) { 
        if (nums.empty()) return { };
        std::sort(nums.begin(), nums.end());
        dp[0] = 1;
        int n = nums.size();
        for (int i = 1; i < n; ++i) { 
            dp[i] = 1;
            for (int j = 0; j < i; ++j) { 
                if (nums[i] % nums[j] == 0) dp[i] = std::max(dp[i], dp[j] + 1);
            }
            if (dp[i] > ans_len) { 
                ans_len = dp[i];
                ans_index = i;
            }
        }
        print(ans_index, nums);
        return ans;
    }
};

两整数之和
不使用运算符 + 和 - ，计算两整数 a 、b 之和。

a ^ b可以得到两数相加不进位的加法结果
(a & b) << 1可以得到两数相加产生的进位

class Solution { 
public:
    int getSum(int a, int b) { 
        while (b) { 
            auto carry = ((unsigned int)(a & b)) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};