【ARTS 周刊】第三期：氓之蚩蚩，抱布贸丝

2023.07.24

零、碎碎念

很多公司都会要求员工有 OwnerShip。第一次听到这个说法时会觉得很疑惑：我其实并不“拥有”我负责的项目，我也无法决定业务的走向，更无法直接从业务中拿到收益，而且我都换了好几条业务线了，说让你换就得换，根本就不不归我所有的东西，怎么会有期望有 Owner 意识呢？

后来想到这可能仅仅是一种责任分配的方式，是一种激发员工主动性的管理方法。但是对打工人来说，在工作中增强自己的能力，积累资本，增加自身在整个职场中的竞争力才是最重要的，只有这样才能实现员工和公司双赢。

直到最近看到这篇讨论：链接，备份1，在这里我不做评价，各人有各人的观点。摆正位置很重要，想清楚自身的核心能力是什么，加油！

一、Algorithm

每周至少做一个算法题。

计划每天做两道新题目，复习之前的题目，这样可以有更好的刷题效果。

本周继续做链表的题目

判断链表是否有环

141. Linked List Cycle

分析：判断链表中有环的话，可以使用快慢指针法，使用两个节点去一直访问后继节点，如果两个节点能跑到最后一个节点，就说明没有环，如果在过程中相遇了，则说明有环。

也可以用哈希表法，遍历链表一次，每次遍历先检查哈希表里有没有该节点，有则认为之前已经访问过了，因此是有环的，如果无则将当前节点放到哈希表里。

快慢指针的解：

JavaScript

var hasCycle = function(head){
    let fast = head;
    let slow = head;

    while(slow && fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;

        if(fast === slow){
            return true
        }
    }
    return false
}

Python

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = head
        slow = head
        while fast and slow and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

小结：时间复杂度是 O(n)，空间复杂度是 O(1)。因为如果有环，则快指针会追上慢指针，时间复杂度是 O(n)，如果没有环，则快指针会先到达链表末尾，时间复杂度同样是 O(n)

哈希表的解：

JavaScript

var hasCycle = function(head){
    const hashTable = new Map();
    let curr = head;
    while(curr && curr.next){
        if(hashTable.get(curr)){
            return true;
        }
        hashTable.set(curr,curr.val);
        curr = curr.next;
    }
    return false
}

Python:

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        hashTable = {}
        curr = head
        while curr and curr.next:
            if curr in hashTable:
                return True
            hashTable[curr] = curr.val
            curr = curr.next
        return False

哈希表方式的时间复杂度是 O(n)，因为只要遍历一次链表，但是空间复杂度也是 O(n)，因为还要将访问过的链表的节点存进去，最差情况下每个节点都不同，也就是无环，哈希表要存 n 个节点

环形链表

142. Linked List Cycle II

分析：需要检查链表是否有环，并且要找出环是从哪个节点开始的，如果有环则返回环的起始节点的索引，如果无则返回-1.

可以用一个哈希表来存储遍历过的节点，然后 key 为节点，value 为该节点所在的索引。

也可以用快慢指针法

最长递增子序列的数量

673. Number of Longest Increasing Subsequence

这是 7.20 日的每日一题，

下面是我最开是写的版本，然后我拿去问了 ChatGPT

const findNumberOfLIS = function (nums) {
  // 以nums[i] 结尾的最长递增子序列的长度
  const lengths = [];
  // 以nums[i] 结尾的最长递增子序列的数量
  const counts = [];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < i; j++) {
      if (nums[i] > nums[j]) {
        if (lengths[i] === lengths[j]) {
          counts[i] += counts[j];
        }
        if (lengths[i] > lengths[j]) {
          counts[i] = counts[j];
        }
      }
    }
  }
  // 找到最大长度的递归子序列的长度
  const maxLen = Math.max(lengths);
  // 找到长度等于maxLen的所有结尾节点
  const largestIndex = lengths.filter((it) => it === maxLen);
  // 再把这些节点结尾的 子序列加起来
  const result = largestIndex.reduce((prev, curr) => {
      return prev + curr;
    }, 0);
    return result;
};

让 ChatGPT 给优化之后

const findNumberOfLIS = function(nums) {
  const n = nums.length;
  const lengths = Array(n).fill(1);
  const counts = Array(n).fill(1);

  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < i; ++j) {
      if (nums[i] > nums[j]) {
        if (lengths[i] === lengths[j] + 1) {
          counts[i] += counts[j];
        }
        if (lengths[i] < lengths[j] + 1) {
          lengths[i] = lengths[j] + 1;
          counts[i] = counts[j];
        }
      }
    }
  }

  const maxLen = Math.max(...lengths);

  const largestIndex = lengths.reduce((indices, len, i) => {
    if (len === maxLen) {
      indices.push(i);
    }
    return indices;
  }, []);

  const result = largestIndex.reduce((sum, index) => sum + counts[index], 0);

  return result;
};

二、Review

每周阅读并点评至少一篇英文文章。

看别人写的文章并点评

本期分享的是一篇介绍网络搜索的 Tips 的文章：

Internet Search Tips

关于 Google 搜索小技巧在掘金已经有很多了，但是这篇文章读起来会有所不同。一是因为发布这篇文章的博客，我个人非常喜欢他博客的风格和理念（为 60~70 年的人们写作）

三、Tip

每周学习并分享至少一个技术技巧

日常开发中的技巧。

Org─Mode 中代码块的 noweb 功能，作用是在一个代码块中嵌入另一个代码块的结果，例如我们有一个指定了 #+NAME: sayHi 属性的代码快，它的输出结果是"hello,world"，可以在另一个代码块中使用 <<saiHi()>> 来引用代码块的结果。

这在希望让代码和文档保持一致的场景中非常有用。

echo "hello,world"

content = (("hello" "world"))
print(content)

每周分享至少一篇有观点和思考的技术文章。

最好是自己写的文章。

本周尝试整理程序员知识结构，写了一篇文章：程序员的自我修养：构建知识结构体系

主要内容是从顶层开始梳理了一名程序员所需要的一些知识分类，并尝试逐步去攻克它。

本周的分享就到这里，祝大家生活愉快。

Updated on：2023.07.24

ARTS-周刊

Deep Beep