摘要：據(jù)了解，現(xiàn)在前端面試也喜歡考算法題了。下面說(shuō)一個(gè)跟前端有點(diǎn)相關(guān)并且有點(diǎn)趣的一道算法題。遍歷二維數(shù)組連續(xù)的個(gè)數(shù)連續(xù)的個(gè)數(shù)形狀的總數(shù)第幾個(gè)形狀形狀的面積最后的代碼圖片路徑讀取整張圖片的像素。
據(jù)了解，現(xiàn)在前端面試也喜歡考算法題了。前幾天去面試，果不其然的，面試官給我四道算法題，讓我自己回去做。下面說(shuō)一個(gè)跟前端有點(diǎn)相關(guān)并且有點(diǎn)趣的一道算法題。
題目：
平面上有若干個(gè)不特定的形狀，如下圖所示。請(qǐng)寫程序求出物體的個(gè)數(shù)，以及每個(gè)不同物體的面積。
分析
想要知道有多少個(gè)圖形，想到的就是先獲取圖片中的每一個(gè)像素點(diǎn)然后判獲取像素點(diǎn)的背景顏色（RGBA）。想要獲得圖片中的每一個(gè)像素點(diǎn)，那就可以聯(lián)想到使用h5的canvas。
如下：
菜鳥教程中canvas的getimagedata方法
書寫html標(biāo)簽。
js獲取canvas對(duì)象
let ctxt = canvas.getContext("2d");
js創(chuàng)建image對(duì)象
let img = new Image;
img.src = "./image.png"; //圖片路徑
img.onload = function(){} //加載成功后的執(zhí)行函數(shù)，之后的代碼就寫在其中
創(chuàng)建存儲(chǔ)圖片像素點(diǎn)的二維數(shù)組
let coordinates = [];
for(let i=0; i<200; i++){
coordinates[i] = [];
}
獲取像素點(diǎn)，也就是使用getimagedata方法。
ctxt.drawImage(img, 0, 0); //將圖片畫如canvas
let data = ctxt.getImageData(0, 0, 350, 200).data;//讀取整張圖片的像素。
將像素存入二維數(shù)組
let x=0,y=0; //二維數(shù)組的行和列， x：列 y：行
for(let i =0,len = data.length; i= 350){
x = 0;
y++;
}
}
目前代碼如下：
(function(){
let ctxt = canvas.getContext("2d");
let img = new Image;
let coordinates = [];
let h = 200,
w = 350;
for(let i=0; i<200; i++){
coordinates[i] = [];
}
img.src = "./image.png"; //圖片路徑
img.onload = function(){
ctxt.drawImage(img, 0, 0);
let data = ctxt.getImageData(0, 0, 350, 200).data;//讀取整張圖片的像素。
let x=0,y=0;
for(let i =0,len = data.length; i= 350){
x = 0;
y++;
}
}
console.log(coordinates);
}
})();
如圖：
構(gòu)成類似如下二維數(shù)組：
0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,0,0,0,0,0,0,0
0,1,1,1,1,0,0,0,0,0,0,0
0,1,1,1,0,0,0,1,1,1,1,0
0,0,0,0,0,0,1,1,1,0,0,0
0,0,0,0,0,0,1,1,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0
那么我們就只需要知道二維數(shù)組中這種連續(xù)為1的塊有多少個(gè)就知道了圖片中形狀有多少個(gè)，并且塊中有多少個(gè)1，那么這個(gè)塊的面積就是1的個(gè)數(shù)。
遞歸回溯算法
//計(jì)算連續(xù)的面積和個(gè)數(shù)
const linkSum = (i,j,num)=>{
//走過(guò)的路就置0
coordinates[i][j] = 0;
num++;
//向上
if((i+1 < h) && coordinates[i+1][j] == 1){
num = linkSum(i+1 , j , num);
}
//向下
if((j+1 < w) && coordinates[i][j+1] == 1){
num = linkSum(i , j+1 , num);
}
//向左
if((i-1 >= 0) && coordinates[i-1][j] == 1){
num = linkSum(i-1 , j , num);
}
//向右
if((j-1 >= 0) && coordinates[i][j-1] == 1){
num = linkSum(i , j-1 , num);
}
return num;
}
不熟悉的，直接百度就好，這里就不多說(shuō)了，其實(shí)代碼就反應(yīng)了很多信息。
使用算法，統(tǒng)計(jì)并計(jì)算出結(jié)果。
const getCountAndArea = () =>{
let sum = [];
let count = 0;
for(let i = 0; i < h; i++) //遍歷二維數(shù)組
{
for(let j = 0; j < w; j++)
{
//連續(xù)1的個(gè)數(shù)
if(coordinates[i][j] == 1)
{
let buf = 0; //連續(xù)1的個(gè)數(shù)
buf = linkSum(i,j,buf);
count++; //形狀的總數(shù)
sum.push({
index: count, //第幾個(gè)形狀
area: buf //形狀的面積
});
}
}
}
return {
count,
sum
};
}
最后的代碼
(function(){
let ctxt = canvas.getContext("2d");
let img = new Image;
let coordinates = [];
let h = 200,
w = 350;
for(let i=0; i<200; i++){
coordinates[i] = [];
}
img.src = "./image.png"; //圖片路徑
img.onload = function(){
ctxt.drawImage(img, 0, 0);
let data = ctxt.getImageData(0, 0, 350, 200).data;//讀取整張圖片的像素。
let x=0,y=0;
for(let i =0,len = data.length; i= 350){
x = 0;
y++;
}
}
// console.log(coordinates);
let rst = getCountAndArea();
// console.log(rst);
console.log("個(gè)數(shù)： " + rst.count);
for(let i=0; i{
let sum = [];
let count = 0;
for(let i = 0; i < h; i++)
{
for(let j = 0; j < w; j++)
{
//連續(xù)1的個(gè)數(shù)
if(coordinates[i][j] == 1)
{
let buf = 0;
buf = linkSum(i,j,buf);
count++;
sum.push({
index: count,
area: buf
});
}
}
}
return {
count,
sum
};
}
//計(jì)算連續(xù)的面積和個(gè)數(shù)
const linkSum = (i,j,num)=>{
//走過(guò)的路就置0
coordinates[i][j] = 0;
num++;
//向上
if((i+1 < h) && coordinates[i+1][j] == 1){
num = linkSum(i+1 , j , num);
}
//向下
if((j+1 < w) && coordinates[i][j+1] == 1){
num = linkSum(i , j+1 , num);
}
//向左
if((i-1 >= 0) && coordinates[i-1][j] == 1){
num = linkSum(i-1 , j , num);
}
//向右
if((j-1 >= 0) && coordinates[i][j-1] == 1){
num = linkSum(i , j-1 , num);
}
return num;
}
})();
運(yùn)行的結(jié)果：
