最大子三角形

[编程题]最大子三角形

热度指数：1266 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全 1 子三角形，输出三角形的边长 b。

示例1

输入

2,[0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1]

输出

说明

如下图，可以找到一个边长为2的子三角形，但并不唯一。

备注:

对于所有的输入数据，满足 。

描述这个六边形 01 矩阵 maps 的数组下标，每个数字依次从左到右，再从上到下对应每一个区域。详见下图：

算法知识视频讲解

Java

satchmo

究极遍历皮皮虾之象拔蚌之菜鸟解法：

构造一个矩阵使其刚刚好能将六边形的每个位置的数按照对应的位置一一放进去，其他没有的位数全部用0填充。

然后遍历整个矩阵，若遍历到的该位置为1，则判断它所对应的三角形在六边形中尖尖是向上的还是向下的。以此为顶点向上（或向下）去找若构成大三角形所对应的位置是否都为1，并记录下能遍历的深度。最终返回能向上（或向下）遍历最深的次数。

import java.util.*;
import java.util.Arrays;

public class Solution {
    /**
     * 计算六边形01矩阵中最大的全1子三角形的边长
     * @param a int整型 六边形01矩阵的边长
     * @param maps int整型一维数组 矩阵的具体数据，从上到下，从左到右顺次排列
     * @return int整型
     */
    public int largestSubTriangle (int a, int[] maps) {
        // write code here
        int n = (4*a-1);
        int[][] arr = new int[2*a][n];//构造一个刚好能放入六边形大陆的矩阵
        int h = 0;//对矩阵行的指针
        for(int i=0; i<maps.length/2;){//遍历上半部分大陆数组
            for(int j=0; j<n; j++){//遍历每一行的每个位置
                if(j<(a-1-h) || j>(n-a+h)){//找出大陆在该行的头尾,之外的部分全部赋值为0
                    arr[h][j] = 0;
                }else{                     //将大陆在该行的位置情况录入
                    arr[h][j] = maps[i];
                    i++;
                }
            }
            h++;
        }
        int h1 = h;
        for(int i=maps.length/2; i<maps.length;){//遍历下半部分大陆数组
            for(int j=0; j<n; j++){//遍历每一行的每个位置
                if(j<(a-1-h1) || j>(n-a+h1)){
                    arr[h][j] = 0;
                }else{
                    arr[h][j] = maps[i];//将大陆在该行的位置情况录入
                    i++;
                }
            }
            h1--;
            h++;
        }
        int result = 0;
        //====开始遍历矩阵==========//
        for(int x=0; x<2*a; x++){//遍历行
            for(int y=0; y<n; y++){//遍历列
                int count = 1;
                if(arr[x][y]==1){//若该点为1，可以作为顶点
                    if((a-1-x)%2==0 && y%2==0 || (a-1-x)%2!=0 && y%2!=0){//若该点为向上的三角形
                        outterloop:for(int i=1; i<2*a-x; i++){//开始向下遍历行
                            for(int k=0; k<=i; k++){//遍历下一行的左右点数
                                if(y+k>=n || y-k<0 || arr[x-i][y+k]!=1 || arr[x-i][y-k]!=1){
                                    break outterloop;
                                }
                            }
                            count++;
                        }
                    }else{//若该点为向下的三角形
                        outterloop:for(int i=1; i<x+1; i++){//开始向上遍历行
                            for(int k=0; k<=i; k++){
                                if(y+k>=n || y-k<0 || arr[x+i][y+k]!=1 || arr[x+i][y-k]!=1){
                                    break outterloop;
                                }
                            }
                            count++;
                        }
                    }
                }
                result = Math.max(result,count);
            }
        }
        return result;
    }
}

发表于 2020-03-13 21:12:45 回复(1)

notrp

先将输入转换至一个足够大的矩阵，在分别从上到下，从下到上分别做一次dp

dir数组表示小三角形的朝向。 1 朝上， 0 朝下。非六边形区域无所谓。

以从下到上为例（此时统计的是三角形顶点朝上）：

dp[i][j] 统计的是以 mymap[i][j]这个小三角形为最顶端的三角形的边长最大值。

若mymap[i][j]是朝上的，那么mymap[i-1][j-1] 与 mymap[i-1][j+1] 也是朝上的。

那么若是 mymap[i-1][j]这个小三角形是可行的（值为1）

那么 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + 1

从上到小同理，求的是顶点朝下的三角形边长最大值

class Solution {
public:
    /**
     * 计算六边形01矩阵中最大的全1子三角形的边长
     * @param a int整型 六边形01矩阵的边长
     * @param maps int整型vector 矩阵的具体数据，从上到下，从左到右顺次排列
     * @return int整型
     */
    int largestSubTriangle(int a, vector<int>& maps) {
        // write code here
        vector<vector<int>> mymap(2*a, vector<int>(4*a-1, 0));
        vector<vector<int>> dir(2*a, vector<int>(4*a-1, 0));
        vector<vector<int>> dp(2*a, vector<int>(4*a-1, 0));
        int cnt = 0, ans = 0;
        for(int i = 0, d = 1; i < a; i ++, d = 1) 
            for(int j = a - 1 - i; j < 3*a+i; j ++,d ++) {
                mymap[i][j] = maps[cnt ++];
                dir[i][j] = d%2;
            }
        for(int i = a-1,d = 0; ~i; i --,d = 0) 
            for(int j = a - 1 - i; j < 3*a+i; j ++,d ++) {
                mymap[2*a-1-i][j] = maps[cnt ++];
                dir[2*a-1-i][j] = d%2;
            }
        for(int i = 2*a-1; ~ i; i --) {
            for(int j = 4*a-2; ~j; j --) {
                if(mymap[i][j]) {
                    dp[i][j] = 1;
                    if(i < 2*a-1 && j < 4*a-2 && j > 0 && dir[i][j] == 1 && dp[i+1][j] == 1) 
                        dp[i][j] = min(dp[i+1][j-1], dp[i+1][j+1]) + 1;
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        for(int i = 0; i < 2*a; i ++) {
            for(int j = 0; j < 4*a-1; j ++) {
                if(mymap[i][j]) {
                    dp[i][j] = 1;
                    if(i > 0 && j < 4*a-2 && j > 0 && dir[i][j] == 0 && dp[i-1][j] == 1) 
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + 1;
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
};

编辑于 2020-03-27 00:43:49 回复(0)