Leetcode終于上線劍指offer的題目了?? 記下刷題記錄
面試題03. 數(shù)組中重復(fù)的數(shù)字
簡單題
空間復(fù)雜度：O(N)
時間復(fù)雜度：O(N)
var findRepeatNumber = function(nums) {
const arr = new Array(nums.length)
for(let n of nums) {
if(arr[n]) {
return n
}
arr[n] = true
}
return false
};
面試題04. 二維數(shù)組中的查找
簡單題
空間復(fù)雜度：O(1) 輔助數(shù)據(jù)也就是坐標(biāo)i爹殊，j而已。
時間復(fù)雜度：O(N+M) 最復(fù)雜的情況就是從上到下，從右到左。
const findNumberIn2DArray = function(matrix, target) {
// 左到右遞增
// 上到下遞增
// 從左上角開始或衡，item > target j--, item < target i++
const n = matrix.length
if(n === 0) return false
const m = matrix[0].length
if(m === 0) return false
if(target < matrix[0][0]) return false
if(target > matrix[n-1][m-1]) return false
let i = 0, j = m-1
while(i<n && i>=0 && j<m && j>=0) {
if(matrix[i][j] === target) {
return true
}
if(matrix[i][j] > target) {
j--
continue
}
if(matrix[i][j] < target) {
i++
continue
}
}
return false
};
面試題05. 替換空格
簡單題
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)
// 先復(fù)習(xí)下字符串操作API吧
// replace實(shí)現(xiàn)
const replaceSpace = function(s) {
return s.replace(/ /g, '%20')
};
// split + join
const replaceSpace = function(s) {
return s.split(' ').join('%20')
};
// 數(shù)組 + join做法
const replaceSpace = function(s) {
const arr = []
for(const c of s) {
c === ' ' ? arr.push('%20') : arr.push(c)
}
return arr.join('')
};
面試題06. 從尾到頭打印鏈表
簡單題
遞歸法和循環(huán)壓棧逆序輸出法速兔，都是O(N)
const reversePrint = function(head) {
// 用遞歸法
const res = []
const reverse = (node) => {
if(!node) {
return
} else {
reverse(node.next)
res.push(node.val)
}
}
reverse(head)
return res
};
const reversePrint = function(head) {
// 用循環(huán)法
const res = []
while(head) {
res.push(head.val)
head = head.next
}
return res.reverse()
};
面試題07. 重建二叉樹
中等題
時間復(fù)雜度O(N)
空間復(fù)雜度O(N) 函數(shù)調(diào)用椦憔海空間浪費(fèi)秒咐。
var buildTree = function(preorder, inorder) {
// 重建二叉樹
// 前序遍歷：先中后左最后右，因此第一個是中節(jié)點(diǎn)
// 中序遍歷：先左后中最后右盈简，因此第一個是左樹
const n = preorder.length
if(n === 0) return null
const build = (ps, pe, is, ie) => {
const mid = preorder[ps]
const midNode = new TreeNode(mid)
if(ps === pe || is === ie) {
return midNode
}
// im是中節(jié)點(diǎn)的inorder坐標(biāo)凑耻，它同時代表：左子樹的長度=im-is太示，右子樹的長度是ie-im
let im
for(let i=is;i<=ie;i++) {
if(inorder[i] === mid) {
im = i
break
}
}
let leftLen = im-is, rightLen = ie-im
// 1,1,0,0
midNode.left = leftLen > 0 ? build(ps+1, ps+1+leftLen-1, is, is+leftLen-1) : null
midNode.right = rightLen > 0 ? build(ps+1+leftLen, ps+1+leftLen+rightLen-1, im+1, im+1+rightLen-1) : null
return midNode
}
return build(0, n-1, 0, n-1)
};
翻了一下過去的提交，發(fā)現(xiàn)自己又踩坑了香浩，居然沒記住這個結(jié)果：就是構(gòu)建樹的過程本來就是一個先序遍歷类缤，所以每次只要考慮inorderIndex就行了。??
var buildTree = function(preorder, inorder) {
/**
* 其實(shí) 這個build的過程本身就是一個先序遍歷邻吭，因此只需要設(shè)置一個全局自增的Index就能走先序遍歷的過程了
* 所以 目前需要的下標(biāo)就是中序遍歷的left和right部分
*/
let index = 0
const inorderMap = new Map()
for(let i=0;i<inorder.length;i++) {
inorderMap.set(inorder[i], i)
}
const recBuild = (inLeft, inRight) => {
if(inLeft === inRight) {
return null
}
const rootVal = preorder[index]
const root = new TreeNode(rootVal)
const inorderIndex = inorderMap.get(rootVal)
index++
root.left = recBuild(inLeft, inorderIndex)
root.right = recBuild(inorderIndex+1, inRight)
return root
}
return recBuild(0, inorder.length)
};
面試題09. 用兩個棧實(shí)現(xiàn)隊(duì)列
簡單題
var CQueue = function() {
this.s1 = []
this.s2 = []
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.s1.push(value)
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
if(this.s2.length) return this.s2.pop()
if(!this.s1.length) return -1
while(this.s1.length) {
this.s2.push(this.s1.pop())
}
return this.s2.pop()
};
面試題10- I. 斐波那契數(shù)列
簡單題
var fib = function(n) {
const cache = {
0: 0n,
1: 1n
};
return Fibonacci(n) % 1000000007n;
/**
* @param {number} n
* @return {number}
*/
function Fibonacci(n) {
if (cache[n] !== undefined) {
return cache[n];
}
cache[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
return cache[n];
}
};
面試題10- II. 青蛙跳臺階問題
同上
面試題11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
簡單題
簡單題的簡單思路
var minArray = function(numbers) {
let i
for(i=numbers.length-1;i>0;i--) {
if(numbers[i]<numbers[i-1]) {
break
}
}
return numbers[i]
};
但是這道題在leetcode原本的題庫是困難題餐弱，因?yàn)樗梢曰影俪觥?/p>
var minArray = function(numbers) {
let left = 0, right = numbers.length-1
while(left < right) {
let mid = Math.floor((left+right)/2)
// mid一定在數(shù)組的右邊
if(numbers[mid]>numbers[right]) {
left = mid+1
// mid一定在數(shù)組的左邊
} else if (numbers[mid]<numbers[right]) {
right = mid
} else {
right = right-1
}
}
return numbers[left]
};
面試題12. 矩陣中的路徑
中等題
極速地寫了一個，沒有優(yōu)化過囱晴，但是思路很明顯膏蚓，就是dfs。
const exist = function(board, word) {
const n = board.length
const m = board[0].length
const len = word.length
// 如果字母a畸写，上下左右都有下一個字母驮瞧，那就得全部都試一試?yán)玻幸粋€達(dá)成和word一樣就立馬推出枯芬。
// travel 目前的位置i,j和目前走到word第幾個w
const travel = (i,j,w, visit) => {
if(w===len-1) {
return true
}
// 看看左邊剧董？
if(j-1>=0 && board[i][j-1]===word[w+1]) {
let pos = `${i}-${j-1}`
if(!visit[pos]) {
if(travel(i,j-1,w+1,{[pos]:true,...visit})) return true
}
}
// 看看右邊？
if(j+1<m && board[i][j+1]===word[w+1]) {
let pos = `${i}-${j+1}`
if(!visit[pos]) {
if(travel(i,j+1,w+1,{[pos]:true,...visit})) return true
}
}
// 看看上邊破停？
if(i-1>=0 && board[i-1][j]===word[w+1]) {
let pos = `${i-1}-${j}`
if(!visit[pos]) {
if(travel(i-1,j,w+1,{[pos]:true,...visit})) return true
}
}
// 看看下邊？
if(i+1<n && board[i+1][j]===word[w+1]) {
let pos = `${i+1}-${j}`
if(!visit[pos]) {
if(travel(i+1,j,w+1,{[pos]:true,...visit})) return true
}
}
return false
}
for(let i=0;i<n;i++) {
for(let j=0;j<m;j++) {
if(board[i][j]===word[0]) {
let pos = `${i}-${j}`
if(travel(i,j,0, {[pos]: true})) return true
}
}
}
return false
};
面試題13. 機(jī)器人的運(yùn)動范圍
中等題
Leetcode題解里的BFS尉剩，比我使用DFS復(fù)雜度低了真慢。
空間復(fù)雜度O(N)，時間復(fù)雜度O(N)
var movingCount = function(m, n, k) {
let res = 0;
const directions = [
[1, 0],
[0, 1]
];
const queue = [[0, 0]];
const visited = {
"0-0": true
}; // 標(biāo)記 (x,y) 是否被訪問過
while (queue.length) {
const [x, y] = queue.shift();
// (x, y) 的數(shù)位之和不符合要求
// 題目要求節(jié)點(diǎn)每次只能走1格理茎，所以無法從當(dāng)前坐標(biāo)繼續(xù)出發(fā)
if (bitSum(x) + bitSum(y) > k) {
continue;
}
++res;
for (const direction of directions) {
const newx = direction[0] + x;
const newy = direction[1] + y;
if (
!visited[`${newx}-${newy}`] &&
newx >= 0 &&
newy >= 0 &&
newx < m &&
newy < n
) {
queue.push([newx, newy]);
visited[`${newx}-${newy}`] = true;
}
}
}
return res;
};
function bitSum (n) {
let res = 0
while(n) {
res += n%10
n = Math.floor(n/10)
}
return res
}
面試題16. 數(shù)值的整數(shù)次方
中等題
先寫個普通循環(huán)版本黑界，果不其然超時了。
var myPow = function(x, n) {
let res = 1
if(n >= 0) {
while(n--) {
res *= x
}
} else {
while( (n++)!=0 ) {
res /= x
}
}
return res
};
想了下可以用遞歸來實(shí)現(xiàn)二分思想皂林。
如果指數(shù)是偶數(shù)的情況下：Pow(base,exponent) = Pow(base,exponent/2)*Pow(base,exponent)
指數(shù)是奇數(shù)的情況下：Pow(base,exponent) = base * Pow(base,exponent/2) * Pow(base,exponent/2)
再區(qū)分下奇數(shù)偶數(shù)的情況朗鸠，就能成了：
var myPow = function(x, n) {
const pow = (x,n) => {
if(n===0) {
return 1
}
if(n===1) {
return x
}
const exp = Math.floor(n/2)
return n % 2 === 1 ? x*pow(x,exp)*pow(x,exp):pow(x,exp)*pow(x,exp)
}
return n >= 0 ? pow(x,n) : 1/pow(x,-n)
};
突然想到之前學(xué)計(jì)算機(jī)安全導(dǎo)論的時候?qū)W過一個叫快速冪的算法，這里用來試試础倍。
var myPow = function(x, n) {
const pow = (x,n) => {
let ans = 1
while(n) {
if(n & 1) {
ans *= x
}
x *= x
n = Math.floor(n/2)
}
return ans
}
return n >= 0 ? pow(x,n) : 1/pow(x,-n)
};
快速冪的思想是：
摘自百度百科
面試題17. 打印從1到最大的n位數(shù)
簡單題
直接調(diào)用API辣烛占，其實(shí)也可以用上面的快速冪計(jì)算10的n次冪
var printNumbers = function(n) {
const res = []
const max = 10 ** n - 1
for(let i=1;i<=max;i++) {
res.push(i)
}
return res
};
面試題18. 刪除鏈表的節(jié)點(diǎn)
var deleteNode = function(head, val) {
if(head.val === val) {
head = head.next
return head
}
let node = head
while(node.next) {
if(node.next.val === val) {
node.next = node.next.next
break
}
node = node.next
}
return head
};
面試題19. 正則表達(dá)式匹配
簡單題
回溯法
var isMatch = function(s, p) {
const _isMatch = (i, j) => {
if(i === s.length && j===p.length) {
return true
}
if(i !== s.length && j === p.length) {
return false
}
if(p[j+1] === '*') {
if(s[i]===p[j] || (p[j]==='.' && i !== s.length)) {
return _isMatch(i+1,j) || _isMatch(i,j+2)
} else {
return _isMatch(i,j+2)
}
}
if (s[i]===p[j] || (p[j]==='.' && i !== s.length)){
return _isMatch(i+1, j+1)
} else {
return false
}
}
return _isMatch(0,0)
};
322. 零錢兌換
回溯法剪枝依然超時，所以應(yīng)該用動態(tài)規(guī)劃
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
/**
* 最優(yōu)化問題
* 可以用回溯法和動態(tài)規(guī)劃法解決
* 優(yōu)化目標(biāo)：硬幣數(shù)量最少
* 先用回溯法莽一波
* 動態(tài)規(guī)劃也可以減少解空間
*/
/**
* rest: 剩余金額
* count: 使用硬幣數(shù)
*/
let res = Infinity
const sub = (rest, count) => {
// 剪枝
if(count > res) {
return
}
if(rest === 0) {
res = Math.min(count, res)
return
} else if(rest < Math.min(coins)) {
return
}
// 剩余情況
for(const coin of coins) {
sub(rest-coin, count+1)
}
}
sub(amount, 0)
return res === Infinity ? -1 : res
};
var coinChange = function(coins, amount) {
/**
* 最優(yōu)化問題
* 可以用回溯法和動態(tài)規(guī)劃法解決
* 優(yōu)化目標(biāo)：硬幣數(shù)量最少
* 先用回溯法莽一波
* 動態(tài)規(guī)劃也可以減少解空間
*/
// dp是此金額花費(fèi)的硬幣數(shù)
const dp = Array(amount+1).fill(Infinity)
dp[0] = 0
for(let i=1;i<=amount;i++) {
for(let coin of coins) {
if(i-coin>=0) {
dp[i] = Math.min(dp[i], dp[i-coin]+1)
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
};
面試題37. 序列化二叉樹
var serialize = function(root) {
// 用層次遍歷來讀入
if(!root) return '[]'
let res = '['
const queue = [root]
while(queue.length) {
const t = queue.shift()
if(t === null) {
res+='null,'
}else {
res+=`${t.val},`
}
// null節(jié)點(diǎn)不會再加入它們的子節(jié)點(diǎn)而導(dǎo)致出錯
if(!t) continue
queue.push(t.left)
queue.push(t.right)
}
return res.slice(0, res.length-1) + ']'
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
if(data === '[]' || !data) return null
data = data.slice(1,data.length-1).split(',')
let index = 0
const head = getTreeNode(data[index++])
const queue = [head]
while(queue.length) {
let node = queue.shift()
node.left = getTreeNode(data[index++])
node.right = getTreeNode(data[index++])
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
return head
};
const getTreeNode = (value) => {
if(value === 'null') return null
else return new TreeNode(Number(value))
}
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
面試題38. 字符串的排列
/**
* @param {string} s
* @return {string[]}
*/
var permutation = function(s) {
if (!s.length) {
return [];
}
const result = [];
_permutation(s.split(""), 0, result);
return result
};
/**
* 回溯遍歷得到所有的結(jié)果
*
* @param {string[]} strs
* @param {number} start
* @param {string[]} result
*/
function _permutation(strs, start, result) {
if (start === strs.length) {
result.push(strs.join(""));
return;
}
const map = {}
for (let i = start; i < strs.length; ++i) {
if (map[strs[i]]) {
// 進(jìn)行剪枝
continue;
}
map[strs[i]] = true;
[strs[i], strs[start]] = [strs[start], strs[i]];
_permutation(strs, start + 1, result);
[strs[i], strs[start]] = [strs[start], strs[i]];
}
}
面試題39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
var majorityElement = function(nums) {
/**
* 摩爾投票法
*/
let count = 1
let res = nums[0]
for(let n of nums) {
if(n !== res) {
count--
if(count === 0) {
res = n
count = 1
}
} else {
count++
}
}
return res
};
