当前位置: 首页 > news >正文

【友塔笔试面试复盘】八边形取反问题

问题:一个八边形每条边都是0,现在有取反操作,选择一条边取反会同时把当前边和2个邻边取反(如果是0变为1,如果是1变为0)
现在问你怎么取反能使得八条边都变为1.

当时陷入了暴力递归漩涡,给出一个2的8次方复杂度的解,被薄纱了
讨论过程中发现如果决定了相邻2条边之后就可以依次决定所有边,如果成功说明这选择可行,2条边一共就4种情况,取取,不取取,取不取,不取不取,挨个试就行,如果都不行就是不行,该复杂度就只有O(n),太漂亮了,过去了一年多,现在决定代码实现一下

ps:每一条边也只会被三条边影响

#include<iostream>
#include<vector>
#include<map>
using namespace std;void changenumber(int &i) {if (i != 0 && i != 1)return;if (i == 0)i = 1;else if (i == 1)i = 0;
}
void doback(int a[], int i,int n) {if (i >= n)return;if (i == 0) {changenumber(a[n - 1]);changenumber(a[0]);changenumber(a[1]);}else if (i == n - 1) {changenumber(a[n - 1]);changenumber(a[n-2]);changenumber(a[0]);}else {changenumber(a[i-1]);changenumber(a[i]);changenumber(a[i+1]);}
}void printnums(int a[],int n) {for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");
}void printstrings(string a[], int n) {for (int i = 0; i < n; i++) {printf("%s \n", a[i]);}
}int Finalnums(int a[],int flag[], int i, int j,int ido,int jdo,int n) {if (ido) {doback(a, i, n);flag[i] = 2;}else {flag[i] = 1;}if (jdo) {doback(a, j, n);flag[j] = 2;}else {flag[j] = 1;}j++;while (j < n) {if (a[j-1] == 0) {doback(a, j, n);flag[j] = 2;}else {flag[j] = 1;}j++;}j = 0;if (i == 0)return a[n-1];if (a[n - 1] == 0) {doback(a, j, n);flag[j] = 2;}else {flag[j] = 1;}j++;while (j < i) {if (a[j - 1] == 0) {doback(a, j, n);flag[j] = 2;}else {flag[j] = 1;}j++;}return a[j - 1];
}void resetnums(int a[], int n) {for (int i = 0; i < n; i++) {a[i] = 0;}
}
int main() {int a[8] = { 0 };int flag[8] = { 0 };if (Finalnums(a, flag, 0, 1, 0, 0, 8)) {printf("0不取,1不取就可以满足要求:");printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 1, 0, 8)) {printf("0取,1不取就可以满足要求:");printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 0, 1, 8)) {printf("0不取,1取就可以满足要求:");printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}if (Finalnums(a, flag, 0, 1, 1, 1, 8)) {printf("0取,1取就可以满足要求:");printnums(a, 8);printnums(flag, 8);resetnums(a, 8);resetnums(flag, 8);}
}

有明确思路都写了一小时,属实有点难度了
在这里插入图片描述

想了想,第二种真就随便想啊
依稀记得面试官说考察候选人智力,焯!

http://www.lryc.cn/news/301687.html

相关文章:

  • GB 18585-2023 壁纸中有害物质限量
  • 全面的ASP.NET Core Blazor简介和快速入门
  • HGAME 2024 WEEK2 Crypto WP
  • Postman轻松签名,让SHA256withRSA保驾护航!
  • C#面:简述装箱和拆箱
  • 【Kubernetes in Action笔记】1.快速开始
  • 踩坑实录(Fourth Day)
  • 【python】网络爬虫与信息提取--requests库
  • 洛谷 P8627 [蓝桥杯 2015 省 A] 饮料换购
  • Academic Inquiry|投稿状态分享(ACS,Wiley,RSC,Elsevier,MDPI,Springer Nature出版社)
  • 1+X运维试题样卷C卷(初级)
  • Spring学习笔记(二)Spring的控制反转(设计原则)与依赖注入(设计模式)
  • MySQL 基础知识(四)之表操作
  • 计算机网络——10FTP
  • javascript中的this指向
  • WebServer 之 http连接处理(下)
  • Android电量相关知识
  • 【Java多线程】线程中几个常见的属性以及状态
  • 鸿蒙OS跨进程IPC与RPC通信
  • Effective Objective-C 学习(三)
  • 蓝桥杯备赛攻略
  • react反向代理
  • 债券专题二:可转债估值-二叉树模型
  • 【闲谈】开源软件的崛起与影响
  • 【教程】Linux使用aria2c多线程满速下载
  • 【漏洞复现】蓝网科技临床浏览系统信息泄露漏洞
  • JSON转换List<Map<String, Object>>、Map<String, Object>
  • 单主模式和多主模式切换
  • petalinux2018.3安装步骤
  • ubuntu22.04下使用conda安装pytorch(cpu及gpu版本)