python实现输⼊数组_LeetCodeinpython简单题--数组篇1.两数之和
167.两数之和 II - 输⼊有序数组
26. 删除排序数组中的重复项
27. 移除元素
66. 加⼀
88. 合并两个有序数组
118. 杨辉三⾓
119. 杨辉三⾓II
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
169. 求众数
189.旋转数组
给定⼀个整数数组 nums 和⼀个⽬标值 target,请你在该数组中出和为⽬标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输⼊只会对应⼀个答案。但是,你不能重复利⽤这个数组中同样的元素。
⽰例:
给定 nums = [2, 7, 11, 15], target = 9
python获取数组长度因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代码:
解法1:暴⼒解法,双重循环
class Solution(object):
def twoSum(self, nums, target):
m = len(nums)
for i in range(m-1):
temp = target - nums[i]
for j in range(i+1,m):
if temp == nums[j]:
return i,j
解法2:⼀次循环,看target-nums[i]在不在数组中。
class Solution(object):
def twoSum(self, nums, target):
m = len(nums)
for i in range(m):
temp = target - nums[i]
if temp in nums:
j = nums.index(temp)
if i != j:
return i,j
解法3:可以借⽤哈希(Python 叫字典),我们遍历元素的时候,且记录元素的下标,当我们 target-a 时候,只需要在字典,就可以了,查字典时间复杂度为 O(1)O(1)。
class Solution(object):
def twoSum(self, nums, target):
m = len(nums)
d = {}
for i in range(m):
temp = target - nums[i]
if temp in d:
return [d[temp], i]
d[nums[i]] = i
给定⼀个已按照升序排列 的有序数组,到两个数使得它们相加之和等于⽬标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须⼩于 index2。
说明:返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输⼊只对应唯⼀的答案,⽽且你不可以重复使⽤相同的元素。
⽰例:
输⼊: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于⽬标数 9 。因此 index1 = 1, index2 = 2 。
思路
左右两个指针移动,sum等于左右两个元素的和,sum和target⽐较,当sum⼩于target时,start往右⾛,当sum⼤于target的时候,end 往左⾛。
代码
class Solution(object):
def twoSum(self, numbers, target):
""":type numbers: List[int]:type target: int:rtype: List[int]"""
start = 0
end = len(numbers) - 1
sum = 0
while start < end:
sum = numbers[start] + numbers[end]
if sum < target:
start += 1
elif sum > target:
end -= 1
else:
return [start+1, end+1]
给定⼀个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现⼀次,返回移除后数组的新长度。
不要使⽤额外的数组空间,你必须在原地修改输⼊数组并在使⽤ O(1) 额外空间的条件下完成。
⽰例 :
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输⼊数组是以“引⽤”⽅式传递的,这意味着在函数⾥修改输⼊数组对于调⽤者是可见的。你可以想象内部操作如下:
// nums 是以“引⽤”⽅式传递的。也就是说,不对实参做任何拷贝int len = removeDuplicates(nums);
// 在函数⾥修改输⼊数组对于调⽤者是可见的。// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路:借助⼀个计数变量:count,初始化为0,⽤nums[count]和array中的数字⽐较,当不同的时候,count加1,且将这个不同的数字置为nums[count]。
代码:
class Solution(object):
def removeDuplicates(self, nums):
if len(nums) == 0:
return 0
count = 0
for i in range(len(nums)):
if nums[count] != nums[i]:
count += 1
nums[count] = nums[i]
return count+1
给定⼀个数组 nums 和⼀个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
不要使⽤额外的数组空间,你必须在原地修改输⼊数组并在使⽤ O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后⾯的元素。
⽰例 :
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后⾯的元素。
思路:
定义⾸尾两个指针,当⾸部指针对应的元素是需要删除的元素时,和最后⼀个元素交换,使尾部指针减1实现删除元素,如果不需要删,则将⾸部指针加1.最后返回last+1即删除后array的长度。
代码:
class Solution(object):
def removeElement(self, nums, val):
if not nums:
return 0
i, last = 0, len(nums)-1
while i <= last:
if nums[i] == val:
nums[i], nums[last] = nums[last], nums[i]
last -= 1
else:
i += 1
return last+1
给定⼀个由整数组成的⾮空数组所表⽰的⾮负整数,在该数的基础上加⼀。
最⾼位数字存放在数组的⾸位, 数组中每个元素只存储⼀个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
⽰例 :
输⼊: [1,2,3]
输出: [1,2,4]
解释: 输⼊数组表⽰数字 123。
代码
class Solution(object):
def plusOne(self, digits):
for i in reversed(range(len(digits))):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
digits[0] = 1
digits.append(0)
return digits
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为⼀个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有⾜够的空间(空间⼤⼩⼤于或等于 m + n)来保存 nums2 中的元素。
⽰例:
输⼊:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路
设置两个指针,从尾部开始⽐较,较⼤的数字放在最后,对应的指针减1;若nums2的指针在nums1的指针为0时仍不为0,那么说明这个指针之前的数字都⽐nums1的最⼩数字还要⼩,所以直接添加到nums1的前⾯
代码
class Solution(object):
def merge(self, nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m-1] < nums2[n-1]:
nums1[m+n-1] = nums2[n-1]
n -= 1
else:
nums1[m+n-1], nums1[m-1] = nums1[m-1], nums1[m+n-1]
m -= 1
if m == 0 and n > 0:
nums1[:n] = nums2[:n]
return nums1
给定⼀个⾮负整数 numRows,⽣成杨辉三⾓的前 numRows ⾏。
在杨辉三⾓中,每个数是它左上⽅和右上⽅的数的和。
⽰例:
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论