###### tags: `Weekly Contest`
# Weekly Contest 337

## [2595. Number of Even and Odd Bits](https://leetcode.com/problems/number-of-even-and-odd-bits/) (<font color=#00B8A3>Easy</font>)

### Solution

#### 時間複雜度: ***O(logn)***

#### 空間複雜度: ***O(1)***

程式碼:

class Solution {
public:
    vector<int> evenOddBit(int n) {
        vector<int>ans = {0,0};
        int counter = 0;
        while(n>0)
        {
            counter ++;
            if(n%2)
            {
                if(counter%2)
                    ans[0]++;
                else
                    ans[1]++;
            }
            n/=2;
        }
        return ans;
    }
};

## [2596. Check Knight Tour Configuration](https://leetcode.com/problems/check-knight-tour-configuration/) (<font color=#FFC011>Medium</font>)

### Solution 1

#### 時間複雜度 ***O(n^4)***

#### 空間複雜度 ***O(1)***
超白癡的暴力法，時間複雜度很可怕，但我看了測資範圍很小(<=7)，故我就直接暴力了，我們請dfs的同學來講解好了。

程式碼:

class Solution
{
public:
    bool checkValidGrid(vector<vector<int>>& grid)
    {
        int i=0;
        int j=0;
        int c=1;
        bool ans=true;
        while(1)
        {
            for(int x=0; x<grid.size(); x++)
            {
                for(int y=0; y<grid[x].size(); y++)
                {
                    if(grid[x][y]==c)
                    {
                        if(x==i+2&&y==j+1)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i+2&&y==j-1)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i-2&&y==j+1)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i-2&&y==j-1)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i+1&&y==j-2)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i-1&&y==j-2)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i+1&&y==j+2)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else if(x==i-1&&y==j+2)
                        {
                            i=x;
                            j=y;
                            c++;
                        }
                        else
                        {
                            cout<<i<<' '<<j<<' '<<c<<endl;
                            ans=false;
                            return ans;
                        }
                    }
                }
            }
            if(c==grid.size()*grid.size())
                return true;

        }
    }
};

### Solution 2
先去找 0 的位子在哪，再沿著他開始順著走，順著走完就返回true，走不完就返回 false。

class Solution
{
public:
    bool checkValidGrid(vector<vector<int>>& grid)
    {
        int nowNumber = 1;
        int gSize = grid.size();
        int maxNumber = gSize*gSize - 1;
        int x = 0, y = 0;

        for (int i = 0; i < gSize; i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == 0)
                {
                    x = i;
                    y = j;
                }
            }
        }

        while (nowNumber <= maxNumber)
        {
            // 1
            vector<int> temp_x = { x + 1, x + 2, x + 2, x + 1, x - 1, x - 2, x - 2, x - 1 };
            vector<int> temp_y = { y + 2, y + 1, y - 1, y - 2, y - 2, y - 1, y + 1, y + 2 };
            bool controller = true;
          for (int i = 0; i < 8; i++)
            {
                int xx = temp_x[i];
                int yy = temp_y[i];
                if (xx >= 0 && xx < gSize && yy >= 0 && yy < gSize && grid[yy][xx] == nowNumber)
                {
                    x = xx;
                    y = yy;
                    nowNumber++;
                    controller = false;
                    break;
                }
            }
            if (controller == true)
            {
                cout << nowNumber << endl;
                return false;
            }
        }
        return true;
    }
};

## [2597. The Number of Beautiful Subsets ](https://leetcode.com/problems/the-number-of-beautiful-subsets/)(<font color=#FFC011>Medium</font>)
### 限制
>1 <= nums.length <= 20
1 <= nums[i], k <= 1000

### Solution
因n非常小，所以使用 dfs+backtracking 的方式去暴力搜尋所有的可能。
#### 時間複雜度 : ***O(2^n)***

#### 空間複雜度 : ***O(n)***

程式碼:

class Solution {
public:
    int ans;
    map<int, int> mp;
    void dfs(int idx, vector<int> &nums, int &k){
        //cout<<idx<<"\n";
        ans++;
        mp[nums[idx]]++;
        for(int i=idx+1;i<nums.size();i++){
            if(mp[nums[i]-k]==0)
                dfs(i, nums, k);
        }
        mp[nums[idx]]--;
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        ans = 0;
        sort(nums.begin(), nums.end());

        for(int i=0;i<nums.size();i++)
            dfs(i, nums, k);

        return ans;
    }
};

## [2598. Smallest Missing Non-negative Integer After Operations ](https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations/)(<font color=#FFC011>Medium</font>)

### Solution
這題主要在考同餘的觀念，比較值得注意第12行的部分，因餘數會與被除數同號，故若被除數<0則得再加一次除數。
#### 時間複雜度: ***O(n)***
大概是遍歷3次吧

#### 空間複雜度: ***O(n?)***
check的空間

程式碼:

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        int ans=0;
        vector<int>check(value);
        //初始化
        for(int i=0;i<value;i++)
        {
            check.push_back(0);
        }
        //處理<0的狀況並以餘數分類，記錄各個餘數的數量
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]<0)
            {
                nums[i]=nums[i]%value+value;
            }
                
            check[nums[i]%value]++;
        }
        while(1)
        {
            int reg=ans%value;
            if(check[reg]>0)
            {
                check[reg]--;
                ans++;
            }
            else if(check[reg]==0)
            {
            //當沒有同餘的存貨時，end。
                return ans;
            }
        }
        return ans;
    }
};