亚马逊经典面试题实例详解

亚马逊面试题：

如下所示的Map中，0代表海水，1代表岛屿，其中每一个岛屿与其八领域的区间的小岛能相连组成岛屿群。写代码，统计Map中岛屿个数。

/*
Q1.
Map
[
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
]
*/

实现代码：

#include<iostream>
#include<queue>
using namespace std;

typedef struct {
  int i;
  int j;
}position;

void search(int a[][], int n, int i, int j, int cnt) {

  queue<position> qu = new queue<position>();

  position p;
  p.i = i;
  p.j = j;

  qu.push(p);
  a[i][j] = cnt;

  while (!qu.empty()) {
    p = qu.pop();

    for (int ii = p.i - 1; ii <= p.i + 1; ii++) {
      for (int jj = p.j - 1; jj <= p.j + 1; jj++) {
        if (ii >= 0 && ii < n && jj >= 0 && jj < n && a[ii][jj] == 1 && (ii != i || jj != j)) {
          a[ii][jj] = cnt;
          p.i = ii;
          p.j = jj;
          qu.push(p);
        }
      }
    }
  }
}

int count(int a[][], int n) {
  int cnt = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i][j] == 1) {
        cnt++; // 发现一个新陆地
        search(a, n, i, j, cnt);
      }
    }
  }
  return cnt;
}

int main() {

  int n;
  cin >> n;

  int a[][] = new int[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }

  int cnt = count(a, n);

  cout << cnt - 1 << endl;

  return 0;
}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • 分享几道你可能遇到的python面试题

    本文主要给大家介绍的是关于最近在面试中遇到的几个python面试题,分享出来供大家参考学习,下面话不多说,来一起看看详细的介绍: 一.生成斐波那契数列并取前10项 def func(m): n,a,b = 0,1,1 while n < m: yield a a,b = b,a+b n += 1 for one in func(10): print one 这个可以说是一道常见的简单算法题了,关键点就是理解a,b=b,a+b以及yield的作用. 二.扩展一个列表,列表中的元素可能也包含列表 d

  • Java main 方法面试题的详细整理

    Java main 方法面试题的详细整理 1.不用main方法如何定义一个类? 不行,没有main方法我们不能运行Java类. 在java 7之前,你可以通过使用静态初始化运行Java类.但是,从Java 7开始就行不通了. 2.main()方法需要的参数不是字符串数组? 不是的,main()方法的参数必须是字符串数组. 但是,在引进变参时,你可以将字符串类型的变参作为参数传递给main()方法.变参一定得是数组. package com.instanceofjava; public class

  • 面试题快慢链表和快慢指针

    腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点.算法复杂度是:O(3*n/2).而更快的方法就是利用快慢指针的原理. 快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚开始都指向单链表的头结点.但是*search指针的移动速度是*mid的两倍.当*search到尾结点的时候,mid刚好到了中间.算法复杂度是:O(n/2) int GetMidNode(LinkList *L,int elem){ Li

  • Java高级面试题小结

    这是一个高级Java面试系列题中的第一部分.这一部分论述了可变参数,断言,垃圾回收,初始化器,令牌化,日期,日历等等Java核心问题.接下来我们就看看具体都有哪些问题. 1.什么是可变参数? 2.断言的用途? 3.什么时候使用断言? 4.什么是垃圾回收? 5.用一个例子解释垃圾回收? 6.什么时候运行垃圾回收? 7.垃圾回收的最佳做法? 8.什么是初始化数据块? 9.什么是静态初始化器? 10.什么是实例初始化块? 11.什么是正则表达式? 12.什么是令牌化? 13.给出令牌化的例子? 14.

  • C++ 面试题翻译电话号码实例代码

    C++ 面试题翻译电话号码实例代码

    C++ 面试题翻译电话号码实例代码 例如: 输入:OneTwoThree 输出:123 输入:OneTwoDoubleTwo 输出:1222 输入:1Two2 输出:ERROR 输入:DoubleDoubleTwo 输出:ERROR 有空格,非法字符,两个Double相连,Double位于最后一个单词 都错误. #include <iostream> #include <string> using namespace std; void process(string str) {

  • Java常见数据结构面试题（带答案）

    1.栈和队列的共同特点是(只允许在端点处插入和删除元素) 4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5.下列关于栈的叙述正确的是(D)      A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征 6.链表不具有的特点是(B)A.不必事先估计存储空间       B.可随机访问任一元素 C.插入删除不需要移动元素      D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是(便于插入和删除操作) 8.在单链表中,增加头结点的目的是(

  • C++面试题之结构体内存对齐计算问题总结大全

    C++面试题之结构体内存对齐计算问题总结大全

    前言 本文给大家介绍的是关于C++结构体内存对齐计算的相关内容,内存对齐计算可谓是笔试题的必考题,但是如何按照计算原则算出正确答案一开始也不是很容易的事,所以专门通过例子来复习下关于结构体内存对齐的计算问题.话不多说,来一起看看详细介绍吧. 编译环境:vs2015 对齐原则: 原则1:数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中,比较小的那个

  • 亚马逊经典面试题实例详解

    亚马逊面试题: 如下所示的Map中,0代表海水,1代表岛屿,其中每一个岛屿与其八领域的区间的小岛能相连组成岛屿群.写代码,统计Map中岛屿个数. /* Q1. Map [ 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ] */ 实现代码: #include<iostream> #include<queue> using namespace

  • Python爬取当当、京东、亚马逊图书信息代码实例

    Python爬取当当、京东、亚马逊图书信息代码实例

    注:1.本程序采用MSSQLserver数据库存储,请运行程序前手动修改程序开头处的数据库链接信息 2.需要bs4.requests.pymssql库支持 3.支持多线程 from bs4 import BeautifulSoup import re,requests,pymysql,threading,os,traceback try: conn = pymysql.connect(host='127.0.0.1', port=3306, user='root', passwd='root',

  • php加密之discuz内容经典加密方式实例详解

    本文实例讲述了php加密之discuz内容经典加密方式.分享给大家供大家参考,具体如下: 导读:有的时候,我们希望对表里的某些敏感字段进行加密,想了好长时间没有比较好的解决方案,后台在网上查了查,放心discuz论坛的这种方案对这种情况解决的不错,特copy过来,给大家分享一下,代码如下: header ( "Content-type:text/html;charset=UTF-8" ); echo $string='花园路888号'; echo '<hr/>加密有效期10

  • python爬取亚马逊书籍信息代码分享

    我有个需求就是抓取一些简单的书籍信息存储到mysql数据库,例如,封面图片,书名,类型,作者,简历,出版社,语种. 我比较之后,决定在亚马逊来实现我的需求. 我分析网站后发现,亚马逊有个高级搜索的功能,我就通过该搜索结果来获取书籍的详情URL. 由于亚马逊的高级搜索是用get方法的,所以通过分析,搜索结果的URL,可得到node参数是代表书籍类型的.field-binding_browse-bin是代表书籍装饰. 所以我固定了书籍装饰为平装,而书籍的类型,只能每次运行的时候,爬取一种类型的书籍难

  • Python实现爬取亚马逊数据并打印出Excel文件操作示例

    Python实现爬取亚马逊数据并打印出Excel文件操作示例

    本文实例讲述了Python实现爬取亚马逊数据并打印出Excel文件操作.分享给大家供大家参考,具体如下: python大神们别喷,代码写的很粗糙,主要是完成功能,能够借鉴就看下吧,我是学java的,毕竟不是学python的,自己自学看了一点点python,望谅解. #!/usr/bin/env python3 # encoding=UTF-8 import sys import re import urllib.request import json import time import zli

  • 用pushplus+python监控亚马逊到货动态推送微信

    用pushplus+python监控亚马逊到货动态推送微信

    xbox series和ps5发售以来,国内黄牛价格一直居高不下.虽然海外amazon上ps5补货很少而且基本撑不过一分钟,但是xbox series系列明显要好抢很多. 日亚.德亚的xbox series x/s都可以直邮中国大陆,所以我们只需要借助脚本,监控相关网页的动态,在补货的第一时刻通过微信告知我们,然后迅速人工购买即可! 需求:pushplus(需要微信关注公众号).python3 一.pushplus相关介绍 pushplus提供了免费的微信消息推送api,具体内容可以参考他的官网

  • 用Python获取亚马逊商品信息

    用Python获取亚马逊商品信息

    目录 引言 一.获取亚马逊列表页的信息 二.获取详情页信息 三.代理设置 四.全部代码 总结 引言 亚马逊网站相较于国内的购物网站,可以直接使用python的最基本的requests进行请求.访问不是过于频繁,在未触发保护机制的情况下,可以获取我们想要的数据.本次通过以下三部分简单介绍下基本爬取流程: 使用requests的get请求,获取亚马逊列表和详情页的页面内容使用css/xpath对获取的内容进行解析,取得关键数据动态IP的作用及其使用方法 一.获取亚马逊列表页的信息 以游戏区为例: 获

  • react版模拟亚马逊人机交互菜单的实现

    react版模拟亚马逊人机交互菜单的实现

    目录 前言 需求介绍 实现方案 实现需求3 部分逻辑代码 实现效果 前言 前段时间接了一个需求,实现一个模仿亚马逊和京东的菜单交互效果,这种效果被称为模拟人机交互.在网上搜了一下,目前没有见到有 react和Vue的版本,然后就自己参考了一下现有的方式,实现了一个react版本. 需求介绍 本文都是在web端的需求 参考亚马逊和京东商城的首页左侧菜单效果,实现一个react版本的组件,以供业务使用. 我们先看下亚马逊和京东商城的效果: 亚马逊商城 京东商城 从上面的效果得出我们的菜单效果需求点:

  • 基于Python获取亚马逊的评论信息的处理

    基于Python获取亚马逊的评论信息的处理

    目录 一.分析亚马逊的评论请求 二.获取亚马逊评论的内容 三.亚马逊评论信息的处理 四.代码整合 4.1代理设置 4.2while循环翻页 总结 上次亚马逊的商品信息都获取到了,自然要看一下评论的部分.用户的评论能直观的反映当前商品值不值得购买,亚马逊的评分信息也能获取到做一个评分的权重. 亚马逊的评论区由用户ID,评分及评论标题,地区时间,评论正文这几个部分组成,本次获取的内容就是这些. 测试链接:https://www.amazon.it/product-reviews/B08GHGTGQ2

  • ThinkPHP3.2.3框架邮件发送功能图文实例详解

    本文实例讲述了ThinkPHP3.2.3框架邮件发送功能.分享给大家供大家参考,具体如下: 背景 web 开发过程中,经常会用到邮件的发送功能,比如接收消费账单的提醒.亚马逊图书推荐的推送,或者网站不正常操作报警的邮件提示等. 下面是一个在ThinkPHP 3.2.3 框架下集成 PHPMailer 使用的邮件发送功能实现过程,仅供参考,谢谢... 一.前期准备 1).首先对 STMP 的知识稍作了解 STMP 简介 <百度百科> 2).开启邮箱 STMP 服务 以 163.com 邮箱为例,

随机推荐