前言

原文章：線性列舉(二) - 統計法入門

概念

線性列舉中，一個很常用的演算法就是對陣列中的元素進行統計，比如 : 統計陣列中的奇數的個數、統計陣列中是5的倍數的數的個數，方法都是類似，需要對陣列進行遍歷列舉，然后根據題目條件做相應的判斷，條件滿足則計入統計，計數器加一，

LeetCode 1295. 統計位數為偶數的數字

原題鏈接：1295. 統計位數為偶數的數字

代碼

class Solution {
public:

    bool IsEvenBit(int n)
    {
        int ans = 0;
        while (n)
        {
            n /= 10;
            ++ans;
        }
        return (ans % 2 == 0);
    }
    int findNumbers(vector<int>& nums)
    {
        int count = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (IsEvenBit(nums[i]))
            {
                ++count;
            }
        }
        return count;
    }
};

540. 有序陣列中的單一元素

原題鏈接：540. 有序陣列中的單一元素

分析

方法一 ：
因為陣列是有序的，所以我們直接遍歷一遍，每次讓條件 i+2，如果nums[i] 不等于nums[i + 1]，就找到了唯一元素，

方法二：
位運算：異或
因為一個資料對同一個資料異或兩次，最終結果不變，

方法1

int singleNonDuplicate(int* nums, int numsSize)
{
   if (numsSize < 2)
   {
       return nums[0];
   }

   for (int i = 0; i < numsSize - 1; i += 2)
   {
       if (nums[i] != nums[i + 1])
       {
           return nums[i];
       }
   }
    return nums[numsSize - 1];
}

方法二

int singleNonDuplicate(int* nums, int numsSize)
{
    int ans = 0;
   for (int i = 0; i < numsSize; ++i)
   {
       ans ^= nums[i];
   }
    return ans;
}

劍指 Offer 21. 調整陣列順序使奇數位于偶數前面

原題鏈接：劍指 Offer 21. 調整陣列順序使奇數位于偶數前面

方法1：首尾雙指標

 void Swap(int* a, int* b)
 {
     int temp = *a;
     *a = *b;
     *b = temp;
 }
int* exchange(int* nums, int numsSize, int* returnSize)
{
   int left = 0;
   int right = numsSize - 1;

   while(left < right)
   {
       if ((nums[left] & 1) == 1)
       {
           left++;
           continue;
       }
       if ((nums[right] & 1) == 0)
       {
           right--;
           continue;
       }
       Swap(&nums[left], &nums[right]);
   }

   *returnSize = numsSize;
   return nums;
}

方法2：快慢指標

 void Swap(int* a, int* b)
 {
     int temp = *a;
     *a = *b;
     *b = temp;
 }
int* exchange(int* nums, int numsSize, int* returnSize)
{
    int fast = 0;
    int low = 0;

    while (fast < numsSize)
    {
        if ((nums[fast] & 1) == 1)
        {
            Swap(&nums[low], &nums[fast]);
            low++;
        }
        fast++;
    }

    *returnSize = numsSize;
    return nums;
}

1991. 找到陣列的中間位置

原題鏈接：1991. 找到陣列的中間位置

分析

若要保證中間位置左右兩邊元素和相等，
那就需要一個等式：

左邊和 + 右邊和 + 中間位置值 = 總元素和

那如果要找到準確的中間位置，又需要
左邊和 == 右邊和

因此可推出公式

左邊和 * 2 + 中間位置值 = 總元素和

代碼

int findMiddleIndex(int* nums, int numsSize)
{
    if (NULL == nums) return -1;

    int sum = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        sum += nums[i];
    }

    int leftsum = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        if (leftsum*2 + nums[i] == sum)
        {
            return i;
        }
        leftsum += nums[i];
    }

    return -1;
}

724. 尋找陣列的中心下標

原題鏈接：724. 尋找陣列的中心下標

代碼

和上個題一樣的

int pivotIndex(int* nums, int numsSize)
{
    int total = 0;
    //總和
    for (int i = 0; i < numsSize; ++i)
    {
        total += nums[i];
    }

    int sum = 0;
    //total == nums[i] + sum + sum;
    for (int i = 0; i < numsSize; ++i)
    {
        if (total - nums[i] == sum * 2)
        {
            return i;
        }
        sum += nums[i];
    }
    return -1;
}

26. 洗掉有序陣列中的重復項

原題鏈接：26. 洗掉有序陣列中的重復項

分析

根據題目要求，原地修改陣列，回傳修改后的長度，

代碼

方法很妙

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize < 2)
    {
        return numsSize;
    }

    int n = 0;
    
    for (int i = 1; i < numsSize; ++i)
    {
        if (nums[n] != nums[i])
        {
            nums[++n] = nums[i];
        }
    }

    return n + 1;
}

1018. 可被 5 整除的二進制前綴

原題鏈接：1018. 可被 5 整除的二進制前綴

分析

注：圖片來自力扣

代碼

bool* prefixesDivBy5(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    if (nums == NULL) return NULL;

    bool* ans = (bool*)malloc(sizeof(bool) * numsSize);

    int tmp = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        tmp = ((tmp << 1) + nums[i]) % 5;
        
        ans[i] = tmp == 0;
    }

    return ans;
}

1015. 可被 K 整除的最小整數

原題鏈接：1015. 可被 K 整除的最小整數

代碼

int smallestRepunitDivByK(int k)
{
    if (k % 2 == 0 || k % 5 == 0)
        return -1;
    
    int i = 1;
    for (int n = 1; n % k != 0; ++i)
    {
        n %= k;
        n = n * 10 + 1;
    }

    return i;
}

課后習題

1869. 哪種連續子字串更長

原題鏈接：1869. 哪種連續子字串更長