1. Algorithm: 每周至少做一个 LeetCode 的算法题

题目

82. Remove Duplicates from Sorted List II



Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.



Return the linked list sorted as well.



Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3



定义公用的链表

用于打印链表数据



package common;
public class ListNode {
    public int val;
    public  ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    static public ListNode listNodeWithIntArray(int[] input) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i: input) {
            ListNode newNode = new ListNode(i);
            node.next = newNode;
            node = node.next;
        }
        return head.next;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode node = this;
        while (node != null) {
            sb.append(node.val).append("-->");
            node = node.next;
        }
        return sb.append("Null").toString();
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        return false;
    }
}



遍历解法

思路：

1. 用快慢两个指针，慢指针指着上一个节点，快指针找出下一个不重复的节点；

2. 如果找到重复的节点，则慢指针的下一个节点就不等于当前快指针 if (slow.next != fast)，那慢指针就指向快指针的下一个值；也就是下一个不重复的值；

3. 如果没找到重复的节点，则都指向下一个节点；

4. 无论是否找到重复的节点，快指针都要指向下一个节点fast = fast.next;



package linkedlist;
import common.ListNode;
public class RemoveDuplicatesFromSortedListII {
  public ListNode deleteDuplicates(ListNode head) {
    //check edge
    if (head == null || head.next == null) {
      return head;
    }
    ListNode dummy = new ListNode(0);
    ListNode slow = dummy;
    ListNode fast = head;
    slow.next = fast;
    while (fast != null) {
      while (fast.next != null && fast.val == fast.next.val) {
        fast = fast.next; // while loop to find the last duplicate item
      }
      // find duplicate
      if (slow.next != fast) {
        slow.next = fast.next;  // remove the duplicate items
      } else {
        slow = slow.next; // move down next point
      }
      fast = fast.next;
    }
    return dummy.next;
  }
}



递归解法

递归的思路就是翻译了遍历的做法。

1. 如果当前节点不是唯一节点，则递归调用指向下一个节点。

2. 如果当前节点是唯一节点，则用当前节点指向，递归调用的下一个节点。



package linkedlist;
import common.ListNode;
public class RemoveDuplicatesFromSortedListII {
	/**
	   * if current node is not unique, return deleteDuplicates with head.next.
	   * If current node is unique, link it to the result of next list made by recursive call. Any improvement?
	   * @param head
	   * @return
	   */
  public ListNode deleteDuplicatesWithRecursive(ListNode head) {
    if (head == null) {
      return head;
    }
    if (head.next != null && head.val == head.next.val) {
      while (head.next != null && head.val == head.next.val) {
        head = head.next;
      }
      return deleteDuplicatesWithRecursive(head.next);
    } else {
      head.next = deleteDuplicatesWithRecursive(head.next);
    }
    return head;
  }
}



2. Review: 阅读并点评至少一篇英文技术文章

Paul Graham (programmer)

https://en.wikipedia.org/wiki/Paul_Graham_(programmer)



http://www.paulgraham.com/articles.html



阅读了保罗·格雷厄姆的生平，他的技术博客也在上面。身为互联网投资教父，不仅技术牛，还写了很多有影响力的文章。《黑客与画家》的英文文章都在他的博客里面





3. Tips: 学习至少一个技术技巧

笔者写的博客：

Mac OS 开启三指拖移，三指缩放，拖拽窗口，切换全面页面变成四指



说明

• 平时 XCode 调试的断点，可以用三个手指移除；

• 可以三个手指拖动窗口

• 截图的时候可以三个手指 伸缩窗口大小。



这么神奇的黑客、hack操作，请根据下面指引设置。 笔者设置于 macOS Catalina。

配置

开启适用于 Force Touch 触控板的“三指拖移”

“三指拖移”是 OS X 中的一种 Multi-Touch 手势。通过这个手势，您能使用三个手指移动屏幕上的活跃窗口。



本文介绍了在您的 Mac 配备了 Force Touch 触控板的情况下，该如何开启“三指拖移”。



1. 从 Apple 菜单中，选取“系统偏好设置”。

2. 点按“Accessibility”图标。



1. 从左侧的选项中选取“鼠标与触控板”。



1. 点按“触控板选项”。



1. 在“启用拖移”旁边勾选。

2. 从相关的弹出式菜单中，选取“三指拖移”，这样该项旁边会显示一个勾号。

3. 点按“好”。



参考

https://support.apple.com/zh-cn/HT204609



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接



极客大学架构师训练营 大数据平台、Sqoop、Canal、Flume、物联网平台 第27课 听课总结



说明

讲师：首席架构师 李智慧



大数据平台



大数据技术应用的挑战

大数据计算的海量分布式计算方案，必然导致计算速度不是很快，即使在一个规模不太大的数据集上进行一次简单计算，MapReduce 也可能需要几分钟，Spark 快一点，也至少需要数秒的时间。



互联网产品处理用户请求，通常需要毫秒级的响应，也就是说，要在 1 秒内完成计算，大数据计算必然不能实现这样的响应要求。但是互联网应用又需要使用大数据，实现统计分析、数据挖掘、关联推荐、用户画像等一系列功能。



那么如何才能弥补互联网和大数据之间的差异呢？



大数据平台架构

蓝色部分归属于大数据平台范围。



大数据处理流程：

1. App、浏览器的用户数据、日志、打点采集的数据、爬虫的数据存储到数据库；

2. 数据同步系统，比如消息队列导入到大数据存储系统 HDFS；

3. 大数据计算, 通过 MapReduce, Spark, Hive计算，结果还是写到 HDFS 里面；实时流大数据处理 Stomr, Spark Streaming, Flink;

4. 数据同步系统，导出数据到 数据库。实时流大数据流，可以订阅结果，实时输出分析报表，进行活动方案调整，比如双十一当天活动。

5. 应用把结果导出报表，看看应用的bug在哪里，通知开发人员去解决；

6. 数据监控把结果导出报表，看看业务是否有什么异常，如果有就要采取相应的策略；

7. 运营决策把结果导出报表，看看运营策略效果如何，进行运行活动调整。



纠错： 数据处理层的批量数据同步，的头应该从 大数据存储(HDFS) 指出。



数据采集与导入

将应用程序产生的数据和日志等同步到大数据系统中，由于数据源不同，这里的数据同步系统实际上是多个相关系统的组合。数据库同步通常用 Sqoop，日志同步可以选择 Flume，打点采集的数据经过格式化转换后通过 Kafka 等消息队列进行传递。



不同的数据源产生的数据质量可能差别很大，数据库中的数据也许可以直接导入大数据系统就可以使用了，而日志和爬虫产生的数据就需要进行大量的清洗、转化处理才能有效使用。



用 Sqoop 导入导出数据库数据

批处理用 Sqoop



用 Canal 实时导入 MySQL 数据

处理 MySQL 数据，可以一条一条实时同步数据。

原理： Canal 把自己伪装为 MySQL的 Slave。



用 Flume 从日志导入数据

Flume 级联部署



Flume 分布式部署

前端埋点采集数据

• 核心数据： 用户增加、流失等，实时上报；

• 实时数据：用户操作数据，实时上报；

• 离线数据：非核心数据，存储到手机本地，当连接 WiFi的情况下才上传；



网络爬虫收集外部数据

爬虫一般是爬取竞争对手，或者政府机构的数据。

重点是如何突破竞争对手的反爬虫系统。



数据输出与展示

大数据计算产生的数据还是写入到 HDFS 中，但应用程序不可能到 HDFS 中读取数据，所以必须要将 HDFS 中的数据导出到数据库中。数据同步导出相对比较容易，计算产生的数据都比较规范，稍作处理就可以用 Sqoop 之类的系统导出到数据库。



这时，应用程序就可以直接访问数据库中的数据，实时展示给用户，比如展示给用户关联推荐的产品。淘宝卖家的量子魔方之类的产品，其数据都来自大数据计算产生。



除了给用户访问提供数据，大数据还需要给运营和决策层提供各种统计报告，这些数据也写入数据库，被相应的后台运营和管理人员访问，查看数据报表，看业务是否正常。



大数据平台 Lamda 架构原型

淘宝大数据平台



淘宝大数据平台导入导出数据