# Leetcode note
> [TOC]
# Python
## 198. House Robber
```python!
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp = [0]*len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
print(dp)
for i in range(2,len(nums)):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
print(dp)
return dp[-1]
```
## 300. Longest Increasing Subsequence
```python!
# Example:
# [0, 1, 0, 3, 2, 3] ## [1, 2, 4, 6] ## [1, 3, 2, 2] #
# # # # # # # ## # # # # ## # # # # #
# [1, 2, , , , ] ## [1, 2, , ] ## [1, 2, 1, 1] #
# [1, 2, 1, , , ] ## [1, 2, 3, ] ## [1, 2, 2, 1] #
# [1, 2, 1, 3, , ] ## [1, 2, 3, 4] ## [1, 2, 2, 2] #
# [1, 2, 1, 3, 3, ] ## ## #
# [1, 2, 1, 3, 3, 4] ## ## #
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1]*len(nums)
for i in range(1,len(nums)): # 作為DP的index
for j in range(i): # loop 0~i
if (nums[i] > nums[j]): # 往前比較
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
```
## 62. Unique Paths
Example 3,3 :
| | **1** | **2** | **3** |
| ----- | ----- | ----- | ----- |
| **1** | 1 | 1 | 1 |
| **2** | 1 | 2 | 3 |
| **3** | 1 | 3 | 6 |
```python!
def uniquePaths(self, m: int, n: int) -> int:
dp = m *[[1] *n]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
```
## 383. Ransom Note
- string.count(char)
**Example**: "aaaa".count('a') // 4
- 使用 set() 來省略重複的char
```python!
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
for word in set(ransomNote):
if ransomNote.count(word) > magazine.count(word):
return False
return True
```
## 647. Palindromic Substrings
使用[::-1]來反轉string
Example: "abc"to "cba"
```python!
def countSubstrings(self, s: str) -> int:
count = 0
for i in range(len(s)):
for j in range(i,len(s)):
if(s[i:j+1] == s[i:j+1][::-1]):
count +=1
return count
```
## 13. Roman to Integer
```python!
def romanToInt(self, s: str) -> int:
d = {
'I':1,
'V':5,
'X':10,
'L':50,
'C':100,
'D':500,
'M':1000
}
count = 0
s = s.replace("IV", "IIII").replace("IX", "IIIIIIIII")
s = s.replace("XL", "XXXX").replace("XC", "XXXXXXXXX")
s = s.replace("CD", "CCCC").replace("CM", "CCCCCCCCC")
for i in s:
count += d[i]
return count
```
## 14. Longest Common Prefix
```python!
def longestCommonPrefix(self, strs: List[str]) -> str:
firstS = strs[0]
curr,rs = 0, ""
try:
while(curr >= 0 and curr<len(firstS)):
for s in strs[1:]:
if firstS[curr] != s[curr]:
return rs
rs += firstS[curr]
curr += 1
except:
return rs
return rs
```
## 26. Remove Duplicates from Sorted Array
**nums[:]**
```python!
def removeDuplicates(self, nums: List[int]) -> int:
nums[:] = sorted(set(nums))
return len(nums)
```
## 66. Plus One
map() 必須搭配list使用
**ex**: list(map(func(),array))
```python!
def plusOne(self, digits: List[int]) -> List[int]:
s = ''.join(map(str, digits))
s = int(s)+1
s = list(str(s))
s = list(map(int,s))
return s
```
## 101. Symmetric Tree
mirror tree
```python!
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def check(node1,node2):
if (not node1) and (not node2):
return True
elif not node1 or not node2:
return False
elif node1.val != node2.val:
return False
return check(node1.left,node2.right) and check(node1.right,node2.left)
if not root:
return True
return check(root.left,root.right)
```
## 108. Convert Sorted Array to Binary Search Tree
```python!
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums):
mid = len(nums)//2
return TreeNode(
nums[mid],
self.sortedArrayToBST(nums[:mid]),
self.sortedArrayToBST(nums[mid+1:]))
else:
return None
```
## 125. Valid Palindrome
**string.isalnum()** : is alpa or num
```python!
def isPalindrome(self, s: str) -> bool:
sp = ""
s = s.lower()
for c in s:
if c.isalnum():
sp += c
if sp == sp[::-1]:
return True
else:
return False
```
## 171. Excel Sheet Column Number
```python!
def titleToNumber(self, columnTitle: str) -> int:
total = 0
columnTitle = columnTitle[::-1]
for i in range(len(columnTitle)):
total += (ord(columnTitle[i])-64) * (26**i)
return total
```
## 190. Reverse Bits
```python!
def reverseBits(self, n: int) -> int:
r = 0
for i in range(32):
r = r<<1
if (n & 1):
r += 1
n = n>>1
return r
```
## 202. Happy Number
```python!
def isHappy(self, n: int) -> bool:
def getSQ(num):
if num < 5:
return num
temp = 0
while (num):
t = num % 10
num = num//10
temp += t**2
return getSQ(temp)
if getSQ(n) ==1:
return True
else:
return False
```
## 326. Power of Three
```python!
def isPowerOfThree(self, n: int) -> bool:
if n <= 0:
return False
while n % 3 == 0:
n /= 3
return n == 1
```
## 2. Add Two Numbers
```python!
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
newNode = ListNode()
head = newNode
carry = 0
while(l1 or l2):
val1,val2 = 0,0
if l1:
val1 = l1.val
l1 = l1.next
if l2:
val2 = l2.val
l2 = l2.next
temp = val1+val2+carry
carry = 0
if temp >=10:
carry = temp//10
temp %= 10
newNode.next = ListNode(temp)
newNode = newNode.next
if carry>0:
newNode.next = ListNode(carry)
return head.next
```
## 3. Longest Substring Without Repeating Characters
```python!
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
st = set()
for left in range(len(s)):
st.clear()
right = left
while (right < len(s)):
if s[right] in st:
break
st.add(s[right])
right += 1
res = max(res,right-left)
return res
```
---
---
---
# MySQL
## Join
- **join** must with **on**
```sql!
SELECT *
FROM t1 left join t2
on t1.Id = t2.Id;
```
---
## Compare in Same Table
```sql!
SELECT
# rename row name
a.Name AS 'Employee'
FROM
Employee AS a,
Employee AS b
WHERE
a.ManagerId = b.Id AND a.Salary > b.Salary;
```
**Input** :
| id | name | salary | managerId |
| --- | ----- | ------ |:---------:|
| 1 | Joe | 70000 | 3 |
| 2 | Henry | 80000 | 4 |
| 3 | Sam | 60000 | Null |
| 4 | Max | 90000 | Null |
**Output** :
| Employee |
| -------- |
| Joe |
---
## Having, Group by, Count
- `WHERE` 用於在執行`SELECT`之前,`HAVING`用於`GROUP BY`之後
- Find duplicate
```sql!
select Email from Person
group by Email
having count(Email) > 1;
```
- `count(*)` : count row (include null)
- `count(1)` : exclude null
- group by two cols
```sql!
select actor_id, director_id
from ActorDirector
group by actor_id, director_id
having count(1) >= 3
```
---
## Not in
- table2 not in table1
```sql!
select name as 'Customers'
from Customers
where Customers.id not in (
select customerid from orders)
```
---
## Delete
- delete duplicate
```sql!
delete t1
from Person as t1, Person as t2
where t1.email = t2.email and t1.id > t2.id;
```
---
## Datediff, Subdate
```sql!
select t2.id
from Weather as t1, Weather as t2
where datediff(t2.recordDate,t1.recordDate) = 1
and t2.temperature > t1.temperature;
```
```sql!
select t2.id
from Weather as t1, Weather as t2
where subdate(t2.recordDate,1) = t1.recordDate
and t2.temperature > t1.temperature;
```
**Input**:
| id | recordDate | temperature |
| --- | ---------- | ----------- |
| 1 | 2015-01-01 | 10 |
| 2 | 2015-01-02 | 25 |
| 3 | 2015-01-03 | 20 |
| 4 | 2015-01-04 | 30 |
**Output**:
| id |
| -- |
| 2 |
| 4 |
---
## Order by, Limit
- find largest Number
- limit x: show x number of records
```sql!
SELECT
customer_number
FROM
orders
GROUP BY customer_number
ORDER BY count(customer_number) DESC
limit 1;
```
**Input**:
| order_number | customer_number |
| ------------ | --------------- |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 3 |
**Output**:
| customer_number |
| --------------- |
| 3 |
---
## Nest
- 596 Classes More Than 5 Students
```sql!
select class
from (select class,count(class) as num
from Courses
group by class) as temp
where num >= 5;
```
Input:
| student | class |
| ------- | -------- |
| A | Math |
| B | English |
| C | Math |
| D | Biology |
| E | Math |
| F | Computer |
| G | Math |
| H | Math |
| I | Math |
Output:
| class |
| ----- |
| Math |
---
## Case
- triangle
```sql!
select *,
case
when x+y>z and x+z>y and y+z>x then 'Yes'
else 'No'
end as 'triangle'
from triangle;
-- case
-- when (condition) then (result)
-- else (result)
-- end
```
---
## Update
- swap
```sql!
update Salary
set sex =
case sex
when 'f' then 'm'
else 'f'
end;
-- case (var)
-- when (condition) then (result)
-- else (result)
-- end
```
---
## Max()
```sql!
select max(num) as num
from (
select *
from MyNumbers
group by num
having count(num) = 1
) as t;
```
---
## Round, Avg
- **Round off**
- **round()** : (1.415,2) => 1.42
- **ceiling()** : 1.415 => 2, -6.43 => -6
- **floor()** : 1.415 => 1, -6.43 => -7
```sql
select p.project_id, round(avg(experience_years),2) as average_years
from Project as p left join Employee as e
on p.employee_id = e.employee_id
group by project_id
```
Input:
Project table:
| employee_id | project_id |
| ----------- | ---------- |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 1 | 2 |
| 4 | 2 |
Employee table:
| employee_id | name | experience_years |
| ----------- | ------ | ---------------- |
| 1 | Khaled | 3 |
| 2 | Ali | 2 |
| 3 | John | 1 |
| 4 | Doe | 2 |
Output:
| project_id | average_years |
| ---------- | ------------- |
| 1 | 2.00 |
| 2 | 2.50 |
---
## Distinct
- Distinct: unique
```sql!
select COUNT(DISTINCT user_id)
from Activity as a;
```
---
## Group_concat
- group category
- group_concat(product)
- group_concat(product order by product)
```sql!
select sell_date,
count(distinct product) as num_sold,
group_concat(distinct product order by product) as products
from Activities
group by sell_date
```
---
## Regex / regexp
```sql!
select *
from Users
where mail regexp '^[a-zA-Z][a-zA-Z0-9._-]*@leetcode\\.com';
```
---
## Offset
- offset: skip 1 row
**return empty**
```sql!
select Salary
from Employee
order by salary desc
limit 1
offset 1;
```
**return 'null'**
```sql!
select(
select Salary
from Employee
order by salary desc
limit 1
offset 1
) as 'SecondHighestSalary';
```
---
## Function
```sql!
```
---
## Variable, Function
```sql!
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
set n=n-1;
RETURN (
select(
select distinct salary
from Employee
order by salary desc
limit 1 offset N
)
);
END
```
---
## Rank, Dense_rank
| name | score |
| ----- | ----- |
| Alice | 90 |
| Bob | 85 |
| Carl | 90 |
| Dave | 80 |
- dense_rank()
```sql
SELECT name, score, DENSE_RANK() OVER (ORDER BY score DESC) AS dense_rank
FROM students;
```
| score | dense_rank |
| ----- | ---------- |
| 90 | 1 |
| 90 | 1 |
| 85 | 2 |
| 80 | 3 |
- rank()
```sql
SELECT name, score, RANK() OVER (ORDER BY score DESC) AS rank
FROM students;
```
| score | rank |
| ----- | ---- |
| 90 | 1 |
| 90 | 1 |
| 85 | 3 |
| 80 | 4 |
---
# C#
### 110. Balanced Binary Tree
> A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
> 也就是左右的高度差不能大於1
```csharp!
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public bool IsBalanced(TreeNode root) {
int r = GetHeight(root);
Console.WriteLine(r);
return r != -1;
}
private int GetHeight(TreeNode node) {
// solution:
// if null, return 0
// travel left and return the height
// travel right and return the height
// (depth of the two subtrees of every node never differs by more than one, from describe)
// left height - right height
if (node == null) return 0;
int left = GetHeight(node.left);
if (left == -1) return -1;
int right = GetHeight(node.right);
if (right == -1) return -1;
if (Math.Abs(left-right) > 1) return -1;
return Math.Max(left, right) + 1;
}
}
```
```
1
/ \
2 2 // 程式跑到這裡會回傳-1， 因為左邊是2但右邊是|2-0| = 2
/ \
3 3
/ \
4 4
```
```
1 // 程式跑到這裡會回傳-1
/ \
2 2
/ \
3 3
/ \
4 4
```
```
3 //左邊為1 右邊為2， |1-2| = 1，沒有大於1
/ \
9 20
/ \
15 7
```
---
# Rust
### 1768. Merge Strings Alternately
合并兩個兩個字串，以靠前的index為優先
- 先取兩個字串的最低長度，並以此作爲迴圈長度，當迴圈跑完就表示剩下的字串（word1 or word2）可以直接append到結果
```rust!
impl Solution {
pub fn merge_alternately(word1: String, word2: String) -> String {
let mut i: i32 = 0;
let mut result = String::new();
let l1 = word1.len();
let l2 = word2.len();
let min_len = std::cmp::min(l1,l2);
for i in 0..min_len {
result.push(word1.chars().nth(i).unwrap());
result.push(word2.chars().nth(i).unwrap());
}
if l1 > l2 {
result.push_str(&word1[min_len..]);
} else {
result.push_str(&word2[min_len..]);
}
result
}
}
```
---
### 122. Best Time to Buy and Sell Stock II
```rust!
public class Solution {
public int MaxProfit(int[] prices) {
// findMin
// findMax
// initialize
int profit = 0;
for (int i = 0; i < prices.Length - 1; i++)
{
if (prices[i] < prices[i + 1]) { // increasing
profit += prices[i+1] - prices[i];
}
}
return profit;
}
}
```
---
### 189. Rotate Array
```rust!
impl Solution {
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
// solution:
// create an new list of int named result_list
// the k_index = k - nums.len() was index the first loop
// first loop: for j in k_index..nums.len(), push [j] to result_list
// second loop: for i in 0..(k - nums.len()), push [i] to rusult_list
let mut result_list: Vec<i32> = Vec::new();
let l = nums.len();
let k = (k as usize) % l; // some case of k were larger than the length of nums
let k_index = l - k;
for j in k_index..l {
result_list.push(nums[j]);
}
for i in 0..k_index {
result_list.push(nums[i]);
}
*nums = result_list;
}
}
```
---
### 136. Single Number
```rust!
impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
let mut ans:i32 = 0;
for i in nums {
ans = ans ^ i;
}
ans
}
}
```
- use XOR to compare numbers
- 找出非一對的數字(只會有一個)
| A | B | A ^ B (XOR) |
|:---:|:---:|:-----------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
input: nums = [4, 1, 2, 1, 2]
| Step | Binary Operation | Decimal Result |
|--------------------|-----------------------------|----------------|
| **Initial Value** | `ans = 0000 ^ 0100 = 0100` | `ans = 4` |
| **First Iteration** | `ans = 0100 ^ 0001 = 0101` | `ans = 5` |
| **Second Iteration**| `ans = 0101 ^ 0010 = 0111` | `ans = 7` |
| **Third Iteration** | `ans = 0111 ^ 0001 = 0110` | `ans = 6` |
| **Fourth Iteration**| `ans = 0110 ^ 0010 = 0100` | `ans = 4` |
---
Sign in with Wallet
Connect another wallet