# Practice 2023
- [x] 5/1
### 1491. Average Salary Excluding the Minimum and Maximum Salary
#### Easy
* 去除最大最小值得到的平均
~~~ C++=
class Solution {
public:
double average(vector<int>& salary) {
double sum = 0, max = salary[0], min = salary[0];
for (auto unit: salary) {
if (unit > max)
max = unit;
if (unit < min)
min = unit;
sum += unit;
}
//cout << sum << ":" << min << ":" << max << ":" << salary.size() << endl;
return (sum - min - max) / (salary.size() - 2);
}
};
~~~

- [x] 5/2
### 1822. Sign of the Product of an Array
##### Easy
~~~ C++=
class Solution {
public:
int arraySign(vector<int>& nums) {
int sign = 1;

for (int num : nums) {
if (num == 0) {
return 0;
} else if (num < 0) {
sign = -sign;
}
}

return sign;
}
};
~~~
- [x] 5/3
### 2215. Find the Difference of Two Arrays
##### Easy
* Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

* answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
* answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

* unordered_set 用法
* 使用資料結構雜湊表(hash table)
* 指定元素: insert(x), erase(x)
* 有無出現過: count(x), 有:1 沒有：0
* iterator: begin(), end()
* 清空: clear()
* 宣吿 set: `unordered_set<int> set1(nums1.begin(), nums1.end());`
~~~C++=
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());

vector<int> distinct_nums1, distinct_nums2;
for (int num : set1) {
if (set2.count(num) == 0) {
distinct_nums1.push_back(num);
}
}

for (int num : set2) {
if (set1.count(num) == 0) {
distinct_nums2.push_back(num);
}
}

return {distinct_nums1, distinct_nums2};
}
};
~~~

- [x] 5/4
### 649. Dota2 Senate
* QUEUE 用法:
* push：把值加到尾巴
* pop：移除頭的值
* back：回傳尾巴的值
* front：回傳頭的值
* size：回傳目前長度
* empty：回傳是否為空
* 兩隊陣營 PUSH 到各自 QUEUE, 並儲存順序index
* index 小的取代index大的再加 String size 往後放
* 直到其中一者為空, 另一方獲勝


~~~C++=
class Solution {
public:
string predictPartyVictory(string senate) {
int n = senate.size();
queue<int> radiant, dire;
for (int i = 0; i < n; i++) {
if (senate[i] == 'R') {
radiant.push(i);
} else {
dire.push(i);
}
}
while (!radiant.empty() && !dire.empty()) {
int r = radiant.front(); radiant.pop();
int d = dire.front(); dire.pop();
if (r < d) {
radiant.push(r + n);
} else {
dire.push(d + n);
}
}
return radiant.empty() ? "Dire" : "Radiant";
}
};
~~~
- [x] 5/5
### 1456. Maximum Number of Vowels in a Substring of Given Length
~~~C++=
class Solution {
public:
bool isVew(char c) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
return true;
else
return false;
}
int maxVowels(string s, int k) {
int res = 0, max = 0;
int tmp = 0, last = 0;

if (k == 1) {
for (char c: s){
if (isVew(c))
return 1;
}
return 0;
}

for (int i = 0; i < k; i++) {
if (isVew(s[i]))
max++;
}

tmp = max;
for (int i = 1; i+k-1 < s.size() ;i++) {
cout << i+k-1 <<endl;
if (isVew(s[i-1]))
tmp --;
if (isVew(s[i-1+k]))
tmp++;
max = std::max(tmp, max);
}
return max;
}
};
~~~
- [x] 5/6
### 1498. Number of Subsequences That Satisfy the Given Sum Condition
~~~C++=
class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
constexpr int kMod = 1e9 + 7;
const int n = nums.size();
vector<int> p(n + 1, 1);
for (int i = 1; i <= n; ++i)
p[i] = (p[i - 1] << 1) % kMod;
sort(begin(nums), end(nums));
int ans = 0;
for (int i = 0, j = n - 1; i <= j; ++i) {
while (i <= j && nums[i] + nums[j] > target) --j;
if (i > j) continue;
// In subarray nums[i~j]:
// min = nums[i], max = nums[j]
// nums[i] + nums[j] <= target
// {nums[i], (j - i - 1 + 1 values)}
// Any subset of the right part gives a valid subsequence
// in the original array. And There are 2^(j - i) ones.
ans = (ans + p[j - i]) % kMod;
}
return ans;
}
};
~~~
- [X] 5/7
### 1964. Find the Longest Valid Obstacle Course at Each Position

~~~C++=
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> ans;
vector<int> dp;
for (int i = 0; i < obstacles.size(); i++) {
int len = lower_bound(dp.begin(), dp.end(), obstacles[i] + 1) - dp.begin();
cout << dp.size() <<endl;
if (len == dp.size()) {
dp.push_back(obstacles[i]);
} else {
dp[len] = obstacles[i];
}
// cout << "len: " << len << ", val: "<<dp[len] << endl;
ans.push_back(len + 1);
}
return ans;
}
};
~~~
- [X] 5/8
### 1572. Matrix Diagonal Sum
##### Esay
* 只要左邊每次加 1, 右邊每次減 1, 高遞增
* 加完後, 如寬是奇數則減去中間值
* rows and columns

~~~C++=
class Solution {
public:
int diagonalSum(vector<vector<int>>& mat) {
int left = 0, right = mat.size()-1, sum = 0;
for (int i = 0; i < mat.size(); i++) {
sum = sum + mat[i][left] + mat[i][right];
left++;
right--;
}
if (mat.size() % 2)
sum = sum - mat[(mat.size()-1)/2][(mat.size()-1)/2];
return sum;
}
};
~~~
- [X] 5/9
### 54. Spiral Matrix
##### Medium
~~~C++=
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {

vector<int>ans;
int row=matrix.size();
int col =matrix[0].size();
int count =0;
int total =row*col;

//// all index

int startingrow=0;
int startingcol=0;
int endingrow=row-1;
int endingcol=col-1;

while(count<total)
{
for(int i=startingcol;count<total && i<=endingcol; i++)
{
ans.push_back(matrix[startingrow][i]);
count++;
}
startingrow++;

for(int i=startingrow;count<total && i<=endingrow; i++)
{
ans.push_back(matrix[i][endingcol]);
count++;
}
endingcol--;

for(int i=endingcol;count<total && i>=startingcol; i--)
{
ans.push_back(matrix[endingrow][i]);
count++;
}
endingrow--;

for(int i=endingrow;count<total && i>=startingrow; i--)
{
ans.push_back(matrix[i][startingcol]);
count++;
}
startingcol++;
}

return ans;

}
};
~~~
- [X] 5/10
### 59. Spiral Matrix II
##### Medium
* 同上
- [X] 5/11
### 1035. Uncrossed Lines
- Dynamic programing
* 2 Dimensional array: declaration
~~~C++=
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
int m=nums2.size();
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(i==0||j==0)
{
dp[i][j]=0;
}
else if(nums1[i-1]==nums2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
};
~~~

* 類似問題: the longest common subsequence
* A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

~~~C++=
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
};
~~~
- [X] 5/12
### 2140. Solving Questions With Brainpower
* Dynamic programing
~~~C++=
#define ll long long int
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<ll> dp(n+1, 0);
for(int i=n-1; i>=0 ;i--){
int point = questions[i][0];
int jump = questions[i][1];

int nextQuestion = min(n, i+jump+1);
dp[i] = max(dp[i+1], point + dp[nextQuestion]);
//cout <<"i:" <<i<<", nextQuestion:" << nextQuestion <<",dp[i]:"<<dp[i]<<endl;
}
return dp[0];
}
};
~~~
- [X] 5/13
### 2466. Count Ways To Build Good Strings