确定有限状态自动机
只出现一次的数字1
LeetCode 136
观察每一个位，如果某一个位上1的个数是奇数，说明那个出现一次的这个数的二进制在这个位上是1，否则位0.根据这条规则我们就可以设计一个确定有限状态自动机。用二进制 K K K表示当前的状态，状态转移如下：
遇到 0 0 0不改变当前状态，遇到 1 1 1转移到下一个状态。
有了状态，现在该想想如何用二进制运算表示状态转移了。
我们知道异或运算符，一个操作数为 0 0 0的时候，结果还是另一个操作数，一个操作数为 1 1 1的时候，结果是另一个操作数的取反，正好符合我们的运算要求，因此我们就使用异或操作运算符即可。
class Solution
{
public:
int singleNumber(vector<int> &nums)
{
int k = 0;
for (auto it = nums.begin(); it != nums.end(); ++it)
{
k ^= *it;
}
return k;
}
};
只出现一次的数字2
LeetCode 137
同理上面的题，也是查看每一位，这一位上 1 1 1的个数对 3 3 3的余数定义为状态，如果余数是 1 1 1那么就说明出现一次的数字的二进制上这个位 1 1 1，否则是 0 0 0，因此状态机如下：
class Solution
{
public:
int singleNumber(vector<int> &nums)
{
int one = 0;
int two = 0;
for (int i : nums)
{
one = ((~one & ~two) & i) | (one & ~i);
two = ((~one & ~two) & i) | (two & ~i);
}
return one;
}
};
只出现一次的数字3
LeetCode 260
这题需要用到分类的思想，关键是怎么把两个数分开，对全体元素进行异或，结果上如果某一个位是 1 1 1，那么有一个数在这一位上必定是 1 1 1，因此参照这一条原则将 a b ab ab分开即可，对两组分布异或得到结果。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
long long xo = 0;
for(int i : nums) xo ^= i;
xo &= -xo;
long long a = 0;
long long b = 0;
for(int i : nums)
{
if(i & xo) a ^= i; else b ^= i;
}
vector<int> ans;
ans.push_back(a);
ans.push_back(b);
return ans;
}
};
判断是否为有效的数字
LeetCode 65
列出状态转移图。
函数指针写法：
#define NUM \
case '0': \
case '1': \
case '2': \
case '3': \
case '4': \
case '5': \
case '6': \
case '7': \
case '8': \
case '9'
#define E \
case 'e': \
case 'E'
#define OP \
case '+': \
case '-'
#define ED \
default: \
return 9;
#define DOT case '.'
typedef int (*SFP)(char);
int SFP0(char input)
{
switch (input)
{
DOT:
return 8;
OP:
return 1;
NUM:
return 2;
ED
}
}
int SFP1(char input)
{
switch (input)
{
DOT:
return 8;
NUM:
return 2;
ED
}
}
int SFP2(char input)
{
switch (input)
{
DOT:
return 3;
NUM:
return 2;
E:
return 5;
ED
}
}
int SFP3(char input)
{
switch (input)
{
NUM:
return 4;
E:
return 5;
ED
}
}
int SFP4(char input)
{
switch (input)
{
NUM:
return 4;
E:
return 5;
ED
}
}
int SFP5(char input)
{
switch (input)
{
NUM:
return 7;
OP:
return 6;
ED
}
}
int SFP6(char input)
{
switch (input)
{
NUM:
return 7;
ED
}
}
int SFP7(char input)
{
switch (input)
{
NUM:
return 7;
ED
}
}
int SFP8(char input)
{
switch (input)
{
NUM:
return 4;
ED
}
}
class Solution
{
public:
bool isNumber(string s)
{
SFP sfps[] = {SFP0, SFP1, SFP2, SFP3, SFP4, SFP5, SFP6, SFP7, SFP8};
int curr = 0;
for (int i = 0; i < s.size(); i++)
{
curr = (*sfps[curr])(s[i]);
if (curr == 9)
return false;
}
return curr == 2 || curr == 4 || curr == 3 || curr == 7;
}
};
数组状态图法：
class Solution {
public:
enum State {
STATE_INITIAL,
STATE_INT_SIGN,
STATE_INTEGER,
STATE_POINT,
STATE_POINT_WITHOUT_INT,
STATE_FRACTION,
STATE_EXP,
STATE_EXP_SIGN,
STATE_EXP_NUMBER,
STATE_END
};
enum CharType {
CHAR_NUMBER,
CHAR_EXP,
CHAR_POINT,
CHAR_SIGN,
CHAR_ILLEGAL
};
CharType toCharType(char ch) {
if (ch >= '0' && ch <= '9') {
return CHAR_NUMBER;
} else if (ch == 'e' || ch == 'E') {
return CHAR_EXP;
} else if (ch == '.') {
return CHAR_POINT;
} else if (ch == '+' || ch == '-') {
return CHAR_SIGN;
} else {
return CHAR_ILLEGAL;
}
}
bool isNumber(string s) {
unordered_map<State, unordered_map<CharType, State>> transfer{
{
STATE_INITIAL, {
{CHAR_NUMBER, STATE_INTEGER},
{CHAR_POINT, STATE_POINT_WITHOUT_INT},
{CHAR_SIGN, STATE_INT_SIGN}
}
}, {
STATE_INT_SIGN, {
{CHAR_NUMBER, STATE_INTEGER},
{CHAR_POINT, STATE_POINT_WITHOUT_INT}
}
}, {
STATE_INTEGER, {
{CHAR_NUMBER, STATE_INTEGER},
{CHAR_EXP, STATE_EXP},
{CHAR_POINT, STATE_POINT}
}
}, {
STATE_POINT, {
{CHAR_NUMBER, STATE_FRACTION},
{CHAR_EXP, STATE_EXP}
}
}, {
STATE_POINT_WITHOUT_INT, {
{CHAR_NUMBER, STATE_FRACTION}
}
}, {
STATE_FRACTION,
{
{CHAR_NUMBER, STATE_FRACTION},
{CHAR_EXP, STATE_EXP}
}
}, {
STATE_EXP,
{
{CHAR_NUMBER, STATE_EXP_NUMBER},
{CHAR_SIGN, STATE_EXP_SIGN}
}
}, {
STATE_EXP_SIGN, {
{CHAR_NUMBER, STATE_EXP_NUMBER}
}
}, {
STATE_EXP_NUMBER, {
{CHAR_NUMBER, STATE_EXP_NUMBER}
}
}
};
int len = s.length();
State st = STATE_INITIAL;
for (int i = 0; i < len; i++) {
CharType typ = toCharType(s[i]);
if (transfer[st].find(typ) == transfer[st].end()) {
return false;
} else {
st = transfer[st][typ];
}
}
return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;
}
};