【ARTS 周刊】第四期：今我来思，雨雪霏霏

2023.08.09

零、碎碎念

赛博朋克 2077 世界的特点是高科技低生活，也有人说那是一个科技前所未有的强大，但生命却前所未有的低贱的时代。人变成了公司人，生老病死都由“公司”控制，还未出生便背负上了永远也偿还不清的原罪。

公司人失去工作就无法生存，离开了公司就寸步难行。不得不被债务异化成工具，从身体到灵魂都被肆意改造、扭曲。思想受到层层检视，精力被利用到极致。每天重复着上班、下班、娱乐、睡觉的循环，像是一只蹬着跑轮的仓鼠，永无休止直到计划报废的那一天。

这样的世界可真是枯燥、恐怖而又绝望。

最近一周沉迷于复古游戏机以及复古游戏，即所谓的 Retro Game 和开源掌机。具体而言是指 Miyoo Mini Plus 掌机和一大堆 GBA、DOS 、FC、PICO-8 游戏。它成功洗刷了我对开源掌机的坏印象，现在已经是我首选的电子核桃，不时拿出来盘两下。

我尤其喜爱 DOS 游戏，它们大多发行在 1993 年前后，甚至更早，这意味着有许多游戏是在我出生之前便已经存在的，令人不禁想象当时的人们游玩这些游戏的感受。在它们精致又简单的独特画风下，可以体会到一种纯粹的游戏性。没有 648 充值抽卡，没有华丽复杂的技能、特效、系统，甚至也没有需要玩很久才能入门的复杂流程。

相比 GBA 游戏设计为在掌机上游玩，DOS 游戏本身是为了在 PC 上运行，两者的操作逻辑有所不同。那时候电脑配置普遍不高，然而现在 Miyoo Mini Plus 的配置运行 DOS 游戏可以说是毫不费力。高清晰度的屏幕，配合上精致又细腻的画风，有一种先进又落后的风味。掌机化之后能够简简单单地随时随地打开就玩，也能随时从中抽离，为的是汲取那一份简单的快乐。

我想这台掌机也许是人生中最简单而又廉价的娱乐设备，它简单又不失强大。FC 游戏能完美运行，虽然机能孱弱，却也能运行 DOS 时代的 FPS 游戏。它是两个时代的合作，是现代科技与旧日文化的融合。很难想象那个年代在机能限制的情况下能够做出如此杰出的游戏，而在当时也很难想象这些游戏有一天能够汇集在一台掌上设备中，只一台机器就能带上成千部游戏。口袋里带着一台掌机，就好象把握住了曾经的一整个时代。

这可能也是一种历史的衔接。 GBA、DOS 平台上的游戏是过去的代表，来自那个我未曾亲身体验过的时代，而赛博朋克 2077 的故事则发生在遥远的未来。我现在居于两者之间，每天都在创造出独属于我自己的故事。想到这里，又觉得别有一番趣味。

一、Algorithm

每周至少做一个算法题。

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

本周题目是堆栈与队列专题

1.1 判断括号字符串是否有效 20. Valid Parentheses

题目分析：给定由括号符号组成的字符串，判断该字符串中的括号是否是成对有效的。考虑用 Stack 来实现，逐个将字符串中元素放入 Stack 里，先放进去的括号符号后出。如果括号字符串是有效的，那么最终应该能全部弹出。

实现思路：将字符串拆成数组，从数组下标 0 开始遍历。如果元素是开括号，则放入 Stack 中，如果是闭括号，则找到对应的开括号符号，跟 Stack 中最后一个元素对比，如果相同则认为这一对括号有效，如果不同则认为出现了不能闭合的括号，可以直接认为不是有效的括号字符串。

实现如下：

const isValid = function(s) {
    const stack = [];
    const openingBrackets = ['(', '{', '['];
    const closingBrackets = [')', '}', ']'];


    if(s.length % 2 !==0){
        return false
    }

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (openingBrackets.includes(char)) {
            stack.push(char);
        } else if (closingBrackets.includes(char)) {
            const correspondingOpeningBracket = openingBrackets[closingBrackets.indexOf(char)];

            if (stack.length === 0 || stack.pop() !== correspondingOpeningBracket) {
                return false;
            }
        }
    }

    return stack.length === 0;
};

有点小技巧的地方在于 stack.pop 那一行，同时做了弹栈操作及比对弹出元素是否匹配的操作，这里需要对 Array.pop 比较熟悉。

if (stack.length === 0 || stack.pop() !== correspondingOpeningBracket) {
// ...
}

以下是 Python 版本

class Solution(object):
    def isValid(self,s):
        stack = [];
        opening_bracket = ['{','(','['];
        closing_bracket = ['}',')',']'];

        if len(s) % 2 != 0:
            return False

        for char in s:
            if char in opening_bracket:
                stack.append(char)
            elif char in closing_bracket:
                if len(stack) == 0 or stack.pop() != opening_bracket[closing_bracket.index(char)]:
                    return False
        return len(stack) == 0

时间复杂度是 O(n)，因为只需要遍历一次字符串，空间复杂度是 O(n)，因为最差情况下字符串全部由开括号组成，需要将整个字符串存入 Stack

1.2 用栈实现队列 232. Implement Queue using Stacks

队列的特性是先进先出，第一个放进去的元素第一个出来，但是栈的特点是先进后出如何使用栈来实现队列呢？

对于 JavaScript，很容易想到一个简单方法，直接用 Array 来模拟队列。对于队列来说，有以下几个方法：

push 向队列末尾添加元素
pop 将队列头部的元素出队
peek 查看队列头部的元素
empty 查看队列是否为空

我们很容易完成以下代码：

var MyQueue = function() {
    this.stack = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    return this.stack.shift()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.stack[0];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack.length === 0
};

提交上去也是能通过的，但是有没有更好的解决方法呢？

我们看到在 push 和 pop 时，是直接用的 Array 字面量。出栈 pop 操作时用的是 shift 方法，会导致每次出队时数组中元素都需要重新排序。如果采用两个栈，一个专门存储入栈数据，一个存储出栈数据，在出队和获取队首元素时才将入栈数据移动到出栈数据中来。

var MyQueue = function() {
    this.inputStack = [];
    this.outputStack = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.inputStack.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if (this.outputStack.length === 0) {
        while (this.inputStack.length !== 0) {
            this.outputStack.push(this.inputStack.pop());
        }
    }
    return this.outputStack.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (this.outputStack.length === 0) {
        while (this.inputStack.length !== 0) {
            this.outputStack.push(this.inputStack.pop());
        }
    }
    return this.outputStack[this.outputStack.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
};

第一种的 pop 时间复杂度是 O(n)，因为每次执行出队都需要对数组元素排序

后一种的 push、pop、peek、empty 的时间复杂度都是 O(1)，空间复杂度是 O(n)

1.3 用队列实现栈 225. Implement Stack using Queues

经过前一道用栈来模拟队列，很容易就想到如何用队列模拟栈了。

我们写下如下代码：

var MyStack = function() {
    this.queue = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    return this.queue.pop()
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.queue[this.queue.length-1];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.queue.length === 0;
};

心算一下，代码肯定是能跑过的，但是性能可能有问题。提交一下看看:

Beats 70.01%of users with JavaScript

没理由呀，现在都已经用底层数据结构了，也没有多余的遍历操作，怎么会只打败 70%的结果呢？

而且这里存在一个严重的问题，题目是要求用队列来实现栈，而不是用 JavaScript 的数组来实现。

上面用数组来实现虽然能够实现栈的基本功能，但是内部数据存储的顺序并不是按栈的方式来存的。

队列只有以下方法：

push 往队尾添加元素
pop 获取队首元素

看来得重新想方案：

双队列法：一个队列用来做进栈草操作，一个队列用来弹栈操作。但是两种方式
单队列法

单队列法实现如下：

class MyStack {
  constructor() {
    this.queue = [];
  }

  push(x) {
    const size = this.queue.length;
    this.queue.push(x);
    for (let i = 0; i < size; i++) {
      this.queue.push(this.queue.shift());
    }
  }

  pop() {
    return this.queue.shift();
  }

  top() {
    return this.queue[0];
  }

  empty() {
    return this.queue.length === 0;
  }
}

这里做的事情是用了一个队列，在 push 操作时调整元素顺序，将最后 push 进去的元素放在队首。这样将能做到栈的特性：最后入栈的元素最先出栈。注意本题中想要让元素出栈，必须使用队列的弹出队首的方法。

这种方式的时间复杂度 push 为 O(n)，因为遍历了一次队列，而 pop 的时间复杂度是 O(1); 空间复杂度是 O(n)。

提交一下，这次打败了 97%的用户。

Beats 97.56%of users with JavaScript

1.4 返回数据流中第 K 大的数 703. Kth Largest Element in a Stream

题目分析：

题目要求实现 KthLargest 类，使用整数 k 和整数流 nums 来初始化对象，并实现：

add 后将 val 插入到数据流 nums 后，返回当前数据流中第 k 大的元素

实现思路：

暴力法，顺着题目意思，我直接把 nums 降序排序，每次 add 后都都排序一次，再返回第 k 个元素
使用最小堆的结构，每次 add 时把 val 跟堆顶元素比较，如果比堆顶元素小，则丢弃，如果大，则删除堆顶元素，插入新元素。

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
  this.k = k;
  this.heap = [];
  for(let num of nums){
    this.add(num)
  }
};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
  this.heap.push(val);
  this.heap.sort((a,b)=>b-a);
  if(this.heap.length > this.k){
    this.heap.pop();
  }
  return this.heap[this.k-1];
};

时间复杂度：在初始化过程中遍历了 nums，nums 的长度是固定的，可以说是 O(n)，在 add 函数中的使用了 sort，在 javascript 的 sort 函数时间复杂度是 O(k Log k)，k是数组的长度，因此构造函数的时间复杂度是 O(n log k ) add 函数的时间复杂度是 O(k log k)

这种实现方式存在性能问题，首先是因为每次 add 都需要 sort, 导致时间复杂度到了 O(n log k)。

我们在此基础上进行优化：

var KthLargest = function(k, nums) {
  this.k = k;
// [4,3,4,2,1]
  this.heap = nums.sort((a,b)=>b-a);
};

KthLargest.prototype.add = function(val) {
  let index=0;
  // [5,2,1,] , 3 => [5,^3,2,1]
  while(index < this.heap.length && this.heap[index] > val){
    index++;
  }
  //save some time by not use sort function
  this.heap.splice(index,0,val);
  if(this.heap.length > this.k){
    this.heap.pop();
  }
  return this.heap[this.k-1];
};

现在构造函数的时间复杂度是 O(n log n)，n 是数组 nums 的长度，add 方法的时间复杂度是 O(k)

1.5 返回滑动窗口中的最大值 239. Sliding Window Maximum

给定整数数组 nums，创建一个大小为 k 的滑动窗口，每次只能访问数组中的 k 个元素，窗口每次向右移动一个元素。要求返回滑动窗口中的最大值。

笨办法。循环遍历数组 nums，每次遍历中都提取窗口内的元素，并执行一次排序，返回最大值。

var maxSlidingWindow = function (nums, k) {
  const result = []
  if (nums.length < k) {
      result.push(nums.sort((a, b) => b - a)[0]);
      return result;
  }
  for (var i = 0; i < nums.length - k + 1; ++i) {
    result.push(nums.slice(i,k+i).sort((a,b)=>b-a)[0]);
  }
  return result
};

很快我们写出了以上代码，在 nums 长度较小的时候能够正常执行。分析时间复杂度，使用尺寸为 k 的滑动窗口来遍历数组，则复杂度是 O(n-k),每次循环中执行一次 push O(1)、一次 slice O(n)、一次 sort O(k log k)，一次数组下标访问 O(1)。因此总的时间复杂度是 O(n log k)

如果用双端队列来实现：

var maxSlidingWindow = function(nums,k){
  // 存储最后结果
  const result =[];
  // 双端队列，存储元素的索引
  const deque = [];

  for (var i = 0; i < nums.length; ++i) {
    // 如果deque的第一个元素的下标超出滑动窗口，则将其移除
    if(deque.length>0 && deque[0] > i-k+1){
      deque.shift();
    }

    // 如果当前元素比deque中的元素中每一个元素都大，则将deque中最后一个元素移除
    while (deque.length > 0 && nums[i] > nums[deque[deque.length -1]]) {
      deque.pop();
    }
    deque.push(i);
   // 当滑动窗口起始索引大于等于0时，将窗口最大值 放到结果数组中
    if(i >= k-1){
      result.push(nums[deque[0]]);
    }
    return result;
  }
}

Python 版本实现：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
      if not nums: return []
      window, res = [], []
      for i, x in enumerate(nums):
        if i >= k and window[0] <= i - k:
          window.pop(0)
        while window and nums[window[-1]] <= x:
          window.pop()
        window.append(i)
        if i >= k - 1:
          res.append(nums[window[0]])
      return res

此时时间复杂度是 O(n)，只需要一次遍历即可查到所有滑动窗口的最大值。

二、Review

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

看别人写的文章并点评

看了下待读库，很奇妙的积累类一些跟工作效率有关的文章，放在这里一起读一下。

三、Tip

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

日常开发中的技巧

关于现代化网页中的图片懒加载

随着 Chrome 等浏览器的逐渐普及，图片、iframe 等元素已经支持懒加载了。可以像这样使用：

<img src="image.png" loading="lazy" alt="…" width="200" height="200">

直接给 img 标签加上 loading=“lazy"属性，就自动获得了图片懒加载能力。目前 Chrome、Firefox、Edge、Safari 都支持该功能，具体使用细节可以看以下文档

DEMO

详细文档：https://web.dev/browser-level-image-lazy-loading/

iframe 的懒加载

正如图片的懒加载一样，Chrome 和 Safari 已经支持以下写法，并且 iframe 懒加载已经进入了 Web 标准：链接

<iframe loading=lazy>

DEMO

详细情况可以看以下内容：https://web.dev/iframe-lazy-loading/

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

最好是自己写的文章。

本期分享两篇，一个是张小策的视频

《我宁愿痛苦，也不要麻木！》

看着是随手录的视频，但是立意很高

中国独立开发者的运营成本

另一个是由最近的 APP 备案政策引起的想法，中国国内独立开发者的经营难度究竟有多大。

工业和信息化部近日印发《工业和信息化部关于开展移动互联网应用程序备案工作的通知》（以下简称《通知》），组织开展移动互联网应用程序（简称 App）备案工作，要求在中华人民共和国境内从事互联网信息服务的 App 主办者，应当依照《中华人民共和国反电信网络诈骗法》《互联网信息服务管理办法》等规定履行备案手续，未履行备案手续的，不得从事 App 互联网信息服务。
《通知》明确提出，App 主办者、网络接入服务提供者、应用分发平台、智能终端生产企业应当建立健全违法违规信息监测和处置机制，发现法律、行政法规禁止发布或者传输的信息，应当立即停止传输该信息，采取消除等处置措施，防止信息扩散，保存有关记录，并向电信主管部门报告，依据电信主管部门要求进行处置。网络接入服务提供者、应用分发平台、智能终端生产企业不得为未履行备案手续的 App 提供网络接入、分发、预置等服务。

来源链接：链接

这意味着继网站域名的 ICP 备案、公安网安备案、ICP 增值业务许可证之外，对 App 也新增了备案要求。并且『智能终端生产企业』也就是生产手机的公司，如苹果、小米、华为等生产的手机是不允许安装未经备案的 App 的。

有些人认为这只是不允许手机厂商的应用市场上架未备案应用，那么我备案不就行了，或者我直接发布 apk 文件。

首先苹果如果遵守这项法律，目前独立开发者以及普通用户是没办法绕过的。其次既然这项通知中已经明确提到要备案，国内厂商肯定会加码，会直接禁止非应用市场安装 App。

个人开发者怎么应对？在一开始就不要对国内市场有期待，政策风险太大了。尽快赚钱。

更新于：2023.08.09

ARTS-周刊

扑蝶花语