第44周 ARTS 2019 08 18_综合

Algorithm：274. H指数
Review：
Tip/Tech：
Share：

Algorithm

274. H指数

https://leetcode-cn.com/problems/h-index/
在这里插入图片描述
这题的重点就是理解（N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次，其实就是你要找一个区间，**在这个区间里面，最低引用数量论文的引用数，起码要大于等于这个区间里面的论文数量。**这么说有点抽象，我这里举一个例子的图来说明
在这里插入图片描述
你看我画圈圈的三个点，最低的引用量是5，但是这里面的文章是多少？3。可以满足至多3篇文章的论文引用了3次。那么如果吧引用量为3的那篇也算进来呢？那么就不满足条件了，因为这样，论文的数量达到了4篇，但是这4篇中的最底的引用量则变了3。所以H指数为3。
那么看清楚了，上面的思想，具体说一下操作步骤：
（1）排序，把每篇的论文，根据引用量进行排序
（2）遍历比较，因为排序是升序遍历，我们找到所有，citations[len - 1 - i] > i，的满足的论文数量。
下面我们来看看代码。

class Solution {
    public int hIndex(int[] citations) {
    if (citations == null || citations.length == 0) {
    return 0;}Arrays.sort(citations);int ans = 0;for (int i = 0, len = citations.length; i < len; ++i) {
    // i从小到打，那么排好序的citations就要从后往前走if (i < citations[len - 1 - i]) {
    ans ++;} else {
    break;}}return ans;}
}

以上的时间复杂度是： $O (l o g N)$ 。空间复杂度是： $O (1)$ 。

更好的解法

其实以上的题目的最大的时间开销来自于排序，如果可以在排序节约时间，那么时间复杂度会提升不少。那么在时间复杂度为 $O (N)$ 的排序中，计数排序是比较符合这里的，当然我是马后炮的，因为我知道了答案才直接说计数排序的。如果你不理解，那么就继续往下看。
要知道用计数排序，这里需要知道一个前提条件，就是，这里的最后答案是论文数，你引用量再大，最后答案也是和论文的关系更大。比如有一篇论文，它的引用量是100，那么这里答案
（1）也就说答案根本不可能超过论文的数量。所以就有一个结论：

一旦引用量超过了论文的数量，那么这个就可以用论文数量来代替了。

因为这里用计数排序，最大的问题是会出现那种引用量特别大的论文，这样会影响计数排序的效率，但是如果把那个大值改成长度，那么就会少了许多不必要的计数了。
那么接下里就是要从后向前遍历整个桶，如果有出现说论文的总数大于引用数的，那果断的退出吧。返回值就是那个引用数，也就是索引i。

class Solution {
    public int hIndex(int[] citations) {
    if (citations == null || citations.length == 0) {
    return 0;}int len = citations.length;int[] buckets = new int[len + 1];for (int item : citations) {
    int tempIndex = Math.min(item, len);buckets[tempIndex] ++;}int paperCount = 0;for (int i = len; i >= 0; --i) {
    paperCount += buckets[i];if (i <= paperCount) {
     return i;}}return 0;}
}

这里的时间复杂度就是 $O (n)$ ，空间复杂度 $O (n)$ 。

Review

Effects of Type Erasure and Bridge Methods

类型擦除的影响和桥接方法

https://docs.oracle.com/javase/tutorial/java/generics/bridgeMethods.html

public class Node<T> {
    public T data;public Node(T data) {
     this.data = data; }public void setData(T data) {
    System.out.println("Node.setData");this.data = data;}
}public class MyNode extends Node<Integer> {
    public MyNode(Integer data) {
     super(data); }public void setData(Integer data) {
    System.out.println("MyNode.setData");super.setData(data);}
}

接下来看看这段代码：

MyNode mn = new MyNode(5);
Node n = mn;            // A raw type - compiler throws an unchecked warning
n.setData("Hello");     
Integer x = mn.data;    // Causes a ClassCastException to be thrown.

这段代码会运行报错，一般来说，需要用个转换类型。

MyNode mn = new MyNode(5);
Node n = (MyNode)mn;         // A raw type - compiler throws an unchecked warning
n.setData("Hello");
Integer x = (String)mn.data; // Causes a ClassCastException to be thrown.

在java编译器会进行类型擦除：

public class Node {
    public Object data;public Node(Object data) {
     this.data = data; }public void setData(Object data) {
    System.out.println("Node.setData");this.data = data;}
}public class MyNode extends Node {
    public MyNode(Integer data) {
     super(data); }public void setData(Integer data) {
    System.out.println("MyNode.setData");super.setData(data);}
}

为了解决这个问题并在类型擦除后保留泛型类型的多态性，Java编译器会生成一个桥接方法，以确保子类型按预期工作。对于MyNode类，编译器为setData生成以下桥接方法。

class MyNode extends Node {
    // Bridge method generated by the compiler//public void setData(Object data) {
    setData((Integer) data);}public void setData(Integer data) {
    System.out.println("MyNode.setData");super.setData(data);}// ...
}

Tip/Tech

用循环链表的思想来解决约瑟夫问题

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
    if(m <= 0 || n <= 0){
    return -1;}//先构造循环链表ListNode head = new ListNode(0); //头结点, 值为0ListNode pre = head;ListNode temp = null;for(int i = 1; i < n; i++){
    temp = new ListNode(i);pre.next = temp;pre = temp;}temp.next = head;//将尾结点指向头结点，形成一个循环链表ListNode node = null;while(n != 1){
    node = head;//先找到第m个结点的前驱for(int i = 1; i < m - 1; i++){
    node = node.next;}//删除第m个结点：将第m个结点的前驱指向第m个结点后面那个结点,node表示第m个结点的前驱node.next = node.next.next;head = node.next; //更新头结点n--;}return head.value;}
}/*** 结点*/
class ListNode {
    int value;ListNode next = null;public ListNode(int val) {
    this.value = val;}
}

https://techcrunch.com/2019/07/28/fortnite-world-cup-has-handed-out-30-million-in-prizes-and-cemented-its-spot-in-the-culture/

Fortnite世界杯已经发放了3000万美元的奖金

对于这个电竞的行业，我真的有点不明白，你说玩游戏这个为什么会值这么多钱，这个奖金比温网的奖金还要高，有的时候，你不得不承认，你需要去不断的接受新的事物了，即使你之前不认为电竞之前有多少价值，但是现在随着各种的竞赛，各种的奖金，你也不得不承认电竞也学真的有一台呢会和NBA，NBL那样，会变成我们平常所看的那种比赛一样，同样流行。