LeetCode攀登之旅(16)
LeetCode攀登之旅(16)
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