數(shù)組問題
數(shù)組是最常用的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)呈驶，它將元素保存在連續(xù)的內(nèi)存中。它也是面試最喜歡的問題之一疫鹊，在代碼面試中你會(huì)經(jīng)常聽到很多關(guān)于數(shù)組的問題袖瞻，例如，數(shù)組的反轉(zhuǎn)拆吆、數(shù)組的排序或者查找數(shù)組中的一個(gè)元素聋迎。
數(shù)組結(jié)構(gòu)的一個(gè)關(guān)鍵優(yōu)點(diǎn)是在知道索引的情況能夠以 O(1) 的復(fù)雜度找到一個(gè)元素。但是增加或者刪除一個(gè)元素是很慢的枣耀，因?yàn)橐坏﹦?chuàng)建了一個(gè)數(shù)組霉晕，你就不能改變它的大小了。
為了創(chuàng)建一個(gè)更長(zhǎng)或者更短的數(shù)組捞奕，你需要?jiǎng)?chuàng)建一個(gè)新的數(shù)組牺堰，然后將所有元素從舊數(shù)組中復(fù)制到新數(shù)組中。
解決數(shù)組問題的關(guān)鍵是颅围，你要對(duì)數(shù)組這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)深刻的認(rèn)識(shí)伟葫，同時(shí)還要了解基本的程序流程如循環(huán)、遞歸以及基本的操作符院促。
下面是一些經(jīng)常問到和數(shù)組相關(guān)的面試題扒俯，你可以拿來練習(xí)：
1、在一個(gè)給定的從1到100的整型數(shù)組中一疯，如何快速找到缺失的數(shù)字撼玄？
2、如何找到一個(gè)給定的整型數(shù)組中的重復(fù)數(shù)字墩邀？
3掌猛、在一個(gè)未排序的整型數(shù)組中，如何找到最大和最小的數(shù)字眉睹？
4荔茬、在一個(gè)整型數(shù)組中，如何找到一個(gè)所有成對(duì)的數(shù)字，滿足它們的和等于一個(gè)給定的數(shù)字碰酝？
5余爆、如果一個(gè)數(shù)組包含多個(gè)重復(fù)元素，如何找到這些重復(fù)的數(shù)字孔飒？
6灌闺、用 Java 實(shí)現(xiàn)從一個(gè)給定數(shù)組中刪除重復(fù)元素？
7坏瞄、如何利用快速排序?qū)σ粋€(gè)整型數(shù)組進(jìn)行排序桂对？
8、如何從一個(gè)數(shù)組中刪除重復(fù)元素鸠匀？
9蕉斜、用 Java 實(shí)現(xiàn)數(shù)組反轉(zhuǎn)？
10缀棍、如何不借助庫實(shí)現(xiàn)從數(shù)組中刪除重復(fù)元素宅此？
鏈表問題
鏈表是另外一個(gè)常見的數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)組結(jié)構(gòu)是一個(gè)補(bǔ)充爬范。和數(shù)組類似父腕，它也是一個(gè)線性的數(shù)據(jù)結(jié)構(gòu)，以線性方式存儲(chǔ)元素坦敌。
不過和數(shù)組不同的是侣诵，鏈表的元素不是存儲(chǔ)在連續(xù)位置中，而是分散在各個(gè)內(nèi)存中的各個(gè)位置狱窘，通過節(jié)點(diǎn)鏈接起來杜顺。一個(gè)鏈表就是一個(gè)包含了下個(gè)節(jié)點(diǎn)內(nèi)存地址的節(jié)點(diǎn)列表。
基于這種結(jié)構(gòu)蘸炸，可以很容易實(shí)現(xiàn)鏈表中元素的添加和刪除躬络，因?yàn)橹恍枰淖児?jié)點(diǎn)的指向而無需創(chuàng)建一個(gè)新的數(shù)組。不過鏈表中的查找是相對(duì)困難的搭儒，在一個(gè)單向鏈表中需要花費(fèi) O(n) 的時(shí)間代價(jià)來查找一個(gè)元素穷当。
鏈表有幾種不同的形式。首先是單向鏈表淹禾，在這個(gè)結(jié)構(gòu)你只能向一個(gè)方向遍歷（向前或者反轉(zhuǎn)）馁菜；其次是雙向鏈表，你可以雙向遍歷（向前或者向后）铃岔；最后是環(huán)形鏈表汪疮，組成一個(gè)環(huán)的形式。
要解決鏈表問題毁习，你就必須了解遞歸的相關(guān)知識(shí)智嚷，因?yàn)殒湵硎且环N遞歸的數(shù)據(jù)結(jié)構(gòu)。如果你從鏈表中去掉一個(gè)節(jié)點(diǎn), 剩下的數(shù)據(jù)結(jié)構(gòu)仍然是鏈表纺且，因此, 許多鏈表問題有比遍歷更簡(jiǎn)單的遞歸解決方案.
下面是一些最常見和流行的鏈表面試問題
1盏道、在一次遍歷中，怎樣發(fā)現(xiàn)單個(gè)鏈表的中間元素?
2载碌、怎樣驗(yàn)證給定的鏈表是環(huán)形的? 怎樣發(fā)現(xiàn)這個(gè)環(huán)的起始節(jié)點(diǎn)?
3猜嘱、怎樣翻轉(zhuǎn)鏈表?
4衅枫、不使用遞歸，怎樣反轉(zhuǎn)單個(gè)鏈表?
5泉坐、在未排序鏈表中为鳄，怎樣移除重復(fù)的節(jié)點(diǎn)?
6裳仆、怎樣找出單個(gè)鏈表的長(zhǎng)度?
7腕让、從單個(gè)鏈表的結(jié)尾處，怎樣找出鏈表的第三個(gè)節(jié)點(diǎn)?
8歧斟、怎樣使用棧計(jì)算兩個(gè)鏈表的和?
字符串相關(guān)問題
與數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)一起纯丸，字符串是編程工作面試中的另一個(gè)熱門話題。我從未參加過沒有問過基于字符串相關(guān)問題的編碼面試静袖。
字符串的一個(gè)優(yōu)勢(shì)在于觉鼻，如果你了解數(shù)組，你可以很容易地解決基于字符串的問題队橙，因?yàn)樽址畠H僅是一個(gè)字符數(shù)組坠陈。
因此，在解決基于數(shù)組的編程問題中所學(xué)到的所有技術(shù)也可用于解決字符串編程問題捐康。
以下是編程求職面試中常見的字符串編程問題：
1仇矾、如何輸出字符串中的重復(fù)字符？
2解总、如何判斷兩個(gè)字符串是否互為回文贮匕？
3、如何從字符串中輸出第一個(gè)不重復(fù)字符花枫？
4刻盐、如何使用遞歸實(shí)現(xiàn)字符串反轉(zhuǎn)?
5、如何檢查字符僅包含數(shù)字字符劳翰？
6敦锌、如何在字符串中找到重復(fù)字符？
7佳簸、如何對(duì)給定字符串中的元音及輔音進(jìn)行計(jì)數(shù)乙墙？
8、如何計(jì)算給定字符傳中特定字符出現(xiàn)的次數(shù)溺蕉？
9伶丐、如何找到一個(gè)字符串的全排列？
10疯特、在不使用任何庫方法的情況下如何反轉(zhuǎn)給定語句中的單詞哗魂？
11、如何判斷兩個(gè)字符串是否互為旋轉(zhuǎn)漓雅？
12录别、如何判斷給定字符串是否是回文朽色？
二叉樹問題
到目前為止，我們只研究了線性數(shù)據(jù)結(jié)構(gòu)组题，但現(xiàn)實(shí)世界中的所有信息無法全部使用線性方式表示葫男，而這正是樹數(shù)據(jù)結(jié)構(gòu)所擅長(zhǎng)的地方。
樹是一種支持以分層方式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)崔列。根據(jù)你存儲(chǔ)數(shù)據(jù)的方式梢褐，有不同類型的樹，例如二叉樹赵讯，其中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)盈咳。
與它的近親二叉搜索樹一起，它們也是最流行的樹數(shù)據(jù)結(jié)構(gòu)之一边翼。因此鱼响，你會(huì)發(fā)現(xiàn)很多基于它們的問題，例如如何遍歷它們组底、計(jì)算節(jié)點(diǎn)數(shù)丈积、查找深度，以及檢查它們是否平衡债鸡。
解決二叉樹問題的一個(gè)關(guān)鍵點(diǎn)是對(duì)其理論的深刻理解江滨，例如：什么是二叉樹的大小或深度，什么是葉節(jié)點(diǎn)娘锁，什么是節(jié)點(diǎn)牙寞，以及對(duì)流行的遍歷算法的理解，例如前序莫秆、后序和中序遍歷间雀。
下面是一些經(jīng)常問到的基于二叉樹的面試題，你可以拿來練習(xí)：
1镊屎、二叉搜索樹是如何實(shí)現(xiàn)的惹挟？
2、如何在給定二叉樹上實(shí)現(xiàn)前序遍歷缝驳？
3连锯、不使用遞歸如何按照前序遍歷給定二叉樹？
4用狱、如何在給定二叉樹上實(shí)現(xiàn)中序遍歷运怖？
5、不使用遞歸情況下如何使用中序遍歷輸出給定二叉樹所有節(jié)點(diǎn)夏伊？
6摇展、如何實(shí)現(xiàn)后序遍歷算法？
7溺忧、如何不使用遞歸實(shí)現(xiàn)二叉樹的后續(xù)遍歷咏连？
8盯孙、如何輸出二叉搜索樹的所有葉節(jié)點(diǎn)？
9祟滴、如何在給定二叉樹中計(jì)算葉節(jié)點(diǎn)數(shù)目振惰？
10、如何在給定數(shù)組中執(zhí)行二分搜索垄懂？
編程面試問題之雜項(xiàng)
除了基于數(shù)據(jù)結(jié)構(gòu)的問題之外骑晶，大多數(shù)編程工作面試還會(huì)詢問算法、設(shè)計(jì)埠偿、位操作和基于邏輯的常規(guī)問題透罢，我將在本節(jié)中對(duì)其進(jìn)行介紹榜晦。
練習(xí)這些概念很重要冠蒋，因?yàn)橛袝r(shí)在實(shí)際面試中解決這些概念很棘手。提前練習(xí)它們不僅能讓你熟悉它們乾胶，而且還讓你更自信地向面試官解釋其解決方案抖剿。
1、冒泡排序是如何實(shí)現(xiàn)的?
2识窿、迭代式快排算法是如何實(shí)現(xiàn)的斩郎？
3、你如何實(shí)現(xiàn)插入排序算法喻频？
4缩宜、合并排序算法是如何實(shí)現(xiàn)的？
5甥温、桶排序算法是如何實(shí)現(xiàn)的锻煌？
6、計(jì)數(shù)排序算法是如何實(shí)現(xiàn)的姻蚓？
7宋梧、基數(shù)排序算法是如何實(shí)現(xiàn)的？
8狰挡、在不使用第三個(gè)變量的前提下如何交換兩個(gè)數(shù)捂龄？
9、如何檢查兩個(gè)矩形是否重疊加叁？
10倦沧、如何設(shè)計(jì)一個(gè)自動(dòng)售貨機(jī)？
以上這些是數(shù)據(jù)結(jié)構(gòu)和算法之外的一些最常見的面試問題它匕，可以幫助你在面試中做得很好展融。
如果有小伙伴愿意共享自己的解題方法或者思路可以聯(lián)系我哦~屆時(shí)可以整理出有答案的更有意義的一篇~
