![个人头像照片](https://ucc.alicdn.com/avatar/avatar3.jpg)
暂无个人介绍
题目描述 你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示: ....... .##.... .##.... ....##. ..####. ...###. ....... 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。 由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。 例如上图中的海域未来会变成如下样子: ....... ....... ....... ....... ....#.. ......
从另一个方向看,可以考虑每个字符对结果的贡献值分别是多少; 分别向左右两个方向查找该字符,向左找到该字符的位置记录为left(找不到就为0);向右找到该字符的位置记录为right(找不到就为字符串长度+1);向左找到的位置就是该字符做贡献的开始,向右找到的位置就是该字符做贡献的结束; 不难推理出:每个字符的贡献值为(i-left)*(right-i) i为该字符的位置(从1开始计数); 那样例来说:第一个a向左查找,left记为0,向右查找,right记为3,那么第一个a的贡献值为 (1-0)*(3-1)==2; 类推: (2-0)*(4-2)==4; (3-1)*(6-3)=
算法