138 lines
2.7 KiB
C++
138 lines
2.7 KiB
C++
#include "¾ØÕó.h"
|
|
|
|
#include <set>
|
|
|
|
bool ¾ØÕó::isValidSudoku(vector<vector<char>>& board) {
|
|
if (board.empty() || board.size() != 9 || board[0].size() != 9)\
|
|
return false;
|
|
|
|
set<char> row, col, pos;
|
|
for (int i = 0; i < board.size(); i++) {
|
|
for (int j = 0; j < board[0].size(); j++) {
|
|
if (board[i][j] == '.')
|
|
continue;
|
|
int value = i * 10 + board[i][j];
|
|
if (row.count(value)) {
|
|
return false;
|
|
}
|
|
row.insert(value);
|
|
|
|
value = j * 10 + board[i][j];
|
|
if (col.count(value))
|
|
return false;
|
|
col.insert(value);
|
|
|
|
value = ((i / 3) * 3 + (j / 3)) * 10 + board[i][j];
|
|
if (pos.count(value))
|
|
return false;
|
|
pos.insert(value);
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
vector<int> ¾ØÕó::spiralOrder(vector<vector<int>>& matrix) {
|
|
vector<int> vec;
|
|
if (matrix.size() == 0)
|
|
return vec;
|
|
int minX = 0, minY = 0, maxX = matrix[0].size() - 1, maxY = matrix.size() - 1;
|
|
int x = -1, y = 0;
|
|
|
|
while (true)
|
|
{
|
|
if (x >= maxX)
|
|
break;
|
|
while (x < maxX) {
|
|
vec.push_back(matrix[y][++x]);
|
|
}
|
|
minY++;
|
|
if (y >= maxY)
|
|
break;
|
|
while (y < maxY) {
|
|
vec.push_back(matrix[++y][x]);
|
|
}
|
|
maxX--;
|
|
if (x <= minX)
|
|
break;
|
|
while (x > minX) {
|
|
vec.push_back(matrix[y][--x]);
|
|
}
|
|
maxY--;
|
|
if (y <= minY)
|
|
break;
|
|
while (y > minY) {
|
|
vec.push_back(matrix[--y][x]);
|
|
}
|
|
minX++;
|
|
}
|
|
return vec;
|
|
}
|
|
|
|
void ¾ØÕó::setZeroes(vector<vector<int>>& matrix) {
|
|
set<int> x, y;
|
|
for (int i = 0; i < matrix.size(); i++) {
|
|
for (int j = 0; j < matrix[0].size(); j++) {
|
|
if (matrix[i][j] == 0) {
|
|
if (x.find(j) == x.end())
|
|
x.insert(j);
|
|
if (y.find(i) == y.end())
|
|
y.insert(i);
|
|
}
|
|
}
|
|
}
|
|
for(auto it : x)
|
|
{
|
|
for (int i = 0; i < matrix.size(); i++)
|
|
matrix[i][it] = 0;
|
|
}
|
|
for (auto it : y)
|
|
{
|
|
for (int i = 0; i < matrix[0].size(); i++)
|
|
matrix[it][i] = 0;
|
|
}
|
|
}
|
|
|
|
void ¾ØÕó::gameOfLife(vector<vector<int>>& board) {
|
|
vector<vector<int>> vec = board;
|
|
int rows = vec[0].size();
|
|
for (int i = 0; i < vec.size(); i++) {
|
|
for (int j = 0; j < vec[0].size(); j++) {
|
|
int live = 0;
|
|
if (i > 0) {
|
|
if (j > 0) {
|
|
if (vec[i - 1][j - 1] == 1)
|
|
live++;
|
|
}
|
|
if (vec[i - 1][j] == 1)
|
|
live++;
|
|
if (j < rows - 1) {
|
|
if (vec[i - 1][j + 1] == 1)
|
|
live++;
|
|
}
|
|
}
|
|
if (j > 0 && vec[i][j - 1] == 1)
|
|
live++;
|
|
if (j < rows - 1 && vec[i][j + 1] == 1)
|
|
live++;
|
|
if (i < vec.size() - 1) {
|
|
if (j > 0) {
|
|
if (vec[i + 1][j - 1] == 1)
|
|
live++;
|
|
}
|
|
if (vec[i + 1][j] == 1)
|
|
live++;
|
|
if (j < rows - 1) {
|
|
if (vec[i + 1][j + 1] == 1)
|
|
live++;
|
|
}
|
|
}
|
|
|
|
// »îϸ°û£¬Ö»ÓÐÖܱßÁ½Èý¸ö»î²ÅÄÜ»î
|
|
if (board[i][j] == 1 && live != 2 && live != 3)
|
|
board[i][j] = 0;
|
|
// ËÀϸ°û£¬ÖܱßÈý¸ö»îÔòÒ²»î
|
|
if (board[i][j] == 0 && live == 3)
|
|
board[i][j] = 1;
|
|
}
|
|
}
|
|
} |