Leetcode 260 題 Single Number III 又是一道只能使用 bitwise operation 才能達到要求的題目,除了需要使用基本的 AND, XOR 之外,還引入了 lowbit function 的概念。

Image for post
Image for post
https://images.unsplash.com/photo-1554175940-c7d7ede2ecb9?ixlib=rb-1.2.1&ixid=eyJhcHBfaWQiOjEyMDd9&auto=format&fit=crop&w=1650&q=80

Leetcode 260 — description

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

提供一組元素全為「數字」的陣列,其中「只有兩個」元素是唯一存在,其他元素「都會重複兩次」。

如果要達到任務,在時間複雜度 O(N)、空間複雜度 O(N) 的要求下其實不難,但偏偏題目要求時間複雜度 O(N),然後空間複雜度要 O(1)。

在不能增加空間來儲存元素的額外資訊(譬如出現次數,或有沒有看過)的情況下,一時想到能做的,只有透過修改元素值來當作標記,通常的做法是將正數改為負數,但這題有趣的是,題目提供的陣列當中,數字包含負數,所以類似下面這種做法就完全行不通:

let result = []
for (let i = 0; i < nums.length; i++){
let index = Math.abs(nums[i]) - 1
if (nums[index] < 0) {
result.push(index …


Image for post
Image for post
Source: https://images.unsplash.com/photo-1571218027918-a734b7f264c8?ixlib=rb-1.2.1&ixid=eyJhcHBfaWQiOjEyMDd9&auto=format&fit=crop&w=1650&q=80

同學提問:執行下面的程式碼

let arr = [1, 3, 2]
arr.sort((a, b) => {
console.log(`Now comparing a = ${a} & b = ${b}`);
return a - b;
});

得到結果會是

Now comparing a = 3 & b = 1
Now comparing a = 2 & b = 3
Now comparing a = 2 & b = 3

Now comparing a = 2 & b = 1

為什麼其中的 2 和 3 會被比較兩次呢?

在 Array.sort() 裡面放入 console.log() 還真是我沒有想過的點子,非常有趣,但一放進去就發現問題,讓我花了半天的時間尋找答案。那麼同樣的,接下來就歡迎有興趣的朋友跟著我一起探索吧!

先講結論

根據經驗,大概有 70% 以上的人不會把文章看完,所以這裡先講結論

在目前的 V8 engine 當中,處理 array.prototype.sort() 的時候是使用 Timsort(跟我同名的)排序法。

Timsort 的概念是,將一大筆資料拆成小批次的資料,在小批次的資料當中使用 Binary Inserttion Sort,之後再將已經排序好的小批次資料,用 Merge Sort 把所有小批次資料整合在一起。

不過在進行 Binary Insertion Sort 之前,Timsort 會進行一個特別的動作,就是它會先去搜尋「小批次資料當中前面的『有序』資料」,把這些資料抓出來之後,這段資料就不需要進行 Binary Insertion Sort。

因此剛剛的結果,其實是 console.log 分別在不同的階段被呼叫(因為資料量小,所以沒有動用到…


Image for post
Image for post
source: http://www.passportjs.org/

歷來學生都不斷地詢問一個問題:

要如何將 Passport 當中的錯誤訊息顯示出來

雖然過去在每一班都回覆過類似的問題,但發現每回覆一次,就會發現新的東西,讓我自己覺得不太安寧。因此,決定透過這篇文章,來結束這場戰鬥 😤

前情提要

Passport.js 是在開發 Node.js 應用程式時,常用到的驗證系統。想了解更多,可以參考以下文章

這篇文章不會講解 Passport 如何使用,將會著重在 failure message 上

先講結論

要呈現 Passport 驗證過程中的錯誤訊息,有以下幾種方法

1. 直接呼叫 req.flash()

在使用 LocalStrategy 的時候 直接呼叫 req.flash() ,這應該是最直接的方法,但是要注意的是,使用這個方法需要 req ,所以上面的 passReqToCallback 一定要設定為 true ,我們才能夠在 verify function 當中傳入並使用 req

2. 開啟 failureFlash 設定

然後可以在 verify function 當中的 done 傳入

// flash type 自動設定為 error
“I’m error message”
// flash type 自動設定為 error。注意這裡的 key 必須為 message
{message: "I’m error message”}
// 手動設定flash type 為 hi。注意後面訊息的 key 必須為 message
{type: 'hi', message: “I’m error message”}

另外一個可以設定的地方在這裡

app.post('/signin', passport.authenticate(
'local',
{ ...


Image for post
Image for post
Source: https://hackernoon.com/drafts/h3wk32zy.png

[quick note]

Handlebars 升級到 4.6 之後,會限制傳入的資料規格,不允許帶有 prototype properties 的物件。

From version 4.6.0 on, Handlebars forbids accessing prototype properties and methods of the context object by default. The reason are various security issues that arise from this possibility. The following options can be used to control this access.

(Ref: https://handlebarsjs.com/api-reference/runtime-options.html)

雖然仍然給予使用者調整限制的權限,不過官方不建議自己調整。

因此,當我們透過 Sequelize 從資料庫取出資料之後,需要讓他變成 pure object,目前已知有以下幾種做法

在 query option 當中設定 raw: true

let users = await User.findAll({ raw: true, nest: true })

這個方法適合所有的查詢方式,特別是多筆資料的查詢。

取出 dataValue

let user = await User.findOne({ where: { id: req.user.id } })
user = user.dataValue

用 .get() 方法

let user = await User.findOne({ where: { id: req.user.id } })
user = user.get()

以上兩個方法適用在只取出一筆資料的情況。另外,其實 .get()


Image for post
Image for post

當助教有時候需要幫學生解 bug,但我覺得更有趣的是,用不一樣的方法來解釋原本已知的知識,過程中有時會思考到事物的本質。也因此,我希望能把自己的一些想法給紀錄下來。

上週遇到一位學生問:

我一直搞不懂變數是什麼,宣告是什麼?

電腦能幫我們做很多事情,但前提是,電腦需要知道

  • 要處理什麼資料
  • 怎麼處理資料

就像是老闆跟我說「誒 td,把去年的財務報表從檔案庫當中拿出來給我」,這時候我就知道

  • 要處理什麼資料:財務報表
  • 怎麼處理資料:從檔案庫當中拿出給老闆

但實際上,「財務報表」也只是個名詞而已,他對應到的,實際上是一疊 A4 大小的紙,上面有財務數據。

回頭來看看電腦怎麼運作,假設我希望電腦幫我「把我的薪水印出來」,這時候電腦需要知道

  • 要處理什麼資料:薪水
  • 怎麼處理資料:印出來

但實際上這時候,電腦程式空空如也,既不知道薪水是什麼,也不知道怎麼印出來,因此我們就會給他一些指令,像是

console.log(salary)            // 印出 salary

但這時候電腦還是不知道 salary 裡面究竟是什麼東西,就像是不知道所謂的「財務報表」長什麼樣子,因此,我們需要讓電腦知道,大聲的宣告「我的薪水就是兩萬元啦!」

let salary = 20000             // 宣告 salary

好了,如果把上面兩行程式碼放在一起,那麼就可以順利的讓電腦完成任務:

let salary = 20000    
console.log(salary) // 看到輸出結果為 20000

那你可能會問,為什麼不直接印出來就好(如下)

console.log(20000)

其實也不是不行,但隨著年資增長,我的「薪水」也會慢慢增加,也就是說 salary 裡面的資料其實會變動。

如果在 console.log() 裡面將數字寫死,那麼就無法反應我的薪水的實際狀況。 另外,如果程式的其他地方也需要薪水的資料,那麼我就要在很多地方寫上 20000,假設哪一天我的薪水有變動,我就需要同步在所有地方更改這些數字。

說到這裡,其實「變數」就是存放需要讓電腦處理的資料,我們可以自行命名這個變數的名稱,並給這個變數資料,譬如

let salary = 20000  
let mySalary = 30000
let tdSalary = 40000

建立一個新的變數的過程,就是「宣告」。

當一個變數被宣告之後,就可以在程式的其他地方被使用。像是我先前的例子,當我們宣告(詔告)大家:這疊 A4 紙的資料就是「財務報表」,之後,大家只要提到「財務報表」,就知道我們指的資料、需要處理的資料就是剛剛那疊 A4 紙。

About me

Self-taught and trained in software development knowledge and skills, I am passionate about creating changes through technology.

Find more at Github, LinkedIn, Teaching at ALPHA Camp


Image for post
Image for post

上週嘗試把 Node.js app 部署到 AWS Elastic Beanstalk 上,同時也在 Namecheap 上買了人生第一個 domain name: td.coffee。當中還有許多自己不了解的細節,不過這裡就先紀錄一下過程。

AWS Elastic Beanstalk

Elastic Beanstalk 是 AWS 提供的一項服務,能讓開發團隊快速部署及管理應用程式。Elastic Beanstalk 是在 EC2 (Elastic Compute Cloud) 之上所建立的一層 layer,因此透過 Elastic Beanstalk 部署,不僅僅只是幫我們開啟 server,過程中更可以透過設定,開啟 S3, Simple Notification Service, CloudWatch, auto-scaling, load balancing 等服務,可以說是個方便的一站式服務。

部署完成之後,Elastic Beanstalk 會自動產生連結,我們就可以透過這個連結,連線到我們的 application。不過這個連結非常的長,大概長這樣 http://myapplication-env.xxx-xxxxxxxx.ap-southeast-1.elasticbeanstalk.com/,如果想要使用一個名字好記、能夠代表自己的連結,就需要自己購買新的網域。

Namecheap

Namecheap 是一家域名註冊與 hosting 的服務商。其實購買網域相當方便,就像是逛線上商店一樣,選好自己要的網域名,然後再次確認自己可以付得起,就可以結帳囉!

Image for post
Image for post


Image for post
Image for post
Source: https://getbootstrap.com/docs/4.0/components/alerts/

其實本來只是想要找 flash 的一個問題,結果意外發現 connect-flash 這個 package 的程式碼相當的小,於是就趁機嘗試讀了一下。

哪裡找 source code?

這個問題的答案看起來超簡單:直接到 Github 上看。也的確是這樣沒錯,不過前幾週看了 Code Spelunking: teach yourself how Rails works,講者提到

如果今天在飛機上我們遇到程式問題,但卻又連不上網路,無法 Google 或是 Stack Overflow 的話,我們是否能透過手上僅有的程式碼,來教會我們自己呢?

因此這讓我想到,如果我能夠讀懂 source code,是不是就有機會教會自己更多東西呢?然後在我們使用 Node.js 來做專案的時候,其實就已經把所有套件的程式碼都下載到 node_modules 裡面,根本就是寶庫啊(前提是要看得懂)

從哪裡開始?

程式碼總有個起頭,就像是 Node.js 的 app.js或是 index.js。對一個 Node.js package 來說,通常不是在最外面的 index.js ,就是在 lib 資料夾當中,可以找到 index.js 或其他名稱的檔案。

以 connect-flash 來說,就是 /lib/index.js 。同時也會發現, lib 資料夾裡面也只有兩份檔案(真的是超級小)

輸出什麼?

接下來,可能會想要很快看一下這個 package 最後輸出了什麼東西,好讓我們在自己專案當中可以用

const flash = require('connect-flash')

來引入。於是我們在 /lib/index.js 當中看到

exports = module.exports = require('./flash');

其實整份文件也就只有這一行程式碼!就是引入隔壁的 flash.js 檔案。如果我們進入 flash.js 檔案,首先,可以看到需要引入的套件

var format = require('util').format;
var isArray = require('util').isArray;

接著,很快就可以看到 flash.js 的主體

module.exports = function flash(options) {  
options = options || {};
var safe = (options.unsafe === undefined) ? true : !options.unsafe; …


昨天 (2020.06.02) 更新 macOS 後 (更新內容:macOS Catalina 10.15.5 Supplemental Update),就發現 VScode 開始出現以下擾人的訊息

The default interactive shell is now zsh.
To update your account to use zsh, please run `chsh -s /bin/zsh`.
For more details, please visit https://support.apple.com/kb/HT208050.

然後也同時發現,原本在 .bash_profile 裡面設定的 command 都失效了。在更新之前,沒有看過上面的訊息,操作上也沒有出現任何問題,因此猜測是 macOS 更新的問題。

人生第一次直接面對最新的 macOS 更新災情。

我在 VScode 裡面的 Terminal: Select Default Shell 裡面點選 bash 無法解決問題。

在 MacBook 的 System Preference > Users & Groups > Advanced Options 裡面的 Login shell 重新選擇 /bin/bash 也沒有用。

因此接下來,我

重新安裝 bash

使用 homebrew 重新安裝 bash

brew install bash

將 bash 加入到 shell list 裡面

echo '/usr/local/bin/bash' | sudo tee -a /etc/shells

啟用新的 bash

chsh -s…

在先前的文章 How not to use body-parserBuild our own body-parser 討論過關於如何在 Express 當中使用、不使用 body-parser。

在學習過程中,覺得在 Express 裡面使用 body-parser 好像理所當然。不過昨天在查看 Express 的原始碼的時候,發現在 ./lib/express.js 的最一開始就引入了 body-parser 套件。如果查看 express 的官方文件,也會看到

express.json([options])
[This middleware is available in Express v4.16.0 onwards.]
This is a built-in middleware function in Express. It parses incoming requests with JSON payloads and is based on body-parser.

以及

express.urlencoded([options])
[This middleware is available in Express v4.16.0 onwards.]
This is a built-in middleware function in Express. It parses incoming requests with urlencoded payloads and is based on body-parser.

後來發現,Express 初期其實有內建了許多 middlewares,不過在 Express v4.0.0 (2014 年) 的時候移除了許多的 middlewares,但也許是 body-parser 的角色太常用了,因此在 Express v4.16.0 (2017年) 的時候被加回到 Express 當中成為內建的功能。

因此,我們先前使用 body-parser 做的設定

const express = require('express')
const app = express()
const bodyParser = require('body-parser')
...
app.use(bodyParser.json())
app.use(bodyParser.urlencoded({ extended: true }))

就可以直接用 express 來取代

const express = require('express')
const app = express()
...
app.use(express.json())
app.use(express.urlencoded({ extended: true }))

Reference:


在先前的文章 Node.js & MongoDB with Docker (2) 當中提到,我們可以撰寫內容如下的 Dockerfile 來打包 Node.js app

FROM node:latest
WORKDIR ‘/app’
COPY ./package.json ./app
RUN npm install
COPY . .
EXPOSE 3000
CMD [ “npm”, “start” ]

但這裡會產生一個問題,因為我們只有先複製 package.json 檔案進入 image 文件,如果在 package.json 裡面我們沒有直接指定一個套件版本的話,當開始在 image 裡面跑 npm install 時候,可能就會安裝到不同版本的套件。

最近遇到的問題是因為 handlebars 的版本不如預期,導致畫面無法正常顯示。

如果要確保建立 image 時的套件版本跟在本機開發時「完全一樣」,那麼要記得把 package-lock.json 也給先放進去。更新後的 Dockerfile 如下

FROM node:latest
WORKDIR ‘/app’
COPY ./package*.json ./app
RUN npm install
COPY . .
EXPOSE 3000
CMD [ “npm”, “start” ]

其中 ./package*.json 就同時代表著 ./package.json./package-lock.json 兩份檔案。

TD

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store