# Intro 21-40

#21 *isIPv4Address*
---
1. **題目** : An IP address is a numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol for communication. There are two versions of the Internet protocol, and thus two versions of addresses. One of them is the IPv4 address.
Given a string, find out if it satisfies the IPv4 address naming rules.
2. **範例** :
* For `inputString = "172.16.254.1"`, the output should be `solution(inputString) = true`;
* For `inputString = "172.316.254.1"`, the output should be `solution(inputString) = false`;
3. **解法** :

import re
def solution(inputString):
    parts = inputString.split('.')
    
    # Check if the string has exactly four parts
    if len(parts) != 4:
        return False
    # Check each part
    for part in parts:
        # Check if each part consists only of digits
        if not part.isdigit():
            return False
        # Check if each part is within the range 0 to 255
        if not 0 <= int(part) <= 255:
            return False
        # Check if each part contains leading zeros
        if len(part) > 1 and part[0] == '0':
            return False
    
    return True

#22 *avoidObstacles*
---
1. **題目** : You are given an array of integers representing coordinates of obstacles situated on a straight line.
Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.
Find the minimal length of the jump enough to avoid all the obstacles.
2. **範例** :
* For `inputArray = [5, 3, 6, 7, 9]`, the output should be `solution(inputArray) = 4`.
* 

3. **解法** :

def solution(inputArray):
    number = 2
    found = False
    while not found:
        found = True
        # 检查當前數字的每一個倍数是否在數組中出现
        for num in inputArray:
            if num % number == 0:
                found = False
                break
        # 如果當前數字的每一個倍数都不在數组中出现，返回该數字
        if found:
            return number
        # 否则，继续检查下一个数字
        number += 1

#23 *Box Blur(模糊值)*
---
1. **題目** : Last night you partied a little too hard. Now there's a black and white photo of you that's about to go viral! You can't let this ruin your reputation, so you want to apply the [box blur algorithm](https://en.wikipedia.org/wiki/Box_blur) to the photo to hide its content.
The pixels in the input image are represented as integers. The algorithm distorts the input image in the following way: Every pixel x in the output image has a value equal to the average value of the pixel values from the 3 × 3 square that has its center at x, including x itself. All the pixels on the border of x are then removed.
Return the blurred image as an integer, with the fractions rounded down

2. **範例** :
* For

image = [[1, 1, 1], 
         [1, 7, 1], 
         [1, 1, 1]]

the output should be` solution(image) = [[1]]`.
To get the value of the middle pixel in the input 3 × 3 square: *(1 + 1 + 1 + 1 + 7 + 1 + 1 + 1 + 1) = 15 / 9 = 1.66666 = 1*. The border pixels are cropped from the final result.
* For

image = [[7, 4, 0, 1], 
         [5, 6, 2, 2], 
         [6, 10, 7, 8], 
         [1, 4, 2, 0]]

the output should be

solution(image) = [[5, 4], 
                   [4, 4]]

There are four 3 × 3 squares in the input image, so there should be four integers in the blurred output. To get the first value: *(7 + 4 + 0 + 5 + 6 + 2 + 6 + 10 + 7) = 47 / 9 = 5.2222 = 5.* The other three integers are obtained the same way, then the surrounding integers are cropped from the final result.
3. **解法** :
根據範例我們可以知道模糊是根據`3*3`矩陣算出一個特定值，所以收先要先算出有幾個`3*3`的可能組合，再依照指定公式算出即可

def solution(image):
    rows = len(image)
    cols = len(image[0])
    blurred_image = []

    for i in range(rows - 2):  # 只需遍歷到 rows - 2 和 cols - 2，因為要取3x3的子矩陣
        row_result = []
        for j in range(cols - 2):
            # 計算3x3子矩陣的模糊值
            sum_pixels = sum([sum(row[j:j+3]) for row in image[i:i+3]])
            blurred_pixel = sum_pixels // 9  # 四捨五入為最接近的整數
            row_result.append(blurred_pixel)
        blurred_image.append(row_result)

    return blurred_image

#24 *Minesweeper*
---
1. **題目** : In the popular Minesweeper game you have a board with some mines and those cells that don't contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

2. **範例** :
* For

matrix = [[true, false, false],
          [false, true, false],
          [false, false, false]]

the output should be

solution(matrix) = [[1, 2, 1],
                    [2, 1, 1],
                    [1, 1, 1]]

3. **解法** :
根據範例我們可以知道就是要透過踩地雷遊戲得到平常的結果，依據當下方格相鄰的`true` 數量
>這段程式碼使用了一個 directions 列表，其中包含了所有相鄰方向的偏移量。
>然後在內部迴圈中，我們遍歷這些方向，並檢查相應位置是否在矩陣的範圍內，
>如果在範圍內且是True，就將計數器加一

def solution(matrix):
    # Create a new matrix to store the updated values
    updated_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

    # Define directions for adjacent neighbors
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            count = 0
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y]:
                    count += 1
            updated_matrix[i][j] = count

    return updated_matrix

#25 *Array Replace*
---
1. **題目** : Given an array of integers, replace all the occurrences of elemToReplace with substitutionElem.

2. **範例** :
* For `inputArray = [1, 2, 1]`,` elemToReplace = 1`, and `substitutionElem = 3`, the output should be```solution(inputArray, elemToReplace, substitutionElem) = [3, 2, 3]```
3. **解法** :

def solution(inputArray, elemToReplace, substitutionElem):
    for i in range(len(inputArray) ):
        if inputArray[i] == elemToReplace:
            inputArray[i]=substitutionElem
    return inputArray

#26 *evenDigitsOnly*
---
1. **題目** : Check if all digits of the given integer are even.

2. **範例** :
* For `For n = 248622`, the output should be
`solution(n) = true`
3. **解法** :

def solution(n):
    count=0
    #將整數轉換為字串
    for i in str(n):
    # str(n) 將整數 n 轉換為字串，而我們需要將其轉換回整數形式以便進行數學運算
        if int(i) % 2 == 0: 
            pass
        else :
            count+=1
    return count==0  

#27 *variableName*
---
1. **題目** : Correct variable names consist only of English letters, digits and underscores and they can't start with a digit.
Check if the given string is a correct variable name.

2. **範例** :
* For `name = "var_1__Int"`, the output should be `solution(name) = true`;
* For `name = "qq-q"`, the output should be `solution(name) = false`;
3. **解法** : 運用正則運算式
> ^: 符合字串的開頭。
> [a-zA-Z_]: 符合一個字母（大小寫不限）或底線。
> [a-zA-Z0-9_]*: 符合零個或多個字母（大小寫不限）、數字或底線。
> $: 匹配字串的結尾。

import re
def solution(name):
    pattern = r'^[a-zA-Z_][a-zA-Z0-9_]*$'
    return bool(re.match(pattern, name))

#28 *alphabeticShift*
---
1. **題目** : Given a string, your task is to replace each of its characters by the next one in the English alphabet; i.e. replace a with b, replace b with c, etc (z would be replaced by a).

2. **範例** :
* For `inputString = "crazy"`, the output should be `solution(inputString) = "dsbaz"`
3. **解法** :
Python 的內建函數 ord()，它會傳回給定字元的 Unicode 碼點值。 例如，ord('a') 回傳 97

def solution(inputString):
    replaced_name = ""
    for char in inputString:
        # If it's a letter, replace it with the next letter
        if char.isalpha():
            if char == 'z':
                replaced_name += 'a'
            else:
                replaced_name += chr(ord(char) + 1)
    return replaced_name

#29 *chessBoardCellColor*
---
1. **題目** : Given two cells on the standard chess board, determine whether they have the same color or not.

2. **範例** :
* For `cell1 = "A1" and cell2 = "C3"`, the output should be `solution(cell1, cell2) = true`
3. **解法** :
透過Python 的內建函數 ord()，轉換字元的 Unicode 碼點值，並找出棋盤特性**黑色都在偶數列偶數欄 或是 奇數列奇數行(加起來是偶數)**

def solution(cell1, cell2):
    col1=ord(cell1[0])-ord('A')+1
    row1=int(cell1[1])
    col2=ord(cell2[0])-ord('A')+1
    row2=int(cell2[1])
    # ex 黑色都在偶數列偶數欄 或是 奇數列奇數行(加起來是偶數)
    return (col1+row1) %2  == (row2 + col2) % 2

#30 *Circle of Numbers*
---
1. **題目** : Consider integer numbers from 0 to n - 1 written down along the circle in such a way that the distance between any two neighboring numbers is equal (note that 0 and n - 1 are neighboring, too).
Given n and firstNumber, find the number which is written in the radially opposite position to firstNumber.

2. **範例** :
* For `n = 10 and firstNumber = 2`, the output should be`solution(n, firstNumber) = 7`.
*

3. **解法** :
找到與 firstNumber 相對位置的數字，但要考慮這行程式碼檢查第一個數字 firstNumber 是否等於 n 的一半及循環中點的索引會超出陣列的範圍

def solution(n, firstNumber):
    if firstNumber==(n/2):        
        return 0
    elif firstNumber+(n/2) > n-1:
        return firstNumber+(n/2)-n
    else:
        return firstNumber+(n/2)

#31 *depositProfit*
---
1. **題目** : You have deposited a specific amount of money into your bank account. Each year your balance increases at the same growth rate. With the assumption that you don't make any additional deposits, find out how long it would take for your balance to pass a specific threshold.

2. **範例** :
* For `deposit = 100`, `rate = 20`, and `threshold = 170`, the output should be `solution(deposit, rate, threshold) = 3`.

* Each year the amount of money in your account increases by 20%. So throughout the years, your balance would be:

year 0: 100;
year 1: 120;
year 2: 144;
year 3: 172.8.
3. **解法** :

def solution(deposit, rate, threshold):
    n = 0
    while deposit * (1 + rate / 100) ** n < threshold:
        n += 1
    if n == 0:  # If threshold is already met in the first year
        return 0
    else:
        return n

#32 *absoluteValuesSumMinimization*
---
1. **題目** : Given a sorted array of integers a, your task is to determine which element of a is closest to all other values of a. In other words, find the element x in a, which minimizes the following sum

2. **範例** :
* For` a = [2, 4, 7]`, the output should be `solution(a) = 4`.
* The lowest possible value is when x = 4, so the answer is 4.

for x = 2, the value will be abs(2 - 2) + abs(4 - 2) + abs(7 - 2) = 7.
for x = 4, the value will be abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5.
for x = 7, the value will be abs(2 - 7) + abs(4 - 7) + abs(7 - 7) = 8.

3. **解法** :
使用兩個嵌套的循環來計算每個元素與列表中其他元素的絕對差之和，並動態更新最小值元素及索引
* NOTE: 使用 range(len(a)) 可以迭代列表 a 中的每個元素及其索引(若只需要元素而不需要索引 可以直接用` for i in a`)

def solution(a):
    min_diff = float('inf')  # Initialize min_diff to positive infinity
    min_index = -1  # Initialize min_index to 0
    for i in range(len(a)):
        diff = 0
        for j in range(len(a)):
            diff += abs(a[j] - a[i])
        if diff < min_diff:
            min_diff = diff
            min_index = i
    return a[min_index]

#33 *stringsRearrangement*
---
1. **題目** : Given an array of equal-length strings, you'd like to know if it's possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it's possible, and false if not.

**Note: You're only rearranging the order of the strings, not the order of the letters within the strings!**

2. **範例** :
* For` inputArray = ["aba", "bbb", "bab"]`, the output should be
`solution(inputArray) = false.`
* There are 6 possible arrangements for these strings:

["aba", "bbb", "bab"]
["aba", "bab", "bbb"]
["bbb", "aba", "bab"]
["bbb", "bab", "aba"]
["bab", "bbb", "aba"]
["bab", "aba", "bbb"]

None of these satisfy the condition of consecutive strings differing by 1 character, so the **answer is false.**

3. **解法** :
使用 permutations 函式從 inputArray 中生成所有可能的排列，對於每個排列 perm，我們遍歷它的每對相鄰元素，並計算它們之間不同字符的數量。如果對於任何一對相鄰元素，不同字符的數量不等於 1，我們將 valid 設置為 False，並break

from itertools import permutations

def solution(inputArray):
    result = list(permutations(inputArray))
    for perm in result:
        valid = True
        for i in range(len(perm) - 1):
            diff_count = sum(a != b for a, b in zip(perm[i], perm[i + 1]))
            if diff_count != 1:
                valid = False
                break
        if valid:
            return True

    return False

#34 *extractEachKth*
---
1. **題目** : Given array of integers, remove each kth element from it.

2. **範例** :
* For` For inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]` and k = 3, the output should be
`solution(inputArray, k) = [1, 2, 4, 5, 7, 8, 10].`

3. **解法** :

def solution(inputArray, k):
    filtered_array = []
    for i in range(len(inputArray)):
        # Check if the index (i+1) is a multiple of k
        if (i + 1) % k != 0:
            filtered_array.append(inputArray[i])
    return filtered_array

#35 *extractEachKth*
---
1. **題目** : Given array of integers, remove each kth element from it.

2. **範例** :
* For`inputString = "var_1__Int"`, the output should be
`solution(inputString) = '1';`

3. **解法** :

import re
# re: 這是 Python 的正則表達式庫
def solution(inputString):
   # \d 匹配任何數字字符（0-9）
    return re.findall('\d', inputString)[0]

#36 *differentSymbolsNaive*
---
1. **題目** : Given a string, find the number of different characters in it.

2. **範例** :
* For` s = "cabca"`, the output should be`solution(s) = 3`. There are 3 different characters `a`, `b` and `c`.

3. **解法** :

from collections import Counter
def solution(s):
    count = Counter(s)
    # 返回不同字母的数量，即 Counter 對象的键的數量
    return len(count.keys())

#37 arrayMaxConsecutiveSum
---
1. **題目** : Given array of integers, find the maximal possible sum of some of its k consecutive elements.

2. **範例** :
* For `inputArray = [2, 3, 5, 1, 6]` and `k = 2`, the output should be `solution(inputArray, k) = 8`.
All possible sums of 2 consecutive elements are:

2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.

* Thus, the answer is **8**.

3. **解法** :
根據k值計算序列最大的k個總和，最直接就是用以下迴圈作法

def solution(inputArray, k):

    # 先求出每個 k 個元素的和
    sums = [sum(inputArray[i:i+k]) for i in range(len(inputArray) - k + 1)]
    # 找出最大的和
    max_sum = max(sums)
    return max_sum

* 但是這種方法很容易TLE，因為**時間複雜度 O((n-k+1)*k)**，當n 和 k 值很大时，計算時間會相應增加，所以較有效率的做法是使用*滑動窗口 Sliding Window*，在每次迭代中只對視窗內的元素進行加和，而不是對整個子序列進行加和，**時間複雜度變為是 O(n)**

def solution(inputArray, k):
    # 首先計算前 k 個元素的和作為初始值
    current_sum = sum(inputArray[:k])
    max_sum = current_sum
    # 使用滑動窗口計算相鄰 k 個元素的和
    for i in range(1, len(inputArray) - k + 1):
        current_sum = current_sum - inputArray[i - 1] + inputArray[i + k - 1]
        max_sum = max(max_sum, current_sum)
    return max_sum

* 可以透過以下測試看出當我們N變大到100000左右，K=46000多時，時間差為20-0.001秒
> for test Sliding Window Algorithm


#38 growingPlant
---
1. **題目** : Caring for a plant can be hard work, but since you tend to it regularly, you have a plant that grows consistently. Each day, its height increases by a fixed amount represented by the integer upSpeed. But due to lack of sunlight, the plant decreases in height every night, by an amount represented by downSpeed. Since you grew the plant from a seed, it started at height 0 initially. Given an integer desiredHeight, your task is to find how many days it'll take for the plant to reach this height.

2. **範例** :
* For` upSpeed = 100`, `downSpeed = 10`, and `desiredHeight = 910`, the output should be
`solution(upSpeed, downSpeed, desiredHeight) = 10`.

3. **解法** :

def solution(upSpeed, downSpeed, desiredHeight):
    if desiredHeight<=upSpeed:
        return 1
    else:
        day=  (desiredHeight-upSpeed )//(upSpeed-downSpeed)
        if day >=1:
            return day+1
        else:
            return 2

#39 Knapsack Light
---
1. **題目** : You found two items in a treasure chest! The first item weighs weight1 and is worth value1, and the second item weighs weight2 and is worth value2. What is the total maximum value of the items you can take with you, assuming that your max weight capacity is maxW and you can't come back for the items later? Note that there are only two items and you can't bring more than one item of each type, i.e. you can't take two first items or two second items.

2. **範例** :
* For` value1 = 10`, `weight1 = 5`, `value2 = 6`, `weight2 = 4`, and` maxW = 8`, the output should be `solution(value1, weight1, value2, weight2, maxW) = 10`. You can only carry the first item.

* For` value1 = 10`,` weight1 = 5`, `value2 = 6`, `weight2 = 4`, and `maxW = 9`, the output should be `solution(value1, weight1, value2, weight2, maxW) = 16`. You're strong enough to take both of the items with you.

3. **解法** :
根據考慮的情況包括：
1. 不能帶走任何一件。
2. 只能帶走其中一件。
3. 可以帶走兩件。

def solution(value1, weight1, value2, weight2, maxW):
    if maxW < min(weight1, weight2):
        return 0
    elif maxW < weight1 + weight2:
        if weight1 > maxW:
            return value2
        elif weight2 > maxW:
            return value1
        else:
            # both < maxW
            return max(value1, value2)
    else:
        return value1 + value2

#40 longestDigitsPrefix
---
1. **題目** : Given a string, output its longest prefix which contains only digits.

2. **範例** :
* For `inputString = "123aa1"`, the output should be
`solution(inputString) = "123"`.

3. **解法** :
要最長的只包含數字的前綴，所以當遇到數字變成英文就break

def solution(inputString):
    prefix = ""
    for char in inputString:
        if char.isdigit():
            prefix += char
        else:
            break
    return prefix