---
title: '2022/09/09 Lintcode records'
disqus: hackmd
---
{%hackmd BJrTq20hE %}
2022/09/09 Lintcode records
===
## Table of Problems
:::info
**21. 整數排序
22. 尋找素數
23. 陣列第二大數
24. 主元素
25. 楊輝三角
26. 旋轉陣列
27. 迴文數II
28. 分解質因數
29. 反轉字串中的單詞
30. 陣列剔除元素後的乘積
31. 旋轉字串
32. 迴文數
33. 大小寫轉換II
34. 最後一個單詞的長度
35. 最大字母**
:::
Solving process
---
### 21. 整數排序
> 使用最基礎的bubble sort, 其他sorting也要掌握!
```python=
from typing import (
List,
)
class Solution:
"""
@param a: an integer array
@return: nothing
"""
def sort_integers(self, arr: List[int]):
# write your code here
# bubble sort
n = len(arr)
# n-1是因為最後一個元素不用做兩兩交換
# i表示共要做幾輪, 要做0~(n-1)輪!
for i in range(n-1):
# j用來實作每一輪, 都從0一路做到(n-1)-i, 每一輪開始都是從最左開始作
for j in range(0, n-i-1):
if (arr[j]>arr[j+1]):
arr[j],arr[j+1] = arr[j+1],arr[j]
return arr
# ex:
# arr = [4,3,2,1]
# bubbleSort(arr)
**********************************************
i:0
j:0
arr:[3, 4, 2, 1]
ind:[0, 1, 2, 3, 4]
--------------------------------------
i:0
j:1
arr:[3, 2, 4, 1]
ind:[0, 1, 2, 3, 4]
--------------------------------------
i:0
j:2
arr:[3, 2, 1, 4]
ind:[0, 1, 2, 3, 4]
--------------------------------------
**********************************************
i:1
j:0
arr:[2, 3, 1, 4]
ind:[0, 1, 2, 3, 4]
--------------------------------------
i:1
j:1
arr:[2, 1, 3, 4]
ind:[0, 1, 2, 3, 4]
--------------------------------------
**********************************************
i:2
j:0
arr:[1, 2, 3, 4]
ind:[0, 1, 2, 3, 4]
--------------------------------------
**********************************************
```
---
### 22. 尋找質數
> 做法為檢查所有範圍內的數字是否相除都沒有餘數。
```python=
from typing import (
List,
)
class Solution:
"""
@param n: an integer
@return: return all prime numbers within n.
"""
def prime(self, n: int) -> List[int]:
# write your code here
result = []
# 2到n都要檢查
for i in range(2, n+1):
if self.is_prime(i):
result.append(i)
return result
def is_prime(self,x):
# 2到輸入的數字x之間, 只要去除以任何數有餘數, 便是false
for i in range(2,x):
if(x % i ==0):
return False
return True
```
---
### 23. 陣列第二大數
> 思路: 找到最大數, 丟掉, 再次找到最大數。正統作法應該用排序。
```python=
from typing import (
List,
)
class Solution:
"""
@param nums: An integer array
@return: The second max number in the array.
"""
def second_max(self, nums: List[int]) -> int:
# write your code here
Max = max(nums)
nums.remove(Max)
second = max(nums)
return second
```
---
### 24. 主元素
> 活用hash, 了解如何尋找key, value
```python=
from typing import (
List,
)
class Solution:
"""
@param nums: a list of integers
@return: find a majority number
"""
def majority_number(self, nums: List[int]) -> int:
# write your code here
# 總元素個數
total_element = len(nums)
# 找到每一個元素的計數
count_dict={}
for i in nums:
if i not in count_dict:
count_dict[i]=1
else:
count_dict[i]+=1
# 找到total_element中擁有最多計數的key值
# max_key = max(total_element, key=lambda key: total_element[key])
max_key = max(count_dict, key = count_dict.get)
if (count_dict[max_key]>(total_element/2)):
return max_key
else:
return None
```
---
### 25. 楊輝三角
> 數字 11 的冪的遞增值形成了帕斯卡三角形圖案。
> 想要把整數拆成一個一個數字, 可以先用string, 再用split拆分
```python=
11*0 = 1
11*1 = 11
11*2 = 121
11*3 = 1331
11*4 = 14641
from typing import (
List,
)
class Solution:
"""
@param n: a Integer
@return: the first n-line Yang Hui's triangle
"""
def calc_yang_huis_triangle(self, n: int) -> List[List[int]]:
# write your code here
# 11的冪形成pascal triangle
num_list = []
for i in range(n):
num_list.append(11**i)
result = []
# 將數字拆成每一位均為一個數字
for j in num_list:
Str = str(j)
split = []
for i in range (0, len(Str)):
split.append(int(Str[i:i+1]))
# 放進result list
result.append(split)
return (result)
```
> 以上作法有誤, 會發現下列狀況!
>
> 更正為數學作法, 每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 n 行的第 i 个数等于第 n−1 行的第 i−1 个数和第 i 个数之和。
```python=
ret = list()
for i in range(n):
row = list()
for j in range(0, i + 1):
if j == 0 or j == i:
row.append(1)
else:
row.append(ret[i - 1][j] + ret[i - 1][j - 1])
ret.append(row)
return ret
```
### 26. 旋轉陣列
> 至少有三种方法可以解决这个问题.
```python=
def rotate(self, nums: List[int], k: int) -> List[int]:
# Write your code here
# 當k>len(nums)時! 他是一個循環的向右移動!
k %= len(nums)
return nums[-k:] + nums[:-k]
```
---
### 27. 迴文數II
> 雙指標, 倆倆交換!
```python=
def reverse_array(self, nums: List[int]):
# write your code here
if not nums:
return nums
left, right = 0, len(nums)-1
while left <= right:
nums[left], nums[right] = nums[right], nums[left]
right -= 1
left += 1
return nums
```
---
### 28. 分解質因數
> up一般设定为sqrt(num), 降低時間複雜度
```python=
def prime_factorization(self, num: int) -> List[int]:
# write your code here
# up一般设定为sqrt(num)，因为一个数大于其根号的质因数最多只有一个，
# 那么遍历其根号内的数可以将时间复杂度减小至根号n，
# 若遍历完prime后该数不为1，则其值为最后一个质因数
up = int(num**0.5 + 1)
ans = []
for i in range(2,up):
while num % i == 0:
num /= i
ans += [i]
# 若最后剩余数不为1，则为最后一个质因数
if num != 1:
ans += [int(num)]
return ans
```
---
### 29. 反轉字串中的單詞
> 延伸思考: reversed(), split()如果沒有libary要怎麼作?
```python=
def reverse_words(self, s: str) -> str:
# write your code here
# split()按照空格分割字符串，reversed翻转，''.join按照空格连接字符串
return ' '.join(reversed(s.split()))
```
---
### 30. 陣列剔除元素後的乘積
> 其他解答可以看下, 只用了最直觀的方法來解
```python=
class Solution:
"""
@param nums: Given an integers array A
@return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
"""
def product_exclude_itself(self, nums: List[int]) -> List[int]:
# write your code here
B = []
for i in range(0,len(nums)):
s = 1
# 每個元素, 將其去除後得到一個暫時的list
tmp =nums.copy()
tmp.remove(nums[i])
print(tmp)
# 得到list中每個元素的乘積
for j in tmp:
s*=j
B.append(s)
return B
```
---
### 31. 旋轉字串
> 翻轉三次大法可以達成
```python=
def rotate_string(self, s: List[str], offset: int):
# write your code here
if not s or offset == 0:
return
length = len(s)
# 預防offset比length長
offset = offset % length
# 將整個數組翻轉
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
# 目的：rotate k次，就是把后k个数移到前面。
# 后k个数就是从length - k 到length -1, 先把这一截翻转
# 再把前length - k个数翻转，即: 0 到length -k -1
# 再整体反转即可
reverse(s, length - offset, length -1)
reverse(s, 0, length -offset -1)
reverse(s, 0, length -1)
# 開新list來作的方法如下
# t = list(s)
# print(t)
# tt = t[-offset:]+t[:-offset]
# Str = "".join(tt)
# print(Str)
```
---
### 32. 迴文數
> 利用到翻轉整個數列, 及數字如何拆分成list, list如何轉回數字的技巧
```python=
def is_palindrome(self, num: int) -> bool:
# write your code here
# 翻轉此數
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
# 將一個數字拆分後轉成list, python的話要先轉str即可作
nums = list(str(num))
reverse(nums,0,len(nums)-1)
# 將此list轉回數字
number = "".join(nums)
# 作判斷是否相等
if (number ==str(num)):
return True
else:
return False
```
---
### 33. 大小寫轉換II
> 考數字的部分不轉換的話, 條件怎麼寫
```python=
def lowercase_to_uppercase2(self, letters: str) -> str:
# write your code here
s = list(letters)
#遍历整个字符串，将所有的小写字母转成大写字母
for i in range(len(s)):
# 如果是數字的部分不要轉換!
if s[i] >= 'a' and s[i] <= 'z':
# 轉換成大寫是ascii碼-32
# chr: chr() 用一个范围在 range（256）内的（就是0～255）整数作参数，返回一个对应的字符。
# ord: ord() 以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值
s[i] = chr(ord(s[i]) - 32)
return ''.join(s)
```
---
### 34. 最後一個單詞的長度
> 注意exception即可
```python=
def length_of_last_word(self, s: str) -> int:
# write your code here
# 找到所有單詞
if len(s)>0:
List = list(s.split())
print(List[-1])
# 找到最後一個單詞
tail = List[-1]
# 回傳最後一個單詞的長度
return len(tail)
else:
return 0
```
---
### 35. 最大字母
>
```python=
class Solution:
"""
@param s: a string
@return: a string
"""
def largestLetter(self, s):
# 返回大寫中最大的字母
# 沒有大寫返回NO
# set() 函数创建一个无序不重复元素集
existing = set(s)
# 26個字母由後往前找, step=-1
# 確保回傳是最大的字母
for i in range(25, -1, -1):
#找到一个字母字符，其大写和小写字母均出现在S中
if chr(ord('A') + i) in existing and chr(ord('a') + i) in existing:
return chr(ord('A') + i)
else:
return 'NO'
```
---
> Read more about lintcode here: https://www.lintcode.com/problem/
Coding flows
---
```sequence
Lintcode->Leetcode: Easy to midium and hard
Note left of Lintcode: Initial 50 + Advance 80
Note right of Leetcode: Conquer 150 problems
Note right of Leetcode: GOOGLE coding interview
Leetcode->Lintcode: Algorithm and Data Structure
Leetcode-->Google: Familiar with 500 problems up
```
> Read more about sequence-diagrams here: https://po-jen-lai.gitbook.io/coding-practice/sort
Project Timeline
---
```mermaid
gantt
title Gantt Diagram
axisFormat %m-%d
section Lintcode
Initial 50 :a1, 09-08, 3d
Advance 80 :a2, after a1, 7d
section Leetcode
Problems 150 :a3, after a2, 20d
Google 500 :after a3, 60d
```
> Read more about mermaid here: http://mermaid-js.github.io/mermaid/
## Appendix and FAQ
:::info
**Get some improvement everyday!** ...let's move on!
:::
###### tags: `Leetcode` `Lintcode`
Sign in with Wallet
Connect another wallet