LeetCode攀登之旅(16)

之旅(16)"/>

LeetCode攀登之旅(16)

LeetCode攀登之旅(16)

【今日知图】

权限切换

# user切换到root
sudo su
# root切换到light
su light

0.前言1.反转字符串中的单词III2.思路3.除自身以外数组的乘积4.作者的话

0.前言

【光城知图】创新点，在每篇文章开头放上简短的知识点，这次以linux基础放在前面(后续还有很多干货哦~)，如大家所见，我把它命名为：光城知图~~~

在后面几天会推出scrapy爬虫以及知识图谱等内容，我们一起来期待！！！刷题】

本节刷题题目是：反转字符串中的单词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 = 0s_len = len(s)s1=' '+ss=''word=0print(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+=1elif 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]continueelse:# 多个空格处理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 numsdef cal_multipy(self, nums):t=1arr = []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=1high=1for i in range(len(nums)):res[i]*=lowres[len(nums)-i-1]*=highlow*=nums[i]high*=nums[len(nums)-i-1]return res

4.作者的话

最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！

我今天才知道，我之所以漂泊就是在向你靠近。

--《廊桥遗梦》