这个系列好像都是简单题...有点没有挑战性~

1822. Sign of the Product of an Array

Analysis

这个题如果直接算，会溢出。实际上，并没有算出来的必要，用负数的个数就可以来判断最终结果是否为负。

Code

class Solution {
public:
    int arraySign(vector<int>& nums) {
        int negative = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) return 0;
            else if(nums[i] < 0) negative++;
        }
        return negative % 2 == 1 ? -1 : 1;
    }
};

话说回来，还是 WA 了一次，还是看题仔细一点啊。

1502. Can Make Arithmetic Progression From Sequence

Analysis

一开始没看懂 arithmetic progression，看了用例才知道，原来是等差数列的意思。也就是说，题目意思就是判断给定数字序列是否构成一个等差数列。这样的话，直接排序然后逐个判断就行了。

Code

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = arr[0] - arr[1];
        for(int i = 1; i < arr.size() - 1; i++) {
            if(diff != arr[i] - arr[i + 1]) return false;
        }
        return true;
    }
};

202. Happy Number

Analysis

这个题目名字有点喜感...
题目有 PAT 的味道了。
按照题目的意思，对于每一个数字而言，如果是快乐数，那么最终会变成 1；如果不是快乐数，那么最终会无限循环下去。那么，应该如何判断陷入无限循环中了呢？

Code

method 1

要判断陷入无限循环，可以借助哈希表，只要出现过的数字又一次出现了，那么一定说明这个数不是快乐数。

class Solution {
public:
    bool isHappy(int n) {
        int now;
        set<int> ht;
        while(1) {
            now = 0;
            while(n) {
                now += pow(n % 10, 2);
                n /= 10;
            }
            if(now == 1) return true;
            if(ht.find(now) != ht.end()) break;
            ht.insert(now);
            n = now;
        }
        return false;
    }
};

method 2

既然知道了会陷入循环，而且题目又给出了一个循环的例子，大可以看看循环中的数都是些什么。按照 $n=2$ 输入后，最后会得到：$4, 16, 37, 58, 89, 145, 42, 20, 4,...$ 的循环。也就是说，非快乐数最终会陷入这样的无限循环中。这样，我们就可以设置两个指针来解决这个问题。

/* method 2 */
class Solution {
public:
    int getnumber(int n) {
        int ret = 0;
        while(n) {
            int d = n % 10;
            n /= 10;
            ret += d * d;
        }
        return ret;
    }
    bool isHappy(int n) {
        int slow = n, fast = getnumber(n);
        while(fast != 1 && slow != fast) {
            slow = getnumber(slow);
            fast = getnumber(getnumber(fast));
        }
        return fast == 1;
    }
};

因为最终陷入循环的数字序列是固定的（也可以把这个数字序列看出是循环的），所以 slow 跟 fast 一定会相遇。

method 3

有了上面的过程，就可以直接设置一个固定的哈希表，如果算到这些数字了，直接返回 false 即可。

class Solution {
public:
    unordered_set<int> numbers {4, 16, 37, 58, 89, 145, 42, 20};
    int getnumber(int n) {
        int ret = 0;
        while(n) {
            int d = n % 10;
            n /= 10;
            ret += d * d;
        }
        return ret;
    }
    bool isHappy(int n) {
        int now;
        while(n != 1) {
            now = getnumber(n);
            if(numbers.find(now) != numbers.end()) return false;
            n = now;
        }
        return true;
    }
};

1790. Check if One String Swap Can Make Strings Equal

Analysis

题意比较简单，只要能通过不超过 1 次交换得到两个相同的字符串，就返回 true，所以直接模拟就可以了。

Code

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        if(s1.length() != s2.length()) return false;
        vector<int> index;
        for(int i = 0; i < s1.length(); i++) {
            if(s1[i] != s2[i]) index.push_back(i);
            if(index.size() == 2) break;
        }
        if(index.size() == 0) return true;
        else if(index.size() == 1) return false;
        swap(s2[index[0]], s2[index[1]]);
        return s1 == s2;
    }
};

Summary

简单题想要直接 AC 也需要费一点功夫啊。今天的第三个题，其实后面的 2 种做法就不是那么的简单，但是在性能上是更优秀的，这就是凸显技术能力强弱的地方了，所以，要好好把握。