# LeetCode | Data Structure I | 14 Days Challenge | Day 5-6
###### tags: `LeetCode` `Data Structure I` `14 Days Challenge`
## Day 5

### [36. Valid Sudoku](https://leetcode.com/problems/valid-sudoku/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:*

>*Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.*

>*Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:*

>*A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.*

### 測資

Example 1:


:::info
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
:::

Example 2:

:::info
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
:::

### 核心概念

==set、unordered_set、二維vector==

### 數值範圍

board.length == 9
board\[i].length == 9
board\[i]\[j] is a digit 1-9 or '.'.

### 想法

分成三個功能，判斷行、判斷列、判斷九宮格。
搭配unordered_set判斷同一數字是否出現多次。
盡量寫完一區塊就進行偵錯，才不會把解題時間拉太久。

***time : 40~60 mins
time complexity : $O(n^2)$
space complexity : $O(n)$***

n為固定數字，==n=9==

### 程式碼

class Solution {
public:
    int box_row_reg = -1, box_col_reg = -1;
    bool box_status_reg;
    bool CheckCol(vector<vector<char>>& board, int col) {
        unordered_set<char> s;
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.') {
                if (!s.count(board[i][col]))
                    s.insert(board[i][col]);
                else
                    return false;
            }
        }
        return true;
    }

    bool CheckRow(vector<vector<char>>& board, int row) {
        unordered_set<char> s;
        for (int i = 0; i < 9; i++) {
            if (board[row][i] != '.') {
                if (!s.count(board[row][i]))
                    s.insert(board[row][i]);
                else
                    return false;
            }
        }
        return true;
    }

    bool CheckBox(vector<vector<char>>& board, int row, int col) {
        unordered_set<char> s;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int temp = board[row + i][col + j];
                if (temp != '.') {
                    if (!s.count(temp))
                        s.insert(temp);
                    else
                        return false;
                }
            }
        }
        return true;
    }

    bool CheckVid(vector<vector<char>>& board, int row, int col) {
        bool check_col, check_row, check_box;
        int box_row = row - row % 3, box_col = col - col % 3;
        check_col = CheckCol(board, col);
        check_row = CheckRow(board, row);
        check_box = CheckBox(board, box_row, box_col);
        
        return check_row && check_col && check_box;
    }

    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (!CheckVid(board, i, j)) return false;
            }
        }
        return true;
    }
};

### [74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*You are given an m x n integer matrix matrix with the following two properties:
> * Each row is sorted in non-decreasing order.
> * The first integer of each row is greater than the last integer of the previous row.

>*Given an integer target, return true if target is in matrix or false otherwise.

>***You must write a solution in O(log(m * n)) time complexity.***

### 測資

Example 1:


:::info
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
:::

Example 2:


:::info
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
:::

### 核心概念

==Binary Search==

### 數值範圍

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4^ <= matrix[i][j], target <= 10^4^

### 想法

當看到題目這行
> ***You must write a solution in O(log(m * n)) time complexity.***

就絕對不能用暴力解XD，不然一定TLE，因此就來練習二元搜吧~

首先先判斷target在哪一行，不然很難做。(數字有可能大於陣列最大值，記得做限制)

再來就是進行二元搜，這裡就不多作介紹了，找找找~最後找的到就輸出true，找不到就輸出false。

***time : 30~40 mins
time complexity : $O(logn)$
space complexity : $O(1)$***

### 程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int tar_row = -1;

        // find which row is the target range
        for (int i = 0; i < row; i++) {
            if (target >= matrix[i][0] && target <= matrix[i][col - 1]) {
                tar_row = i;
                break;
            }
        }

        if (tar_row == -1) return false;

        // binarysearch
        int left = 0, right = col - 1, middle, cur;
        while (left <= right) {
            middle = left + (right - left) / 2;
            cur = matrix[tar_row][middle];

            if (target > cur) {
                left = middle + 1;
            }
            else if (target < cur) {
                right = middle - 1;
            }
            else return true;
        }
        return false;
    }
};

## Day 6

### [387. First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.*

### 測資

Example 1:

:::info
Input: s = "leetcode"
Output: 0
:::

Example 2:

:::info
Input: s = "loveleetcode"
Output: 2
:::

Example 3:

:::info
Input: s = "aabb"
Output: -1
:::

### 核心概念

==map、unordered_map、string==

### 數值範圍

1 <= s.length <= 10^5
s consists of only lowercase English letters.

### 想法

終於進入字串題了~
這題使用map而不是set是因為要記錄字符所在的index。
跟第一二天的題目一樣，判斷是否重複，輸出index，就是這麼樸實無華且枯燥。

***time : 10~20 mins
time complexity : $O(n)$
space complexity : $O(n)$***

### 程式碼

class Solution {
public:
    int firstUniqChar(string s) {
        int len = s.size();
        if (len == 1) return 0;

        unordered_map<char, int> mp;
        int first = -1e9, ans = 1e9;
        for (int i = 0; i < len; i++) {
            if (!mp.count(s[i])) 
                mp[s[i]] = i;
            else if(mp[s[i]] != -1)
                mp[s[i]] = -1;
        }

        for (auto j : mp) {
            if (j.second != -1) 
                ans = min(ans, j.second);
        }

        if (ans == 1e9) return -1;
        else return ans;
    }
};

### [383. Ransom Note](https://leetcode.com/problems/ransom-note/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.*

>*Each letter in magazine can only be used once in ransomNote.*

### 測資

Example 1:

:::info
Input: ransomNote = "a", magazine = "b"
Output: false
:::

Example 2:

:::info
Input: ransomNote = "aa", magazine = "ab"
Output: false
:::

Example 3:

:::info
Input: ransomNote = "aa", magazine = "aab"
Output: true
:::

### 核心概念

==map、unordered_map、string==

### 數值範圍

1 <= ransomNote.length, magazine.length <= 10^5^

ransomNote and magazine consist of lowercase English letters.

### 想法

這題簡單到有點過分了...
用map紀錄出現次數，最後run一次map中的鍵值，若小於0，則輸出false(因為ransomNote和magazine的字符出現次數要是一樣的，相當於重組句子的意思)

***time : 3~5 mins
time complexity : $O(n)$
space complexity : $O(n)$***

### 程式碼

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;
        for (char i : magazine) mp[i]++;
        for (char i : ransomNote) mp[i]--;
        for (auto i : mp) if (i.second < 0) return false;
        return true;
    }
};

### [242. Valid Anagram](https://leetcode.com/problems/valid-anagram/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given two strings s and t, return true if t is an anagram of s, and false otherwise.

>*An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.*

### 測資

Example 1:

:::info
Input: s = "anagram", t = "nagaram"
Output: true
:::

Example 2:

:::info
Input: s = "rat", t = "car"
Output: false
:::

Example 2:

:::info
Input: s = "aabb"
Output: -1
:::

### 核心概念

==map、unordered_map、string==

### 數值範圍

1 <= s.length, t.length <= 5 * 10^4^
s and t consist of lowercase English letters.

### 想法

跟上一題一樣。

***time : 3-5 mins
time complexity : $O(n)$
space complexity : $O(n)$***

### 程式碼

class Solution {
public:
    bool isAnagram(string s, string t) {
        
        if (s.size() != t.size()) return false;

        unordered_map<char, int> mp;

        for (char i : s) {
            if (!mp.count(i)) mp[i] = 1;
            else mp[i]++;
        }
        for (char i : t) {
            if (!mp.count(i)) return false;
            else if (--mp[i] < 0) return false;
        }
        
        return true;
    }
};