Algorithm & Data structure | LeetCode_ 數(shù)組系列

由于對數(shù)據(jù)結(jié)構(gòu)和算法掌握的不熟練氛悬，目前是小白入門階段则剃，痛下決心，要好好補(bǔ)一補(bǔ)如捅。從大神大牛的算法學(xué)習(xí)棍现，逐漸自己加強(qiáng)自身技能，若有理解錯誤镜遣，還望批評指教己肮。---ZJ

LeetCode | 數(shù)組系列 | Leetbook | JackCui | LeetCode 探索

1.兩數(shù)之和（Easy）

題目描述

給定一個整數(shù)數(shù)組和一個目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個數(shù)。

你可以假設(shè)每個輸入只對應(yīng)一種答案谎僻，且同樣的元素不能被重復(fù)利用娄柳。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

自己的理解：

遍歷，雙重 for 循環(huán)遍歷
我的想法很傻
先學(xué)習(xí)大神們的算法

方法一：（96.65%）

學(xué)習(xí)原作者：JackCui的算法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        # 1. 先判斷 nums 是否是 2 個數(shù)艘绍，<= 1 則返回 False
        if len(nums) <= 1:
            print("數(shù)組長度錯誤")
            return False
        # 2. 創(chuàng)建空字典
        result_dic = {}
        
        # 3. for 循環(huán)遍歷 nums 的長度
        for i in range(len(nums)):
            print(i)
            # 4. 如果 nums 中 第 i 個元素是 字典中的 key
            # 那么返回 一個list 赤拒，list 中包含 result_dic 字典中 num[i] 作為 key 對應(yīng)的 value 的值，以及 i 值鞍盗，為最終結(jié)果
            if nums[i] in result_dic:
                print("result_dic :",result_dic)
                return [result_dic[nums[i]], i]
            # 5. 如果 nums 中 第 i 個元素不在字典中需了，
            # 那么 在字典中添加 以 target 減去 nums[i] 元素的值 作為 key ，value 為 索引值 i 
            else:
                 result_dic[target - nums[i]] = i

s = Solution()
print("result:",s.twoSum([6,0,0,2, 5, 11, 15,7], 9))

0
1
2
3
4
5
6
7
result_dic : {3: 0, 9: 2, 7: 3, 4: 4, -2: 5, -6: 6}
result: [3, 7]

s = Solution()
print("result:",s.twoSum([1,5,0,2, 5, 11, 15,7], 6))

0
1
result_dic : {5: 0}
result: [0, 1]

方法二：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
#         hash = {}
#         #循環(huán)nums數(shù)值般甲，并添加映射
#         for i in range(len(nums)):
#             if target - nums[i] in hash:
#                 return [hash[target - nums[i]], i]
#             hash[nums[i]] = i
#         #無解的情況
#         return [-1, -1]
        hash = {}
        for i in range(len(nums)):
            if target - nums[i] in hash:
                return [hash[target - nums[i]], i]
            hash[nums[i]] = i
        return [-1, -1]

解釋：

從上面兩個例子運算的過程及結(jié)果可以看出來肋乍，這個算法的巧妙之處在于，將原有的加法問題敷存，轉(zhuǎn)換為以結(jié)果為主導(dǎo)的減法問題
result_dic 字典中的 key 是 target 減去當(dāng)前 i 值后的數(shù)墓造，并記錄使得該算式成立的 i 值
所以若 nums[i] 正存在于 result_dic 中，則又找到了與之前存的內(nèi)容正好匹配的兩個值锚烦，同時也對應(yīng)著兩個索引
所以返回的是觅闽，之前存的 key 對應(yīng)的 value （也就是其中一個索引值）以及當(dāng)前的 i 值

26. 刪除排序數(shù)組中的重復(fù)項 (Easy)

題目描述

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素涮俄，使得每個元素只出現(xiàn)一次蛉拙，返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間彻亲，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成孕锄。

示例 1:

給定數(shù)組 nums = [1,1,2], 

函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。 

你不需要考慮數(shù)組中超出新長度后面的元素苞尝。

示例 2:

給定 nums = [0,0,1,1,1,2,2,3,3,4],

函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4畸肆。

你不需要考慮數(shù)組中超出新長度后面的元素。

說明:

為什么返回數(shù)值是整數(shù)宙址，但輸出的答案是數(shù)組呢?

請注意轴脐，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的抡砂。

你可以想象內(nèi)部操作如下:

// nums 是以“引用”方式傳遞的大咱。也就是說，不對實參做任何拷貝
int len = removeDuplicates(nums);

// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的注益。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素徽级。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

方法一：

class Solution1(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """      
        i = 0
        while i < len(nums)-1:
            print(nums)
            if nums[i] == nums[i+1]:                
                del nums[i]
            else:
                i+=1
        return len(nums)  
    
#         new = list(set(nums))
#         new.sort()
#         length = len(new)
#         for i in range(length):
#             nums[i] = new[i]
#         return length

s1 = Solution1()
print("result:", s1.removeDuplicates([0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]))

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9]
result: 7

a = [0,3,4,9,1,1,0,3,4,7,2,2]
print(a)
a.sort() # 使用 list.sort() 方法來排序，此時 list 本身將被修改聊浅。
print(a)

[0, 3, 4, 9, 1, 1, 0, 3, 4, 7, 2, 2]
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]

錯誤記錄：

注意審題餐抢，“給定一個排序數(shù)組 ”现使，已經(jīng)排好序，則從已經(jīng)排好的序的角度去考慮旷痕，不要去考慮亂序的碳锈，哪怕真是亂序的 list ，那么第一步也應(yīng)該是先排序欺抗，之后再處理

方法二：

# 85.45% 60ms
class Solution2(object):
    """ 
    @param A: a list of integers 
    @return an integer 
    """  
    def removeDuplicates(self, nums):  
        #write your code here  
#         k=0  
#         for i in range(1,len(A)):  
#             if A[i] != A[k]:  
#                 k+=1  
#                 A[k] = A[i]  
          
#         del A[k+1:len(A)]  
#         return len(A)  
        # for-loop 遍歷 nums 從 1 到 len(nums) 的長度售碳，去除 長度為 0 的情況
        # 如果
        
        k = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[k]:
                k+=1
                nums[k] = nums[i]
                print(nums)
             
        del nums[k+1:len(nums)]
        print(nums)
        return len(nums)

s2 = Solution2()
print("result:", s2.removeDuplicates([0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]))

[0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9]
result: 7

# 56ms (不帶 刪除的代碼) 60 ms 帶有刪除的代碼   del nums[pos:len(nums)]
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pos = 0
        this_num = None
        for num in nums:
            if num != this_num:
                nums[pos] = num
                print(nums)
                this_num = num
                pos += 1
        del nums[pos:len(nums)]
        print(nums)
        return pos

s2 = Solution()
print("result:", s2.removeDuplicates([0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]))

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 1, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 2, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 2, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 3, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9, 3, 4, 4, 7, 9]
[0, 1, 2, 3, 4, 7, 9]
result: 7

總結(jié)：

法 1 和法 2 對比，明顯法 2 更快
法 1 是兩兩對比绞呈，會將同一個數(shù)贸人，跟其他的數(shù)多次對比判斷
法 2 用的則是，先找出來所有不相同的數(shù)佃声，將不同的數(shù)賦值到最前面艺智，最終能得到，所有唯一的數(shù)都排列在最前面圾亏，中間舍棄了一些相同的數(shù)十拣，后面相同的數(shù)，最后也會被提取或刪掉

121. 買賣股票的最佳時機(jī) (Easy)

題目描述

給定一個數(shù)組志鹃，它的第 i 個元素是一支給定股票第 i 天的價格夭问。

如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計一個算法來計算你所能獲取的最大利潤曹铃。

注意你不能在買入股票前賣出股票缰趋。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出陕见，最大利潤 = 6-1 = 5 秘血。
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0淳玩。

思路：

先找到最小值直撤，然后再找最小值后面的最大值
第 2 小值非竿，以及第 2 小值后面的最大值如：[2, 9, 1, 3]
也就是所有小值蜕着，以及后面最大值之間的差值，再比較哪個更大
雙指針遍歷所有情況红柱，選擇最大利潤承匣。時間復(fù)雜度 $O(n^2)$

方法一：

# 非常蠢的方法，沒有通過測試用例
class Solution3(object):
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        result = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                print("i=%d, j=%d"%(i,j))
                result = max(result, prices[j] - prices[i])
                print(result)
        return result

s = Solution3()
print(s.maxProfit([7,6,4,3,1]))

i=0, j=1
0
i=0, j=2
0
i=0, j=3
0
i=0, j=4
0
i=1, j=2
0
i=1, j=3
0
i=1, j=4
0
i=2, j=3
0
i=2, j=4
0
i=3, j=4
0
0

方法一在 LeetCode 上沒通過 199 / 200 個通過測試用例

最后執(zhí)行的輸入：
[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9....]

超出時間限制

方法二：

動態(tài)規(guī)劃：選取最小的價格購買锤悄，保留最大的利潤韧骗。只需一次遍歷。時間復(fù)雜度$O(n)$

思路：

# 73.33% 40 ms
class Solution(object):
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        # if len(prices) < 2:return 0
        if prices is None or len(prices) == 0:
            return 0
        begin_value = princes[0]
        result = 0
        for p in prices:
            result = max(result, p- begin_value)
            begin_value = min(begin_value, p)
        return result

s = Solution3()
print(s.maxProfit([7,6,4,3,1]))

i=0, j=1
0
i=0, j=2
0
i=0, j=3
0
i=0, j=4
0
i=1, j=2
0
i=1, j=3
0
i=1, j=4
0
i=2, j=3
0
i=2, j=4
0
i=3, j=4
0
0

方法三：

# 32ms
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        if not prices:
            return 0
        
        revenue = 0
        
        prev = float('inf')
        
        for price in prices:
            if price < prev:
                prev = price
            else:
                revenue = max(price - prev, revenue)

        return revenue

Python 中可以用如下方式表示正負(fù)無窮：

float("inf"), float("-inf")

方法四：

# 28ms
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices) <= 1:
            return 0

        minBuy = prices[0]
        max_profit = 0
        for p in prices[1:]:
            if p < minBuy:
                minBuy = p
            if p - minBuy > max_profit:
                max_profit = p - minBuy

        return max_profit

122. 買賣股票的最佳時機(jī) II (Easy)

題目描述

給定一個數(shù)組零聚，它的第 i 個元素是一支給定股票第 i 天的價格袍暴。

設(shè)計一個算法來計算你所能獲取的最大利潤些侍。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）政模。

返回的是最大盈利的數(shù)字岗宣。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 淋样。
     隨后耗式，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 趁猴。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入刊咳，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接連購買股票儡司，之后再將它們賣出娱挨。
     因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票枫慷。

示例 3:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0让蕾。

# 36ms
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices is None or len(prices) < 2:
            return 0
        result = 0
        Begin_value = prices[0]
        for p in prices:
            # 越復(fù)雜的問題，越要用簡單的方式去思考
            # 只要后面的值大于前面的值 就賣出或听，并重新買入
            if p > Begin_value:
                result += p-Begin_value  #漲股利潤累加
                Begin_value = p          #重新買股
            else:
                # 若后面的值探孝，小于前面的值，則重新設(shè)置最小值                
                Begin_value = min(Begin_value, p)
        return result

s = Solution()
print(s.maxProfit([7,1,5,3,6,4]))

# 32ms
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        profit = 0
        for i in range(n - 1):
            if prices[i + 1] - prices[i] >= 0:
                profit += prices[i + 1] - prices[i]
        return profit

# 28ms
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        for index in xrange(1, len(prices)):
            if prices[index] > prices[index - 1]:
                profit += prices[index] - prices[index - 1]
        return profit

xrange 用法與 range 完全相同誉裆，所不同的是生成的不是一個 list對象，而是一個生成器足丢。

>>> xrange(5)
xrange(5)
>>> list(xrange(5))
[0, 1, 2, 3, 4]
>>> xrange(1,5)
xrange(1, 5)
>>> list(xrange(1,5))
[1, 2, 3, 4]
>>> xrange(0,6,2)
xrange(0, 6, 2)
>>> list(xrange(0,6,2))
[0, 2, 4]

189. 旋轉(zhuǎn)數(shù)組 (Easy)

旋轉(zhuǎn)數(shù)組

參考文章:LeetCode:Rotate Array

題目描述

將包含 n 個元素的數(shù)組向右旋轉(zhuǎn) k 步粱腻。

例如，如果 n = 7 , k = 3斩跌，給定數(shù)組 [1,2,3,4,5,6,7] 绍些，向右旋轉(zhuǎn)后的結(jié)果為 [5,6,7,1,2,3,4]。

注意:

盡可能找到更多的解決方案耀鸦，這里最少有三種不同的方法解決這個問題柬批。

提示:

要求空間復(fù)雜度為 O(1)

關(guān)聯(lián)的問題: 反轉(zhuǎn)字符串中的單詞 II

致謝:
特別感謝 @Freezen 添加此問題并創(chuàng)建所有測試用例。

方法一：

時間復(fù)雜度O（n）袖订，空間復(fù)雜度O(1)

思路：將數(shù)組元素依次循環(huán)向右平移 k 個單位

【目前理解這個方法還是很懵氮帐，腦袋清醒了再回來看】

# 方法一 時間復(fù)雜度O（n），空間復(fù)雜度O(1) 
class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        idx = 0
        distance = 0
        cur = nums[0]
        for x in range(n):
            # 取 % 這個操作 正好可以找到 當(dāng)前索引位置的數(shù)要被轉(zhuǎn)換到的位置            
            idx = (idx + k) % n
            print('idx', idx)
            # 兩個數(shù)互換             
            nums[idx], cur = cur, nums[idx]
            # cur 存儲當(dāng)前被換出來的數(shù)             
            print('cur',cur)
            
            # cur 3 6 2 5 1 4             
            
            distance = (distance + k) % n
            # =0 代表恰好可以整除             
            if distance == 0:
                idx = (idx + 1) % n
                cur = nums[idx]
            print('nums2',nums)

s = Solution()
print(s.rotate([1,2,3,4,5,6,7],3))

idx 3
cur 4
nums2 [1, 2, 3, 1, 5, 6, 7]
idx 6
cur 7
nums2 [1, 2, 3, 1, 5, 6, 4]
idx 2
cur 3
nums2 [1, 2, 7, 1, 5, 6, 4]
idx 5
cur 6
nums2 [1, 2, 7, 1, 5, 3, 4]
idx 1
cur 2
nums2 [1, 6, 7, 1, 5, 3, 4]
idx 4
cur 5
nums2 [1, 6, 7, 1, 2, 3, 4]
idx 0
cur 1
nums2 [5, 6, 7, 1, 2, 3, 4]
None

方法二：

時間復(fù)雜度 O（n）洛姑，空間復(fù)雜度O(1)

思路：以 n - k 為界上沐，分別對數(shù)組的左右兩邊執(zhí)行一次逆置；然后對整個數(shù)組執(zhí)行逆置楞艾。

# 方法二 時間復(fù)雜度O（n）参咙，空間復(fù)雜度O(1) 
class Solution(object):
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        n = len(nums)
        k %= n
        self.reverse(nums, 0, n - k)
        self.reverse(nums, n - k, n)
        self.reverse(nums, 0, n)
        print(nums)

    def reverse(self, nums, start, end):
        for x in range(start, int((start + end) / 2)):
            nums[x] ^= nums[start + end - x - 1]
            nums[start + end - x - 1] ^= nums[x]
            nums[x] ^= nums[start + end - x - 1]

s = Solution()
print(s.rotate([1,2,3,4,5,6,7],3))

[5, 6, 7, 1, 2, 3, 4]
None

實現(xiàn)兩個數(shù)交換：

a ^= b
b ^= a
a ^= b

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length = len(nums) 
        if k==0:
            return
        if(k<length):
            nums[0:k], nums[k:length] = nums[length-k:length], nums[0:length-k]
        elif(k>length):
            k = k - length
            nums[0:k], nums[k:length] = nums[length-k:length], nums[0:length-k]

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # 直接將 需要旋轉(zhuǎn)的 k 個放到前面龄广，前面的放到后面
        #  如：nums[4:] 從索引 4 開始一直到最后一個
        # nums[:4] 從 0 開始一直到 索引4 不包含 索引4  的值
        nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]

217.存在重復(fù)(Easy)

題目描述

給定一個整數(shù)數(shù)組，判斷是否存在重復(fù)元素蕴侧。

如果任何值在數(shù)組中出現(xiàn)至少兩次蜀细，函數(shù)應(yīng)該返回 true。如果每個元素都不相同戈盈，則返回 false奠衔。

# 不解釋了
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(set(nums)) != len(nums)

136. 只出現(xiàn)一次的數(shù)字(Easy)

題目描述

給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外塘娶，其余每個元素均出現(xiàn)兩次归斤。找出那個只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時間復(fù)雜度刁岸。你可以不使用額外空間來實現(xiàn)嗎脏里？

示例 1:

輸入: [2,2,1]
輸出: 1

示例 2:

輸入: [4,1,2,1,2]
輸出: 4

思路：

我的想法很蠢，不說了

參考：

Leetcode解題思路總結(jié)(Medium)

LeetCode: Single Number解題思路

a^a=0, a^0=a虹曙，根據(jù)交換律a^b=b^a迫横，比如3^4^3=4，根據(jù)異或操作的這種性質(zhì)酝碳，我們可以將所有元素依次做異或操作矾踱，相同元素異或為 0，最終剩下的元素就為 Single Number疏哗。

因為A XOR A = 0呛讲，且XOR運算是可交換的，于是返奉，對于實例{2,1,4,5,2,4,1}就會有這樣的結(jié)果：

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5

就把只出現(xiàn)了一次的元素(其余元素均出現(xiàn)兩次)給找出來了贝搁！

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp = 0
        for item in nums:
            temp ^= item
            print(temp)

        return temp

s = Solution()
print(s.singleNumber([4,1,2,1,2]))

class Solution {
public:
    int singleNumber(vector<int>& nums) {
     int count=0;
     for(int i=0;i<nums.size();i++){
         count^=nums[i];
      }
     return count;
}    
};

^按位異或運算符：當(dāng)對應(yīng)的二進(jìn)位相異(不同)時，結(jié)果為 1 （不同為 1芽偏，相同為 0）

(a ^ b) 輸出結(jié)果 49 雷逆，二進(jìn)制解釋： 0011 0001

a = 60 # 0011 1100

b = 13 # 0000 1101 

a ^ b  # 0011 0001

350. 兩個數(shù)組的交集 II (Easy)

題目描述

給定兩個數(shù)組，寫一個方法來計算它們的交集污尉。

例如:

給定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

輸出結(jié)果中每個元素出現(xiàn)的次數(shù)膀哲，應(yīng)與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致。
(只跟次數(shù)有關(guān)十厢，跟順序無關(guān))

我們可以不考慮輸出結(jié)果的順序等太。

例： nums1 = [3,3,3,3,3,3,1,1], nums2 = [1,3,3,3,2,1] 答案：[3,3,3,1,1] [1,3,3,3,1] 兩個都對捂齐，跟順序無關(guān)

跟進(jìn):

如果給定的數(shù)組已經(jīng)排好序呢蛮放？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多奠宜，哪種方法更優(yōu)包颁？
如果 nums2 的元素存儲在磁盤上瞻想，內(nèi)存是有限的，你不能一次加載所有的元素到內(nèi)存中娩嚼，你該怎么辦蘑险？

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # 用來存儲出現(xiàn)的 數(shù)字，以及與之對應(yīng)的次數(shù)         
        nums_map = {}
        for i in nums2:
            if i in nums_map:
                nums_map[i] += 1
            else:
                nums_map[i] = 1
        # 存儲 要返回的list 結(jié)果岳悟，與順序無關(guān)
        print('nums_map',nums_map)
        res = []
        for i in nums1:
            if i in nums_map and nums_map[i] > 0:
                res += [i]
                print(res)
                # 前面的 字典中佃迄，有其中一個 nums 中元素出現(xiàn)的次數(shù)的統(tǒng)計，
                # 當(dāng)遍歷第二個的時候贵少，每向 list 中添加一個 字典中統(tǒng)計的次數(shù)就減少一個
                nums_map[i] -= 1
                print('nums_map_final:',nums_map)
        return res

s = Solution()
print('result:',s.intersect([1,3,3,3,3,3,3,3,3,3,3,3,2,1],[3,3,3,1,1]))

nums_map {3: 3, 1: 2}
[1]
nums_map_final: {3: 3, 1: 1}
[1, 3]
nums_map_final: {3: 2, 1: 1}
[1, 3, 3]
nums_map_final: {3: 1, 1: 1}
[1, 3, 3, 3]
nums_map_final: {3: 0, 1: 1}
[1, 3, 3, 3, 1]
nums_map_final: {3: 0, 1: 0}
result: [1, 3, 3, 3, 1]

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        m = {}
        for x in nums1:
            if m.has_key(x):
                m[x] += 1
            else:
                m[x] = 1
        
        res = []
        for x in nums2:
            if m.has_key(x) and m[x] > 0:    
                res.append(x)
                m[x] -= 1
        return res

66. 加一 (Easy)

題目描述

給定一個非負(fù)整數(shù)組成的非空數(shù)組呵俏，在該數(shù)的基礎(chǔ)上加一，返回一個新的數(shù)組滔灶。

最高位數(shù)字存放在數(shù)組的首位普碎，數(shù)組中每個元素只存儲一個數(shù)字。

你可以假設(shè)除了整數(shù) 0 之外录平，這個整數(shù)不會以零開頭麻车。

示例 1:

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。

示例 2:

輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321斗这。

理解 & 思路：

LeetCode 66. Plus One（加1）
LeetCode 66

這道題目給了我們一個 digits 的 array动猬，這個 array 等于一個數(shù)字，讓我們加 1表箭。

來分析一下枣察，如果是不需要進(jìn)位的 < 9 ，那么直接加 1 就返回燃逻。

如果是需要進(jìn)位的序目，=9，那么我們需要把目前的 digit 改為0伯襟，接著繼續(xù)檢查前一位猿涨，因為你不確定前一位加 1 是不是需要進(jìn)位。

一旦當(dāng)我們找到不需要進(jìn)位的那個 digit姆怪，加 1 返回就可以了叛赚。

如果碰到一種極端的情況，類似于 999 的話稽揭，那么我們遍歷完之后是 000俺附，還需要一個1 ，所以要重新建立一個array溪掀， size + 1事镣，把 1 加在 [0] 的位置。

一個非負(fù)數(shù)的內(nèi)容從高位到低位(十進(jìn)制位)依次放到數(shù)組的每一位揪胃，例如：123璃哟，存放到數(shù)組中就是[1,2,3]英融，現(xiàn)在將這個數(shù)加 1 糕非，返回加1后的結(jié)果，如[1,2,3]應(yīng)該返回[1,2,4].

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        carry = 1
        # 倒序，從 數(shù)組的最后一位開始熊响， 4猾编， 3,2 1,0         
        for i in range(len(digits))[::-1]:  
            # 先對數(shù)字進(jìn)行 加 1 操作
            digits[i] += carry  
            if digits[i] > 9:  
                # digits[i] 原本 =9 , 加 1 后 大于 9 為 10 逝薪，則需進(jìn)一位杠览。
                # 則  digits[i] -10 變?yōu)?0
                digits[i] -= 10  
                carry = 1  
            else:  
                carry = 0  
        # 這個針對于 都是 9999 這種情況 需要整個長度上 加 1 插入 索引 0 位  1                  
        if carry > 0:  
            print('digits:',digits)
            digits.insert(0, 1)  
        return digits

s = Solution()
print(s.plusOne([9,9,9,9,9,9]))

digits: [0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]

for i in range(0,5)[::-1]:
    print(i)
    
a = [9,9,9,9]    

a.insert(0,1)
print(a)

4
3
2
1
0
[1, 9, 9, 9, 9]

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        cur =1
        a=len(digits)
        for i in range(a):  
            # 用來實現(xiàn)倒數(shù) a-1-i  4， 3,2,1             
            if digits[a-1-i]+cur>9:
                digits[a-1-i]=0
                cur=1
            else:
                digits[a-1-i]+=cur 
                cur=0
        if cur==1:
            digits.insert(0,1)
              
        return digits

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        # 先把 list 轉(zhuǎn)化成字符串当宴，再轉(zhuǎn)成 int 類型 進(jìn)行 加 1 操作挽荡，
        # 之后再循環(huán)遍歷轉(zhuǎn)成 list
        tmp = ''
        for i in digits:
            tmp += str(i)
        tmp = int(tmp) + 1
        digits = [int(i) for i in list(str(tmp))]
        #  return [int(i) for i in str(tmp)]
        return digits

283. 移動零 (Easy)

題目描述

給定一個數(shù)組 nums, 編寫一個函數(shù)將所有 0 移動到它的末尾，同時保持非零元素的相對順序即供。

例如定拟，定義 nums = [0, 1, 0, 3, 12]，調(diào)用函數(shù)之后逗嫡， nums 應(yīng)為 [1, 3, 12, 0, 0]青自。

注意事項:

必須在原數(shù)組上操作，不要為一個新數(shù)組分配額外空間驱证。
盡量減少操作總數(shù)延窜。

思路：

一開始的想法是，判斷是 0 后抹锄，保持最前面的不動逆瑞，把后面的前移，最后末尾再加 0
然后測試用例伙单，后面幾個沒有通過
看到別人的想法是兩兩互換

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        s = e = 0
        while e < len(nums):
            if nums[e]:
                nums[s] = nums[e]
                print('nums1:',nums)
                s += 1
            e += 1
            
        while s < len(nums):
            nums[s] = 0
            s += 1
            print('s:',s)
            print('nums2:',nums)

s = Solution()
print(s.moveZeroes([1,0,2,3,0,0,4,0,9]))

nums1: [1, 0, 2, 3, 0, 0, 4, 0, 9]
nums1: [1, 2, 2, 3, 0, 0, 4, 0, 9]
nums1: [1, 2, 3, 3, 0, 0, 4, 0, 9]
nums1: [1, 2, 3, 4, 0, 0, 4, 0, 9]
nums1: [1, 2, 3, 4, 9, 0, 4, 0, 9]
s: 6
nums2: [1, 2, 3, 4, 9, 0, 4, 0, 9]
s: 7
nums2: [1, 2, 3, 4, 9, 0, 0, 0, 9]
s: 8
nums2: [1, 2, 3, 4, 9, 0, 0, 0, 9]
s: 9
nums2: [1, 2, 3, 4, 9, 0, 0, 0, 0]
None

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # point 記住的元素為 0 的索引位置 
        point = 0
        for i in range(len(nums)):
            # 當(dāng)前位置元素不為 0 的情況下获高，跟之前記錄的索引為 0 的值交換
            if nums[i]:
                nums[point] , nums[i] = nums[i], nums[point]
                point += 1
            print(nums)
            print("point:",point)
            print('i:',i,'\n'+('-'*30))

s = Solution()
print(s.moveZeroes([0,1,0,2,3,0,0,4,0,9]))

[0, 1, 0, 2, 3, 0, 0, 4, 0, 9]
point: 0
i: 0 
------------------------------
nums[i] 1
[1, 0, 0, 2, 3, 0, 0, 4, 0, 9]
point: 1
i: 1 
------------------------------
[1, 0, 0, 2, 3, 0, 0, 4, 0, 9]
point: 1
i: 2 
------------------------------
nums[i] 2
[1, 2, 0, 0, 3, 0, 0, 4, 0, 9]
point: 2
i: 3 
------------------------------
nums[i] 3
[1, 2, 3, 0, 0, 0, 0, 4, 0, 9]
point: 3
i: 4 
------------------------------
[1, 2, 3, 0, 0, 0, 0, 4, 0, 9]
point: 3
i: 5 
------------------------------
[1, 2, 3, 0, 0, 0, 0, 4, 0, 9]
point: 3
i: 6 
------------------------------
nums[i] 4
[1, 2, 3, 4, 0, 0, 0, 0, 0, 9]
point: 4
i: 7 
------------------------------
[1, 2, 3, 4, 0, 0, 0, 0, 0, 9]
point: 4
i: 8 
------------------------------
nums[i] 9
[1, 2, 3, 4, 9, 0, 0, 0, 0, 0]
point: 5
i: 9 
------------------------------
None

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num=0
        for i in range(len(nums)):
            if nums[i]==0:
                num+=1
            else:
                nums[i-num]=nums[i]
            print('nums:',nums)    
        aa=len(nums)
        for j in range(num):
            nums[aa-1-j]=0
            print('nums1:',nums)

s = Solution()
print(s.moveZeroes([1,0,2,3,0,0,4,0,9]))

nums: [1, 0, 2, 3, 0, 0, 4, 0, 9]
nums: [1, 0, 2, 3, 0, 0, 4, 0, 9]
nums: [1, 2, 2, 3, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 3, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 3, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 3, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 4, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 4, 0, 0, 4, 0, 9]
nums: [1, 2, 3, 4, 9, 0, 4, 0, 9]
nums1: [1, 2, 3, 4, 9, 0, 4, 0, 0]
nums1: [1, 2, 3, 4, 9, 0, 4, 0, 0]
nums1: [1, 2, 3, 4, 9, 0, 0, 0, 0]
nums1: [1, 2, 3, 4, 9, 0, 0, 0, 0]
None

36. 有效的數(shù)獨 (Medium)

題目描述

判斷一個 9x9 的數(shù)獨是否有效。只需要根據(jù)以下規(guī)則吻育，驗證已經(jīng)填入的數(shù)字是否有效即可念秧。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次布疼。
數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次摊趾。

數(shù)獨部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示游两。

示例 1:

輸入:

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

輸出: true

示例 2:

輸入:

[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

輸出: false

解釋: 除了第一行的第一個數(shù)字從 5 改為 8 以外砾层，空格內(nèi)其他數(shù)字均與示例1 相同。
但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨是無效的贱案。

說明:

一個有效的數(shù)獨（部分已被填充）不一定是可解的肛炮。
只需要根據(jù)以上規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨序列只包含數(shù)字 1-9 和字符 '.' 铸董。
給定數(shù)獨永遠(yuǎn)是 9x9 形式的。

https://blog.csdn.net/coder_orz/article/details/51596499

https://blog.csdn.net/yzp1011/article/details/79702496

https://blog.csdn.net/coder_orz/article/details/51596499

https://blog.csdn.net/runningtortoises/article/details/45830627

https://www.cnblogs.com/zhuifengjingling/p/5277555.html

思考：

我目前的想法還是很蠢肴沫，不說了
來自大神的思考粟害，記錄所有出現(xiàn)過的行、列颤芬、塊的數(shù)字及相應(yīng)位置悲幅，最后判斷是否有重復(fù)。用 set 操作精簡代碼

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        seen = []
#       i: 所有的行索引（0-8）站蝠，row 數(shù)組汰具，每一行的數(shù)組  
        for i, row in enumerate(board):
#             print('i:',i, 'row:',row)
#           j: 所有的列索引（0-8），c ：每一個字符
            for j, c in enumerate(row):
                if c != '.':
#                     print('j:',j, 'c:',c)
#                     print('(i, c):',(i, c))
#                     print('(i/3, j/3, c):',i/3, j/3, c)
                    # (c, j) 表示 每一行中菱魔，每個字符數(shù)字留荔，與之對應(yīng)的位置 如  (c, j): ('5', 0) 就是 數(shù)字 5 在行中的位置 是 0 
                    # 這樣就能判斷 每一列是否有重復(fù)的數(shù)字
                    # (i, c) 表示，每一列中澜倦，列索引對應(yīng)的字符數(shù)字聚蝶，如： (0, '5') (0, '3')(0, '7') 代表 豎著看，按列來看藻治，0 的 位置上 有 5  3  7 
                    # 則能判斷 每一行是都有重復(fù)的數(shù)字 如重復(fù)出現(xiàn) （0,5）（0,5）
                    # (i/3, j/3, c) ,三宮格 中(只考慮 三宮格內(nèi)的 三行三列就可以) 對應(yīng)的坐標(biāo)位置及 字符數(shù)字
                    seen += [(c, j),(i, c),(i/3, j/3, c)] 
                    
#                     print('seen:\n',seen,'\n')       
        return len(seen) == len(set(seen))

board = [["5","3",".",".","7",".",".",".","."],
         ["6",".",".","1","9","5",".",".","."],
         [".","9","8",".",".",".",".","6","."],
         ["8",".",".",".","6",".",".",".","3"],
         ["4",".",".","8",".","3",".",".","1"],
         ["7",".",".",".","2",".",".",".","6"],
         [".","6",".",".",".",".","2","8","."],
         [".",".",".","4","1","9",".",".","5"],
         [".",".",".",".","8",".",".","7","9"]]

board1 = [
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
s = Solution()
# print(s.isValidSudoku(board))
print(s.isValidSudoku(board1))

False

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        return (self.is_row_valid(board)) and (self.is_col_valid(board)) and (self.is_square_valid(board))
    
    def is_row_valid(self, board):
        for row in board:
            if not self.is_unit_valid(row):
                return False
        return True
    
    def is_col_valid(self, board):
        for col in zip(*board):
            if not self.is_unit_valid(col):
                return False
        return True
    
    def is_square_valid(self, board):
        for i in (0, 3, 6):
            for j in (0, 3, 6):
#               將 board 分成了 9 塊 
                square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
                if not self.is_unit_valid(square):
                    return False
        return True
    
    def is_unit_valid(self, unit):
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)

board = [["5","3",".",".","7",".",".",".","."],
         ["6",".",".","1","9","5",".",".","."],
         [".","9","8",".",".",".",".","6","."],
         ["8",".",".",".","6",".",".",".","3"],
         ["4",".",".","8",".","3",".",".","1"],
         ["7",".",".",".","2",".",".",".","6"],
         [".","6",".",".",".",".","2","8","."],
         [".",".",".","4","1","9",".",".","5"],
         [".",".",".",".","8",".",".","7","9"]]
# 相當(dāng)于轉(zhuǎn)置
print(*board)

for col in zip(*board):    
    print(col)

['5', '3', '.', '.', '7', '.', '.', '.', '.'] ['6', '.', '.', '1', '9', '5', '.', '.', '.'] ['.', '9', '8', '.', '.', '.', '.', '6', '.'] ['8', '.', '.', '.', '6', '.', '.', '.', '3'] ['4', '.', '.', '8', '.', '3', '.', '.', '1'] ['7', '.', '.', '.', '2', '.', '.', '.', '6'] ['.', '6', '.', '.', '.', '.', '2', '8', '.'] ['.', '.', '.', '4', '1', '9', '.', '.', '5'] ['.', '.', '.', '.', '8', '.', '.', '7', '9']
('5', '6', '.', '8', '4', '7', '.', '.', '.')
('3', '.', '9', '.', '.', '.', '6', '.', '.')
('.', '.', '8', '.', '.', '.', '.', '.', '.')
('.', '1', '.', '.', '8', '.', '.', '4', '.')
('7', '9', '.', '6', '.', '2', '.', '1', '8')
('.', '5', '.', '.', '3', '.', '.', '9', '.')
('.', '.', '.', '.', '.', '.', '2', '.', '.')
('.', '.', '6', '.', '.', '.', '8', '.', '7')
('.', '.', '.', '3', '1', '6', '.', '5', '9')

48. 旋轉(zhuǎn)圖像（Medium）

給定一個 n × n 的二維矩陣表示一個圖像碘勉。

將圖像順時針旋轉(zhuǎn) 90 度。

說明：

你必須在原地旋轉(zhuǎn)圖像桩卵，這意味著你需要直接修改輸入的二維矩陣验靡。請不要使用另一個矩陣來旋轉(zhuǎn)圖像。

示例 1:

給定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋轉(zhuǎn)輸入矩陣雏节，使其變?yōu)?
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

給定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋轉(zhuǎn)輸入矩陣胜嗓，使其變?yōu)?
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

思路：

原矩陣的 i，j 會變到 j钩乍，(n-1)-i 這個位置上

（如果直接去換兼蕊，此處有坑：遍歷下一個的時候，可能已經(jīng)變成最新的元素了件蚕，則又把它變走了）

所以先轉(zhuǎn)置上三角孙技，再每一行翻轉(zhuǎn)

class Solution1(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        # i 行索引， j 列索引 先進(jìn)行行列互換         
        for i in range(n):
            for j in range(i+1, n):
                matrix[j][i], matrix[i][j] = matrix[i][j],matrix[j][i]
                
        print('matrix:',matrix)  
        # 每一行翻轉(zhuǎn)
        for i in range(n):
            matrix[i].reverse()

class Solution2(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        matrix[:] = map(list,zip(*matrix))

補(bǔ)：

對于 map() 它的原型是：map(function,sequence)排作，就是對序列sequence中每個元素都執(zhí)行函數(shù)function操作牵啦。

對于zip()，原型是zip(*list)妄痪，list是一個列表哈雏，zip(*list)返回的是一個元組.

python 矩陣轉(zhuǎn)置- 使用zip()函數(shù)和map( )函數(shù)

map(list,zip(*matrix))

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

s1 = Solution1()
s1.rotate(matrix)
print('s1:',matrix)

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
s2 = Solution2()
s2.rotate(matrix)
print('s2:',matrix)

matrix [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
s1: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
s2: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

matrix.reverse()
print(matrix)

[[7, 8, 9], [4, 5, 6], [1, 2, 3]]

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子裳瘪，更是在濱河造成了極大的恐慌土浸，老刑警劉巖，帶你破解...
沈念sama閱讀 211,290評論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件彭羹，死亡現(xiàn)場離奇詭異黄伊，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)派殷，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,107評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門还最，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人毡惜，你說我怎么就攤上這事拓轻。” “怎么了经伙？”我有些...
開封第一講書人閱讀 156,872評論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵扶叉，是天一觀的道長。經(jīng)常有香客問我帕膜，道長辜梳，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,415評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任泳叠，我火速辦了婚禮作瞄，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘危纫。我一直安慰自己宗挥，他們只是感情好，可當(dāng)我...
茶點故事閱讀 65,453評論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布种蝶。她就那樣靜靜地躺著契耿，像睡著了一般。火紅的嫁衣襯著肌膚如雪螃征。梳的紋絲不亂的頭發(fā)上搪桂，一...
開封第一講書人閱讀 49,784評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音盯滚，去河邊找鬼踢械。笑死，一個胖子當(dāng)著我的面吹牛魄藕，可吹牛的內(nèi)容都是我干的内列。我是一名探鬼主播，決...
沈念sama閱讀 38,927評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼嫩与，長吁一口氣：“原來是場噩夢啊……” “哼处坪！你這毒婦竟也來了胶征？” 一聲冷哼從身側(cè)響起服傍，我...
開封第一講書人閱讀 37,691評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤套蒂，失蹤者是張志新（化名）和其女友劉穎骨坑，沒想到半個月后匈辱，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體浅碾，經(jīng)...
沈念sama閱讀 44,137評論 1贊 303
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡根暑，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,472評論 2贊 326
?白月光啟示錄
正文我和宋清朗相戀三年淳地，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,622評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡路幸，死狀恐怖荐开，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情简肴，我是刑警寧澤晃听，帶...
沈念sama閱讀 34,289評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站砰识，受9級特大地震影響能扒，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜辫狼，卻給世界環(huán)境...
茶點故事閱讀 39,887評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一初斑、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧膨处，春花似錦见秤、人聲如沸砂竖。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,741評論 0贊 21
一樁弒父案鹃答，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽乎澄。三九已至，卻和暖如春测摔，著一層夾襖步出監(jiān)牢的瞬間置济，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,977評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工锋八，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留浙于，地道東北人。一個月前我還...
沈念sama閱讀 46,316評論 2贊 360
代替公主和親
正文我出身青樓挟纱，卻偏偏與公主長得像羞酗，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子樊销，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 43,490評論 2贊 348

Algorithm & Data structure | LeetCode_ 數(shù)組系列

1.兩數(shù)之和 （Easy）

題目描述

解釋：

26. 刪除排序數(shù)組中的重復(fù)項 (Easy)

題目描述

121. 買賣股票的最佳時機(jī) (Easy)

題目描述

122. 買賣股票的最佳時機(jī) II (Easy)

題目描述

189. 旋轉(zhuǎn)數(shù)組 (Easy)

題目描述

217.存在重復(fù)(Easy)

題目描述

136. 只出現(xiàn)一次的數(shù)字(Easy)

題目描述

350. 兩個數(shù)組的交集 II (Easy)

題目描述

66. 加一 (Easy)

題目描述

283. 移動零 (Easy)

題目描述

36. 有效的數(shù)獨 (Medium)

題目描述

48. 旋轉(zhuǎn)圖像 （Medium）

推薦閱讀更多精彩內(nèi)容

1.兩數(shù)之和（Easy）

48. 旋轉(zhuǎn)圖像（Medium）