# 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)
## 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)
## 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:
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)
* 
## 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:
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)
* 
<!--
## XXX. 模板(難度)
### 題目描述
### 解題思路
### 程式碼
```cpp=
```
### 時間/空間複雜度
-->
Sign in with Wallet
Connect another wallet