【C++刷题】优选算法——递归第二辑
- 全排列
vector<vector<int>> vv;
void dfs(vector<int>& nums, vector<int>& v, vector<bool>& check)
{if(v.size() == nums.size()){vv.push_back(v);return;}for(int i = 0; i < nums.size(); ++i){if(check[i] == false){v.push_back(nums[i]);check[i] = true;dfs(nums, v, check);// 回溯 -- 恢复现场v.pop_back();check[i] = false;}}
}
vector<vector<int>> permute(vector<int>& nums)
{vector<int> v;vector<bool> check(nums.size(), false);dfs(nums, v, check);return vv;
}
- 子集
// 解法一
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, int step)
{if(step == nums.size()){vv.push_back(v);return;}// 不选 nums[step]dfs(nums, step + 1);// 选 nums[step]v.push_back(nums[step]);dfs(nums, step + 1);v.pop_back();
}
vector<vector<int>> subsets(vector<int>& nums)
{dfs(nums, 0);return vv;
}// 解法二
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, int step)
{vv.push_back(v);for(int i = step; i < nums.size(); ++i){v.push_back(nums[i]);dfs(nums, i + 1);v.pop_back();}
}
vector<vector<int>> subsets(vector<int>& nums)
{dfs(nums, 0);return vv;
}
- 找出所有子集的异或总和再求和
int total = 0;
int val = 0;
void dfs(vector<int>& nums, int step = 0)
{total += val;for(int i = step; i < nums.size(); ++i){val ^= nums[i];dfs(nums, i + 1);val ^= nums[i];}
}
int subsetXORSum(vector<int>& nums)
{dfs(nums, 0);return total;
}
- 全排列 II
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& nums, vector<bool>& check)
{if(v.size() == nums.size()){vv.push_back(v);return;}for(int i = 0; i < nums.size(); ++i){if(check[i] == false){if(i == 0 || check[i-1] == true || nums[i-1] != nums[i]){v.push_back(nums[i]);check[i] = true;dfs(nums, check);check[i] = false;v.pop_back();}}}
}
vector<vector<int>> permuteUnique(vector<int>& nums)
{sort(nums.begin(), nums.end());vector<bool> check(nums.size(), false);dfs(nums, check);return vv;
}
- 电话号码的字母组合
unordered_map<char, string> m = {{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}
};
vector<string> vs;
string s;
void dfs(string& digits, int step)
{if(step == digits.size()){vs.push_back(s);return;}for(int i = 0; i < m[digits[step]].size(); ++i){s += m[digits[step]][i];dfs(digits, step + 1);s.pop_back();}
}
vector<string> letterCombinations(string digits)
{if(digits.size() == 0) return vs;dfs(digits, 0);return vs;
}
- 括号生成
vector<string> vs;
string s;
void dfs(int left, int right)
{if(right == 0){vs.push_back(s);return;}if(left > 0){s += "(";dfs(left - 1, right);s.pop_back();}if(right > left){s += ")";dfs(left, right - 1);s.pop_back();}
}
vector<string> generateParenthesis(int n)
{dfs(n, n);return vs;
}
- 组合
vector<vector<int>> vv;
vector<int> v;
void dfs(int n, int k, int step)
{if(v.size() == k){vv.push_back(v);return;}for(int i = step; i <= n; ++i){v.push_back(i);dfs(n, k, i + 1);v.pop_back();}
}
vector<vector<int>> combine(int n, int k)
{dfs(n, k, 1);return vv;
}
- 目标和
int ret = 0;
void dfs(vector<int>& nums, int target, int step, int sum)
{if(step == nums.size()){if(sum == target) ret += 1;return;}dfs(nums, target, step + 1, sum + nums[step]);dfs(nums, target, step + 1, sum - nums[step]);
}
int findTargetSumWays(vector<int>& nums, int target)
{dfs(nums, target, 0, 0);return ret;
}
- 组合总和
vector<vector<int>> vv;
vector<int> v;
void dfs(vector<int>& candidates, int target, int step, int sum)
{if(sum > target) return;if(sum == target){vv.push_back(v);return;}for(int i = step; i < candidates.size(); ++i){v.push_back(candidates[i]);dfs(candidates, target, i, sum + candidates[i]);v.pop_back();}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{dfs(candidates, target, 0, 0);return vv;
}
- 字母大小写全排列
vector<string> vs;
string path;
void dfs(string& s, int step)
{if(step == s.size()){vs.push_back(path);return;}path += s[step];dfs(s, step + 1);path.pop_back();if(s[step] >= 'a' && s[step] <= 'z'){path += toupper(s[step]);dfs(s, step + 1);path.pop_back();}else if(s[step] >= 'A' && s[step] <= 'Z'){path += tolower(s[step]);dfs(s, step + 1);path.pop_back();}
}
vector<string> letterCasePermutation(string s)
{dfs(s, 0);return vs;
}
- 优美的排列
int ret = 0;
void dfs(int n, int step, vector<bool>& check)
{if(step > n) ret += 1;for(int i = 1; i <= n; ++i){if(check[i] == false){if(i % step == 0 || step % i == 0){check[i] = true;dfs(n, step + 1, check);check[i] = false;}}}
}
int countArrangement(int n)
{vector<bool> check(n + 1, false);dfs(n, 1, check);return ret;
}
- N 皇后
vector<vector<string>> vvs;
void dfs(vector<string>& vs, vector<vector<bool>*>& check3, int step)
{if(step == vs.size()){vvs.push_back(vs);return;}for(int j = 0; j < vs.size(); ++j){if((*check3[0])[j] == false && (*check3[1])[step - j + vs.size() - 1] == false&& (*check3[2])[step+j] == false){(*check3[0])[j] = (*check3[1])[step - j + vs.size() - 1] = (*check3[2])[step+j] = true;vs[step][j] = 'Q';dfs(vs, check3, step + 1);vs[step][j] = '.';(*check3[0])[j] = (*check3[1])[step - j + vs.size() - 1] = (*check3[2])[step+j] = false;}}
}
vector<vector<string>> solveNQueens(int n)
{vector<string> vs(n);for(int i = 0; i < n; ++i)vs[i].append(n, '.');vector<vector<bool>*> check3 = {new vector<bool>(n, false),new vector<bool>(2 * n - 1, false),new vector<bool>(2 * n - 1, false)};dfs(vs, check3, 0);delete check3[0];delete check3[1];delete check3[2];return vvs;
}
- 解数独
vector<vector<bool>>* row = new vector<vector<bool>>(10, vector<bool>(10, false));
vector<vector<bool>>* col = new vector<vector<bool>>(10, vector<bool>(10, false));
vector<vector<vector<bool>>>* check = new vector<vector<vector<bool>>>(3, vector<vector<bool>>(3, vector<bool>(10, false)));
bool dfs(vector<vector<char>>& board)
{for(int i = 0; i < 9; ++i){for(int j = 0; j < 9; ++j){if(board[i][j] == '.'){for(int n = 1; n <= 9; ++n){if(!(*row)[i][n] && !(*col)[j][n] && !(*check)[i/3][j/3][n]){board[i][j] = '0' + n;(*row)[i][n] = (*col)[j][n] = (*check)[i / 3][j / 3][n] = true;if(dfs(board) == true) return true;board[i][j] = '.';(*row)[i][n] = (*col)[j][n] = (*check)[i / 3][j / 3][n] = false;}}return false;}}}return true;
}
void solveSudoku(vector<vector<char>>& board)
{for (int i = 0; i < 9; ++i){for (int j = 0; j < 9; ++j){if (board[i][j] != '.'){int num = board[i][j] - '0';(*row)[i][num] = (*col)[j][num] = (*check)[i / 3][j / 3][num] = true;}}}dfs(board);delete row;delete col;delete check;
}
- 单词搜索
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
// 循环 - 方式
bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visit, int i, int j, int step)
{if(step == word.size()) return true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < board.size())&& (y >= 0 && y < board[0].size())&& (visit[x][y] == false)&& (board[x][y] == word[step])){visit[x][y] = true;if(dfs(board, word, visit, x, y, step + 1)) return true;visit[x][y] = false;}}return false;
}
// 分支 - 方式
bool dfs(vector<vector<char>>& board, string& word, vector<vector<bool>>& visit, int i, int j, int step)
{if(step == word.size()) return true; if(i - 1 >= 0 && visit[i-1][j] == false && board[i-1][j] == word[step]){visit[i-1][j] = true;if(dfs(board, word, visit, i - 1, j, step + 1)) return true;visit[i-1][j] = false;}if(i + 1 < board.size() && visit[i+1][j] == false && board[i+1][j] == word[step]){visit[i+1][j] = true;if(dfs(board, word, visit, i + 1, j, step + 1)) return true;visit[i+1][j] = false;}if(j - 1 >= 0 && visit[i][j-1] == false && board[i][j-1] == word[step]){visit[i][j-1] = true;if(dfs(board, word, visit, i, j - 1, step + 1)) return true;visit[i][j-1] = false;}if(j + 1 < board[0].size() && visit[i][j+1] == false && board[i][j+1] == word[step]){visit[i][j+1] = true;if(dfs(board, word, visit, i, j + 1, step + 1)) return true;visit[i][j+1] = false;}return false;
}
bool exist(vector<vector<char>>& board, string word)
{vector<vector<bool>> visit = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), false));for(int i = 0; i < board.size(); ++i){for(int j = 0; j < board[0].size(); ++j){if(board[i][j] == word[0]){visit[i][j] = true;if(dfs(board, word, visit, i, j, 1)) return true;visit[i][j] = false;}}}return false;
}
- 黄金矿工
int ret = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int i, int j, int quantity)
{if(quantity > ret) ret = quantity;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (visit[x][y] == false)&& (grid[x][y] != 0)){visit[x][y] = true;dfs(grid, visit, x, y, quantity + grid[x][y]);visit[x][y] = false;}}
}
int getMaximumGold(vector<vector<int>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size(), false));for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] != 0){visit[i][j] = true;dfs(grid, visit, i, j, grid[i][j]);visit[i][j] = false;}}}return ret;
}
- 不同路径 III
int ret = 0;
int count = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit,
int i, int j, int step)
{if(grid[i][j] == 2){if(count == step) ret += 1;return;}for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (visit[x][y] == false)&& (grid[x][y] != -1)){visit[x][y] = true;dfs(grid, visit, x, y, step + 1);visit[x][y] = false;}}
}
int uniquePathsIII(vector<vector<int>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));int si, sj;for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] != -1) ++count;if(grid[i][j] == 1){si = i;sj = j;}}}visit[si][sj] = true;dfs(grid, visit, si, sj, 1);return ret;
}
相关文章:
【C++刷题】优选算法——递归第二辑
全排列 vector<vector<int>> vv; void dfs(vector<int>& nums, vector<int>& v, vector<bool>& check) {if(v.size() nums.size()){vv.push_back(v);return;}for(int i 0; i < nums.size(); i){if(check[i] false){v.push_ba…...

【GO基础】1. Go语言环境搭建
Go语言环境搭建 Go的三种安装方式Go标准包安装Windows 安装验证是否安装成功 4.Go的第一个程序 Hello World.go Go的三种安装方式 Go有多种安装方式,可以选择自己适合的。这里介绍三种最常见的安装方式: Go源码安装:这是一种标准的软件安装…...

Py之llama-parse:llama-parse(高效解析和表示文件)的简介、安装和使用方法、案例应用之详细攻略
Py之llama-parse:llama-parse(高效解析和表示文件)的简介、安装和使用方法、案例应用之详细攻略 目录 llama-parse的简介 llama-parse的安装和使用方法 1、安装 2、使用方法 第一步,获取API 密钥 第二步,安装LlamaIndex、LlamaParse L…...
Python库之Scrapy的高级用法深度解析
Python库之Scrapy的高级用法深度解析 引言 Scrapy是一个强大的Web爬虫框架,它提供了丰富的功能和灵活的扩展性,使得在Python中编写爬虫变得简单而高效。本文将深入探讨Scrapy的高级用法,帮助读者充分利用Scrapy的强大功能。 目录 引言Scr…...

Rust Tarui 中的 Scrcpy 客户端,旨在提供控制安卓设备的鼠标和按键映射,类似于游戏模拟器。
Scrcpy-mask 为了实现电脑控制安卓设备,本人使用 Tarui Vue 3 Rust 开发了一款跨平台桌面客户端。该客户端能够提供可视化的鼠标和键盘按键映射配置。通过按键映射实现了实现类似安卓模拟器的多点触控操作,具有毫秒级响应速度。该工具可广泛用于电脑控…...
【shell】脚本练习题
案例: 1. for ping测试指网段的主机 网段由用户输入,例如用户输入192.168.2 ,则ping 192.168.2.10 --- 192.168.2.20 UP: /tmp/host_up.txt Down: /tmp/host_down.txt 2. 使用case实现成绩优良差的判断 1. for ping测试指…...

微信小程序uniapp+django洗脚按摩足浴城消费系统springboot
原生wxml开发对Node、预编译器、webpack支持不好,影响开发效率和工程构建。所以都会用uniapp框架开发 前后端分离,后端给接口和API文档,注重前端,接近原生系统 使用Navicat或者其它工具,在mysql中创建对应名称的数据库࿰…...
超链接的魅力:HTML中的 `<a>` 标签全方位探索!
🌐超链接的魅力:HTML中的 标签全方位探索! 🏞️基础营地:认识 <a> 标签🛠️基本语法📚属性扩展 🚀实战演练:超链接的多样玩法🌈内链与外链Ὄ…...

与优秀者同行,“复制经验”是成功的最快捷径
富在术数不在劳身,利在局势不在力耕。我们始终相信,与优秀者同行,“复制经验”才是走向成功的最快“捷径”! 酷雷曼合作商交流会 作为酷雷曼合作商帮扶体系里的重要一环,合作商交流会是总部专门为合作商们搭建的一个博采众长、相…...

MobaXterm使用私钥远程登陆linux
秘钥的形式使用MobaXterm 远程连接 linux 服务器 MobaXterm使用私钥远程登陆linux just填写远程主机 不指定用户 勾选使用私钥 选择私钥即可 1.使用秘钥连接 远程linux 服务器的好处 只需要第一次添加秘钥,并输入密码后,以后再连接就不需要再输入密码…...

Java设计模式(23种设计模式 重点介绍一些常用的)
创建型模式,共五种:工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。结构型模式,共七种:适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。行为型模式,共十一种:…...

JVM(5):虚拟机性能分析和故障解决工具概述
1 工具概述 作为一个java程序员,最基本的要求就是用java语言编写程序,并能够在jvm虚拟机上正常运行,但是在实际开发过程中,我们所有的程序由于各种各样的原因,并不是总能够正常运行,经常会发生故障或者程序…...

vue3插槽solt 使用
背景增加组件的复用性,个人体验组件化还是react 方便。 Vue插槽solt如何传递具名插槽的数据给子组件? 一、solt 原理 知其然知其所以然 Vue的插槽(slots)是一种分发内容的机制,允许你在组件模板中定义可插入的内容…...
正则项学习笔记
目录 1. L2 正则化 岭回归 1.1 L2 norm计算例子 2. L1 正则化 3. 弹性网正则化 4. Dropout 1. L2 正则化 岭回归 在 PyTorch 中,L2 正则化通常通过设置优化器的 weight_decay 参数实现。以下是一个简单的例子: 介绍博文: 正则化(1)&a…...

Django自定义模板标签与过滤器
title: Django自定义模板标签与过滤器 date: 2024/5/17 18:00:02 updated: 2024/5/17 18:00:02 categories: 后端开发 tags: Django模版自定义标签过滤器开发模板语法Python后端前端集成Web组件 Django模板系统基础 1. Django模板语言概述 Django模板语言(DTL&…...

k8s集群安装后CoreDNS 启动报错plugin/forward: no nameservers found
安装k8s过程中遇到的问题: 基本信息 系统版本:ubuntu 22.04 故障现象: coredns 报错:plugin/forward: no nameservers found 故障排查: #检查coredns的配置,发现有一条转发到/etc/resolv.conf的配置…...

AI图片过拟合如何处理?答案就在其中!
遇到难题不要怕!厚德提问大佬答! 厚德提问大佬答8 你是否对AI绘画感兴趣却无从下手?是否有很多疑问却苦于没有大佬解答带你飞?从此刻开始这些问题都将迎刃而解!你感兴趣的话题,厚德云替你问,你解…...

0基础如何进入IT行业
目录 引言 一、了解IT行业 1.1 IT行业概述 1.2 IT行业的职业前景 二、选择适合的学习路径 2.1 自学 2.2 参加培训班 2.3 高等教育 三、学习基础技能 3.1 编程语言 3.2 数据结构与算法 3.3 计算机基础知识 四、实践与项目经验 4.1 开源项目 4.2 个人项目 4.3 实习…...

一键批量提取TXT文档前N行,高效处理海量文本数据,省时省力新方案!
大量的文本信息充斥着我们的工作与生活。无论是研究资料、项目文档还是市场报告,TXT文本文档都是我们获取和整理信息的重要来源。然而,面对成百上千个TXT文档,如何快速提取所需的关键信息,提高工作效率,成为了许多人头…...

Java-常见面试题收集(十六)
二十五 RocketMQ 1 消息队列介绍 消息队列,简称 MQ(Message Queue),它其实就指消息中间件,当前业界比较流行的开源消息中间件包括:RabbitMQ、RocketMQ、Kafka。(一个使用队列来通信的组件&…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...