Array Pyhton - LeetCode

  Remove Duplicates from Sorted Array

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. 

It does not matter what you leave beyond the returned k (hence they are underscores).

class Solution:
2
    def removeDuplicates(self, nums: List[int]) -> int:
3
        #nums = [1,1,2]
4
        #nums = [0,0,1,1,1,2,2,3,3,4]
5
        
6
        head=0
7
        for i in range(1, len(nums)): 
8
            if nums[head] != nums[i]:
9
                head +=1
10
                nums[head]=nums[i] 
11
        
12
        
13
        print(nums)
14
        print(head+1)
15
        return head+1 # return Output
16
​

  Best Time to Buy and Sell Stock II

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. 

Total profit is 4 + 3 = 7.

class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        
4
        #Input: prices = [7,1,5,3,6,4]
5
        #[1,2,3,4,5]
6
​
7
        ans = 0
8
        for i in range(0, len(prices)-1):
9
            if prices[i + 1] > prices[i]:
10
                ans += prices[i + 1] - prices[i] 
11
                print(ans)
12
                
13
        return ans 
14
​
15
    
16
'''
17
题目大意
18
可以多次进行买卖操作，但是每天只能要么买要么卖，求最大收益。
19
​
20
解题方法
21
这个题不是说可以任意的挑选，而是要按照每天的顺序挑选。这样就很简单了，只要后面的一天比这天的价格高就买入卖出就可。
22
'''

  Rotate Array

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

class Solution:
2
    def rotate(self, nums: List[int], k: int) -> None:
3
        """
4
        Do not return anything, modify nums in-place instead.
5
        """
6
        #nums: [1,2,3,4,5,6,7]    3
7
        #[-1,-100,3,99] 2
8
        
9
        
10
        def numReverse(start, end):
11
            while start < end:
12
                nums[start], nums[end] = nums[end], nums[start]
13
                start += 1
14
                end -= 1
15
               
16
        k, n = k % len(nums), len(nums) # 3%7=3     2%1=0
17
        
18
        if k:
19
            numReverse(0, n - 1) #[7,6,5,4,3,2,1]
20
            numReverse(0, k - 1) #[5,6.7,4,3,2,1]
21
            numReverse(k, n - 1) #[5,6.7,1,2,3,4]
22
​
23
        '''
24
        雙指針（Two Pointer）
25
        
26
        分析/解題：
27
        題目給定一個陣列，將其往右輪轉k步，
28
        要求直接將該陣列調整成輪轉後的結果。
29
​
30
        這題一旦沒有Note的要求的話瞬間簡單一百倍。
31
        舉例來說，我們可以直接將後k項和前l-k項合併起來(l為陣列長度)，
32
        就會是答案了；或者，將整個陣列重複銜接一次，取[(l-k):(2 * l - k)]亦可。
33
        (這兩個解法筆者列在Python的註解中供讀者參閱)
34
        但，它們都不是in-place。
35
​
36
        要考慮到in-place的話，我們必須知道，
37
        一定有方法能讓他們跑到該有的地方，且不需用到超過O(1)以外的空間，
38
        一般就意味著會在陣列進行swap的操作(交換兩個元素)。
39
​
40
        先看一下原本的例子：
41
        [1,2,3,4,5,6,7] and k = 3 -> [5,6,7,1,2,3,4]
42
        先不論其他的部分，我們可以發現5~7從最尾端3個變成最前面的3個了；
43
        與此同時，1~4自然從最前面4個變成最尾端4個。
44
        我們先不論大家的順序，先將整個陣列倒過來的話，
45
        可以先達到1~4，5~7分別占據目標的區塊的效果：[7,6,5,4,3,2,1]。
46
        接著再比對一下，發現區塊是對了，但各自剛好被顛倒過一次，
47
        那麼我們再對7~5及4~1分別各進行一次反轉，就會得到我們要的結果。
48
​
49
        所以整個流程就會變成：
50
​
51
        將整個陣列進行反轉
52
        將前k個數進行反轉
53
        將後l-k個數進行反轉
54
        '''

  Contains Duplicate

Example 1:

Input: nums = [1,2,3,1]
Output: true

class Solution:
2
    def containsDuplicate(self, nums: List[int]) -> bool:
3
        #Input: nums = [1,2,3,1] 
4
        
5
        #集合（set）是一个无序的不重复元素序列。 裡面的值一定不是重複的
6
        
7
        print(nums)
8
        print(set(nums))
9
        print(len(nums))
10
        print(len(set(nums)))
11
        
12
        return len(nums) != len(set(nums))
13
        
14
        
15
        
16
'''
17
                
18
        暴力解 會超時
19
        for i in range(0, len(nums)-1):
20
            for j in range(i+1, len(nums)): #改i+1
21
                if nums[i]==nums[j]:
22
                    return True #也可以return 1
23
        '''
24
​
25
        #或者可以用sorted進行排序 就不會超時

  Single Number

Example 1:

Input: nums = [2,2,1]
Output: 1

class Solution:
2
    def singleNumber(self, nums: List[int]) -> int:
3
        #Input: nums = [2,2,1] 
4
        #[4,1,2,1,2]
5
        
6
        ans = 0
7
        for ele in nums:
8
            ans ^= ele  
9
            print(ans)
10
            
11
        return ans
12
          
13
        
14
'''
15
這題算是經典題目，因為經典做法太神奇了，
16
這題考的概念可以用 XOR 漂亮的解出來。
17
​
18
python 裡面，XOR 的符號表示做 「^」，
19
我們運用以下特性，同一個東西重複 XOR 兩次則變回原樣，
20
就可以在最小時間與空間解決此問題。
21
0 ^ a = a
22
a ^ a = 0
23
b ^ a ^ a = b
24
​
25
a | b | a ^ b
26
--|---|------
27
0 | 0 | 0
28
0 | 1 | 1
29
1 | 0 | 1
30
1 | 1 | 0
31
​
32
'''

  Intersection of Two Arrays II

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

class Solution:
2
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
3
        #Input: nums1 = [1,2,2,1], nums2 = [2,2]
4
        
5
        n1= sorted(nums1)
6
        n2= sorted(nums2) #已經由小到大 排序完成   nums1 = [1,1,2,2], nums2 = [2,2]
7
        
8
        
9
        i=0
10
        j=0
11
        q=[] #設定好串列初始值
12
        
13
        while (i < len(n1)) and (j < len(n2)) :
14
            if n1[i]>n2[j]: 
15
                j +=1        
16
                
17
            elif n1[i]<n2[j]:
18
                i +=1
19
                
20
            else: #n1==n2
21
                q.append(n1[i]) 
22
                i +=1
23
                j +=1 
24
                
25
        return q

  Plus One

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

class Solution:
2
    def plusOne(self, digits: List[int]) -> List[int]:
3
        #Input: digits = [1,2,3]
4
        #Output: [1,2,4]
5
        
6
        number_string = ''
7
        number_new = []
8
​
9
        # list 用字串串起來
10
        for number in digits:
11
            number_string += str(number)   #123
12
            
13
        # 字串轉數字，數字 +1
14
        number_string = str(int(number_string) + 1)    #124
15
​
16
        
17
        # 每一個位元拆開成新的 list
18
        for number in number_string:
19
            #1 
20
            #2 
21
            #4
22
            print(number)
23
            number_new.append(int(number))  
24
            
25
            #TypeError: ['1', '2', '4'] is not valid value for the expected return type integer[]
26
            #轉成integer 用int()
27
        
28
        return number_new
29
         
30
​
31
'''
32
題目分析
33
傳入一個純正整數的陣列
34
該陣列是一個大正整數，依照每個位數拆開
35
計算出該正整數 +1 的結果
36
把結果依照輸入的方式也輸出成陣列
37
解題過程
38
把輸入的陣列數字一個一個串成字串
39
字串轉換成數字，然後 +1
40
每個位元拆開做成新的 list 後回傳
41
'''

  Move Zeroes

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

class Solution:
2
    def moveZeroes(self, nums: List[int]) -> None:
3
        """
4
        Do not return anything, modify nums in-place instead.
5
        """
6
        #Input: nums = [0,1,0,3,12]
7
        
8
        head = 0
9
        for i in range(0,len(nums)):
10
            if nums[i]!=0:  #如果非0的話
11
                nums[head] = nums[i]  
12
                head += 1 
13
        
14
        for j in range(head, len(nums)):
15
            nums[j] = 0
16
            
17
        
18
'''
19
這邊要順便提到的一個名詞叫in-place algorithm。
20
所謂的in-place，就是指所有的操作修改，除了一些計數用的變數外，
21
基本上都在原先的資料結構內解決。
22
​
23
所以好像不能sorted
24
​
25
        nums=sorted(nums) #nums = [0,0,1,3,12]
26
        print(nums)
27
        for i in range(0,len(nums)-1): 
28
            if nums[i+1]!=nums[i]:
29
                count = i+1
30
                break
31
        
32
        head=0
33
        while count<len(nums):
34
            nums[head],  nums[count]= nums[count], 0
35
            print(nums)
36
            count +=1
37
            head +=1
38
            
39
        return nums
40
            
41
'''

  Two Sum

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

class Solution:
2
    def twoSum(self, nums: List[int], target: int) -> List[int]:
3
        # Input: nums = [2,7,11,15], target = 9
4
        # 雙指針（Two Pointer）
5
        # https://ithelp.ithome.com.tw/articles/10263103
6
        # https://ithelp.ithome.com.tw/articles/10269246
7
​
8
        
9
        '''
10
        這題主要考的是 HashTable，
11
        需要先建立一張表 (此處建立 dict)，
12
        利用 「key -> value」 的特性保存 「剩餘值 對應 index」
13
        因此當後續的計算，發現剩餘值存在 dict 的 key 中，
14
        就能快速反查表得到 index。
15
        '''
16
        #字典做法
17
        mydict = {}
18
        
19
        for idx in range(0,len(nums)):     
20
            #print(mydict.keys())       
21
            if nums[idx] in mydict.keys(): 
22
                print(mydict)
23
                return [mydict[nums[idx]], idx] 
24
            else:
25
                mydict[target - nums[idx]] = idx #保存 「剩餘值」 {'7': 0}
26
                
27
        
28
'''      
29
        nums_list = list(nums)
30
        nums_list.sort()
31
        print(nums_list)
32
        i = 0
33
        j = len(nums) - 1
34
​
35
​
36
        if target>=0:
37
            while (i<j):
38
                if (nums_list[i]+nums_list[j]>target):
39
                    j -=1             
40
                elif (nums_list[i]+nums_list[j]<target):
41
                    i +=1
42
                elif (nums_list[i]+nums_list[j]== target):
43
                    return sorted([i,j])
44
        else: #題目會給負值進行測試， 因此要特別改
45
            while (i<j):
46
                if (nums_list[i]+nums_list[j]<target):
47
                    j -=1             
48
                elif (nums_list[i]+nums_list[j]>target):
49
                    i +=1
50
                elif (nums_list[i]+nums_list[j]== target):
51
                    return sorted([i,j])
52
        
53
        return sorted([i,j])
54
                
55
​
56
題目會給負值進行測試， 因此要特別改
57
[-1,-2,-3,-4,-5]
58
-8
59
​
60
​
61
'''