2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關(guān)
1、七種常見(jiàn)的數(shù)組排序算法整理(C語(yǔ)言版本)
2、2019 算法面試相關(guān)(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(guān)(leetcode)--字符串
4、2019 算法面試相關(guān)(leetcode)--棧和隊(duì)列
5、2019 算法面試相關(guān)(leetcode)--優(yōu)先隊(duì)列
6、2019 算法面試相關(guān)(leetcode)--哈希表
7、2019 算法面試相關(guān)(leetcode)--樹(shù)、二叉樹(shù)、二叉搜索樹(shù)
8、2019 算法面試相關(guān)(leetcode)--遞歸與分治
9、2019 算法面試相關(guān)(leetcode)--貪心算法
10、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃(Dynamic Programming)
11、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃之背包問(wèn)題
反轉(zhuǎn)字符串
無(wú)重復(fù)字符的最長(zhǎng)子串
最長(zhǎng)公共前綴
字符串相關(guān)的面試題還是挺多的，主要挑一些比較經(jīng)典的leetcode上的題目說(shuō)下。
一、反轉(zhuǎn)字符串
編寫(xiě)一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)。
示例 1:
輸入: "hello"
輸出: "olleh"
示例 2:
輸入: "A man, a plan, a canal: Panama"
輸出: "amanaP :lanac a ,nalp a ,nam A"
不可謂不經(jīng)典。
- 1.逆序遍歷字符串，將字符存在一個(gè)新字符串上。
var reverseString = function(s) {
let res = ''
for(let i = s.length - 1; i >= 0; i--){
res += s[i]
}
return res
};
這種方法時(shí)間和空間復(fù)雜度都是o(n),并不理想
- 2.雙指針?lè)ǎ罕闅v字符串，將對(duì)稱位置上與當(dāng)前位置上交換字符
var reverseString = function(s) {
s = s.split('')
for(let i = 0; i < ~~(s.length/2); i++){
[s[i], s[s.length - i - 1]] = [s[s.length - i - 1], s[i]];
}
return s.join('')
};
循環(huán)了n/2次，也沒(méi)有占用多余的空間
-
3.使用遞歸實(shí)現(xiàn),參考反轉(zhuǎn)鏈表
遞歸函數(shù)存在的最大問(wèn)題是，當(dāng)遞歸次數(shù)足夠大時(shí)，會(huì)導(dǎo)致函數(shù)棧溢出而死機(jī)，而函數(shù)棧的大小一般是一個(gè)固定值。
使用遞歸實(shí)現(xiàn)的話，雖然時(shí)間復(fù)雜度也是o(n)，但在leetcode上卻由于棧開(kāi)銷過(guò)大從而導(dǎo)致未通過(guò)。
所以遞歸不適用于較大字符串的情況。
var reverseString = function(s) {
if(s.length <= 1) return s
return reverseString(s.substring(1)) + s[0]
};
二、無(wú)重復(fù)字符的最長(zhǎng)子串
給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。
比較容易想到的是暴力遍歷，時(shí)間復(fù)雜度是o(n^3),太過(guò)暴力，這里不再贅述，這里說(shuō)一個(gè) 雙指針+滑動(dòng)窗口的方法:
維護(hù)一個(gè)滑動(dòng)窗口，遍歷字符串，如果下個(gè)字符s[j]在當(dāng)前滑動(dòng)窗口里，則窗口從左開(kāi)始移除元素，直至s[j]不在該窗口里，再繼續(xù)循環(huán)，記錄窗口的最大長(zhǎng)度
var lengthOfLongestSubstring = function(s) {
if(s.length == 0) return 0;
let maxLength = 1;
let i = j = 0;
let map = {};
while(i < s.length - maxLength & j < s.length){
if(s[j] in map){
delete map[s[i++]]
}else{
map[s[j++]] = 0
maxLength = Math.max(maxLength,j - i);
}
}
return maxLength;
};
三、 最長(zhǎng)公共前綴
編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。
說(shuō)明:
所有輸入只包含小寫(xiě)字母 a-z 。
首先找出數(shù)組中最短字符串的長(zhǎng)度，接下來(lái)的遍歷就不用超過(guò)這個(gè)長(zhǎng)度。
接下來(lái)選取數(shù)組第一個(gè)字符串當(dāng)作基準(zhǔn)，逆序遍歷，直至找出其余字符串的前綴是該子串為止
var longestCommonPrefix = function(strs) {
if(!strs.length) return ""
let str = strs[0], minLength = str.length
for(let i = 1; i < strs.length; i++){
minLength = Math.min(minLength,strs[i].length)
}
for(let j = minLength - 1; j >= 0 ; j--){
let tmp = str.substring(0,j + 1)
let isPre = true;
for(let i = 1; i < strs.length; i++){
if(strs[i].indexOf(tmp) != 0){
isPre = false
break;
}
}
if(isPre) return tmp
}
return ""
};
