跳到主要內容

LeetCode之旅——字母異位詞分組（Group Anagrams）

· 閱讀需 2 分鍾

題目​

給定一個字符串數組，要求將相同字母組成的字符串分組返回。字符串只由小寫字母組成。

示例：

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

思路一​

將輸入的每個字符串拆成字符排序，然後利用Map分組。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map()
    for (let i = 0; i < strs.length; ++i) {
        const key = strs[i].split('').sort().join()
        map.has(key)
            ? map.set(key, map.get(key).concat(strs[i]))
            : map.set(key, [strs[i]])
    }
    return Array.from(map.values())
};

思路二​

由於字符串限定只由小寫字母組成，可以構建一個長為26的“桶”，每一格存儲對應的字母出現的次數。這樣，每個字符串都被轉化為一個這樣的桶。然後把“桶”重新轉為字符串，作為Map的鍵對原字符串數組進行分組。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const list = []
    for (const str of strs) {
        //为每个字符串构造一个“桶”
        const layer = []
        for (const s of str) {
            c = s.charCodeAt(0)
            let value = layer[c - 0x60]
            value = value ? value + 1 : 1
            layer[c - 0x60] = value
        }
        list.push(layer.join(' '))
    }
    //把桶字符串化后作为key对原数组进行分组
    const res = new Map()
    for (let i = 0; i < list.length; ++i) {
        res.has(list[i]) 
            ? res.set(list[i], res.get(list[i]).concat(strs[i]))
            : res.set(list[i], [strs[i]])
    }
    return Array.from(res.values())
};

總結​

思路一更簡潔，但排序可能會消耗更多的時間。思路二利用了桶排序的思想，將排序復雜度降到了線性復雜度。在字符串較長時思路二應該會表現更好。

徹底搞懂JavaScript怪異函數——bind

· 閱讀需 7 分鍾

2020.4.30
事實上存在new.target這個變量，在函數中會指向構造函數。如果不是以new操作符調用的構造函數，new.target為undefined。因此我們可以通過new.target判斷函數是否是new操作符調用。不過各瀏覽器對bind的支持比對new.target要早，所以在bind函數的polyfill中使用new.target可能不太合適。

我們可能遇到過實現bind函數這樣的題目，但似乎並不存在完美模擬原生bind函數的可能。ECMAScript 2015中將bind創建的函數稱為exotic function object（怪異函數對象），這很適宜，因為它的確存在一些“怪異”之處。

在繼續之前我們需要先了解bind函數。這可以參考MDN的解釋：
bind() 方法創建一個新的函數，在 bind() 被調用時，這個新函數的 this 被指定為 bind() 的第一個參數，而其餘參數將作為新函數的參數，供調用時使用。

另外還需要了解new操作符的實現，同樣參考MDN的解釋：

  1. 創建一個空的簡單JavaScript對象（即{}）；
  2. 鏈接該對象（即設置該對象的構造函數）到另一個對象；
  3. 將步驟1新創建的對象作為this的上下文 ；
  4. 如果該函數沒有返回對象，則返回this。

第2步即為對象綁定隱式原型，將對象的__proto__屬性指向構造函數的prototype，而函數默認的prototype擁有constructor屬性指向構造函數，從而實現了所謂的“鏈接構造函數”。

這裡約定一下，bind()方法的實現函數叫bind函數，創建的新函數叫做綁定函數，被封裝的原函數叫做原函數。

bind函數至少有這些特性：

  1. 除非是被new操作符調用，否則原函數執行環境中的this總是為bind函數被調用時傳遞的第一個參數；
  2. 綁定函數的prototype為undefined；
  3. 通過new操作符調用綁定函數時，原函數執行環境的this仍為new操作符創建的新對象，即bind函數的this綁定被忽略；
  4. 通過new操作符調用綁定函數返回的對象是原函數的實例。即： 
    function func() {}
    var fBound = func.bind({});
    var foo = new fBound();
    foo instanceof func; // true

MDN推薦的bind函數的Polyfill如下（部分）：

Function.prototype.bind = function(that) {
    var target = this;  //原函数
    var args = Array.prototype.slice.call(arguments, 1); //绑定参数
    var bound; //绑定函数
    //实际上binder才是绑定函数，bound将其再次包装后返回
    var binder = function () {
        if (this instanceof bound) {
            //如果是通过new操作符调用的绑定函数，则绑定函数执行环境的this指向new操作符创建的新对象，而这个对象的隐式原型指向构造函数bound的prototype
            //new操作符调用，忽略bind函数绑定的this，以实际执行环境this调用原函数
            var result = target.apply(
                this,
                args.concat(arguments)
            );
            if (Object(result) === result) {
                //如果构造函数返回的是一个对象，返回该对象
                return result;
            }
            return this;
        } else {
            //非new操作符调用，使用绑定的this
            return target.apply(
                that,
                args.concat(arguments)
            );
        }
    };
    //计算bind函数调用时提供的绑定参数数量
    var boundLength = Math.max(0, target.length - args.length);
    var boundArgs = [];
    for (var i = 0; i < boundLength; i++) {
        boundArgs.push('$' + i);
    }
    //相当于返回binder。之所以用函数再包一层，应该是为了使函数的length拥有正确的值
    bound = Function('binder', 'return function (' + boundArgs.join(',') + '){ return binder.apply(this,arguments); }')(binder);

    //调整原型链，使绑定函数的实例仍然是能通过原函数的原型链检测（因为绑定函数实例的隐式原型（__proto__）的隐式原型指向原函数的prototype）
    //如果原函数没有prototype，则绑定函数具有默认prototype，且不会被外界访问到（除非通过绑定函数的prototype属性）
    if (target.prototype) {
        //构造一个临时的空函数，防止绑定函数的prototype直接引用原函数的prototype。因为原函数的prototype对外界可见，具有不确定性。如果绑定函数被调用时传递一个隐式原型指向原函数prototype的this参数，直接引用原函数就会造成误判为new操作符调用
        var Empty = function Empty() {};
        //绑定函数.prototype->空函数实例；空函数实例.__proto__->原函数prototype
        //从而实现了，通过new得到的绑定函数实例的原型链上有原函数的prototype（文章开头的特性4），但隐式原型为原函数prototype的对象不是绑定函数的实例，因为绑定函数的原型是一个内部的对象（Empty实例），不太可能作为外部某对象的隐式原型（除非是绑定函数被当作了构造函数[new操作]），从而在前面的binder函数中，根据判断绑定函数执行环境的this是否是绑定函数的实例，正确的判断出是否为new操作符调用的绑定函数
        //当然这里的漏洞是，绑定函数的prototype并不是完全不可访问的，因为绑定函数是公开的，从而绑定函数的prototype也就可访问了。但这一般不会出问题，除非你写一些奇怪的代码（后面有分析到）
        Empty.prototype = target.prototype;
        bound.prototype = new Empty();
        Empty.prototype = null;
    }
    return bound;
};

上面的實現已經接近完美了，幾乎也沒有更好的實現方案了。我們來看看它實現了文章開頭列出的哪些特性。

特性2，綁定函數的prototype為undefined。其實這個很容易實現，但為了實現識別new操作符，只好讓綁定函數擁有prototype。幸運的是，這對實際使用幾乎沒有影響。

特性3，通過new操作符調用綁定函數時忽略bind函數綁定的this。OK，通過new調用時一定可以識別到。

特性4，new操作符調用綁定函數返回的對象是原函數的實例。已實現，雖然原型鏈上多了一個節點，但並不影響原型鏈判斷。
原生bind函數實例的原型鏈：原函數prototype->Object.prototype->undefined
polyfill實現的bind函數實例的原型鏈：內部臨時函數Empty.prototype->原函數prototype->Object.prototype->undefined

特性1就耐人尋味了，顯然關鍵在於對new操作符調用的精確判斷。如果是new操作符調用，顯然綁定函數執行環境的this即綁定函數的實例，會被當做new操作符調用對待（忽略bind函數綁定的this）。但非new操作符調用的情況，是否一定能夠被當作一般情況對待？考慮下面的代碼：

function foo(name) {
    this.name = name;
}
var obj = {};
var bar = foo.bind(obj);
const mock = Object.create(bar.prototype ? bar.prototype : null);
bar.call(mock, 'Jack');
console.log(obj.name);
var alice = new bar('Alice');
console.log(obj.name);
console.log(alice.name);
console.log(mock);

理想的輸出是：

Jack
Jack
Alice
[Object: null prototype]

原生bind函數的輸出符合預測，但polyfill實現的版本輸出：

undefined
undefined
Alice
foo { name: 'Jack' }

bar.call(Object.create(bar.prototype), 'Jack')被當作了new操作符調用。因此綁定函數忽略了綁定的this，而使用了傳入的this參數調用原函數，因此原函數中this.name = name，this指向mock，所以賦值操作發生在mock上而非obj。

bind函數被成為怪異對象，怪異就怪異在其內部機制無法完全用合法的JavaScript邏輯模擬（至少我沒有找到方法）。不過上面的實現已經可用了，最後的不一致行為其實屬於“明知故犯”的怪癖代碼，實際生產活動中完全可以杜絕。

參考​

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Function/bind

https://zhuanlan.zhihu.com/p/38968174

JavaScript微任務與宏任務（瀏覽器）

· 閱讀需 3 分鍾

問題描述​

最近在用Ionic框架（基於Angular），有這麼一個需求：
先調用history.go(-delta)返回到某個頁面，再調用Angular的Router#navigate()導航到新的頁面。

大致代碼如下：

go(delta, url) {
    history.go(delta)
    this.router.navigateByUrl(url, { replaceUrl: true })
}

問題出來了，代碼執行後只返回到了之前的頁面，並沒有正確導航到url參數指定的頁面。

原因大概是，Angular監聽了popstate事件以響應瀏覽器的回退操作。然而瀏覽器的事件觸發是異步的，即history.go(delta)執行後，要等到下一輪事件循環Angular才能捕捉到回退事件，並渲染對應的組件。然而這時router.navigateByUrl()已經執行完畢，因此看到的是回退後的頁面而不是希望導航到的新頁面。

原理分析​

JavaScript的事件循環主要是靠兩個隊列：宏任務（macro task）隊列和微任務（micro task）隊列。瀏覽器按下面的順序執行隊列中的任務：

macro task 1 micro task 1 micro task 2 micro task 3 ...... macro task 2 micro task 1 micro task 2 micro task 3 ......

即，在執行完宏任務後必須執行完當前的所有微任務才能執行下一個宏任務。而瀏覽器環境下，UI事件是宏任務，Promise#then()是微任務。

當go()函數被執行時，history.go(delta)執行後，popstate事件被推入宏任務隊列，然後執行navigationByUrl()。Angular的路由導航也是異步的，但在沒有路由守衛的情況下，navigateByUrl()函數發起的整個工作流程都只是微任務（可以認為是一連串立即被resolve的Promise），所以在下一個宏任務被讀取之前，新頁面的導航已經先於回退操作完成。

go函數執行過程如下：

go history.go() 宏任务队列推入popstate事件 navigateByUrl() 微任务队列推入NavigationStart ... ... 微任务队列弹出NavigationStart ... 微任务队列推入NavigationEnd ... 微任务队列弹出NavigationEnd，新页面导航完成 ... 微任务队列空 ... 宏任务弹出popstate事件，解析history.go()回退到的url 渲染回退到的页面

解決方法​

知道了原理就好解決問題了。只需要等到下一次宏任務再執行新頁面的導航就好了。

go(delta, url) {
    history.go(delta)
    setTimeout(() => {
        this.router.navigateByUrl(url, { replaceUrl: true })
    }, 0)
}

注意，setTimeout和setInterval函數創建的都是宏任務。另外，這裡說的都是瀏覽器環境下的JavaScript，部分說法對nodejs並不適用。

Javascript的in操作符

· 閱讀需 1 分鍾

javascript的in操作符用於判斷某個名稱的屬性是否存在於某個對象的原型鏈中。

語法：

prop in object

prop是string類型或Symbol類型，其他類型會被轉化為string，返回值是布爾值，如果object.prop存在則返回true，否則返回false。

需要注意的是，object必須是一個對象。最容易被誤用的場景是對字符串使用in操作符，這將直接拋出一個異常：

> 'length' in 'mystring'    // Uncaught TypeError: Cannot use 'in' operator to search for 'length' in mystring

如果要判斷字符串是否包含另一個字符串，請使用includes方法（ES6）。

參考：MDN Operator in

.NET 匿名函數引用局部變量導致的問題

· 閱讀需 2 分鍾

問題​

寫C#窗口程序，今天遇到的問題。在工作線程（非UI線程）要操作ListView，因此使用了跨線程調用方式。

for (int i = 0; i < videos.Count; ++i)
{
    this.BeginInvoke(new Action(() =>
    {
        var item = lvwVideos.FindItemWithText(videos[i]);
        if (item != null)
            lvwVideos.Items.Remove(item);
    }));
}

代碼一跑給我拋出了異常，數組下標越界。原因分析如下。

分析​

概念理解錯誤，C#的閉包環境並不會復制用到的局部變量。

.NET對閉包的實現是在編譯階段而不是運行階段，事實上，匿名函數中的變量 i 和 for 循環中的i就是同一個變量，由於函數返回後變量還會被匿名函數使用，它會保存在堆中而不是調用棧——不管這個變量是值類型還是引用類型（如果是引用類型即對象和對象的引用都在堆中）。

因此，循環結束後 i 的值已經超出數組 videos 的下標範圍。而BeginInvoke函數是不等待執行完畢的，因此很可能循環結束而匿名函數還沒有執行完畢。這時匿名函數從堆中取到的 i 已經不是定義匿名函數時 i 的值了。

 
用下面的代碼來說可能更清晰。

static void Main(string[] args)
{
    int i = 1;
    Action action = new Action(() =>
    {
        Console.WriteLine(i);
    });
    ++i;
    action();    // 2
}

action執行的時候訪問的 i 和Main函數中的 i 是同一個，存儲在堆中。

解決​

使用Invoke​

這裡最簡單的解決方法是將BeginInvoke改為Invoke。Invoke()會等待UI線程執行完畢才會繼續執行，能夠保證 i 值不會被工作線程改變。

模仿JS​

將上面的代碼稍作修改：

static void Main(string[] args)
{
    int i = 1;
    Action action = null;
    new Action<int>((n) =>
    {
        action = new Action(()=>
        {
            Console.WriteLine(n);
        });
    })(i);
    ++i;
    action();    // 1
}

這相當於將 i 復制了一遍。

基於Go語言的命令行即時聊天工具——StormChat

· 閱讀需 8 分鍾

簡介​

  前段時間心血來潮想學習最近的明星編程語言Golang。於是想做個聊天小程序實踐一下。程序基於TCP協議通信，更詳細的設計見設計思路。

  用Golang實現了服務端程序，同時代碼抄抄改改做了個Golang客戶端，又由於輸出問題，用C++寫了個Windows控制臺的簡陋的輸出控制庫，於是客戶端在Windows上能看了（不過朋友說很醜>_<）。

  在朋友（@Billows）的鼓勵下，我們決定用C#寫一個客戶端程序，正好他在學習WPF編程，於是界面採用了WPF編寫。我負責後臺數據交互，他負責前臺界面邏輯。

  C#客戶端還使用到了JSON格式化庫Newtonsoft.Json，特此說明。

github地址：https://github.com/mattuylee/stormchat

設計思路​

通信流程​

  1. 發送方（客戶端或者服務器）發送數據包；
  2. 接收方（服務器或者客戶端）處理數據；
  3. 如果需要反饋，接收方發送反饋數據包；
  4. 發送方處理反饋數據（如果有）。

通信數據包結構​

數據通信基於TCP協議，每次通信的數據包應包含【包頭域+數據域】。包頭域總是JSON格式、UTF-8編碼的字符串，數據域由包頭決定，可以為空。通信數據包結構如圖。

stormchat通信規則stormchat通信規則

HEAD（包頭域）至少包含兩個參數：

  • Toekn
  • Operation

Token參數是一次通信的標識文本，由請求方隨機生成，處理方返回數據包的Token參數應和請求方的Token參數一致（如果有返回數據）。

Operation參數指定本次通信的請求。它決定了數據包的其他數據。Operation具體行為定義見這裡。

本來做了設計圖表，不過第一次用starUML，畫了一半才發現完全是鬼畫桃符，沒有掌握正確的作圖方式，也沒什麼熱情重新畫了。因此這裡不展示完整的設計文件了（本來也不完整），上面的鏈接是截取的關鍵部分（才知道starUML可以導出html文檔）。

哦，還有服務器端的數據庫結構，見文件stormchat-server/res/stormchat.sql。

環境配置​

  1. 開發環境​

    服務器端：Windows/Linux Golang 1.11
    客戶端-Go：Windows x64，C++，Golang 1.11
    客戶端-C#：Windows，.NET4.0，WPF，Newtonsoft.Json for .NET4.0

  1. 運行環境​

    服務器端：Linux/Windows, MySQL5.5+/MariaDB10.0+
    客戶端：Windows10 x64（其他平臺沒測試過）

程序配置​

由於懶癌發作，一些參數設置只能在編譯時指定好，沒有運行中指定參數的功能。

Go語言的部分（服務器程序和golang客戶端程序）這塊都在control.go文件中，C#客戶端這邊也沒什麼可配置的，也就是連接服務器的地址和端口。下面列出部分配置參數：

服務器端​

  • serveMode
    服務（後臺）模式。如果此參數為true，日志輸出到str_log_file參數指定的文件中，且Debug()函數將不輸出內容。如果為false，日志輸出和Debug()函數都將直接向控制臺或終端輸出。

  • max_head_length
    最大包頭長度，單位字節，如果包頭長度超過此參數將被拋棄。

  • max_message_length
    最大消息長度，單位字節，如果消息長度超過此參數將被拋棄。

  • max_photo_size
    最大頭像大小，單位字節，如果頭像數據長度超過此參數將被拋棄。

  • timeout_message
    客戶端連接最大數據等待時間，單位秒。如果超過此時間客戶端沒有數據到達則斷開連接（此參數當前未啟用）。

  • str_log_file
    日志文件。僅在serveMode為true時有效。注意，程序並不會自動清理此文件。

  • str_db_conn_str
    MySQL數據庫連接字符串。

客戶端（Go）​

  • server_addr
    服務器地址和端口。

客戶端（C#）​

資源定義在StormChat解決方案，Interact項目的屬性->資源中。

  • RemoteServerAddr
    服務器地址。

  • RemoteServerPort
    服務器端口。

如何編譯​

首先安裝git和golang，這一步請自行解決；

克隆項目到本地：

git clone -b master https://github.com/mattuylee/stormchat.git

假設項目已克隆到本地DIR目錄，命令行切換到stormchat目錄:

cd DIR/stormchat

  1. 服務器端​

切換到服務器端工程目錄：​

cd stormchat-server

克隆mysql操作庫​

Go標準庫裡是沒有數據庫操作的庫的，因此先添加mysql操作庫到項目中。創建目錄sotormchat-server/src/github.com/go-sql-driver/，然後克隆MySQL操作庫：

cd src/github.com/go-sql-driver
git clone https://github.com/go-sql-driver/mysql.git

配置環境變量GOPATH​

Windows下：
如果環境變量GOPATH存在，則在GOPATH後添加 ";DIR/stormchat/stormchat-server"(不含引號，注意分號)，如果不存在添加GOPATH環境變量並將其設置為DIR/stormchat/stormchat-server即可，注意把DIR換成git倉庫所在目錄。
Linux下:
先查看GOPATH環境變量的值，再添加項目目錄到GOPATH：

echo $GOPATH
如果值為空：
export GOPATH=DIR/stormchat/stormchat-server
如果值不為空：
export GOPATH=$GOPATH:DIR/stormchat/stormchat-server

編譯程序​

切換到stormchat-server/src/stormchat/目錄，然後編譯：

cd DIR/stormchat/stormchat-server/src/stormchat
go build

配置MySQL​

登錄mysql：

mysql -uroot -p

為stormchat創建數據庫：

CREATE DATABASE stormchat CHARSET=UTF8;

導入數據庫結構:

SOURCE DIR/stormchat/stormchat-server/res/stormchat.sql;

創建用戶並授權：

CREATE USER 'stormchat'@'localhost' IDENTIFIED BY 'stormchat';
GRANT ALL ON stormchat.* TO 'stormchat'@'localhost';
FLUSH PRIVILEGES;

啟動服務器程序​

Linux下執行下列命令以守護進程運行：

nohup ./stormchat &

Windows請自行探索。

  1. 客戶端-Go​

cd DIR/stormchat/stormchat-client-golang/src
go build

注意，客戶端運行時需要conctrl_x64.dll在運行目錄下，此文件在stormchat-client-golang/res/目錄下。

  1. 客戶端-C#​

Visual Studio 2015以上版本打開項目，直接編譯即可。

注意事項​

  • 沒有設計注冊賬戶的API，只能在強插數據庫。emmmm，這個坑懶得填了。
  • 服務器端的日志文件不會自動清除（反正也沒什麼日志要寫）。
  • 其他的，想到再補充。

目錄結構（主要部分）​

stormchat │ .gitattributes │ .gitignore │ LICENSE //许可证 │ README.md //此帮助文件 │ ├─design //设计文件 │ message.png │ operations.svg │ stormchat.zip //starUML设计文件 │ │ ├─stormchat-server //服务器端工程目录 │ ├─res │ │ stormchat.sql //数据库结构 │ │ │ └─src //代码文件 │ └─stormchat │ control.go │ err.go │ main.go │ message.go │ session-deprecated.go //已不推荐使用的接口 │ session.go │ storm-server.go │ user.go │─stormchat-client-golang //Go客户端工程目录 │ ├─res │ │ conctrl_x64.dll //Winodws控制台输出库 │ │ icon.ico //客户端图标 │ │ │ └─src │ control.go //参数控制 │ main.go │ session.go │ stormchat-client.syso //资源文件（图标资源） │ user.go │ win-console.go //输出控制，调用conctrl库 │ └─stormchat-client-csharp //C#客户端工程目录 ├─Interact //数据交互模块 │ │ Interact.csproj //Visual Studio项目文件 │ │ Newtonsoft.Json.dll //JSON格式化库 │ │ AttrNames.cs //一些字符串常量 │ │ Client.cs //提供给数据表现模块的静态类 │ │ Client-Fields.cs //部分类，定义内部字段 │ │ Client-Handle.cs //部分类，处理服务器数据的方法 │ │ Client-Read.cs //部分类，接收服务器数据的方法 │ │ Client-Send.cs //部分类，向服务器发送数据的方法 │ │ Exception.cs │ │ jsonObject.cs //定义一些内部使用的结构，用于JSON格式化 │ │ Message.cs //定义一些数据结构，用于数据交换 │ │ User.cs //定义用户 │ │ │ └─Properties //项目属性和资源 │ AssemblyInfo.cs │ Resources.Designer.cs │ Resources.resx │ └─StormChatWPF //数据表现和用户交互模块*

使用截圖​

Golang客戶端​

stormchat使用截圖stormchat使用截圖
stormchat使用截圖stormchat使用截圖

源代碼​

github地址：https://github.com/mattuylee/stormchat

AVL樹的C語言實現

· 閱讀需 6 分鍾
// 2018-12-08
// By Mattuy
// AVL树的C语言实现
// 实现对AVL树节点的增删改查
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType; //树的数据域

//定义AVL树
typedef struct SearchTree
{
    int height; //树的深度，空树（NULL）的深度为-1
    DataType value;
    struct SearchTree* left;
    struct SearchTree* right;
} TreeNode, SearchTree;

TreeNode* SingleRotateWithLeft(TreeNode* grandpa);    //左左单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa);    //右右单旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa);    //左右双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa);    //右左双旋转
TreeNode* Remove(SearchTree* tree, TreeNode* node);    //删除节点
void Assign(TreeNode* dest, DataType* value);        //将一个节点的值赋给另外一个节点
TreeNode* Find(SearchTree* tree, DataType value);    //查找节点

//获取树高度
int getHeight(SearchTree* tree);
//删除同时有左右孩子的节点时寻找子合适的子节点来顶替被删除节点
TreeNode* findExtreamNode(TreeNode* node);
//中序遍历输出AVL树
void output(SearchTree* tree);

//左左单旋转
TreeNode* SingleRotateWithLeft(TreeNode* grandpa)
{
    //将祖父变为父亲的右儿子，父亲原来的右儿子变为祖父的左儿子（祖父原来的左儿子就是父亲，关系已断开）
    TreeNode* parent = grandpa->left;
    grandpa->left = parent->right;
    parent->right = grandpa;
    //新的关系是，原来的孙子和祖父变成父亲的左右儿子（孙子位置没动）。
    //原祖父(现父亲右儿子)的深度取决于原父亲的右儿子和原祖父的右儿子
    //父亲的深度取决于孙子和祖父（现右儿子），因此须先计算祖父（右儿子）的深度
    grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
    parent->height = max(getHeight(parent->left), grandpa->height) + 1;
    //返回新的根节点（原来是祖父，现在是父亲）
    return parent;
}
//右右单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa)
{
    TreeNode* parent = grandpa->right;
    grandpa->right = parent->left;
    parent->left = grandpa;
    grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
    parent->height = max(getHeight(parent->right), grandpa->height) + 1;
    return parent;
}
//左右双旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa)
{
    grandpa->left = SingleRotateWithRight(grandpa->left);
    return SingleRotateWithLeft(grandpa);
}
//右左双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa)
{
    grandpa->right = SingleRotateWithLeft(grandpa->right);
    return SingleRotateWithRight(grandpa);
}

//插入节点，返回插入后的根节点
TreeNode* Insert(SearchTree* tree, DataType value)
{
    if (tree == NULL)
    {
        TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
        if (!temp)
        {
            return NULL;
        } //申请内存失败
        temp->left = temp->right = NULL;
        temp->value = value;
        temp->height = 0;
        return temp;
    } //插入新节点

    if (value < tree->value)
    {
        tree->left = Insert(tree->left, value);
        //当平衡被破坏时调整
        if (getHeight(tree->left) - getHeight(tree->right) == 2)
        {
            //插入的节点在哪边就旋转哪边
            if (value < tree->left->value)
                tree = SingleRotateWithLeft(tree);
            else
                tree = DoubleRotateWithLeft(tree);
        }
    }
    else if (value > tree->value)
    {
        tree->right = Insert(tree->right, value);
        if (getHeight(tree->right) - getHeight(tree->left) == 2)
        {
            if (value > tree->right->value)
                tree = SingleRotateWithRight(tree);
            else
                tree = DoubleRotateWithRight(tree);
        }
    }
    else
        return NULL; //不允许插入值相同的节点
    tree->height = max(getHeight(tree-> left), getHeight(tree->right)) + 1;
    return tree;
}

//删除节点
TreeNode* Remove(SearchTree* tree, TreeNode* node)
{
    if (!tree || !node)
        return NULL;
    if (node == tree)
    {
        if (tree->left && tree->right)
        {
            //找到一个合适的子节点来替换被删除的节点
            TreeNode* leaf = findExtreamNode(tree);
            //记录是在左子树找的子节点还是右子树
            bool doesLeft = true;
            if (leaf->value > tree->value)
                doesLeft = false;
            //用子节点的值替代要删除节点的值
            Assign(tree, leaf->value);
            //删除子节点。因为现在tree节点的值和子节点一样，所以不能直接传tree节点作为参数
            if (doesLeft)
                tree->left = Remove(tree->left, leaf);
            else
                tree->right = Remove(tree->right, leaf);
            tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
            return tree;
        } //被删除的节点有两个儿子
        else if (!tree->left && !tree->right)
        {
            free(tree);
            return NULL;
        } //被删除的是叶子节点
        else if (tree->left || tree->right)
        {
            TreeNode* temp = tree->left ? tree->left : tree->right;
            free(tree);
            return temp;
        } //被删除的节点只有一个儿子
    } //当前节点为待删除节点
    else if(node->value > tree->value)
    {
        tree->right = Remove(tree->right, node);
        //如果删除节点后破坏平衡，调整以重新平衡
        //从右子树删除节点后进行左旋转
        //如果左孩子有左孩子则进行单旋转，否则进行双旋转
        if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
            tree = tree->left->left ? SingleRotateWithLeft(tree) : DoubleRotateWithLeft(tree);
    } //待删除节点在右子树
    else
    {
        tree->left = Remove(tree->left, node);
        //从左子树删除节点后进行右旋转
        //如果右孩子有右孩子则进行单旋转，否则进行双旋转
        if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
            tree = tree->right->right ? SingleRotateWithRight(tree) : DoubleRotateWithRight(tree);
    } //待删除节点在左子树
    tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
    return tree;
}

//为节点赋值
void Assign(TreeNode* dest, DataType* value)
{
    dest->value = value;
}

//查找
TreeNode* Find(SearchTree* tree, DataType value)
{
    TreeNode* cur = tree;
    while (cur != NULL)
    {
        if (cur->value == value)
            break;
        cur = value > cur->value ? cur->right : cur->left;
    }
    return cur;
}

//获取树高度
int getHeight(SearchTree* tree)
{
    return tree ? tree->height : -1;
}
/**
 * 当被删除节点有左右孩子时找出左子树的最右节点或右子树的最左节点。务必保证传入的参数为被搜索的节点，
 *     函数将根据其左右子树的深度来决定返回左孩子的最右子树还是右孩子的最左子树。
 * 此函数仅应被Remove函数调用
 */
TreeNode* findExtreamNode(TreeNode* node)
{
    if (node->right->height > node->left->height)
    {
        TreeNode* cur = node->right;
        while (cur->left)
            cur = cur->left;
        return cur;
    }
    else
    {
        TreeNode* cur = node->left;
        while (cur->right)
        {
            cur = cur->right;
        }
        return cur;
    }
}
//中序遍历输出
void output(SearchTree* tree)
{
    if (!tree)    return;
    output(tree->left);
    printf("value = %d, height = %d\n", tree->value, tree->height);
    output(tree->right);
}

//测试
int main()
{
    SearchTree* tree = NULL;
    for (int i = 1; i <= 8; i++)
        tree = Insert(tree, i);
    tree = Remove(tree, Find(tree, 6));
    output(tree);
    system("pause");
}

LeetCode之旅——Two Sum，哈希表的應用

· 閱讀需 2 分鍾

今天做的題叫Two Sum，簡單題，給定一個整形數組和一個整數target，存在唯一的兩個成員相加等於target，要求返回這兩個成員的位置。

示例：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解決方案​

1. 暴力算法​

最簡單的當然是暴力算法，一個嵌套的for循環搞定。標準答案如下：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
}

2. 哈希表​

第一種方法的時間復雜度是O(n2)，空間復雜度O(1)。另一個更快的解決方案是利用哈希表。遍歷數組並將成員其插入哈希表，再查詢[target - 成員]是否在表中（不能等於自身），如果在則結果已產生。至於是一次遍歷實現還是兩次遍歷個人認為區別不大。
標準答案如下：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
}

總結​

哈希表最大的優勢在於查詢。理想的哈希表可以以O(1)的時間復雜度處理查詢。此題的微妙之處在於，需要將數組索引作為表的值而數組成員作為鍵。而思維慣性可能讓人一時轉不過彎。

哈希表雖然高效，但卻不是任何時候都適用。它的空間復雜度是O(n)，但其常數因子並不小，可能花費甚至浪費很大的空間。另外衝突處理也會一定程度降低哈希表的性能。

因此哈希表並不總是比暴力解法好。如果你的空間足夠，數據量大，查詢頻度高，我認為使用哈希表是合理的選擇。

C++實現貪吃蛇

· 閱讀需 4 分鍾

注意，編譯前源文件字符編碼必須為GB2312/GBK。否則填充字符█會出現異常。

編譯時需要指定按C++11標準編譯，為了支持結構體字面量的語法。
g++ -std=c++11 -o gluttonous-snake.exe ./source.cpp

代碼​

#include <cstdlib>
#include <conio.h>
#include <deque>
#include <iostream>
#include <time.h>
#include <windows.h>
//定义一次步进
typedef struct {
    //是否纵向移动
    bool virticle = false;
    //移动步长
    int offset = 0;
}Step;
//定义'成长礼包'类型
enum GiftType {
    //礼物，增加长度
    GIFT_GIFT = FOREGROUND_GREEN,
    //陷阱，减少长度
    GIFT_TRAP = FOREGROUND_GREEN | FOREGROUND_BLUE,
    //利剑，直接死亡
    GIFT_SWORD = FOREGROUND_RED
};
//定义移动区域。窗口宽度应为width的两倍，因为ansi字符宽度仅高度的1/2。
#define FACTORY_WIDTH 64
#define FACTORY_HEIGHT 36

//定义蛇身颜色
#define SNAKE_BODY_COLOR (FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE)
using namespace std;
//控制台输出句柄
HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
//蛇身数据容器。
deque<COORD> snakeBody;
//死亡标记
bool dead = false;
//'成长礼包'
COORD gift, trap, sword;


//判定点是否在蛇身上
bool inSnake(COORD point) {
    if (snakeBody.size() == 0)
        return false;
    deque<COORD>::iterator iter = snakeBody.begin();
    while (iter != snakeBody.end()) {
        if (point.X == (*iter).X && point.Y == (*iter).Y)
            return true;
        ++iter;
    }
    return false;
}
//生成'成长礼包'
COORD createGift(GiftType color) {
    //统计递归调用次数
    static int count = 0;
    ++count;
    COORD point;
    srand(rand());
    point.X = rand() % FACTORY_WIDTH * 2;
    srand(rand());
    point.Y = rand() % FACTORY_HEIGHT;
    if (inSnake(point)) {
        return createGift(color);
    }
    else {
        SetConsoleCursorPosition(hOutput, point);
        SetConsoleTextAttribute(hOutput, color);
        cout << "█";
        SetConsoleTextAttribute(hOutput, SNAKE_BODY_COLOR);
        dead = count > 12 ? true : false;
        count = 0;
        return point;
    }//连礼包都没地方放了，死了算了
}
//初始化
void init() {
    system("cls");
    snakeBody.clear();
    srand(time(NULL));
    snakeBody.push_front({ 0, 0 });
    snakeBody.push_front({ 2, 0 });
    snakeBody.push_front({ 4, 0 });
    deque<COORD>::iterator iter = snakeBody.begin();
    while (iter != snakeBody.end()) {
        SetConsoleCursorPosition(hOutput, *iter);
        cout << "█";
        ++iter;
    }
    sword = createGift(GIFT_SWORD);
    trap = createGift(GIFT_TRAP);
    gift = createGift(GIFT_GIFT);
}
//步进
void stepOnece(Step step) {
    COORD head = snakeBody.front();
    (step.virticle ? head.Y : head.X) += step.offset;
    //死亡
    if (inSnake(head)
        || snakeBody.size() == 0
        || (head.X == sword.X && head.Y == sword.Y)
        || head.X < 0 || head.X >= FACTORY_WIDTH * 2
        || head.Y < 0 || head.Y >= FACTORY_HEIGHT) {
        dead = true;
        return;
    }
    snakeBody.push_front(head);
    SetConsoleCursorPosition(hOutput, head);
    cout << "█";

    int count;
    if (head.X == trap.X && head.Y == trap.Y) {
        count = 2;
        trap = createGift(GIFT_TRAP);
    }//陷阱，变短
    else if (head.X == gift.X && head.Y == gift.Y) {
        count = 0;
        gift = createGift(GIFT_GIFT);
    }//礼物，增长
    else
        count = 1;
    for (int i = 0; i < count; i++) {
        COORD back = snakeBody.back();
        SetConsoleCursorPosition(hOutput, back);
        printf("  ");
        snakeBody.pop_back();
        if (snakeBody.size() == 0) {
            dead = true;
            break;
        }
    }
}
//控制循环
void gameLoop() {
    Step curStep = { false, 2 };
    Step step = curStep;
    while (!dead) {
        for (int i = 0; i < 200; i++) {
            Sleep(1);
            if (!_kbhit())
                continue;
            char cmd;
            bool breakdown = true;
            cmd = _getch();
            switch (cmd) {
            case 'w':
                step.virticle = true;
                step.offset = -1;
                break;
            case 's':
                step.virticle = true;
                step.offset = 1;
                break;
            case 'a':
                step.virticle = false;
                step.offset = -2;
                break;
            case 'd':
                step.virticle = false;
                step.offset = 2;
                break;
            default:
                breakdown = false;
                break;
            }
            //禁止当前方向反方向步进
            if (step.virticle == curStep.virticle && step.offset * curStep.offset < 0)
                continue;
            else
                curStep = step;
            if (breakdown)
                break;
        }
        stepOnece(curStep);
    }
}
int main() {
    //设置缓冲区大小
    SMALL_RECT rect = { 0, 0, 10, 10 };
    SetConsoleWindowInfo(hOutput, true, &rect);
    SetConsoleScreenBufferSize(hOutput, { FACTORY_WIDTH * 2, FACTORY_HEIGHT });
    //设置窗口大小
    rect = { 0, 0, FACTORY_WIDTH * 2 - 1, FACTORY_HEIGHT - 1 };
    SetConsoleWindowInfo(hOutput, true, &rect);
    //设置窗口样式
    SetConsoleTextAttribute(hOutput, SNAKE_BODY_COLOR);
    CONSOLE_CURSOR_INFO cursorInfo = { 1, false };
    SetConsoleCursorInfo(hOutput, &cursorInfo);
    //规则介绍
    cout << "使用W、S、A、D控制方向，吃到绿色礼包长度增加，吃到黄色礼包时长度减短，"\
        "吃到红色礼包直接死亡。您也可以按CTRL + C退出游戏。按任意键开始游戏。" << endl;
    system("pause");
    //开始游戏
    while (true) {
        init();
        gameLoop();
        system("cls");
        SetConsoleCursorPosition(hOutput, { 0, 0 });
        printf("You has dead! Retry? (y/n)");
        char cmd;
        cin >> cmd;
        if (cmd != 'y')
            break;
        else
            dead = false;
    }
}

逆波蘭法-算術表達式語法分析C++

· 閱讀需 3 分鍾

逆波蘭表達式的C++實現。算術表達式求值，支持加減乘除和冪運算，支持圓括號改變優先級。

//后缀表达式练习
//2018-09-20
#include <stack>
#include <iostream>
#include <cstdlib>
#include <string>
#include <math.h>
using namespace std;
//定义优先级
enum Priority {
    PRI_IGNORE,//无效字符，忽略
    PRI_NUMBER,//操作数
    PRI_PLUS,//加减
    PRI_DIVIDE,//乘除
    PRI_POWER,//幂
    PRI_LEFT_PAR,//左圆括号
    PRI_RIGTHT_PAR,//右圆括号
};
//取操作符优先级
Priority getPriority(char symbol) {
    if ((symbol >= '0' && symbol <= '9') || symbol == '.')
        return PRI_NUMBER;
    else if (symbol == '+' || symbol == '-')
        return PRI_PLUS;
    else if (symbol == '*' || symbol == '/')
        return PRI_DIVIDE;
    else if (symbol == '^')
        return PRI_POWER;
    else if (symbol == '(')
        return PRI_LEFT_PAR;
    else if (symbol == ')')
        return PRI_RIGTHT_PAR;
    else
        return PRI_IGNORE;
}
//中缀表达式转后缀表达式
string toSufixExpression(string express) {
    stack<char> operendStack;//操作符暂存栈
    string output;//输出后缀表达式
    //上一操作符的优先级，如果当前处理的操作符优先级低于它则前操作符出栈
    Priority lastPriority = PRI_NUMBER;
    string::iterator iter = express.begin();
    for (; iter != express.end(); ++iter) {
        Priority priority = getPriority(*iter);
        switch (priority) {
        case PRI_IGNORE:
        default:
            continue;
        case PRI_NUMBER:
            output.push_back(*iter);
            break;
        case PRI_PLUS:
        case PRI_DIVIDE:
        case PRI_POWER:
        case PRI_LEFT_PAR:
            //遇到符号向前追加间隔符
            output.push_back(' ');
            while (operendStack.size()) {
                if (getPriority(operendStack.top()) < priority || operendStack.top() == '(')
                    break;
                output.push_back(operendStack.top());
                operendStack.pop();
            }
            lastPriority = priority;
            operendStack.push(*iter);
            break;
        case PRI_RIGTHT_PAR:
            while (operendStack.size()) {
                if (operendStack.top() != '(') {
                    output.push_back(operendStack.top());
                    operendStack.pop();
                }
                else {
                    operendStack.pop();
                    break;
                }
            }
            break;
        }
    }
    //处理完毕，剩余操作符出栈
    while (operendStack.size()) {
        output.push_back(operendStack.top());
        operendStack.pop();
    }
    return output;
}
//计算后缀表达式
double caculate(string express) {
    stack<double> calcStack;//计算存储栈
    string::iterator iter = express.begin();
    while (iter != express.end()) {
        //字符串转整形，并压入栈
        if (*iter >= '0' && *iter <= '9') {
            string number;
            do {
                number.push_back(*iter);
                ++iter;
            } while ((*iter >= '0' && *iter <= '9') || *iter == '.');
            calcStack.push(atoi(number.c_str()));
            continue;
        }
        //间隔符
        if (*iter == ' ') {
            ++iter;
            continue;
        }
        //操作符，执行运算
        if (calcStack.size() < 2)
            return 0;
        double operandOne = calcStack.top();
        calcStack.pop();
        double operandTwo = calcStack.top();
        calcStack.pop();
        switch (*iter++) {
        case '+':
            calcStack.push(operandTwo + operandOne);
            break;
        case '-':
            calcStack.push(operandTwo - operandOne);
            break;
        case '*':
            calcStack.push(operandTwo * operandOne);
            break;
        case '/':
            calcStack.push(operandTwo / operandOne);
            break;
        case '^':
            calcStack.push(pow(operandTwo, operandOne));
            break;
        default:
            calcStack.push(operandTwo);
            calcStack.push(operandOne);
            break;
        }
    }
    if (calcStack.size() == 1)
        return calcStack.top();
    return 0;
}

int main() {
    cout << "Please enter an expression:" << endl;
    string express;//表达式
    getline(cin, express);
    if (express.empty()) {
        cout << "empty express.\n";
        return 0;
    }
    string output = toSufixExpression(express);
    cout << caculate(output) << endl;
    system("pause");
    return 0;
}