2023每日刷題（二）

Leetcode—137.只出現(xiàn)一次的數(shù)字II

沒有滿足空間復(fù)雜度的Map題解

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int>count;
        for(int iter: nums) {
            ++count[iter];
        }
        int ans = 0;
        for(auto [iter, cnt]: count) {
            if(cnt == 1) {
                // return iter;
                ans = iter;
                break;
            }
        }
        return ans;
    }
};

常規(guī)題解——位運(yùn)算做法

實(shí)現(xiàn)代碼

int singleNumber(int* nums, int numsSize){
    int i, j;
    int opt[32] = {0};
    for(i = 0; i < numsSize; i++) {
        for(j = sizeof(int) * 8 - 1; j >= 0 ; j--) {
            opt[j] += nums[i] & 1;
            nums[i] >>= 1;
        }
    }
    int k = 0;
    unsigned int res = (unsigned int)0;
    for(; k < sizeof(int) * 8; k++) {
        res <<= 1;
        res |= opt[k] % 3;
    }
    return res;
}

為什么要用unsigned int呢，因?yàn)榛蜃笠埔绯鰣?bào)錯(cuò)，例如，
Line 13: Char 13: runtime error: left shift of 2147483646 by 1 places cannot be represented in type ‘int’ [solution.c]

左移的高位如果超過符號(hào)位，就會(huì)報(bào)錯(cuò)。因此要用類型強(qiáng)制轉(zhuǎn)換來unsigned來接住。

提交結(jié)果

有限狀態(tài)自動(dòng)機(jī)FSM+位運(yùn)算法

解題思想

參考的是這兩位大佬的博客，一個(gè)是k神





還有靈茶山艾府大神的，很有啟發(fā)！

實(shí)現(xiàn)代碼

int singleNumber(int* nums, int numsSize){
    int a = 0, b = 0;
    int i;
    int tmp = a;
    for(i = 0; i < numsSize; i++) {
        a = (a ^ nums[i]) & (a | b);
        b = (b ^ nums[i]) & ~tmp;
        tmp = a;
    }
    return b;
}

提交結(jié)果

變式題

這一題還可以繼續(xù)擴(kuò)展，在數(shù)組中每個(gè)元素都出現(xiàn) 5 次，找出只出現(xiàn) 1 次的數(shù)。那該怎么做呢？思路還是一樣的，模擬一個(gè)五進(jìn)制，5 次就會(huì)消除。

int singleNumber(int* nums, int numsSize){
    int i, a, b, c, tmpa, tmpb, tmpc;
    a = 0;
    b = 0;
    c = 0;
    for(i = 0; i < numsSize; i++) {
        tmpa = a;
        tmpb = b;
        tmpc = c;
        a = (a ^ nums[i]) & (b & c);
        b = ((b ^ nums[i]) ^ (~(tmpa | c))) & (~tmpa);
        c = (c ^ nums[i]) & (~tmpa);
    }
    return c;
}

int main()
{
    int x;
    int arr[11] = {9, 9, 9, 9, 9, 5, 3, 3, 3, 3, 3};
    x = singleNumber(arr, 11);
    printf("%d\n", x);
}

之后我會(huì)持續(xù)更新，如果喜歡我的文章，請(qǐng)記得一鍵三連哦，點(diǎn)贊關(guān)注收藏，你的每一個(gè)贊每一份關(guān)注每一次收藏都將是我前進(jìn)路上的無限動(dòng)力 ?。。〃I(▔▽▔)↗感謝支持！文章來源地址http://www.zghlxwxcb.cn/news/detail-723544.html

到了這里，關(guān)于Leetcode—137.只出現(xiàn)一次的數(shù)字II【中等】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！