第53周 ARTS 2019 10 20AlgorithmReviewTip/TechShare

80 阅读 0 评论 53 点赞

我是靠谱客的博主机灵龙猫，这篇文章主要介绍第53周 ARTS 2019 10 20AlgorithmReviewTip/TechShare，现在分享给大家，希望可以做个参考。

Algorithm：378. 有序矩阵中第K小的元素
Review：Java8的注释探索
Tip/Tech：跳表的另外一种实现方式
Share：年收入增长率 + 营业利润率应该等于40％

Algorithm

378. 有序矩阵中第K小的元素

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
因为这题，这周一次性做了六道和这个相关的题目，简直了。
这种第K个小的题目，一般来说，最简单的思想就是用优先队列+多路归并思想来解答。

优先队列+多路归并

当然，这是最通俗的解答。
当然，这个和一般的优先队列的解法不一样
1）为了节约内存，我们不用全部遍历一遍，直接起手遍历最顶层的元素，或者最左边的元素就可以
2）如果是顶层元素，那么就每次从队列里面出队一个元素，然后入队，那个元素的下一层的元素。直到K个元素
3）如果是最左边的元素，那么就每次从队列出对一个元素，然后入队那个元素的右边一层的元素。直到K个元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public int kthSmallest(int[][] matrix, int k) {
PriorityQueue<TwoNumsNode> queue = new PriorityQueue<>(k, (o1, o2) ->{
if (o1.getValue(matrix) < o2.getValue(matrix)) {
return -1;
} else if (o1.getValue(matrix) > o2.getValue(matrix)) {
return 1;
} else {
return 0;
}
});
int rowSize = matrix.length;
int columnSize = matrix[0].length;
for (int i = 0; i < rowSize; ++i) {
queue.offer(new TwoNumsNode(i, 0));
}
int ans = 0;
while (k > 0 && queue.size() > 0) {
TwoNumsNode temp = queue.poll();
ans = matrix[temp.rowIndex][temp.columnIndex];
if (temp.columnIndex + 1 < columnSize) {
queue.offer(new TwoNumsNode(temp.rowIndex, temp.columnIndex + 1));
}
k--;
}
return ans;
}
class TwoNumsNode {
int rowIndex;
int columnIndex;
TwoNumsNode(int row, int column) {
this.rowIndex = row;
this.columnIndex = column;
}
int getValue(int[][] matrix) {
return matrix[rowIndex][columnIndex];
}
}
}

二分查找+查找元素

这个是此类问题的最优解，一般来说，这类问题，基本就是用二分。
关键的就是，你要知道最大的值和最小值的取值，然后不断二分，然后取值。
然后得到中间值，然后判断数组里有多少的值是小于这个值的，然后进行判断，每次根据个数进行判断，
如果少了那就说明目标值在右边的半区，那么就要low = mid + 1，
如果在比k大，那就说明在左边半区high = mid。
至于找值也是有很大技巧的，因为有顺序递增的特性，那么也就可以直接点，从每一列或者每一行的最后一个元素开始遍历，从第一列或者第一行开始，然后逐步往下，比较累加，说这有点复杂，看了代码就明白。。。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int rowLen = matrix.length;
int columnLen = matrix[0].length;
int low = matrix[0][0], high = matrix[rowLen -
1][columnLen - 1];
while (low < high) {
int mid = low + ((high - low) >> 1);
int count = findCountOfLessThanValue(matrix, mid, rowLen, columnLen);
if (count < k) {
low = mid + 1;
} else if (count >= k) {
high = mid;
}
}
return high;
}
// 从列一个元素开始，如果符合就答案加上那一粒j到列的头部的元素的个数。
// 如果不符合，那么列的游标往上移动一位。
private int findCountOfLessThanValue(int[][] matrix, int value, int row, int column) {
int i = 0, j = column - 1, ans = 0;
while (i <= row - 1 && j >= 0) {
if (matrix[i][j] <= value) {
ans += j+1;
i++;
} else {
j--;
}
}
return ans;
}
}

Review

Control Strategies of Two-Player Games 1989

本来想读懂这篇论文的，后来发现自己就是个垃圾，没法一天读懂。。。就先放一放吧，我决定看看别的简单的。。我就是他妈的一个怂货。。。

Explore Annotations in Java 8

Java8的注释探索

https://dzone.com/articles/explore-annotations-in-java-8

主要是简单介绍了Java注解的几种用法，不过介绍还不是详细就是了，我这里自己总结一下。
一般来说，要用之前，你要想清楚，注解能用来干啥子。
现在注解可以吧一些经常使用的代码给规整起来，作为一个非常好的重构的一个起点。
如何实现，首先你要声明一个接口（interface），然后你要设置好，这个注解的使用的地方，这个使用的地方一般来说是和这个注解的功能相关的，比如他告诉编译器这个接口仅仅是个声明，还是根据这个注解给生成一些代码？还是这个注解会在跑代码的使用用到？
这些都是定义注解的时候需要注意的。

Tip/Tech

跳表的另外一种实现方式

这种跳表的实现方式是非常好理解的一种实现方式。

复制代码

class SkipListEntry {
// data
public String key;
public Integer value;
// links
public SkipListEntry up;
public SkipListEntry down;
public SkipListEntry left;
public SkipListEntry right;
// special
public static final String negInf = "-oo";
public static final String posInf = "+oo";
// constructor
public SkipListEntry(String key, Integer value) {
this.key = key;
this.value = value;
}
// methods...
}
public SkipListEntry head;
// First element of the top level
public SkipListEntry tail;
// Last element of the top level
public int n;
// number of entries in the Skip List
public int h;
// Height
public Random r;
// Coin toss
// constructor
public SkipList() {
SkipListEntry p1, p2;
// 创建一个 -oo 和一个 +oo 对象
p1 = new SkipListEntry(SkipListEntry.negInf, null);
p2 = new SkipListEntry(SkipListEntry.posInf, null);
// 将 -oo 和 +oo 相互连接
p1.right = p2;
p2.left = p1;
// 给 head 和 tail 初始化
head = p1;
tail = p2;
n = 0;
h = 0;
r = new Random();
}
private SkipListEntry findEntry(String key) {
SkipListEntry p;
// 从head头节点开始查找
p = head;
while(true) {
// 从左向右查找，直到右节点的key值大于要查找的key值
while(p.right.key != SkipListEntry.posInf
&& p.right.key.compareTo(key) <= 0) {
p = p.right;
}
// 如果有更低层的节点，则向低层移动
if(p.down != null) {
p = p.down;
} else {
break;
}
}
// 返回p，！注意这里p的key值是小于等于传入key的值的（p.key <= key）
return p;
}
public Integer get(String key) {
SkipListEntry p;
p = findEntry(key);
if(p.key.equals(key)) {
return p.value;
} else {
return null;
}
}
public Integer put(String key, Integer value) {
SkipListEntry p, q;
int i = 0;
// 查找适合插入的位子
p = findEntry(key);
// 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
if(p.key.equals(key)) {
Integer oldValue = p.value;
p.value = value;
return oldValue;
}
// 如果跳跃表中不存在含有key值的节点，则进行新增操作
q = new SkipListEntry(key, value);
q.left = p;
q.right = p.right;
p.right.left = q;
p.right = q;
// 再使用随机数决定是否要向更高level攀升
while(r.nextDouble() < 0.5) {
// 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
if(i >= h) {
addEmptyLevel();
}
// 从p向左扫描含有高层节点的节点
while(p.up == null) {
p = p.left;
}
p = p.up;
// 新增和q指针指向的节点含有相同key值的节点对象
// 这里需要注意的是除底层节点之外的节点对象是不需要value值的
SkipListEntry z = new SkipListEntry(key, null);
z.left = p;
z.right = p.right;
p.right.left = z;
p.right = z;
z.down = q;
q.up = z;
q = z;
i = i + 1;
}
n = n + 1;
// 返回null，没有旧节点的value值
return null;
}
private void addEmptyLevel() {
SkipListEntry p1, p2;
p1 = new SkipListEntry(SkipListEntry.negInf, null);
p2 = new SkipListEntry(SkipListEntry.posInf, null);
p1.right = p2;
p1.down = head;
p2.left = p1;
p2.down = tail;
head.up = p1;
tail.up = p2;
head = p1;
tail = p2;
h = h + 1;
}
public Integer remove(String key) {
SkipListEntry p, q;
p = findEntry(key);
if(!p.key.equals(key)) {
return null;
}
Integer oldValue = p.value;
while(p != null) {
q = p.up;
p.left.right = p.right;
p.right.left = p.left;
p = q;
}
return oldValue;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
class SkipListEntry {
// data
public String key;
public Integer value;
// links
public SkipListEntry up;
public SkipListEntry down;
public SkipListEntry left;
public SkipListEntry right;
// special
public static final String negInf = "-oo";
public static final String posInf = "+oo";
// constructor
public SkipListEntry(String key, Integer value) {
this.key = key;
this.value = value;
}
// methods...
}
public SkipListEntry head;
// First element of the top level
public SkipListEntry tail;
// Last element of the top level
public int n;
// number of entries in the Skip List
public int h;
// Height
public Random r;
// Coin toss
// constructor
public SkipList() {
SkipListEntry p1, p2;
// 创建一个 -oo 和一个 +oo 对象
p1 = new SkipListEntry(SkipListEntry.negInf, null);
p2 = new SkipListEntry(SkipListEntry.posInf, null);
// 将 -oo 和 +oo 相互连接
p1.right = p2;
p2.left = p1;
// 给 head 和 tail 初始化
head = p1;
tail = p2;
n = 0;
h = 0;
r = new Random();
}
private SkipListEntry findEntry(String key) {
SkipListEntry p;
// 从head头节点开始查找
p = head;
while(true) {
// 从左向右查找，直到右节点的key值大于要查找的key值
while(p.right.key != SkipListEntry.posInf
&& p.right.key.compareTo(key) <= 0) {
p = p.right;
}
// 如果有更低层的节点，则向低层移动
if(p.down != null) {
p = p.down;
} else {
break;
}
}
// 返回p，！注意这里p的key值是小于等于传入key的值的（p.key <= key）
return p;
}
public Integer get(String key) {
SkipListEntry p;
p = findEntry(key);
if(p.key.equals(key)) {
return p.value;
} else {
return null;
}
}
public Integer put(String key, Integer value) {
SkipListEntry p, q;
int i = 0;
// 查找适合插入的位子
p = findEntry(key);
// 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
if(p.key.equals(key)) {
Integer oldValue = p.value;
p.value = value;
return oldValue;
}
// 如果跳跃表中不存在含有key值的节点，则进行新增操作
q = new SkipListEntry(key, value);
q.left = p;
q.right = p.right;
p.right.left = q;
p.right = q;
// 再使用随机数决定是否要向更高level攀升
while(r.nextDouble() < 0.5) {
// 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
if(i >= h) {
addEmptyLevel();
}
// 从p向左扫描含有高层节点的节点
while(p.up == null) {
p = p.left;
}
p = p.up;
// 新增和q指针指向的节点含有相同key值的节点对象
// 这里需要注意的是除底层节点之外的节点对象是不需要value值的
SkipListEntry z = new SkipListEntry(key, null);
z.left = p;
z.right = p.right;
p.right.left = z;
p.right = z;
z.down = q;
q.up = z;
q = z;
i = i + 1;
}
n = n + 1;
// 返回null，没有旧节点的value值
return null;
}
private void addEmptyLevel() {
SkipListEntry p1, p2;
p1 = new SkipListEntry(SkipListEntry.negInf, null);
p2 = new SkipListEntry(SkipListEntry.posInf, null);
p1.right = p2;
p1.down = head;
p2.left = p1;
p2.down = tail;
head.up = p1;
tail.up = p2;
head = p1;
tail = p2;
h = h + 1;
}
public Integer remove(String key) {
SkipListEntry p, q;
p = findEntry(key);
if(!p.key.equals(key)) {
return null;
}
Integer oldValue = p.value;
while(p != null) {
q = p.up;
p.left.right = p.right;
p.right.left = p.left;
p = q;
}
return oldValue;
}

年收入增长率 + 营业利润率应该等于40％

互联网创业公司有一条40％规则：

如果你的年增长率达到100％，那么可以承受60％的亏损。
如果年增长率为40％，你应该收支平衡。
如果增长率为20％，你应该有20％的营业利润率。
如果没有增长，你应该有40％的营业利润率。
如果业务下降10％，你应该有50％的营业利润率。
我从来没有见过一个如此简单的规则。我总是觉得如果你快速增长，就可以接受赔钱。随着增长放缓，你必须赚钱并增加利润。现在有这样一个简单的公式，我非常喜欢。
这个百分之四十规则，俺解读一下子：
1 可以用金钱换成长，问题是你要成长的够快，烧钱也可以烧的够快，但是你也不能纯烧钱，你要留着一些余地，起码40%的收入，要保证，后面的可以靠着垄断带来的高收益来弥补。
2 增长率提不上去了，烧钱拉客户的时代过去了，那么你就要开始考虑赚钱的事情了。至于说为什么要选择40%？我想，这个就有待商榷了。
3 我觉得低了，这个明显和没和下降10%就得到50%的。
4 其实看看就好，就是告诉你，烧钱要有烧钱的增长，没烧钱你就要利润。

最后

以上就是机灵龙猫最近收集整理的关于第53周 ARTS 2019 10 20AlgorithmReviewTip/TechShare的全部内容，更多相关第53周内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：ARTS
浏览次数：80 次浏览
发布日期：2024-01-04 16:05:23
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_ocf4_13__23__22_0.html

第53周 ARTS 2019 10 20AlgorithmReviewTip/TechShare

Algorithm

378. 有序矩阵中第K小的元素

优先队列+多路归并

二分查找+查找元素

Review

Control Strategies of Two-Player Games 1989

Explore Annotations in Java 8

Java8的注释探索

Tip/Tech

跳表的另外一种实现方式

Share

年收入增长率 + 营业利润率应该等于40％

最后

评论列表共有 0 条评论

发表评论取消回复

第53周 ARTS 2019 10 20AlgorithmReviewTip/TechShare

Algorithm

378. 有序矩阵中第K小的元素

优先队列+多路归并

二分查找+查找元素

Review

Control Strategies of Two-Player Games 1989

Explore Annotations in Java 8

Java8的注释探索

Tip/Tech

跳表的另外一种实现方式

Share

年收入增长率 + 营业利润率 应该等于40％

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

年收入增长率 + 营业利润率应该等于40％

发表评论取消回复