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