433.島嶼的個數(shù) （7.2）
給一個01矩陣万牺，求不同的島嶼的個數(shù)。
0代表海邢享，1代表島鹏往，如果兩個1相鄰，那么這兩個1屬于同一個島骇塘。我們只考慮上下左右為相鄰伊履。
樣例
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
// 輸出3
思路
創(chuàng)建一個visited數(shù)組來保存訪問過的位置，初始化全為false款违，訪問當(dāng)前位置則置為true型奥。遍歷目標(biāo)矩陣铃绒，沒有訪問過的點就遞歸他的上下左右四個點昂芜。
程序
function main(arr){
if(!arr||arr.length==0) return 0
const LEN=arr.length
const LEN2=arr[0].length
const row=Array(LEN2).fill(false)
const visited=Array(LEN).fill(row) // 訪問過的數(shù)組
let res=0
for(let i=0;i<LEN;i++){
for(let j=0;j<LEN2;j++){
if(arr[i][j]&&!visited[i][j]){
DPSlands(arr,visited,i,j)
res++
}
}
}
return res
}
function DPSlands(arr,visited,i,j){
if(i<0||i>=arr.length) return;
if(j<0||j>=arr[0].length) return;
if(!arr[i][j]||visited[i][j]) return;
visited[i][j]=true
DPSlands(arr, visited, i - 1, j);
DPSlands(arr, visited, i, j - 1);
DPSlands(arr, visited, i + 1, j);
DPSlands(arr, visited, i, j + 1);
}
console.log(main(arr)) // 3
457.經(jīng)典二分查找問題
在一個排序數(shù)組中找一個數(shù)吐根，返回該數(shù)出現(xiàn)的任意位置，如果不存在赠尾，返回-1
樣例
給出數(shù)組 [1, 2, 2, 4, 5, 5].
對于 target = 2, ?返回 1 或者 2.
對于 target = 5, ?返回 4 或者 5.
對于 target = 6, ?返回 -1.
挑戰(zhàn)
O(logn) 的時間
const arr=[1, 2, 2, 4, 5, 5]
function findPosition(arr,target){
let start=0,end=arr.length-1,mid=null
let res=[]
if(!arr||target>arr[end]||target<arr[start]) return -1;
while(start<=end){
mid=Math.ceil((end-start)/2)
if(target==arr[mid]) return mid
if(target<arr[mid]){
end=mid
}
if(target>arr[mid]){
start=mid
}
if(arr[start]==target) return start;
if(arr[end]==target) return end;
if(start==end-1) return -1;
}
}
console.log(findPosition(arr,2))//2
488.快樂數(shù) （7.5）
寫一個算法來判斷一個數(shù)是不是"快樂數(shù)"力穗。
一個數(shù)是不是快樂是這么定義的：對于一個正整數(shù)，每一次將該數(shù)替換為他每個位置上的數(shù)字的平方和气嫁，然后重復(fù)這個過程直到這個數(shù)變?yōu)?当窗，或是無限循環(huán)但始終變不到1。如果可以變?yōu)?寸宵，那么這個數(shù)就是快樂數(shù)崖面。
樣例
19 就是一個快樂數(shù)。
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
const MAX_TIMES=9999 //設(shè)置一個遞歸的最大次數(shù)
function isHappy(num,time){
let sum=0,times=time||0
const str=num.toString()
for(let i=0;i<str.length;i++){
let a=str.charAt(i)
sum+=a*a
times++
}
if(sum==1) return '快樂'
if(times>MAX_TIMES) return '不快樂'
return isHappy(sum,times)
}
console.log(isHappy(19)) //快樂
console.log(isHappy(16)) //不快樂
491.回文數(shù)(7.6)
判斷一個正整數(shù)是不是回文數(shù)梯影。
回文數(shù)的定義是巫员，將這個數(shù)反轉(zhuǎn)之后，得到的數(shù)仍然是同一個數(shù)光酣。
樣例
11, 121, 1, 12321 這些是回文數(shù)疏遏。
23, 32, 1232 這些不是回文數(shù)。
function palindromeNumber(num){
if(!num) return false
const str=num.toString()
if(str.length==1) return true
for(let i=0;i<str.length/2;i++){
if(str.charAt(i)!=str.charAt(Math.abs(str.length-i-1))) return false
}
return true
}
console.log(palindromeNumber(1331)) //true
console.log(palindromeNumber(23)) //false
console.log(palindromeNumber(3)) //true
499.單詞計數(shù) (Map Reduce版本) （7.10）
使用 map reduce 來計算單詞頻率
樣例
chunk1: "Google Bye GoodBye Hadoop code"
chunk2: "lintcode code Bye"
Get MapReduce result:
Bye: 2
GoodBye: 1
Google: 1
Hadoop: 1
code: 2
lintcode: 1
實現(xiàn)
const obj={
chunk1: "Google Bye GoodBye Hadoop code",
chunk2: "lintcode code Bye"
}
function WordCount(obj){
let res={}
const arr=Object.keys(obj).reduce((key1,key2)=>{
return obj[key1].split(/\s/).concat(obj[key2].split(/\s/))
})
arr.forEach((word)=>{
res[word]=res.hasOwnProperty(word)?++res[word]:0
})
return res
}
console.log(WordCount(obj)) //Object {Google: 0, Bye: 1, GoodBye: 0, Hadoop: 0, code: 1…}
517.丑數(shù)(7.11)
寫一個程序來檢測一個整數(shù)是不是丑數(shù)救军。
丑數(shù)的定義是，只包含質(zhì)因子 2, 3, 5 的正整數(shù)倘零。比如 6, 8 就是丑數(shù)唱遭，但是 14 不是丑數(shù)以為他包含了質(zhì)因子 7。
樣例
給出 num = 8呈驶，返回 true拷泽。
給出 num = 14，返回 false
實現(xiàn)
function isUgly(num){
if(num<=0) return false
if(num==1) return true
const primeNumArr=[2,3,5]
while(num>1){
let divider=-1
for(let i=0;i<primeNumArr.length;i++){
if(num%primeNumArr[i]==0){
divider=primeNumArr[i]
break;
}
}
if(divider==-1) return false
num/=divider
}
return true
}
console.log(isUgly(6)) //true
console.log(isUgly(14)) //false
524.左填充(8.23)
題目鏈接
實現(xiàn)一個leftpad庫，如果不知道什么是leftpad可以看樣例
樣例
leftpad("foo", 5)
>> " foo"
leftpad("foobar", 6)
>> "foobar"
leftpad("1", 2, "0")
>> "01"
實現(xiàn)
普通實現(xiàn)
function leftpad(str,maxLen,fillStr=' '){
if(arguments.length==0) return false;
if(!maxLen&&!fillStr||str.length>maxLen||isNaN(maxLen)) return str;
let filledStr=''
const filledStrLen=maxLen-str.length
for(let i=0;i<filledStrLen;i++){
filledStr+=fillStr
}
return filledStr.slice(0,filledStrLen)+str
}
console.log(leftpad("foo", 5)) // ' foo'
然而司致，js怎么會連這么簡單的操作都沒有封裝成一個方法哩OVO拆吆，我們可以用padStart()進行實現(xiàn)~~
function leftpad(str,maxLen,fillStr){
return str.padStart(maxLen,fillStr)
}
console.log(leftpad("foo", 5)) // ' foo'
539.移動零(8.24)
給一個數(shù)組 nums 寫一個函數(shù)將 0 移動到數(shù)組的最后面，非零元素保持原數(shù)組的順序
題目鏈接
樣例
給出 nums = [0, 1, 0, 3, 12], 調(diào)用函數(shù)之后, nums = [1, 3, 12, 0, 0].
實現(xiàn)
function moveZeroes(arr){
let len=arr.length
if(!arr||len<1) return;
let i=0
while(i<len){
if(arr[i]===0){
arr.splice(i,1)
arr.push(0)
len--
}else{
i++
}
}
return arr
}
// moveZeroes([4, 0, 0, 3, 12])
// [4, 3, 12, 0, 0]
有前后兩個指針脂矫，當(dāng)刪除一個元素并在尾部添加一個元素時枣耀，后面的指針往前移動，前面的進行遍歷的指針保持不動庭再。
547.兩數(shù)組的交(8.25)
題目鏈接
返回兩個數(shù)組的交
結(jié)果中的元素必須是唯一的捞奕。結(jié)果可以是任何順序。
樣例
nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].
實現(xiàn)
function intersection(arr1,arr2){
let res=[]
const LEN1=arr1.length
const LEN2=arr2.length
arr1.sort()
arr2.sort()
const Arr=arr1.concat(arr2)
let i=0,j=LEN1
while(i<LEN1&&j<LEN1+LEN2){
if(Arr[i]<Arr[j]){
i++
}else if(Arr[i]>Arr[j]){
j++
}else{
if(Arr[i]!=res[res.length-1]){
res.push(Arr[i])
}
i++
j++
}
}
return res
}
console.log(intersection([1,1,2,2],[2,3,3,6,1])) // [1, 2]
排序后放到一個數(shù)組里拄轻，和上面那道題的算法差不多颅围，都是用兩個指針，只不過另一個是從數(shù)組中部遍歷恨搓。
548.兩數(shù)組的交 II(8.28)
計算兩個數(shù)組的交
每個元素出現(xiàn)次數(shù)得和在數(shù)組里一樣
答案可以以任意順序給出
樣例
nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
實現(xiàn)
代碼就不舉例了院促，只是把上面那道題最后的判斷條件去掉就是此題的解題過程了。
569.各位相加(8.29)
相關(guān)鏈接
給出一個非負整數(shù) num斧抱，反復(fù)的將所有位上的數(shù)字相加一疯，直到得到一個一位的整數(shù)。
樣例
給出 num = 38夺姑。
相加的過程如下：3 + 8 = 11墩邀，1 + 1 = 2。因為 2 只剩下一個數(shù)字盏浙，所以返回 2眉睹。
實現(xiàn)
這個就是很簡單的遞歸，在js中要注意類型轉(zhuǎn)換废膘，還有使用reduce時要分配初始值竹海。
function addDigits(num){
if(isNaN(num)) return;
if(num<10) return num
const res=num.toString().split('').reduce((sum,value)=>{
return sum+Number(value)
},0)
return addDigits(res)
}
挑戰(zhàn)
你可以不用任何的循環(huán)或者遞歸算法，在 O(1) 的時間內(nèi)解決這個問題么丐黄？
實現(xiàn)
簡直玄學(xué)~~~
function addDigits(num){
if(num!=0 && num%9==0) return 9;
return num%9;
}
