點擊藍字「dotNET匠人」關注我喲
加個「星標★」,每日 7:15,好文必達!
什麼要刷LeetCode大家都知道,很多對算法要求高一點的軟體公司,比如美國的FLAGM (Facebook、LinkedIn、Amazon/Apple、Google、Microsoft),或國內大廠BAT、TMD、華為,以及國內新興的 AI 公司等等,都對算法水平有所要求。據悉知名遊戲公司的算法崗收入很高,相應的對算法要求也比較高。而這些公司,大多數會以 LeetCode 中的題目或基於 LeetCode 改進後的自家算法題庫來考察候選人。
於是想進入上述大廠,定期做 LeetCode 題目很有必要。即使沒打算進這些大廠,堅持做LeetCode,個人的算法水平、編程能力也會有較大提升。本文主要介紹 .NET 開發者如何入手刷 LeetCode 面試題。
刷LeetCode有哪些好處?計算機中有很多抽象的數據結構,比如: List、Stack(棧)、Linked List(鍊表)、Hash Table(哈希表)、Heap(堆)、Tree等等,而LeetCode 上的大量高質量算法題基本上涵蓋了所有這些數據結構的應用。怎麼將這些題抽象成數學模型,轉化為具體數據結構的應用,則是我們需要提升的地方,而這恰恰幫我們極大地提升了自己的抽象思維水平。
每一個算法實現都有其相應的時間複雜度和空間複雜度,而 LeetCode中的一些題對時間複雜度有明確要求,有的要求O(n)即可,有的則要求O(1)才行,否則代碼無法 AC(Accepted)。
比如你上學時用 C++ 刷一遍,工作後再用 C# 刷一遍,最後再用 Python 刷一遍,那麼你對各個語言的代碼量和性能都會有更深地體會,也會知道用哪一種語言具體該怎麼寫出更簡短、更優雅的代碼。
LeetCode vs 傳統的 OJ中學有NOI信息競賽,大學有ACM算法競賽,按理說應該都有各自的 OJ,這兩類 OJ 不是業內公司的真實面試題。NOI了解的不是特別多,據說以前用 Pascal 語言解題。相應地,我知道有個中學生比較多的 OJ 叫洛谷(https://www.luogu.org/)。而ACM有不少免費 OJ,國內就有一些ACM OJ,比如POJ(北大的)、HDU OJ(杭電的)、ZOJ(浙大的)、HUST OJ(華科的)。另外,還有些職場用的OJ,比如牛客網OJ、浙江大學電腦程式設計能力考試 PTA(拼題A,原全稱為Programming Ability Test,簡稱PAT) 等等。
而國外有 UVAoj http://uva.onlinejudge.org/,
TopCoder (http://www.topcoder.com/tc)等等,另外還記得微軟的校招筆試用的 OJ 是 hihoCoder http://hihocoder.com/。
而 LeetCode 較上述 OJ 而言有如下優勢:
傳統的 OJ 對用戶代碼的判定狀態有如下幾種:
1、Accepted. ——通過!(AC)
2、Wrong Answer.——答案錯。(WA)
3、RunTime Error.——程序運行出錯,意外終止等。(RTE)
4、Time Limit Exceeded. ——超時。程序沒在規定時間內出答案。(TLE)
5、Presentation Error. ——格式錯。程序沒按規定的格式輸出答案。(PE)
6、Memory Limit Exceeded. ——超內存。程序沒在規定空間內出答案。(MLE)
7、Compile Error. ——編譯錯。程序編譯不過。(CE)
而在 LeetCode 中,應該是沒有第5種狀態的。
刷 OJ 時,大家還會常用兩個詞:
刷題時大家的一致感覺是: AC一時爽,一直AC一直爽!
LeetCode刷題時的心態建設在本文開頭,我們提到了很多行內名廠需要考察與 LeetCode 難度難度相當的算法題。但需要注意的是,面試時很可能面試官會對題目的解題要求進行另外的調整,比如要求更低的時間複雜度、更低的空間複雜度之類的,所以呢,面試算法題很重要的是要和面試官保持即時的溝通,而不是一上來就埋頭寫代碼。
有的人刷 LeetCode 中 難度為 Easy 和 Medium 的題3遍左右後成功拿到微軟Offer,還是Special Offer!也有人刷完LeetCode很多遍,也沒能拿到大廠Offer呢。
更多算法題面試要點請參看一畝三分地論壇站長Warald 的文章 Leetcode刷題五遍還沒offer!舉例分析為什麼找工作光刷題不夠 .
C#如何刷遍LeetCode在 LeetCode 中提交 C# 代碼有兩種主流方式,下面以 LeetCode 中的136號題為例來說明。
該題的中文版網址為: https://leetcode-cn.com/problems/single-number/,將代碼語言選為C#,則默認的接口代碼如下:
public class Solution {
public int SingleNumber(int[] nums) {
}
}
如果需要本地測試,只需在該類裡面加入 主函數即可,然後在 主函數中調用相應的函數,debug,觀察調用時的各項值。
使用LeetCode的"執行代碼"案例可以測試當前的測試用例,而界面上的"測試用例"可以自行修改。
如果此時對代碼比較有信心,可以直接點"Test"按鈕左側的"Submit"按鈕提交代碼了。
如果不幸,部分Test case無法通過,則可進行本地debug,下面是我給出的樣例代碼:
using System;
using System.Collections.Generic;
using System.Linq;
namespace leetcoce136
{
public class Solution
{
public int SingleNumber(int[] nums)
{
int res = 0;
Dictionary<int, int> dict = new Dictionary<int, int>();
foreach (var num in nums)
{
if (!dict.ContainsKey(num))
{
dict.Add(num, 1);
}
else
dict[num]++;
}
res = dict.FirstOrDefault(kv => kv.Value == 1).Key;
return res;
}
public static void Main()
{
var sol = new Solution();
int[] input = { 4, 1, 2, 1, 2 };
System.Console.WriteLine(sol.SingleNumber(input));
}
}
}
選項2:VS Code本地Debug + 在LeetCode插件中驗證和提交安裝C#相關插件首先微軟官方 OmniSharp 團隊開發的 C# 插件是必須安裝的,
另外再安裝一下第3個插件,則對C#代碼基本的智能感知,關鍵字高亮等功能就可以順利使用了。
先安裝 .NET Core SDK 3.0,到官網 https://dotnet.microsoft.com/download 下載安裝即可。
首先在 VS Code下方的Terminal窗口中依次輸入如下命令:
$ dotnet --version
3.0.100-preview5-011362
$ cd d:/Coding/csLeetcode
$ dotnet new console -o "leetcoce136"
這裡假設你以及有文件夾 d:/Coding/csLeetcode.
在VS Code中Debug C#這裡我們直接使用剛才帶主函數的本地測試代碼吧,將代碼先拿過來,然後按 F5,選擇 .NETCore,具體操作見下圖:
在配置文件 launch.json中,我們需要選擇類型的是 .NET:Launch.NETCoreConsoleApp.
launch.json的完整配置過程如下:
接下來我們需要修改其中的屬性值 program:
默認的值為:
"program":"${workspaceFolder}/bin/Debug/<target-framework>/<project-name.dll>"
其中的 <target-framework>是指目標運行環境,其具體版本可以在上面還原的項目文件 leetcoce136.csproj 中看到:
而我們的項目名,即 project-name是 leetcode136,於是 program的具體值為:
"${workspaceFolder}/bin/Debug/netcoreapp3.0/leetcode136.dll"
安裝 LeetCode 插件在擴展中搜索安裝作者是 ShengChen的 LeetCode插件。
然後點擊左下角的LeetCode Logo進行登錄:
推薦選擇 力扣leetcode-cn.com:
在國內使用,網絡相對穩定。
然後在 LeetCode 插件的配置文檔中將 leetcode.defaultLanguage設置為 csharp。
其完整操作過程如下:
接下來就可以愉快地使用LeetCode刷題了。
我們在左側題庫列表中選擇 All,找到剛才的例子No.136,雙擊問題標題,可以看到問題描述:
如果需要提交代碼,只需點右下角的"Code Now"按鈕。
當我們寫完代碼後,可以點擊裡面的代碼下方的 Test 按鈕進行測試,這便等價於網頁版的按鈕"執行代碼"。
點 Test後有圖中3種選項,我一般是使用第一個。除非部分 Test Case 無法通過,才會使用第2個或第3個選項。
此時呢,如果對代碼比較有信心,可以直接點"Test"按鈕左側的"Submit"按鈕提交代碼了。
關於VS Code的LeetCode 插件,文章 LeetCode for VS Code: 春招 Offer 收割利器 中有更詳細的說明。
接下來的 LeetCode面試題系列連載 中每篇文章將會提供解題思路、算法複雜度的簡要分析、已AC代碼、提交的答案排名等,敬請期待。
參考資料:
.NET Core and Visual Studio Code
https://code.visualstudio.com/docs/languages/dotnet
使用VS Code 開發.NET CORE 程序指南
https://www.cnblogs.com/xboo/p/11431222.html
作者簡介:Bravo Yeung,計算機碩士,知乎乾貨答主(獲73K 贊同, 34K 感謝, 210K 收藏)。曾在國內 Top3網際網路視頻直播公司短暫工作過,後加入一家外企做軟體開發至今。歡迎在留言區留下你的觀點,一起討論提高。如果今天的文章讓你有新的啟發,學習能力的提升上有新的認識,歡迎轉發分享給更多人。
歡迎各位讀者加入 .NET技術交流群,在公眾號後臺回復「加群」或者「學習」即可。
微信後臺回復「ebook」,給你:一份全網最強的電子書下載指南。回復「運營工具箱」,給你:一整套運營工具,學會後極大地提到運營效率!你點的每一個"在看",
我都當成了喜歡!