礼信堂 网站开发,做网站业务员应该了解什么,中国建设银行是国企还是央企,沧州网站seo公司leetcode-explore-learn-数据结构-数组5-小结1.概述2.例题2.1旋转数组2.2 杨辉三角22.3翻转字符串里的单词2.4反转字符串中的单词32.5 删除排序数组中的重复项2.6 移动零本系列博文为leetcode-explore-learn子栏目学习笔记#xff0c;如有不详之处#xff0c;请参考leetcode官…
leetcode-explore-learn-数据结构-数组5-小结1.概述2.例题2.1旋转数组2.2 杨辉三角22.3翻转字符串里的单词2.4反转字符串中的单词32.5 删除排序数组中的重复项2.6 移动零本系列博文为leetcode-explore-learn子栏目学习笔记如有不详之处请参考leetcode官网https://leetcode-cn.com/explore/learn/card/array-and-string/198/introduction-to-array/768/所有例题的编程语言为python
1.概述
1.数组的常用排序算法及其时间复杂度分析十分重要 2.二分查找是一种十分重要的技术用于在排序数组中搜索特i定元素 3.灵活应用双指针技巧十分重要双指针技可以应用于链表中快慢指针问题滑动窗口问题
2.例题
2.1旋转数组
给定一个数组将数组中的元素向右移动K个位置其中k为非负数。 空间复杂度o(1) 思路1三次求逆先整体求逆然后nums[0,k]求逆然后再nums[k1:]求逆
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.def rever_nums(nums,l,r): # 原地置换用index操作nums[:flag]只是一个备份没有修改元数组while(lr):nums[l],nums[r]nums[r],nums[l]l1r-1nlen(nums)flagk%nrever_nums(nums,0,n-1)rever_nums(nums,0,flag-1)rever_nums(nums,flag,n-1)return nums 思路2计算每个数组移动到的目标位置将目标位置的信息记录下来作为下一个操作的对象(30/35)—[-1,-100,3,99]2测试用例没过.
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.nlen(nums)action0index0current_valnums[0]while(actionn):target_index(indexk)%ntarget_valnums[target_index]nums[target_index]current_valaction1indextarget_indexcurrent_valtarget_valreturn nums 修正思路:环装替换法
参考官网解题思路https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
思路3,暴力法每次移动一个移动k次 (34/35时间超出限制
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.nlen(nums)flagk%nfor i in range(flag):currentnums[n-1]for j in range(n): # j:[0,n-1]tempnums[j]nums[j]currentcurrenttempreturn nums2.2 杨辉三角2
返回杨辉三角的第k行算法空间复杂度,o(k)
思路1计算整个杨辉三角返回最后一行
class Solution(object):def getRow(self, rowIndex):res[]for i in range(rowIndex1): # i:[0,rowIndex] rowIndex1行if i0:res.append([1])elif i1:res.append([1,1])else:res.append([1]*(i1))for j in range(1,i):res[i][j]res[i-1][j-1]res[i-1][j]return res[-1]思路2空间复杂度优化只有上一行计算下一行
class Solution(object):def getRow(self, rowIndex):if rowIndex0:return [1]if rowIndex1:return [1,1]pre[1,1]for i in range(2,rowIndex1):cur[1]*(i1)for j in range(1,i):cur[j]pre[j-1]pre[j]precurreturn cur2.3翻转字符串里的单词
给定一个字符串逐个翻转字符串中的每个单词
**思路1**要识别字符串中的每个单词然后调整顺序。从最后开始遍历识别一个单词后往结果中添加。
class Solution(object):def reverseWords(self, s)::type s: str:rtype: strres nlen(s)flag0 # 判断是否开始识别一个单词for i in range(n-1,-1,-1):#print(i,s[i],flag)if s[i]! and flag0: # 一个单词的起始flag1rightil_word1elif s[i]! and flag1: # 单词左下标往前走l_word1elif s[i] and flag1: # 单词左下标走到了边界words[right-l_word1:right1]flag0reswordres elif s[i] and flag0: # 多个空格的时候continueif flag1: #最后还需要判断是否还有一个单词words[right-l_word1:right1]flag0reswordlen_reslen(res)if len_res0:return if res[-1] :resres[0:-1]return res思路2:借助内置的函数 split() 将字符串按空格分成字符串数组 reverse() 将字符串数组翻转 join 将字符串数组拼接鞥一个字符串。
class Solution(object):def reverseWords(self, s)::type s: str:rtype: strs_arrs.split()s_arr.reverse()res .join(s_arr)return res2.4反转字符串中的单词3
给定一个字符串你需要反转字符串中每个单词的字符顺序同时仍保留空格和单词的初始顺序。 思路识别一个单词送去翻转添加至结果后
class Solution(object):def reverseWords(self, s)::type s: str:rtype: strdef rever_word(word):nlen(word)re_wordfor i in range(n-1,-1,-1):re_wordword[i]#print(re_word)return re_wordnlen(s)l,r0,0reswhile(rn):if s[r]! :r1elif s[r] :words[l:r]resrever_word(word)res lr1r1words[l:r1]resrever_word(word)return res 2.5 删除排序数组中的重复项
给定一个排序数组你需要在 原地 删除重复出现的元素使得每个元素只出现一次返回移除后数组的新长度。 **思路**快慢指针慢指针用于指示下一个写数字的位置快指针用于遍历数组。每次判断快指针指向的数字在数组是否重复出现如果重复出现就下一个如果不是重复出现就更新慢指针的数值。
class Solution(object):def removeDuplicates(self, nums)::type nums: List[int]:rtype: intnlen(nums)l0targetINFfor r in range(n):if nums[r]!target:targetnums[r]nums[l]nums[r]l1 #指示下一个可以写的位置return l 2.6 移动零
给定一个数组编写程序完成将所有的零移动至数组的末尾其他元素相对位置不变。 要求原地操作尽量少的操作次数 暴力求解思路每次移动一个0.时间复杂度o(n^2)
class Solution(object):def moveZeroes(self, nums)::type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead.nlen(nums)i0jn-1while(in and ij): # print(i,j,nums)if nums[i]0: # 置换完i不是立即1,换完nums[i]处还可能是1for k in range(i,j):nums[k],nums[k1]nums[k1],nums[k]j-1else:i1 return nums思路2双指针技巧慢指针之前的元素都是非零快指针与慢指针之间的元素都是0
class Solution(object):def moveZeroes(self, nums)::type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead.nlen(nums)i,j0,0while(in):if nums[i]:nums[i],nums[j]nums[j],nums[i]j1i1
