原题

leetcode 3274 检查棋盘方格颜色是否相同

方法1

因为原题给出了棋盘的格式，所以我的想法是初始化棋盘，然后根据两个坐标访问即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
private:
    const string s1 = "01010101";
    const string s2 = "10101010";
    vector<string> grid;
    void init() {
        grid.resize(8, string(8, '0'));
        for (int i = 0; i < 8; i++) {
            grid[i] = i % 2 ? s1 : s2;
        }
    }
public:
    bool checkTwoChessboards(string coordinate1, string coordinate2) {
        init();
        return grid[coordinate1[0] - 'a'][coordinate1[1] - '0' - 1] ==
               grid[coordinate2[0] - 'a'][coordinate2[1] - '0' - 1];
    }
};

时间复杂度

  1. 使用了常数时间初始化棋盘，可以视作O(1)

空间复杂度

  1. 使用了常数量的空间存储棋盘，可以视作 O(1)

方法2

方法2 就很取巧了。棋盘的横坐标是a~h ascii即为97~104，纵坐标为1~8。 举几个例子：

  1. (a,1)为黑色，(a,2)为白色，后边交替……
  2. (b,1)为白色，(b,2)为黑色，后边交替……
  3. (c,1)为黑色，(c,2)为白色，后边交替……
  4. (d,1)为白色，(d,2)为黑色，后边交替…… 把横坐标使用ascii代替后
  5. (97,1)为黑色，(97,2)为白色，后边交替……
  6. (98,1)为白色，(98,2)为黑色，后边交替……
  7. (99,1)为黑色，(99,2)为白色，后边交替……
  8. (100,1)为白色，(100,2)为黑色，后边交替…… 总结规律： 如果横纵坐标奇偶性一致，为黑色，否则为白色
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    bool same(int a, int b) {
        if (a % 2 && b % 2)
            return true;
        else if (a % 2 == 0 && b % 2 == 0)
            return true;
        return false;
    }
public:
    bool checkTwoChessboards(string s, string t) {
        int s0 = toascii(s[0]);
        int s1 = s[1] - '0';
        int t0 = toascii(t[0]);
        int t1 = t[1] - '0';
        if (same(s0, s1) && same(t0, t1) || !same(s0, s1) && !same(t0, t1))
            return true;
        return false;
    }
};

时间复杂度

  1. O(1)

空间复杂度

  1. O(1)