LeetCode攀登之旅(16)
- 2019 年 10 月 5 日
- 筆記
LeetCode攀登之旅(16)
【今日知圖】
許可權切換
# user切換到root sudo su # root切換到light su light
0.前言1.反轉字元串中的單詞III2.思路3.除自身以外數組的乘積4.作者的話
0.前言
【光城知圖】 在微信群中交流後，想起了一個創新點，在每篇文章開頭放上簡短的知識點，這次以linux基礎放在前面(後續還有很多乾貨哦~)，如大家所見，我把它命名為：光城知圖~~~
在後面幾天會推出scrapy爬蟲以及知識圖譜等內容，我們一起來期待！！！ 【刷題】 又到周二了，慣例刷題，一起來刷演算法，通關面試，直拿offer!
本節刷題題目是：反轉字元串中的單詞III與除自身以外數組的乘積，下面一起來深入吧！
特別是要準備考研的，第一題好好看！！！這裡推薦一波公眾號，這個公眾號由老表創建，我跟他已經堅持15天以上的刷題了，並且建立了微信群專門來刷演算法，公眾號：xksnh888
各位可以點擊我的公眾號右下角->點擊聯繫我->備註：刷題->入演算法群！
1.反轉字元串中的單詞III
給定一個字元串，你需要反轉字元串中每個單詞的字元順序，同時仍保留空格和單詞的初始順序。
示例 1:
輸入: "Let's take LeetCode contest" 輸出: "s'teL ekat edoCteeL tsetnoc"
注意：在字元串中，每個單詞由單個空格分隔，並且字元串中不會有任何額外的空格。
2.思路
方法一：調包
思路：首先將字元串倒置並分割成list，然後在倒回去，最後用空格還原成字元串，這樣就是最終的結果！
這道題是比較特殊的，那如果中間是多個空格呢，又該如何處理？
時間複雜度O(1)，空間複雜度O(1)
class Solution: def reverseWords(self, s): return " ".join(s[::-1].split()[::-1])
方法二：自我實現
思路：首先統計字元串長度，然後在當前字元串前面添加一個空格，為了便於處理！
然後讓原字元串清空！
通過一層for循環進行判斷：
當前字元不為空，且前一字元為空格，則表明當前字元為字元串開頭，將高位的j賦值給低位，當到最後的index並且只有一個字元，則直接處理即可！
當前字元為空，且前一字元不為空，則表明，j-1為當前單詞的最後一位，上面知道i為當前單詞第一位，那麼通過list切並反轉，即可做到原地反轉，並且最後加上一個空格(當前位是空格)；
當前字元不為空，則表示還未到單詞結尾，讓他繼續查找。這裡要判別一下，如果到了最後一個字元，則應該取到上界為j+1，並反轉單詞！
當單詞之間有多個空格時，做最後空格處理！
class Solution: def reverseWords(self, s): i = 0 s_len = len(s) s1=' '+s s='' word=0 print(s1) for j in range(1,s_len+1): if s1[j]!=' ' and s1[j-1]==' ': i=j # 防止只有一個字母情況 if j==s_len: s+=s1[j] word+=1 elif s1[j-1]!=' ' and s1[j]==' ': s+=s1[i:j][::-1] s+=' ' elif s1[j]!=' ': if j==s_len: s+=s1[i:j+1][::-1] continue else: # 多個空格處理 s+=' ' print(word) return s
從這個思路我們知道，我的這個方法有效的處理了多空格的問題，並且處理了單詞統計功能，這個單詞統計在考研或者保研中常考！
時間複雜度O(n)，空間複雜度O(n)！
3.除自身以外數組的乘積
問題
給定長度為 n 的整數數組 nums，其中 n > 1，返回輸出數組 output ，其中 output[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積。
示例:
輸入: [1,2,3,4] 輸出: [24,12,8,6]
說明: 請不要使用除法，且在 O(n) 時間複雜度內完成此題。
進階： 你可以在常數空間複雜度內完成這個題目嗎？（ 出於對空間複雜度分析的目的，輸出數組不被視為額外空間。）
思路一
設計兩個數組，分別用於存儲當前數前面幾個數的乘積與當前數的後面數的乘積！
計算前面數的乘積：[1,a1,a1*a2,a1*a2*a3] 計算後面數的乘積：[a2*a3*a4,a3*a4,a4,1] 除自身以外數組的乘積：[a2*a3*a4,a1*a3*a4,a1*a2*a4,a1*a2*a3]
時間複雜度：O(n)，空間複雜度：O(n)
class Solution: def productExceptSelf(self, nums): arr1 = self.cal_multipy(nums) arr2 = self.cal_multipy(nums[::-1])[::-1] for i in range(len(nums)): nums[i]=arr1[i]*arr2[i] return nums def cal_multipy(self, nums): t=1 arr = [] for i in range(len(nums)): if i==0: arr.append(1) else: arr.append(t) t *= nums[i] return arr
思路二
定義一個最終結果存放的數組，通過低位與高位直接計算，時間複雜度O(n)，空間複雜度O(1)
題中明確說明輸出數組不被視為額外空間，所以這裡直接時間複雜度為O(1)
class Solution(object): def productExceptSelf(self, nums): res = [1]*len(nums) low=1 high=1 for i in range(len(nums)): res[i]*=low res[len(nums)-i-1]*=high low*=nums[i] high*=nums[len(nums)-i-1] return res