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个元素

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。
至于找值也是有很大技巧的，因为有顺序递增的特性，那么也就可以直接点，从每一列或者每一行的最后一个元素开始遍历，从第一列或者第一行开始，然后逐步往下，比较累加，说这有点复杂，看了代码就明白。。。

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;
}

Share

年收入增长率 + 营业利润率 应该等于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 2019 10 20AlgorithmReviewTip/TechShare所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。