这周的题目没有上周的难，但是有一道设计题目，设计题目非常考验编码能力，并且还有国内外顶尖的大牛写的代码进行对比学习到了很多。
剩下的更多的是搞懂了什么叫做贪心算法。
1. although
1.1. 每日一练
1.1.1. 两数相加 II
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-14 21:27
* <p>
* 445. 两数相加 II
* 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
* <p>
* 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
* <p>
* <p>
* <p>
* 进阶：
* <p>
* 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
* <p>
* <p>
* <p>
* 示例：
* <p>
* 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
* 输出：7 -> 8 -> 0 -> 7
**/
思路：将两链表转化为两个栈，然后将依次弹出栈，并且相加，记录进位。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stackL1 = new Stack<>();
Stack<Integer> stackL2 = new Stack<>();
while (l1 != null) {
stackL1.add(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stackL2.add(l2.val);
l2 = l2.next;
}
ListNode head = null;
int temp = 0;
while (!stackL1.isEmpty() || !stackL2.isEmpty()||temp>0) {
int sum = temp;
sum += stackL1.isEmpty() ? 0 : stackL1.pop();
sum += stackL2.isEmpty() ? 0 : stackL2.pop();
temp = sum / 10;
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
}
return head;
}
1.1.2. 跳跃游戏
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-17 22:59
* <p>
* 55. 跳跃游戏
* 给定一个非负整数数组，你最初位于数组的第一个位置。
* <p>
* 数组中的每个元素代表你在该位置可以跳跃的最大长度。
* <p>
* 判断你是否能够到达最后一个位置。
* <p>
* 示例 1:
* <p>
* 输入: [2,3,1,1,4]
* 输出: true
* 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
* 示例 2:
* <p>
* 输入: [3,2,1,0,4]
* 输出: false
* 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
**/
贪心算法：局部最优，最终结果最优。
public boolean canJump(int[] nums) {
int len = nums.length;
int step = 0;
for (int i = 0; i < len; ++i) {
if (step>=i){
int temp = nums[i];
step = Math.max(temp+i,step);
if (step>=len-1){
return true;
}
}
}
return false;
}
1.1.3. 盛最多水的容器
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-18 21:13
* 11. 盛最多水的容器
* 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
* <p>
* 说明：你不能倾斜容器，且 n 的值至少为 2。
* <p>
* <p>
* <p>
* <p>
* <p>
* 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
* <p>
* <p>
* <p>
* 示例：
* <p>
* 输入：[1,8,6,2,5,4,8,3,7]
* 输出：49
**/
双指针，从两边向中间靠拢。
/**
* 双指针法
*
* @param height
* @return
*/
public int maxArea(int[] height) {
int i = 0;
int j = height.length-1;
int maxArea = 0;
while (i < j) {
int h = Math.min(height[i], height[j]);
maxArea = Math.max(maxArea,h*(j-i));
if (height[i]>height[j]){
j--;
}else {
i++;
}
}
return maxArea;
}
1.1.4. 合并区间
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-16 17:54
* <p>
* 56. 合并区间
* 给出一个区间的集合，请合并所有重叠的区间。
* <p>
* 示例 1:
* <p>
* 输入: [[1,3],[2,6],[8,10],[15,18]]
* 输出: [[1,6],[8,10],[15,18]]
* 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
* 示例 2:
* <p>
* 输入: [[1,4],[4,5]]
* 输出: [[1,5]]
* 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
**/
关键点：根据第一个元素进行排序
public int[][] merge(int[][] intervals) {
//先将这个二维数组排序，根据第一个元素
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
//创建一个新的二维数组
int[][] res = new int[intervals.length][2];
//遍历这个二维数组，进行合并
//初始一个值
int i = -1;
for (int[] interval : intervals) {
//判断
if (i == -1 || res[i][1] < interval[0]) {
res[++i] = interval;
} else {
res[i][1] = Math.max(interval[1], res[i][1]);
}
}
return Arrays.copyOf(res, i + 1);
}
1.1.5. 设计推特
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-13 17:44
* 355. 设计推特
* 设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
* <p>
* postTweet(userId, tweetId): 创建一条新的推文
* getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
* follow(followerId, followeeId): 关注一个用户
* unfollow(followerId, followeeId): 取消关注一个用户
* 示例:
* <p>
* Twitter twitter = new Twitter();
* <p>
* // 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
* twitter.postTweet(1, 5);
* <p>
* // 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
* twitter.getNewsFeed(1);
* <p>
* // 用户1关注了用户2.
* twitter.follow(1, 2);
* <p>
* // 用户2发送了一个新推文 (推文id = 6).
* twitter.postTweet(2, 6);
* <p>
* // 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
* // 推文id6应当在推文id5之前，因为它是在5之后发送的.
* twitter.getNewsFeed(1);
* <p>
* // 用户1取消关注了用户2.
* twitter.unfollow(1, 2);
* <p>
* // 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
* // 因为用户1已经不再关注用户2.
* twitter.getNewsFeed(1);
**/
这是一道设计题目，设计关键点是如何写出优雅的代码。
方法一：基础版，链表+最小堆（实现关键的流信息展示）
static class Twitter {
private Map<Integer,Set<Integer>> followerList = new HashMap<>();
private Map<Integer,TwitterItem> twitterList = new HashMap<>();
private int timeInc = 0;
private PriorityQueue<TwitterItem> priorityQueue = new PriorityQueue<>(Comparator.comparing(TwitterItem::getTime).reversed());
/**
* Initialize your data structure here.
*/
public Twitter() {
}
/**
* Compose a new tweet.
*/
public void postTweet(int userId, int tweetId) {
if (twitterList.containsKey(userId)) {
TwitterItem newTweet = new TwitterItem(tweetId);
TwitterItem oldTweet = twitterList.get(userId);
newTweet.next = oldTweet;
twitterList.put(userId,newTweet);
}else {
twitterList.put(userId,new TwitterItem(tweetId));
}
}
/**
* 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) {
priorityQueue.clear();
if (twitterList.containsKey(userId)) {
priorityQueue.add(twitterList.get(userId));
}
Set<Integer> followers = followerList.get(userId);
if (followers!=null&&followers.size()!=0){
for (Integer follower : followers) {
TwitterItem twitterItem = twitterList.get(follower);
if (twitterItem!=null){
priorityQueue.add(twitterItem);
}
}
}
List<Integer> res = new ArrayList<>();
int count = 0;
while (!priorityQueue.isEmpty()&&count<10){
TwitterItem poll = priorityQueue.poll();
res.add(poll.id);
if (poll.next!=null) {
priorityQueue.add(poll.next);
}
count++;
}
return res;
}
/**
* Follower follows a followee. If the operation is invalid, it should be a no-op.
*/
public void follow(int followerId, int followeeId) {
if (followeeId==followerId)return;
Set<Integer> integers = followerList.computeIfAbsent(followerId,(k)->new HashSet<Integer>());
integers.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 (followerList.containsKey(followerId)){
Set<Integer> integers = followerList.get(followerId);
integers.remove(followeeId);
}
}
class TwitterItem{
private int id;
private long time;
private TwitterItem next;
public long getTime() {
return time;
}
public TwitterItem(int id) {
this.id = id;
this.time = timeInc++;
}
}
}
OOP面向对象编程改进：将动作封装到user类中。
static class Twitter {
private Map<Integer,User> userMap;
/** Initialize your data structure here. */
public Twitter() {
userMap = new HashMap<>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (!userMap.containsKey(userId)) {
userMap.put(userId,new User(userId));
}
User user = userMap.get(userId);
user.postTweet(tweetId);
}
/** 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) {
ArrayList<Integer> res = new ArrayList<>();
if (!userMap.containsKey(userId))return res;
User user = userMap.get(userId);
PriorityQueue<Twitte> priorityQueue = new PriorityQueue<>(Comparator.comparing(Twitte::getTime).reversed());
if (user.twitte!=null) {
priorityQueue.add(user.twitte);
}
for (Integer integer : user.followList) {
Twitte twitte = userMap.get(integer).twitte;
if (twitte!=null){
priorityQueue.add(twitte);
}
}
while (!priorityQueue.isEmpty()&&res.size()<10){
Twitte poll = priorityQueue.poll();
res.add(poll.id);
if (poll.next!=null) {
priorityQueue.add(poll.next);
}
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
User user = userMap.computeIfAbsent(followerId, (key) -> new User(followerId));
userMap.computeIfAbsent(followeeId, (key) -> new User(followeeId));
user.follow(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
User user = userMap.computeIfAbsent(followerId, (key) -> new User(followerId));
userMap.computeIfAbsent(followeeId, (key) -> new User(followeeId));
user.unfollow(followeeId);
}
class User{
private Set<Integer> followList;
private Twitte twitte;
private Integer userId;
public User(Integer userId) {
this.userId = userId;
followList = new HashSet<>();
}
public void postTweet(int tweetId) {
Twitte newTwitte = new Twitte(tweetId);
if (this.twitte ==null){
this.twitte = newTwitte;
}else {
newTwitte.next = twitte;
this.twitte = newTwitte;
}
}
public void follow(int followeeId) {
if (followeeId==userId)return;
followList.add(followeeId);
}
public void unfollow(int followeeId) {
followList.remove(followeeId);
}
}
private int timeIcr = 0;
class Twitte{
private int id;
private int time;
private Twitte next;
public Twitte(int id) {
this.id = id;
this.time = timeIcr++;
}
private int getTime() {
return time;
}
}
}
上面的思想是实现了OOP但是并不太贴切实际开发场景，而真正的场景，不可能一下子将所有的流信息load出来，只会一点点分页查出来。
static class Twitter {
private Map<Integer,Set<Integer>> userMap;
private Map<Integer,List<Twitte>> twitteMap;
/** Initialize your data structure here. */
public Twitter() {
userMap = new HashMap<>();
twitteMap= new HashMap<>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (!twitteMap.containsKey(userId)){
twitteMap.put(userId,new LinkedList<>());
}
List<Twitte> list = twitteMap.get(userId);
list.add(0,new Twitte(tweetId));
}
/** 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) {
ArrayList<Integer> res = new ArrayList<>();
List<Twitte> twitteList = twitteMap.computeIfAbsent(userId, key->new ArrayList<>());
PriorityQueue<Feed> priorityQueue = new PriorityQueue<>(Comparator.comparing(feed -> -feed.curr.time));
if (!twitteList.isEmpty()) {
Feed feed = new Feed(twitteList);
priorityQueue.add(feed);
}
Set<Integer> followList = userMap.computeIfAbsent(userId,key->new HashSet<>());
for (Integer followUserId : followList) {
List<Twitte> followTwitteList = twitteMap.getOrDefault(followUserId, Collections.emptyList());
if (!followTwitteList.isEmpty()) {
Feed feed = new Feed(followTwitteList);
priorityQueue.add(feed);
}
}
while (!priorityQueue.isEmpty()&&res.size()<10){
Feed poll = priorityQueue.poll();
res.add(poll.curr.id);
if (poll.advance()) {
priorityQueue.add(poll);
}
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (followeeId==followerId)return;
Set<Integer> set = userMap.computeIfAbsent(followerId, key->new HashSet<>());
set.add(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
Set<Integer> set = userMap.computeIfAbsent(followerId, key -> new HashSet<>());
set.remove(followeeId);
}
private int timeIcr = 0;
class Twitte{
private int id;
private int time;
public Twitte(int id) {
this.id = id;
this.time = timeIcr++;
}
private int getTime() {
return time;
}
}
class Feed{
Iterator<Twitte> iterator;
private Twitte curr;
public Feed(List<Twitte> list) {
this.iterator = list.iterator();
curr = iterator.next();
}
public boolean advance(){
if (!iterator.hasNext())return false;
curr = iterator.next();
return true;
}
}
}
1.1.6. 矩阵
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-16 09:00
* <p>
* 542. 01 矩阵
* 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
* <p>
* 两个相邻元素间的距离为 1 。
* <p>
* 示例 1:
* 输入:
* <p>
* 0 0 0
* 0 1 0
* 0 0 0
* 输出:
* <p>
* 0 0 0
* 0 1 0
* 0 0 0
* 示例 2:
* 输入:
* <p>
* 0 0 0
* 0 1 0
* 1 1 1
* 输出:
* <p>
* 0 0 0
* 0 1 0
* 1 2 1
* 注意:
* <p>
* 给定矩阵的元素个数不超过 10000。
* 给定矩阵中至少有一个元素是 0。
* 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
**/
方法一：广度优先算法求解。并且在原来的数据上做标记，使得最终结果直接是正确的。
public int[][] updateMatrix(int[][] matrix) {
LinkedList<int[]> queue = new LinkedList<>();
int n = matrix.length;
int m = matrix[0].length;
//将所有的0加入到队列中
//将1位置设置成-1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
queue.add(new int[]{i, j});
} else {
matrix[i][j] = -1;
}
}
}
//BFS遍历
//pop出遍历坐标
//上下左右移动
//移动之后将其拿出并比较是否是-1
//-1就在原来的基础上加1
//并且加入的队列中
int[] movex = new int[]{0, 1, 0, -1};
int[] movey = new int[]{1, 0, -1, 0};
while (!queue.isEmpty()) {
int[] pop = queue.pop();
int x = pop[0];
int y = pop[1];
for (int i = 0; i < 4; i++) {
int newX = movex[i] + x;
int newY = movey[i] + y;
if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == -1) {
matrix[newX][newY] = matrix[x][y] + 1;
queue.offer(new int[]{newX, newY});
}
}
}
return matrix;
}
方法二：动态规划:
递推公式为：
f(i,j)= 0 if matrix[i][j]==0f(i,j)=min(f(i-1,j),f(i+1,j),f(i,j+1),f(i,j-1))+1- min的原因是，离0的最小距离
- 技巧
- 从左上第一个开始遍历，只有 右边 与 下边
- 从右下第一个开始遍历，只走 左边 与 上边
/**
* 动态规划的方式
* 如何动态规划？
* <p>
* 地推公式为
* f(i,j)= 0 if matrix[i][j]==0
* f(i,j)=min(f(i-1,j),f(i+1,j),f(i,j+1),f(i,j-1))+1
* min的原因是，离0的最小距离。
* <p>
* 技巧
* 1 从左上第一个开始遍历，只有 右边 与 下边
* 2 从右下第一个开始遍历，只走 左边 与 上边
*
* @param matrix
* @return
*/
public int[][] updateMatrix1(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int[][] dp = new int[n][m];
//赋值dp 将为1的设置成 10000
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = matrix[i][j] == 0 ? 0 : 10000;
}
}
//从左上角开始遍历
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
}
}
}
//从右下角开始遍历
for (int i = n-1; i >= 0; i--) {
for (int j = m-1; j >= 0; j--) {
if (i + 1 < n) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}
if (j + 1 < m) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
}
}
return dp;
}
2. review
3. tip
3.1. git subtree解决不同Git项目共享包问题
git subtree 用于解决 不同Git项目需要共享一个包的问题，在RPC框架中常用到。
3.2. Java中boolean类型到底占用多少个字节？
有三种猜测：
- 占一个bit，因为一个bit位就可以表示true和false
- 占一个字节，因为计算机中最小单位是一个字节(8bit)
- 占四个字节，因为虚拟机规范中说JAVA中使用int(4字节)来表示Boolean类型
第一个可以直接排除，第二个已经给出原因，最后就是在第二个与第三个之间选择，如果认同第三个，那么接下来又有疑问，为什么是用int而不是short或者byte?难道不是更省空间吗？
早前Java虚拟机大部分是跑在32位的机器上的，32位CPU机器，读取一次，最小单位就是32位(4字节)，就算是只要1位也是这样，所以节省运算就直接使用32位来表示Boolean。
而具体的思想还是要看虚拟机是如何实现的。
