1. 兩數(shù)之和

描述

• 給定一個整數(shù)數(shù)組和一個目標值，找出數(shù)組中和為目標值的兩個數(shù)。
• 你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

示例

• 給定 nums = [2, 7, 11, 15], target = 9
• 因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

思路

1、暴力法，依次遍歷，時間復(fù)雜度O(n^2)
2、通過一個Map來保存下標和值，然后遍歷一次數(shù)組，找target-val的值，存在就找到了，時間復(fù)雜度O(n)，空間復(fù)雜度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;
  }
};

// 和上面思路相同，但實現(xiàn)起來更酷的一種寫法
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. 有效的數(shù)獨

描述

• 判斷一個數(shù)獨是否有效，根據(jù)： Sudoku Puzzles - The Rules
• 數(shù)獨部分填了數(shù)字，空的部分用 '.' 表示。

說明

• 一個有效的數(shù)獨（填了一部分的）不一定是可解的，只要已經(jīng)填的數(shù)字是有效的即可。

思路

1. 對于比價抽象的問題，采取擬人法求解。想想如果是人為來判斷是如何進行的。一個數(shù)獨要合理，需要的是3個條件，該行只有1-9，該列只有1-9，該數(shù)字所處小9宮格只有1-9。模擬人為判斷的情形，轉(zhuǎn)換過來就是該數(shù)這一行沒有重復(fù)、這一列沒有重復(fù)、小九宮格沒有重復(fù)，則這一格是OK的。依次遍歷每一格，都OK則數(shù)獨是有效的。
2. 解法二則是利用空間換時間。避免了每個val都要把行列和小9宮格遍歷一遍。利用一個set保存元素出現(xiàn)的次數(shù)。在遍歷的時候?qū)?yīng)位置+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;
  }
};