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