程序员面试金典笔记

水深无声 2023-07-13 03:42 11阅读 0赞

### 面试题01.01 判断字符串中字符是否唯一 ###

遇到题目，先想需要考虑的情况：

1.  字符串是ASCII字符串还是Unicode字符串？假设为ASCII。
2.  首先得有字符串长度判定，超出长度后直接false。

思路主要是使用**位向量**的方法。我们可以使用一个int类型的变量（下文用checker表示）来代替长度为26的bool数组。。假设这个变量占26个bit（在多数语言中，这个值一般不止26），那么我们可以把它看成000...00(26个0)，这26个bit对应着26个字符，对于一个字符c，检查对应下标的bit值即可判断是否重复。那么难点在于如何检查？这里我们可以通过位运算来完成。。首先计算出字符char离'a'这个字符的距离，即我们要位移的距离，用val表示，那么使用左移运算符1 << val则可以得到对应下标为1，其余下标为0的数，如字符char = 'c'，则得到的数为000...00100，将这个数跟checker做与运算，由于这个数只有一个位为1，其他位为0，那么与运算的结果中，其他位肯定是0，而对应的下标位是否0则取决于之前这个字符有没有出现过，若出现过则被标记为1，那么与运算的结果就不为0；若之前没有出现过，则对应位的与运算的结果也是0，那么整个结果也为0。对于没有出现过的字符，我们用或运算checker |= (1 << val)将对应下标位的值置为1。

class Solution {
    public:
        bool isUnique(string astr) {
            int record = 0;
            int move;
            for(auto i : astr)
            {
                move = i - 'a';
                if((record & (1 << move)) != 0)
                    return false;
                else
                {
                    record = record | (1 << move);
                }
            }
            return true;
        }
    };

### 面试题01.02 判定是否互为字符重排 ###

遇到题目，先想需要考虑的情况：

1.  是否区分大小写？假设区分。
2.  是否考虑空白字符？假设考虑。
3.  若两个字符串本身长度就不同，那肯定不行。

再想怎样就满足题意呢？**第一个思路**肯定就是排序后看是否相同，应该能想到。

class Solution {
    public:
        bool CheckPermutation(string s1, string s2) {
            sort(s1.begin(),s1.end());
            sort(s2.begin(),s2.end());
            if(s1 == s2)
                return true;
            return false;
        }
    };

**第二个思路**，就是创建一个数组，效果类似于散列表，将每个字符映射到其出现次数，具体来说就是，第一个字符串进来就加一，第二个进来就减一，若可以重排的话，应该是正好最后为0的。且一旦出现了负值，就直接终止了。

class Solution {
    public:
        bool CheckPermutation(string s1, string s2) {
            int asccii[128] = {0};
            int len1 = s1.size();
            int len2 = s2.size();
            if(len1!=len2)
                return false;
            for(int i=0;i<len1;i++) {
                asccii[s1[i]]++;
                asccii[s2[i]]--;
            }
            for(int i=0;i<128;i++)
                if(asccii[i]!=0)
                    return false;
            return true;
        }
    };

### 面试题01.03 ###

### 面试题01.04 回文排列 ###

这里的回文排列是指把一个字符串的字母进行重新排列后，可以组成回文串。若字符串是奇数个，得有一个字母出现一次，其余的出现两次；若是偶数个，则每个字符都得出现2次。

思路一：使用散列表来统计字符的个数，然后遍历散列表以便确定出现奇数次的字符不超过一个。O(N)。

思路二：直接计数

class Solution {
    public:
        bool canPermutePalindrome(string s) 
        {
            int numOfChars[128] = {0};
            for(int i = 0; i < s.size(); ++i)
            {
                numOfChars[s[i]] += 1;
            }
            int oddNum = 0;
            for(int i = 0; i < 128; ++i)
            {
                if(numOfChars[i] % 2 != 0)
                {
                    if(oddNum == 0)
                        oddNum += 1;
                    else
                        return false;
                }
            }
            return true;
        }
    };

思路三：判断一个数是否刚好有一个比特位为1，可以通过将其减1 的结果与该数本身进行与操作，如果其结果为0，则比特位中1 刚好出现一次。

class Solution {
    public:
        bool canPermutePalindrome(string s) {
            bitset<128> bits;
            for (char c : s){
                bits.flip(c);    //将第c+1位取反
            }
            return bits.none() || bits.count() == 1;
            //bit.none()返回是否没有1，bit.count()返回1的个数
        }
    };