1. 两数之和
描述
- 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
- 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例
- 给定 nums = [2, 7, 11, 15], target = 9
- 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路
1、暴力法，依次遍历，时间复杂度O(n^2)
2、通过一个Map来保存下标和值，然后遍历一次数组，找target-val的值，存在就找到了，时间复杂度O(n)，空间复杂度O(n)
class Solution_01_01 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
bool brk = false;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
result.push_back(i);
result.push_back(j);
brk = true;
break;
}
}
if (brk) break;
}
return result;
}
};
class Solution_01_02 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
if (hash.find(target - nums[i]) != hash.end()) {
result.push_back(hash[target - nums[i]]);
result.push_back(i);
break;
}
hash.insert({nums[i], i});
}
return result;
}
};
// 和上面思路相同，但实现起来更酷的一种写法
class Solution_01_03 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
if (m.count(target - nums[i])) {
return {i, m[target - nums[i]]};
}
m[nums[i]] = i;
}
return {};
}
};
36. 有效的数独
描述
- 判断一个数独是否有效，根据： Sudoku Puzzles - The Rules
- 数独部分填了数字，空的部分用 '.' 表示。
说明
- 一个有效的数独（填了一部分的）不一定是可解的，只要已经填的数字是有效的即可。
思路
- 对于比价抽象的问题，采取拟人法求解。想想如果是人为来判断是如何进行的。一个数独要合理，需要的是3个条件，该行只有1-9，该列只有1-9，该数字所处小9宫格只有1-9。模拟人为判断的情形，转换过来就是该数这一行没有重复、这一列没有重复、小九宫格没有重复，则这一格是OK的。依次遍历每一格，都OK则数独是有效的。
- 解法二则是利用空间换时间。避免了每个val都要把行列和小9宫格遍历一遍。利用一个set保存元素出现的次数。在遍历的时候对应位置+1，当其>1时返回false。先检查所有行，再检查所有列，最后检查9个小9宫格。
class Solution_36_01 {
public:
bool isValidSudoku(vector<vector<char>>& board) {
if (board.empty()) return false;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (!isValidVal(board, row, col)) return false;
}
}
return true;
}
bool isValidVal(vector<vector<char>>& board, int row, int col) {
char val = board[row][col];
// 这一列不能有val
for (int i = 1; i < 9; i++) {
char cur = board[(row + i) % 9][col];
if (cur != '.' && cur == val) return false;
}
// 这一行不能有val
for (int i = 1; i < 9; i++) {
char cur = board[row][(col + i) % 9];
if (cur != '.' && cur == val) return false;
}
// 小的九宫格不能有val
int startRow = row / 3 * 3;
int startCol = col / 3 * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int curRow = startRow + i;
int curCol = startCol + j;
char cur = board[curRow][curCol];
if (cur != '.' && cur == val && (curRow != row || curCol != col)) {
return false;
}
}
}
return true;
}
};
class Solution {
public:
bool isValidSudoku(const vector<vector<char>>& board) {
bool used[9];
for (int i = 0; i < 9; i++) {
// 检查行
fill(used, used + 9, false);
for (int j = 0; j < 9; j++) {
if (!check(board[i][j], used)) {
return false;
}
}
// 检查列
fill(used, used + 9, false);
for (int j = 0; j < 9; j++) {
if (!check(board[j][i], used)) {
return false;
}
}
}
// 检查9个子格子
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
fill(used, used + 9, false);
for (int row = i * 3; row < i * 3 + 3; row++) {
for (int col = j * 3; col < j * 3 + 3; col++) {
if (!check(board[row][col], used)) {
return false;
}
}
}
}
return true;
}
bool check(char ch, bool used[]) {
if (ch == '.') return true;
if (used[ch - '1']) return false;
return used[ch - '1'] = true;
}
};
