回溯问题:LeetCode #37
1
编程题
【STL中的Tuple容器】
在Python中,大家都知道tuple这个概念,是一个只读的元素容器,容器内的元素数据类型可以不同,而在CPP中大部分的容器只能储存相同数据类型的数据,而std::pair函数是为数不多的可以将两个不同类型的值放到一起。我们今天说的tuple是std::pair的推广,表示固定大小的异类值的汇集。 std::tuple是C++11标准开始提出的,其有很多用途,比如一个函数如果拥有多个不同类型的返回值,就可以直接返回一个tuple.不用再像以前一样,定义一个class或者struct保存结果进行返回那么麻烦了! 其使用的重要函数有:
使用Demo示例:
#include <tuple>
#include <iostream>
#include <string>
#include <stdexcept>
std::tuple<double, char, std::string> get_student(int id)
{
if (id == ) return std::make_tuple(3.8, 'A', "Lisa Simpson");
if (id == ) return std::make_tuple(2.9, 'C', "Milhouse Van Houten");
if (id == ) return std::make_tuple(1.7, 'D', "Ralph Wiggum");
throw std::invalid_argument("id");
}
int main()
{
auto student0 = get_student();
std::cout << "ID: 0, "
<< "GPA: " << std::get<>(student0) << ", "
<< "grade: " << std::get<>(student0) << ", "
<< "name: " << std::get<>(student0) << '\n';
double gpa1;
char grade1;
std::string name1;
std::tie(gpa1, grade1, name1) = get_student();
std::cout << "ID: 1, "
<< "GPA: " << gpa1 << ", "
<< "grade: " << grade1 << ", "
<< "name: " << name1 << '\n';
// C++17 结构化绑定, 不用定义变量,也不用使用tie函数
auto [ gpa2, grade2, name2 ] = get_student();
std::cout << "ID: 2, "
<< "GPA: " << gpa2 << ", "
<< "grade: " << grade2 << ", "
<< "name: " << name2 << '\n';
}
【LeetCode #37】解数独(Hard)
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
答案被标成红色。
Note: 给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的
解题思路:
官方的解答已经很好很清晰了,希望大家可以去看一下,主要思想为约束编程和回溯! 约束编程意思是当我们向未知位置填数时,就需要排除其所在行或者所在列以及所在子方格对该数字的使用!在程序中我们分别使用col_, row_, block_三个二维数组记录数字是否被使用,即如果数字使用了,所对应的位置为true。
回溯法意思是我们需要对每个未知位置进行递归求解,使用数字1-9依次进行尝试,如果在col_, row_, block_用到了该数字,则直接continue,否则我们从这个数字开始递归求解,如果不满足条件,则回溯,并初始化相应的状态,换另外一个数字进行递归!
我突然发现这个题目和某大厂的秋招题目很类似,那是一个扫雷问题,貌似是根据已知数字要找出几种放置雷的方式!不知大家有没有印象了!类似的题目还有洛谷P2327!
C++代码(带注解)
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
for (auto i = ; i < ; ++i) {
for (auto j = ; j < ; ++j) {
auto ch = board[i][j];
if (ch == '.') {
spaces_.emplace_back(i, j); // space_用于储存未知位置的行和列
} else {
const auto b = * (i / ) + (j / );
ch -= '1';
// 如果数独中有对应数字,则其所在的行,列,block均标记为true,即不可以再使用
row_[i][ch] = true;
col_[j][ch] = true;
block_[b][ch] = true;
}
}
}
solve(board, );
}
bool solve(vector<vector<char>>& board, const int pos) {
if (pos < spaces_.size()) {
//int x_, y_;
//std::tie (x_, y_) = spaces_.at(pos);
const auto& [x_, y_] = spaces_.at(pos);
const auto b = * (x_ / ) + (y_ / );
for (auto i = ; i < ; ++i) {
if (row_[x_][i] || col_[y_][i] || block_[b][i])
continue; // 如果数字使用过了,直接返回,否则使用该数字进行递归
board[x_][y_] = '1' + i;
row_[x_][i] = true;
col_[y_][i] = true;
block_[b][i] = true; // 使用i,并进行标记
if (solve(board, pos + )) { // 递归到下一个未知位置
return true;
}
board[x_][y_] = '.'; // 如果不满足条件,则回溯,恢复为原来的状态
row_[x_][i] = false;
col_[y_][i] = false;
block_[b][i] = false;
}
return false;
}
return true;
}
private:
bool row_[][] = {};
bool col_[][] = {};
bool block_[][] = {};
vector<tuple<int, int>> spaces_ = {};
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sudoku-solver
完