前言

這算是第一次做 LeetCode Weekly Contest 的紀錄，今天是心血來潮上來打，所以準備考的時候只剩下沒多少時間，但我還是菜雞，因此就專攻第一題試水溫，寫完後就停止

題目敘述

題目難度: Easy
題目敘述: 題目給定一個整數陣列 nums，並且需要先選定一個起始點 curr，其中 nums[curr] =0。從起始點可以選擇往左走或往右走，接著可以重複下面的步驟:

若 curr 超出範圍 [0, n-1] 則步驟停止
透過加減 curr 值來實現向左和向右移動，curr 增加: 向右移動，curr 減少: 向左移動
移動後一旦 nums[curr] > 0 則
- 需要將 nums[curr] 值減一
- 反轉當前的移動方向
- 朝新方向前進一步

當移動結束時，所有元素值都歸零則被視為 Valid，請回傳總共有幾種 Valid 的走法

解法

一開始的想法

首先會需要迭帶題目給的陣列 nums，並且需要找到起始點，可能會有多個起始點，接著就是要從起始點開始向左或向有走來判斷是否 valid，在走訪過程中，一旦碰到大於0的值就會開始反向走，直到碰到另一端的底端或是另一個大於零的值

我的解法

class Solution {
public:
    bool isValid(vector<int>nums, int start, bool direct){
        int n = nums.size();
        int curr = start;
        while(curr >=0 && curr < n) {
            if(nums[curr] ==0){
                if(direct) curr++;
                else curr--;
            }
            else{
                nums[curr]--;
                direct = !direct;
                if(direct) curr++;
                else curr--;
            }
        }
        for(auto it=nums.begin(); it!=nums.end(); ++it){
            if(*it !=0){
                return false;
            }
        }
        return true;
    }

    int countValidSelections(vector<int>& nums){
    
        //select starting position
        int n = nums.size();
        int found = 0;
        for(int i = 0; i< n;i++){
            if(nums[i]==0){
                if(isValid(nums,i,true)){
                    found++;
                }
                if(isValid(nums,i,false)){
                    found++;
                }
            }
        }
        return found;
    }
};

這裡拆開成兩個函數進行，主函數 countValidSelections 用迴圈先找起始點，找到起始點後，就會分別呼叫兩次函數 isValid 並且給定不同的方位。 isValid 函數中，會在 curr >=0 && curr < n 範圍中來回走訪不同元素，一旦碰到值為零的元素，則沿著原本方向繼續走訪，而如果碰到大於0的值，則將 nums[curr] 減掉一，並且反向繼續走一步。最後走訪完畢所有元素後，檢查所有元素是否都歸零，如果是，則為valid，否則為invalid。檢查完回到主函數後，如果路徑有效，則會將 found 變數增加一。之後在跑不同起始點後，就可以回傳變數 found 了。

執行結果

runtime 時間耗費就非常高了

複雜度

時間複雜度

$O(n^2)$

countValidSelections: 最多執行 $n$ 次，對於每個起始位置，isValid 會被呼叫兩次。isValid: while 迴圈在最壞狀況下會走訪整個陣列，因此為 $O(n)$，回傳前還會有個迴圈檢查是否每個元素都為 0。這也需要 $O(n)$ 。因此整體時間複雜度為 $2 \times (O(n) + O(n)) = O(4n) = O(n)$