# Intro (3-20)

#3 *checkPalindrome*
---
1. **題目** : Given the string, check if it is a palindrome.(檢查字串是否對稱)
2. **範例** :
* For `inputString = "aabaa"`, the output should be `solution(inputString) = true`;
* For `inputString = "abac"`, the output should be `solution(inputString) = false`;
3. **解法** :
先初始化左右位置，透過逐一比較並向中心移動若都沒有出現`FALSE` 則表示是palindrome

def solution(inputString):
    left, right = 0, len(inputString) - 1  # 初始化左右指針
    while left < right:  # 當左指針小於右指針時
        if inputString[left] != inputString[right]:  # 如果左右字符不相等，則不對稱
            return False
        left += 1  # 移動左指針
        right -= 1  # 移動右指針
    return True  # 如果遍歷完沒有發現不對稱，則對稱

**另解**
可直接檢查字串反轉後是否和原來一樣，但因為需要額外的記憶體空間：需要存儲反轉後的字串，這可能在處理大型字串時導致記憶體使用量增加

def solution(inputString):
    return inputString == inputString[::-1]

#4 *adjacentElementsProduct*
---
1. **題目** : Given an array of integers, find the pair of adjacent elements that has the largest product and return that product.
2. **範例** :
* For `inputArray = [3, 6, -2, -5, 7, 3]`, the output should be`solution(inputArray) = 21`;
3. **解法** :
透過初始無窮大值為標準，確保計算出來最大若為負值，也有基準可比較，接下來就透過計算相鄰兩個元素的乘積，當前計算的乘積大於之前的最大乘積，我們就更新 `max_product `為當前的乘積值

def solution(inputArray):
    max_product = float('-inf')  # 初始化
    for i in range(len(inputArray) - 1):  
        product = inputArray[i] * inputArray[i + 1]  
        if product > max_product:  
            max_product = product  # 更新最大乘積
    return max_product  # 返回最大乘積

#5 *shapeArea*
---
1. **題目** :

2. **範例** :
* For n = 2, the output should be `solution(n) = 5`;
* For n = 3, the output should be `solution(n) = 13`;
3. **解法** :
透過迴圈累加，並找出規律

def solution(n):
    result=1
    for i in range(1, n + 1):
        result+= 4*(i-1)
    return result

#6 *Make Array Consecutive 2*
---
1. **題目** :Ratiorg got statues of different sizes as a present from CodeMaster for his birthday, each statue having an non-negative integer size. Since he likes to make things perfect, he wants to arrange them from smallest to largest so that each statue will be bigger than the previous one exactly by 1.

2. **範例** :
* For `statues = [6, 2, 3, 8]`, the output should be solution(statues) = 3.Ratiorg needs statues of sizes `4`, `5` and `7`
3. **解法** :
透過先算出Array長度及個數，就知道要補足多少數字

def solution(statues):
    sorted_array = sorted(statues, reverse=True)
    arrey_len=len(statues)
    sizes=sorted_array[0]-sorted_array[-1]+1
    return sizes - arrey_len

#7 *almostIncreasingSequence*
---
1. **題目** :Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than **one** element from the array.
2. **範例** :
* For `sequence = [1, 3, 2]`, the output should be `solution(sequence) = true`.
* For `sequence = [1, 3, 2, 1]`, the output should be solution`(sequence) = false`.
3. **解法** :
要判斷這個序列 是否拿掉一個元素後嚴格遞增，我們會檢查兩種情況
1.是透過兩兩相鄰比較是否**前<後**
2.比較對於當**前元素的前一個<後一個** ，這個情況是為了有可能序列有重複情況或是分段遞增 ex[40, 50, 60, 10, 20, 30]

def solution(sequence):
    fails1 = 0
    fails2 = 0
    
    for i in range(len(sequence)-1):
            if sequence[i] >= sequence[i+1]:
                fails1 = fails1 + 1
                
    for i in range(len(sequence)-2):
            if sequence[i] >= sequence[i+2]:
                fails2 = fails2 + 1
                
    if (fails1 < 2) and (fails2 < 2):
                
        return True
    else:
        return False 

#8 *matrixElementsSum*
---
1. **題目** :Given matrix, a rectangular matrix of integers, where each value represents the cost of the room, your task is to return the total sum of all rooms that are suitable for the CodeBots (ie: add up all the values that don't appear below a 0).
2. **範例** :
* For

 matrix = [[0, 1, 1, 2], 
          [0, 5, 0, 0], 
          [2, 0, 3, 3]]

the output should be `solution(matrix) = 9`.

3. **解法** :
題目要求的就是當遇到當前元素為 **0**，則該欄底下都直接忽略，透過zip函數以及迴圈判斷進行累加就可求得答案

def solution(matrix):
    result = 0  # 初始化
    for column in zip(*matrix):  # 使用zip函数獲取每一列
        if 0 in column:  
            index = column.index(0) 
            column = column[:index]  # :index僅保留0之前的元素
        result += sum(column)  # 進行累加
    return result  # 返回最终结果

#9 *All Longest Strings*
---
1. **題目** :Given an array of strings, return another array containing all of its longest strings.
2. **範例** :
* For `inputArray = ["aba", "aa", "ad", "vcd", "aba"]`, the output should be`solution(inputArray) = ["aba", "vcd", "aba"]`

3. **解法** :

def solution(inputArray):
    sorted_arr = sorted(inputArray , key=len)

    # 取出排序後数组中的最大元素
    max_element = sorted_arr[-1]

    # 找出排序後数组中所有與最大元素相等的元素
    max_elements = [x for x in sorted_arr if len(x) == len(max_element)]
    
    return max_elements

#10 *commonCharacterCount*
---
1. **題目** :Given two strings, find the number of common characters between them.
2. **範例** :
* For `s1 = "aabcc" `and `s2 = "adcaa"`, the output should be `solution(s1, s2) = 3`.
Strings have 3 common characters - 2 "a"s and 1 "c".

3. **解法** :
透過先計算交集的元素，透過counter得到交集元素的出現次數，透過迴圈將鍵值加總

from collections import Counter
def solution(s1, s2):
    # 計算交集
    intersection = set(s1) & set(s2)

    # 計算每个元素的数量  格式ex :{'b': 1, 'c': 1, 'd': 1}
    intersection_count = Counter(s1) & Counter(s2)
    
    # 输出结果
    common_characters=0
    for char, count in intersection_count.items():
        common_characters+=count
    return common_characters

#11 *isLucky*
---
1. **題目** :Ticket numbers usually consist of an even number of digits. A ticket number is considered lucky if the sum of the first half of the digits is equal to the sum of the second half. <br>Given a ticket number` n`, determine if it's lucky or not.
2. **範例** :
* For `n = 1230`, the output should be `solution(n) = true`;
* For `n = 239017`, the output should be` solution(n) = false`.

3. **解法** :
* 透過確定中間位置索引(因為n是數字，要先轉成字串才能取得索引值)，就可以得出前辦及後半內容範圍，再透過sum函數加總比較
* **NOTE**:map(int, ...)：這一部分使用了 map 函式，它將字串中的每個字符轉換為整數，才能套用SUM

def solution(n):
    # 將整數轉換為字串
    n_str = str(n)  
    # 確定中間位置
    digit = len(n_str) // 2 
    # 將字串的前一半數字轉換為整數，並計算其和
    first_sum = sum(map(int, n_str[:digit]))
    # 將字串的後一半數字轉換為整數，並計算其和
    second_sum = sum(map(int, n_str[digit:]))   
    # 檢查兩個和是否相等，並返回結果
    return first_sum == second_sum

#12 *Sort by Height*
---
1. **題目** :Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!
2. **範例** :
* For `a = [-1, 150, 190, 170, -1, -1, 160, 180]`, the output should be`solution(a) = [-1, 150, 160, 170, -1, -1, 180, 190]`

3. **解法** :
* 此題主要是要問如何排序透過篩選後的**特定位置**數字，像這題可以看出**特定位置**為 除了數值=-1以外的數字，透過列表 a 中不是 -1 的元素提取出來，並且對它們進行排序。然後，使用一個指針 j，將排序後的高度值依次放入列表

def solution(a):
    heights = sorted([x for x in a if x != -1])
    j = 0
    for i in range(len(a)):
        if a[i] != -1:
            a[i] = heights[j]
            j += 1
    return a

#13 *reverseInParentheses*
---
1. **題目** :Write a function that reverses characters in (possibly nested) parentheses in the input string.<br>Input strings will always be well-formed with matching `()s`
2. **範例** :
* For `inputString = "(bar)"`, the output should be`solution(inputString) = "rab"`;
* For `inputString = "foo(bar)baz"`, the output should be
`solution(inputString) = "foorabbaz"`;

3. **解法** :
* 此題主要是要問如何反轉特定位置的字串，但因為有可能一個字串有多於一個()且還有內部嵌套(題目也有提到possibly nested)的情況，可能會導致錯誤的結果。<br> EX.有一個字符串為 "(foo(bar))"，如果僅僅根據 ( 和 ) 來判斷括號，你可能會錯誤地將 "(foo(bar)" 視為一個括號對
* 所以使用了一個堆疊（stack）來跟踪括號的位置，運作邏輯為
> 如果遇到左括號 (，將目前的 result 字串推入堆疊中，並將 result 重置為空字串。如果遇到右括號 )，從堆疊中彈出一個字串並將其與 result 字串進行逆序合併。
:::info
NOTE : pop() 方法用於從堆疊（stack）中移除並返回最後一個元素，即上一步stack.append(result)的字串
:::

def solution(inputString):
    stack = []
    result = ""
    for char in inputString:
        if char == "(":
            stack.append(result)
            result = ""
        elif char == ")":
            result = stack.pop() + result[::-1]
        else:
            result += char
    return result

#14 *alternatingSums*
---
1. **題目** :Several people are standing in a row and need to be divided into two teams. The first person goes into team 1, the second goes into team 2, the third goes into team 1 again, the fourth into team 2, and so on.
>You are given an array of positive integers - the weights of the people. Return an array of two integers, where the first element is the total weight of team 1, and the second element is the total weight of team 2 after the division is complete.
2. **範例** :
* For `a = [50, 60, 60, 45, 70]`, the output should be
`solution(a) = [180, 105]`.

3. **解法** :
* NOTE : enumerate() 函式是 Python 中一個很有用的函式，它用於將可迭代對象中的元素以及它們的索引一起迭代

def solution(a):
    sum_arr1, sum_arr2 = 0, 0
    for i, num in enumerate(a): 
        if i % 2 == 0:  
            sum_arr1 += num
        else: 
            sum_arr2 += num
    return [sum_arr1, sum_arr2]

#15 *Add Border*
--
1. **題目** :Given a rectangular matrix of characters, add a border of asterisks(*) to it.

2. **範例** :
* For picture =

["abc",
"ded"]

the output should besolution(picture) =

["*****",
"*abc*",
"*ded*",
"*****"].

3. **解法** :

def solution(picture):
    bordered_picture = []
    width = len(picture[0]) + 2  # 矩陣的寬度加上邊框
    border_row = '*' * width  # 邊框行

    bordered_picture.append(border_row)  # 添加頂部邊框

    for row in picture:
        bordered_row = '*' + row + '*'  # 在每一行的開頭和結尾添加星號
        bordered_picture.append(bordered_row)

    bordered_picture.append(border_row)  # 添加底部邊框

    return bordered_picture

#16 *Are Similar?*
--
1. **題目** :Two arrays are called similar if one can be obtained from another by **swapping at most one pair** of elements in one of the arrays.

> Given two arrays a and b, check whether they are similar.
2. **範例** :
* For `a = [1, 2, 3]` and `b = [1, 2, 3]`, the output should be
`solution(a, b) = true`.
The arrays are equal, no need to swap any elements.

* For `a = [1, 2, 3]` and `b = [2, 1, 3]`, the output should be
`solution(a, b) = true`.
We can obtain b from a by swapping 2 and 1 in b.
3. **解法** :
根據題目需要確定兩個條件，彼此字元駔成個數`Counter(a) == Counter(b)`相同，以及若不同最多只能有兩個位置是不同`的result <= 2`

from collections import Counter
def solution(a, b):
    result = 0
    for num_a, num_b in zip(a, b):  # 使用 zip() 同時迭代 a 和 b 中的元素
        if num_a != num_b:  # 如果相同位置的元素不相等
            result += 1  
    return result <= 2 and   Counter(a) == Counter(b)

#17 *arrayChange*
--
1. **題目** :You are given an array of integers. On each move you are allowed to increase exactly one of its element by one. Find the minimal number of moves required to obtain a strictly increasing sequence from the input.

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

3. **解法** :
根據題目試想算出若要改變呈遞增數列，最少需要改變多少，解法就是根據相鄰元素比較，並更新數列做下一個比較，計算差值並累計minimal number of moves required，記得累計差值要先寫在更新串列元素前面，否則會運用到更新後的串列元素

def solution(inputArray):
    count=0
    for i in range(len(inputArray) - 1):
        if inputArray[i] > inputArray[i + 1]:
            count += inputArray[i] - inputArray[i + 1] + 1
            inputArray[i + 1] = inputArray[i] + 1
        elif inputArray[i] == inputArray[i + 1]:
            count += 1
            inputArray[i + 1] = inputArray[i] + 1
    return count

#18 *palindromeRearranging*
--
1. **題目** :Given a string, find out if its characters can be rearranged to form a palindrome.

2. **範例** :
* For `inputString = "aabb"`, the output should be` solution(inputString) = true`.<br>We can rearrange `"aabb"` to make` "abba"`, which is a palindrome.

3. **解法** :

from collections import Counter
def solution(inputString):
    intersection_count = Counter(inputString)
    # 输出结果
    result=0
    for char, count in intersection_count.items():
        if count % 2 == 0:
            pass
        else:
            result+=1
    return result <= 1
            

#19 *areEquallyStrong*
--
1. **題目** :Call two arms equally strong if the heaviest weights they each are able to lift are equal.Call two people equally strong if their strongest arms are equally strong (the strongest arm can be both the right and the left), and so are their weakest arms.Given your and your friend's arms' lifting capabilities find out if you two are equally strong.

2. **範例** :
* For `yourLeft = 15, yourRight = 10, friendsLeft = 15, and friendsRight = 10,` the output should be `solution(yourLeft, yourRight, friendsLeft, friendsRight) = true`;
* For `yourLeft = 15, yourRight = 10, friendsLeft = 15, and friendsRight = 9`, the output should be `solution(yourLeft, yourRight, friendsLeft, friendsRight) = false`.
3. **解法** :
實際上就是測驗如何得知兩手和對手一樣或是相反 (才為true)

from collections import Counter

def solution(yourLeft, yourRight, friendsLeft, friendsRight):
    # 将你和朋友的左右臂的能力放入Counter中
    your_arms = Counter([yourLeft, yourRight])
    friends_arms = Counter([friendsLeft, friendsRight])
    
    # 检查是否你和朋友的臂同样强壮
    if your_arms == friends_arms:
        return True
    else:
        return False

            

#20 *arrayMaximalAdjacentDifference*
--
1. **題目** :Given an array of integers, find the maximal absolute difference between any two of its adjacent elements.

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

def solution(inputArray):
    max_difference = float('-inf')  # 初始化
    for i in range(len(inputArray) - 1):  
        difference = abs(inputArray[i + 1] - inputArray[i])
        if difference > max_difference:  
            max_difference = difference  # 更新最大乘積
    return max_difference  # 返回最大乘積