只出现一次的数字

这题不难，利用了异或运算，比较巧妙。

class Solution {
public:
    int singleNumber(vector<int>& v) {
        int x = 0;
        for (auto &&i : v) {
            x ^= i;
        }
        return x;
    }
};

859. 亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

我开始的思路是遍历，遇到不同就 counter++，看 counter = 2 或 0. 发现不行，太天真了。比如 abm bc。

错误方法：

class Solution {
 public:
  bool buddyStrings(string s, string goal) {
    if (s.size() != goal.size() || s.size() <= 1) {
      return false;
    }
    vector<int> delta(s.size());
    char c[2];
    int diff = 0;
    int sum = 0;
    for (int i = 0; i < s.size(); i++) {
      delta[i] = s[i] - goal[i];
      sum += s[i] - goal[i];
      if (delta[i] != 0) {
        diff++;
        c[i % 2] = s[i];
      }
    }
    if (sum != 0) {
      cout << "sum != 0" << endl;
      return false;
    }
    if (diff == 1 || diff > 2) {
      cout << "diff == 1 || diff > 2" << endl;
      return false;
    }
    if (c[0] != c[1]) {
      cout << "c[0] != c[1]" << endl;
      return false;
    }

    print_vec(delta);
    return true;
  }
};

关键在于怎么处理相同时，能否交换。看了下答案原来是直接存表（Unicode：你礼貌吗？）

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        int cnt = 0;
        if (s.size() != goal.size()) return false;

        int diff1 = -1; // 第一次不同的位置
        int diff2 = -1; // 第二次不同的位置
        int chars[26];
        memset(chars, 0, sizeof(chars));
        bool valid_no_diff = false;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != goal[i]) {
                cnt++;
                if (cnt > 2) return false;
                if (cnt == 1) diff1 = i;
                if (cnt == 2) diff2 = i;
            }
            chars[s[i]-'a']++;
            if (chars[s[i] - 'a'] >= 2) valid_no_diff = true;
        }

        if (cnt == 0 && valid_no_diff) return true; // 两个串一摸一样，需要有两个以上相同字母出现
        if (cnt == 2 && s [diff1] == goal [diff2] && s [diff2] == goal [diff1]) return true; // 两个串有两个位置不同，需要正好可以互换

        return false;
    }
};

20. 有效的括号

我最喜欢写自动机了（

class Solution {
 public:
  bool isValid(string s) {
    stack<char> stk;
    for (int i = 0; i < s.size(); i++) {
      switch (s[i]) {
        case '(':
        case '{':
        case '[':
          stk.push(s[i]);
          break;
        default:
          if(stk.empty()) return false;
          auto top = stk.top();          
          auto exp = top == '('
                         ? ')'
                         : (top == '[' ? ']' : (top == '{' ? '}' : '\0'));
          if (s[i] != exp) {
            printf("%c got %c\n", exp, s[i]);
            return false;
          }
          stk.pop();
          break;
      }
    }
    if(!stk.empty()) return false;
    return true;
  }
};