Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

※ 引述《oin1104 (是oin的說)》之銘言：
: 題目 :
: 給你一串陣列
: 問你有多少子陣列
: 裡面的奇數剛好有k個
: 思路 :
: 第一眼看到就sliding window
: 可是我是傲嬌
: 所以我用hash+一點點前綴和的感覺去寫
: 先在紀錄裡找有沒有出現過now-k
: 加上他的數量
: 然後再記錄出現的奇數數量now
: 這樣就可以ㄌ

思路:
1.子陣列問題看起來很滑動窗口，每次把當前數字加入窗口，如果恰好有k個奇數就
  會產生 (窗口第一個奇數 - 左邊第一個偶數 + 1) 個 nice 子陣列，把他加總。

2.如果超過 k 個奇數就一直pop直到奇數數量等於k，然後找出新窗口的第一個
  奇數位置。

java code
------------------------------------------------
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int res = 0;
        int odd = 0;
        int first = getNext(nums, 0);
        int j = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                odd++;
            }
            if (odd > k) {
                while (odd > k) {
                    odd -= nums[j++] % 2 == 1 ? 1 : 0;
                }
                first = getNext(nums, first + 1);
            }
            if (odd == k) {
                res += (first - j + 1);
            }
        }
        return res;
    }

    private int getNext(int[] nums, int from) {
        for (int i = from; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                return i;
            }
        }
        return 0;
    }
}
------------------------------------------------

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719038830.A.E8B.html
推 oin1104: 大師