---
# System prepended metadata

title: Sam's Note

---

# Sam's Note

:::info
:earth_asia: **前言**

本筆記用來記錄刷NeetCode的過程。
:::

## 連結

* [NeetCode 150](https://neetcode.io/roadmap)
* [線上IDE](https://www.onlinegdb.com/)

## 217. Contains Duplicate(Easy)

### 題目描述
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:
Input: nums = [1,2,3,1]
Output: true

Example 2:
Input: nums = [1,2,3,4]
Output: false

Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true 

Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
### 解題思路
先將陣列元素由小到大依序排列，比較相鄰元素若一樣則回傳True
### 程式碼

```cpp=
// comment
int cmp(const void* a, const void* b){
  return *(int*)a - *(int*)b;
//return < 0 a放在b前
//return = 0 a跟b順序一樣
//return > 0 a放在b後
}

bool containsDuplicate(int* nums, int numsSize){
  qsort(nums,numsSize,sizeof(int),cmp);//由小到大排序
  //printf(" %d\t", nums[i]);
  for(int i = 1; i < numsSize; i++){//i從1開始
    if(nums[i] == nums[i-1]){
      return true;
    }
  }
  return false;
}
```

### 時間/空間複雜度
Time: O(nlogn)
Space: O(1)
![](https://hackmd.io/_uploads/SJkVY680n.png)

## 238. Product of Array Except Self(Medium)

### 題目描述
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
 

Constraints:

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
### 解題思路
將左側所有元素的乘積與右側所有元素的乘積相乘就是答案
### 程式碼

```cpp=
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int *ans = (int *)malloc(*returnSize * sizeof(int));
    ans[numsSize-1] = 1;
    for(int i = numsSize-2; i >= 0; i--){
        ans[i] = ans[i + 1] * nums[i + 1];
    }
    int leftproduct = 1;
    for(int i = 0; i < numsSize; i++){
        ans[i] = leftproduct * ans[i];
        leftproduct = leftproduct * nums[i];
    } 
    return ans;
    //free(ans);
}
```

### 時間/空間複雜度
* 時間複雜度:O(n)
* 空間複雜度:O(n)
![](https://hackmd.io/_uploads/HyxfDTUk6.png)

## 36. Valid Sudoku(Medium)

### 題目描述
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:

![](https://hackmd.io/_uploads/Bk5W7cZx6.png)

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:

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.
 

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.
### 解題思路
對每一行、列、區塊都掃過一遍，若出現相同數字回傳false
### 程式碼

```cpp=
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    bool Col[9][9]={0};
    bool Row[9][9]={0};
    bool Block[9][9]={0};
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if (board[i][j] == '.'){
                continue;
            }
            int boardIndex = board[i][j] - '0' - 1; 
            // Convert the character digit to an index (0-8) 0 for 9
            if(Row[i][boardIndex]==1){
                return false;
            }else{
                Row[i][boardIndex]=1;
            }

            if(Col[j][boardIndex]==1){
                return false;
            }else{
                Col[j][boardIndex]=1;
            }
            int block_num = ((int)(i / 3))*3 + (int)(j / 3);
            //Separate each sub-block into (0-8) blocks
            if (Block[block_num][boardIndex] == 1){
                return false;
            }else{
                Block[block_num][boardIndex] = 1;
            } 
        }  
    }
    return true;
}
```

### 時間/空間複雜度
* 時間複雜度:O(n^2)
* 空間複雜度:O(n^2)
* ![](https://hackmd.io/_uploads/r1WUGcZlp.png)

## 11. Container With Most Water(Medium)

### 題目描述
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:
![](https://hackmd.io/_uploads/BkHllfFl6.png)
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:

Input: height = [1,1]
Output: 1
 

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
### 解題思路
目標是要得到最大面積乘積，因此先將左右兩邊數值的高度比較，較小高度數值的那邊延續下一個數值進行比較，以此類推計算出最大面積乘積數值回傳
### 程式碼

```cpp=
int maxArea(int* height, int heightSize){
    //     i  :  0 1 2 3 4 5 6 7 8
    // height = [1,8,6,2,5,4,8,3,7] (heightSize = 9)
    //     l ------v
    //     r --------------------v
    int l = 0, r = heightSize - 1;
    int Area, maxArea = 0;
    while(r > l){
        if(height[l] < height[r]){
            Area = height[l]*(r - l);
            l++;
        }else{
            Area = height[r]*(r - l);
            r--;
        }
        
        if(maxArea < Area){
            maxArea = Area;
        }else{
            //do nothing
        }
    }
    return maxArea;
}
```

### 時間/空間複雜度
* 時間複雜度:O(n)
* 空間複雜度:O(1)
* ![](https://hackmd.io/_uploads/r12zJQKe6.png) 
 


<!--
## XXX. 模板(難度)

### 題目描述

### 解題思路

### 程式碼

```cpp=
```

### 時間/空間複雜度
--> 
