LeetCodeDay05

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
• 数独部分填了数字，空的部分用 '.' 表示。

说明

• 一个有效的数独（填了一部分的）不一定是可解的，只要已经填的数字是有效的即可。

思路

1. 对于比价抽象的问题，采取拟人法求解。想想如果是人为来判断是如何进行的。一个数独要合理，需要的是3个条件，该行只有1-9，该列只有1-9，该数字所处小9宫格只有1-9。模拟人为判断的情形，转换过来就是该数这一行没有重复、这一列没有重复、小九宫格没有重复，则这一格是OK的。依次遍历每一格，都OK则数独是有效的。
2. 解法二则是利用空间换时间。避免了每个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;
  }
};