Nemo
Leetcode 数组简单类解答集合(暂停更新)
Leetcode 数组简单类解答集合(暂停更新)

1.两数之和

给定一个整数数组 nums 和一个目标值 target ,请你在该数组中找出和为目标值的那** 两个 **整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

  1. 给定 nums = [2, 7, 11, 15], target = 9
  2. 因为 nums[0] + nums[1] = 2 + 7 = 9
  3. 所以返回 [0, 1]

第一次解答:

  1. class Solution:
  2. def twoSum(self, nums: List[int], target: int) -> List[int]:
  3. for i in range(len(nums)-1):
  4. for r in range(i+1,len(nums)):
  5. if nums[i] + nums[r] == target: #注意这里的相等是==号
  6. return [i,r] #返回一个列表

结果:

  1. 已完成
  2. 执行用时: 52 ms
  3. 输入
  4. [2,7,11,15]
  5. 9
  6. 输出
  7. [0,1]
  8. 差别
  9. 预期结果
  10. [0,1]

但是,在提交检验的时候显示为超出时间限制!因为这个解法使用了两层循环遍历,时间复杂度为O(n^2),太慢了。

第二次解答:

第二次解答在第一次解答上面做了改进,只利用一层循环就可以找出答案:即根据当前遍历得到的元素index,查找target-index是否在剩余数组里出现,如果找得到,则返回其下标值;反之则说明没有该答案。

代码如下:

  1. class Solution(object):
  2. # 可用一遍遍历,即根据当前遍历得到的元素index,
  3. # 查找target-index是否在剩余数组里出现
  4. # 如果找得到,则返回其下标值;反之则说明没有该答案
  5. def twoSum(self, nums, target):
  6. """
  7. :type nums: List[int]
  8. :type target: int
  9. :rtype: List[int]
  10. """
  11. answer = []
  12. for left_index in range(len(nums)):
  13. right = target - nums[left_index]
  14. if right in nums[left_index+1:]:
  15. nums_right = nums[left_index+1:] #往右截断,构建一个新的数组
  16. right_index = nums_right.index(right)+left_index+1 #注意这个+1
  17. answer.extend([left_index, right_index])
  18. break
  19. return answer

结果:

  1. 成功
  2. 显示详情
  3. 执行用时 : 984 ms , Two SumPython3提交中击败了 45.09% 的用户
  4. 内存消耗 : 13.6 MB , Two SumPython3提交中击败了 92.31% 的用户

1002. 查找常用字符

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例 1:

  1. 输入:["bella","label","roller"]
  2. 输出:["e","l","l"]

示例 2:

  1. 输入:["cool","lock","cook"]
  2. 输出:["c","o"]

提示:

  1. 1
  2. 1
  3. A[i][j]是小写字母

解答

思路:遍历第一个数组中的每个元素,把这个元素去和剩下数组中的元素进行比较,结果都为真,就添加到目标数组,然后将这个元素从每个数组中剔除。

  1. class Solution:
  2. def commonChars(self, A: List[str]) -> List[str]:
  3. result = []
  4. for i in A[0]:
  5. if i in A[1] and i in A[2]:
  6. result.append(i)
  7. A[0].replace(i,'')
  8. A[1].replace(i,'')
  9. A[2].replace(i,'')
  10. return result

执行代码通过:

  1. 已完成
  2. 执行用时: 48 ms
  3. 输入
  4. ["bella","label","roller"]
  5. 输出
  6. ["e","l","l"]
  7. 预期结果
  8. ["e","l","l"]

但是提交则出错了:

  1. 最近提交结果:
  2. 解答错误
  3. 显示详情
  4. 输入:
  5. ["cool","lock","cook"]
  6. 输出
  7. ["c","o","o"]
  8. 预期结果
  9. ["c","o"]

更正

  1. class Solution:
  2. def commonChars(self, A: List[str]) -> List[str]:
  3. result = [];
  4. # 队列为空,或者队列长度小于2,返回空
  5. if not A or len(A) 2:
  6. return result;
  7. # 获取队列中第一位的所有的字符
  8. setKey = set(A[0])
  9. # 遍历字符,并获取所有字符串中出现的次数的最小值
  10. for x in setKey:
  11. num = min(a.count(x) for a in A)
  12. for i in range(num):
  13. result.append(x)
  14. return result

1051. 高度检查器

学校在拍年度纪念照时,一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是:能让所有学生以 非递减 高度排列的必要移动人数。

示例:

  1. 输入:[1,1,4,2,1,3]
  2. 输出:3
  3. 解释:
  4. 高度为 43 和最后一个 1 的学生,没有站在正确的位置。

提示:

  1. 1
  2. 1

解答

原来考虑的是比较这个数与它后面数的大小,大的计数+1,后来发现最后一位数字不适用,就想先把列表排序,比较排序后的列表和原列表中不一样的项的数量。

  1. class Solution:
  2. def heightChecker(self, heights: List[int]) -> int:
  3. length = len(heights)
  4. sort_heights = sorted(heights)
  5. nums = 0
  6. for i in range(length):
  7. if sort_heights[i] != heights[i]:
  8. nums += 1
  9. return nums

更优解

暂无

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

  1. 输入: 5
  2. 输出:
  3. [
  4. [1],
  5. [1,1],
  6. [1,2,1],
  7. [1,3,3,1],
  8. [1,4,6,4,1]
  9. ]

解答

思路:杨辉三角形第i行的元素个数和所处的行数是一样的,这样可以用‘for i in range(‘所处的行数’)’对该行的元素进行操作,使用sum()函数对上一行两肩的元素进行求和,最后进行数组的尾加。这种办法属于动态规划,因为我们需要前一行来构建每一行。

  1. class Solution:
  2. def generate(self, numRows: int) -> List[List[int]]:
  3. r = [[1]] #初始第一行
  4. for i in range(1, numRows): #对后续行进行操作
  5. r.append([1] + [sum(r[-1][j:j+2]) for j in range(i)]) #注意J的取值范围
  6. return numRows and r or []

结果

  1. 最近提交结果:
  2. 通过
  3. 显示详情
  4. 执行用时 :52 ms, 在所有Python3提交中击败了84.02%的用户
  5. 内存消耗 :
  6. 12.9 MB, 在所有Python3提交中击败了97.68%的用户

122.买卖股票的最佳时机 Ⅱ

标签:贪心算法、数组

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例1:

  1. 输入:
  2. [7,1,5,3,6,4]
  3. 输出:
  4. 7
  5. 解释:
  6. 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4
  7. 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3

[7, 1, 5, 6] 第二天买入,第四天卖出,收益最大(6-1),所以一般人可能会想,怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了,根据题目的意思,当天卖出以后,当天还可以买入,所以其实可以第三天卖出,第三天买入,第四天又卖出((5-1)+ (6-5) === 6 – 1)。所以算法可以直接简化为只要今天比昨天大,就卖出。

示例2:

  1. 输入:
  2. [1,2,3,4,5]
  3. 输出:
  4. 4
  5. 解释:
  6. 在第 1 天(股票价格 = 1)的时候买入,在第 5 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4
  7. 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
  8. 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例3:

  1. 输入:
  2. [7,6,4,3,1]
  3. 输出:
  4. 0
  5. 解释:
  6. 在这种情况下, 没有交易完成, 所以最大利润为 0

问题分析:
~~寻找最大利润可以看成在这个数组中寻找 ~~

第一次解答

  1. class Solution:
  2. def maxProfit(self, prices: List[int]) -> int:
  3. if len(prices) 2:
  4. return 0
  5. else:
  6. min_price = prices[0]
  7. max_profit = 0
  8. for i in range(len(prices)):
  9. min_prices = min(min_price,prices[i])
  10. max_profit = max(max_profit,prices[i]-min_price)
  11. return max_profit

结果为:

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 0
  3. 预期: 7

原因分析

问题出在这句代码:

  1. prices[i]-min_price

正确解答:

  1. class Solution(object):
  2. def maxProfit(self, prices):
  3. profit = 0
  4. for day in range(len(prices)-1):
  5. differ = prices[day+1] - prices[day]
  6. if differ > 0:
  7. profit += differ
  8. return profit

执行用时: 60 ms

169. 求众数

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

  1. 输入: [3,2,3]
  2. 输出: 3

示例 2:

  1. 输入: [2,2,1,1,1,2,2]
  2. 输出: 2

解答

思路:遍历,计数:nums.count()方法,看看是不是:

  1. class Solution:
  2. def majorityElement(self, nums: List[int]) -> int:
  3. n = len(nums)
  4. for i in nums:
  5. if nums.count(i) > (n/2):
  6. return i

简单执行后通过:

  1. 已完成
  2. 执行用时: 76 ms
  3. 输入
  4. [3,2,3]
  5. 输出
  6. 3
  7. 预期结果
  8. 3

但是提交执行后就出错了:

  1. 最近提交结果:
  2. 超出时间限制
  3. 显示详情
  4. 最后执行的输入:
  5. [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
  6. 查看全部

这是为什么呢?

更好的解法

这里介绍大神三种解法,第一种:

方法一:创建一个列表储存元素

  1. class Solution(object):
  2. def majorityElement(self, nums):
  3. list_1=[]
  4. n=len(nums)
  5. for i in range(n//2+1): # 遍历左边的列表元素(但是为什么是n//2+1?)
  6. if nums[i] in list_1: #这个判断避免后面相同的数字被打印出来
  7. i+=1
  8. continue
  9. else :
  10. list_1.append(nums[i])
  11. if nums.count(nums[i])>n//2:
  12. return nums[i]

结果:

  1. 执行结果:
  2. 通过
  3. 显示详情
  4. 执行用时 :60 ms, 在所有 Python3 提交中击败了96.34%的用户
  5. 内存消耗 :14.1 MB, 在所有 Python3 提交中击败了98.38%的用户

方法二:

排序后找中位数

  1. class Solution(object):
  2. def majorityElement(self,nums):
  3. nums.sort()
  4. return nums[len(nums)//2]
  1. 执行结果:
  2. 通过
  3. 显示详情
  4. 执行用时 :
  5. 52 ms, 在所有 Python3 提交中击败了99.25%的用户
  6. 内存消耗 :
  7. 14.3 MB, 在所有 Python3 提交中击败了73.31%的用户

但是有个疑问,为什么中位数就成了众数?

方法三:

摩尔投票算法

从第一个数开始count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换个数开始计数,总能找到最多的那个

  1. class Solution(object):
  2. def majorityElement(self,nums):
  3. tmp=nums[0]
  4. count=1
  5. for i in range(1,len(nums)):
  6. if count==0:
  7. tmp=nums[i]
  8. count=count+1 if nums[i]==tmp else count-1
  9. return tmp

26.从排序数组中删除重复项

给定一个排序数组,你需要在** 原地 ** 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在** 原地 **修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

  1. 给定数组 nums = [1,1,2],
  2. 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2
  3. 你不需要考虑数组中超出新长度后面的元素。

示例 2:

  1. 给定 nums = [0,0,1,1,1,2,2,3,3,4],
  2. 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4
  3. 你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

  1. //
  2. nums
  3. 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
  4. int len = removeDuplicates(nums);
  5. // 在函数里修改输入数组对于调用者是可见的。
  6. // 根据你的函数返回的长度, 它会打印出数组中
  7. 该长度范围内
  8. 的所有元素。
  9. for (int i = 0; i len; i++) {
  10. print(nums[i]);
  11. }

解答

  1. class Solution:
  2. def removeDuplicates(self, nums: List[int]) -> int:
  3. i = 0
  4. while i len(nums) - 1:
  5. if nums[i] == nums[i+1]:
  6. nums.remove(nums[i])
  7. else:
  8. i += 1
  9. return len(nums)

其他解答

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. def deleteDuplicates(self, head):
  8. """
  9. :type head: ListNode
  10. :rtype: ListNode
  11. """
  12. #不带头节点
  13. if(head==None):
  14. return head
  15. cur=head
  16. while(cur.next):
  17. if(cur.val==cur.next.val):
  18. cur.next=cur.next.next
  19. else:
  20. cur=cur.next
  21. return head

27.移除元素

给定一个数组 nums 和一个值 val ,你需要** 原地 ** 移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在** 原地 修改输入数组** 并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

  1. 给定
  2. nums= [3,2,2,3], val = 3,
  3. 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2
  4. 你不需要考虑数组中超出新长度后面的元素。

示例 2:

  1. 给定
  2. nums = [0,1,2,2,3,0,4,2], val = 2,
  3. 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4
  4. 注意这五个元素可为任意顺序。
  5. 你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以** “引用”** 方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

  1. //
  2. nums
  3. 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
  4. int len = removeElement(nums, val);
  5. // 在函数里修改输入数组对于调用者是可见的。
  6. // 根据你的函数返回的长度, 它会打印出数组中
  7. 该长度范围内
  8. 的所有元素。
  9. for (int i = 0; i len; i++) {
  10. print(nums[i]);
  11. }

来源:
https://leetcode-cn.com/problems/remove-element/

第一次解答

  1. class Solution:
  2. def removeElement(self, nums: List[int], val: int) -> int:
  3. for i in range(len(nums)):
  4. if nums[i] == val:
  5. nums.pop(i)
  6. return len(nums)

提交后显示失误:

  1. 解答错误
  2. 显示详情
  3. 输入
  4. [3,2,2,3]
  5. 3
  6. 输出
  7. [2,2,3]
  8. 预期结果
  9. [2,2]

看到结果里最有一个目标数值3没有被剔除掉,分析原因是因为使用了‘ nums.pop(i) ‘的操作删除target元素后后面的元素会自动向前移,填补已经删除的这个元素的位置,正循环某个元素被删了以后i的值会变,而且会越界。比如[2,3,3,2],i=1的时候num[1]=3,这个被删了以后,下一次应该迭代i=2,但是列表已变成[2,3,2],i=2对应的num[2]=2,中间那个3就删不掉了,而且迭代到i=3的时候会越界。倒序的话,把删去的窟窿以后的元素往前移,对前面没有遍历过的元素不会有影响。

参考代码如下

  1. class Solution:
  2. def removeElement(self, nums: List[int], val: int) -> int:
  3. j=len(nums)
  4. for i in range(j-1,-1,-1):
  5. if nums[i]==val:
  6. nums.pop(i)
  7. return len(nums)

从j-1到-1 以-1的步长进行遍历,假如有5个数,根据含左不含右,那就是4 3 2 1 0 。如果是正序 range(5)的意思是从0到5 含左不含右 0 1 2 3 4

35. 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

  1. 输入:
  2. [1,3,5,6], 5
  3. 输出:
  4. 2

示例 2:

  1. 输入:
  2. [1,3,5,6], 2
  3. 输出:
  4. 1

示例 3:

  1. 输入:
  2. [1,3,5,6], 7
  3. 输出:
  4. 4

示例 4:

  1. 输入:
  2. [1,3,5,6], 0
  3. 输出:
  4. 0
  5. 来源:
  6. https://leetcode-cn.com/problems/search-insert-position/ ```
  7. ## 第一次解答

解答

  1. class Solution:
  2. def searchInsert(self, nums: List[int], target: int) -> int:
  3. if target in nums:
  4. return nums.index(target)
  5. else:
  6. for i in range(len(nums)):
  7. if target > nums[i]:
  8. return i+1

结果:

  1. 已完成
  2. 执行用时: 48 ms
  3. 输入
  4. [1,3,5,6]
  5. 5
  6. 输出
  7. 2
  8. 差别
  9. 预期结果
  10. 2

但是提交以后出现解答错误:

  1. 解答错误
  2. 显示详情
  3. 输入
  4. [1,3,5,6]
  5. 7
  6. 输出
  7. 1
  8. 预期结果
  9. 4

稍作修改:

  1. class Solution:
  2. def searchInsert(self, nums: List[int], target: int) -> int:
  3. if target in nums:
  4. return nums.index(target)
  5. else:
  6. i = 0
  7. while i len(nums) and nums[i]target:
  8. i += 1
  9. return i

还是同样的报错,问题出在哪里呢?
再次修改代码,这次的思想是对原数组nums进行修改,将target添加进nums,对nums进行排序,直接返回target的索引,提交成功。缺点是这种方法会修改数组,建议把数组备份。

  1. class Solution:
  2. def searchInsert(self, nums: List[int], target: int) -> int:
  3. if target in nums:
  4. return nums.index(target)
  5. else:
  6. nums.append(target)
  7. nums.sort()
  8. return nums.index(target)

结果:

  1. 执行用时 : 48 ms , Search Insert PositionPython3提交中击败了 90.33% 的用户
  2. 内存消耗 : 13.4 MB , Search Insert PositionPython3提交中击败了 99.33% 的用户

509.斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 01 开始,后面的每一项数字都是前面两项数字的和。也就是:

  1. F(0) = 0, F(1) = 1
  2. F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N,计算 F(N)

示例 1:

  1. 输入:2
  2. 输出:1
  3. 解释:F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2:

  1. 输入:3
  2. 输出:2
  3. 解释:F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3:

  1. 输入:4
  2. 输出:3
  3. 解释:F(4) = F(3) + F(2) = 2 + 1 = 3.

提示:

  • 0 ≤ N ≤ 30

解答

思路:想到的第一点就是递归,想好基线条件就是N=0,1时返回的值,其他值时调用函数就可以了。这里要注意,调用函数名前要有’self.’

  1. class Solution:
  2. def fib(self, N: int) -> int:
  3. if N == 0:
  4. return 0
  5. if N == 1:
  6. return 1
  7. elif N > 1:
  8. return (self.fib(N-1) + self.fib(N-2))

结果

  1. 成功
  2. 显示详情
  3. 执行用时 : 1632 ms, Fibonacci NumberPython3提交中击败了7.50% 的用户
  4. 内存消耗 : 12.8 MB, Fibonacci NumberPython3提交中击败了99.59% 的用户

耗时太长了,应该花在了两次调用函数上,看看有没有更好的解法

更优解

递归改迭代

  1. class Solution:
  2. def fib(self, N: int) -> int:
  3. i=0
  4. j=1
  5. while N:
  6. N-=1
  7. i,j=j,j+i
  8. return i

耗时

  1. 成功
  2. 显示详情
  3. 执行用时 : 52 ms, Fibonacci NumberPython3提交中击败了82.95% 的用户
  4. 内存消耗 : 13.1 MB, Fibonacci NumberPython3提交中击败了60.16% 的用户

53.最大子序和

关键字:动态规划、分治算法

给定一个整数数组** nums **,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

  1. 输入:
  2. [-2,1,-3,4,-1,2,1,-5,4],
  3. 输出:
  4. 6
  5. 解释:
  6. 连续子数组 [4,-1,2,1] 的和最大,为 6

进阶:

如果你已经实现复杂度为 O( n ) 的解法,尝试使用更为精妙的分治法求解。

乍一想没有头绪,直接看的答案:

  1. class Solution(object):
  2. def maxSubArra(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: int
  6. """
  7. for i in range(1, len(nums)): #i从1开始
  8. nums[i]= nums[i] + max(nums[i-1], 0)
  9. return max(nums) #挑选最大的子序和
  10. 来源:
  11. https://leetcode-cn.com/problems/maximum-subarray/comments/

为什么数组的一项加上前一项的和0的相比的最大值 组成的新数组,就是最大子序列和的值呢?
答 :思想是动态规划,nums[i-1]并不是数组前一项的意思,而是到前一项为止的最大子序和,和0比较是因为只要大于0,就可以相加构造最大子序和。如果小于0则相加为0,nums[i]=nums[i],相当于最大子序和又重新计算。其实是一边遍历一边计算最大序和.

561. 数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:

  1. 输入: [1,4,3,2]
  2. 输出: 4
  3. 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

提示:

  1. n 是正整数,范围在 [1, 10000].
  2. 数组中的元素范围在 [-10000, 10000].

解答

思想:既然是找出每对数组最小值再求和,那就先把数组进行排序,这里要注意python中list的排序方法,list.sort()是排序原数组,sorted(list)是生成一个新的数组,不修改原数组。

  1. class Solution:
  2. def arrayPairSum(self, nums: List[int]) -> int:
  3. nums.sort()
  4. return sum(nums[::2])

结果

成功

显示详情

执行用时 : 220 ms, 在Array Partition I的Python3提交中击败了12.03% 的用户

内存消耗 : 14.9 MB, 在Array Partition I的Python3提交中击败了74.46% 的用户

用时稍微多了点,看看有没有更好的解法

更优解

566. 重塑矩阵

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。

给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例 1:

  1. 输入:
  2. nums =
  3. [[1,2],
  4. [3,4]]
  5. r = 1, c = 4
  6. 输出:
  7. [[1,2,3,4]]
  8. 解释:
  9. 行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:

  1. 输入:
  2. nums =
  3. [[1,2],
  4. [3,4]]
  5. r = 2, c = 4
  6. 输出:
  7. [[1,2],
  8. [3,4]]
  9. 解释:
  10. 没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。

注意:

  1. 给定矩阵的宽和高范围在 [1, 100]。
  2. 给定的 r 和 c 都是正数。

解答

如何验证输入的参数不合理,只需要验证r*c != m*n就可以了

  1. class Solution:
  2. def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
  3. old_row = nums.length()
  4. old_column = nums[0].length()
  5. if old_row * old_column != r*c:
  6. return nums
  7. else:
  8. new_row = []
  9. new_col = []
  10. for row in nums:
  11. for num in row:
  12. new_row.append(num)
  13. for i in range(int(r)):
  14. new_col.append(new_row[i*int(c):(i+1)*int(c)])
  15. return new_col

报错,看一下参考答案

正确解答

这个思路也是先转换成一行,然后再截断,代码如下:

  1. class Solution(object):
  2. def matrixReshape(self, nums, r, c):
  3. """
  4. :type nums: List[List[int]]
  5. :type r: int
  6. :type c: int
  7. :rtype: List[List[int]]
  8. """
  9. temp = []
  10. for i in range(len(nums)): #遍历行
  11. temp.extend(nums[i]) #extend() 函数用于在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)
  12. if r*c != len(temp): #输入错误,返回原列表
  13. return nums
  14. res = []
  15. for i in range(r): #新输入的行值
  16. res.append(temp[c*i: c*i+c]) #一次加满一行
  17. return res

704.二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

  1. 输入: nums = [-1,0,3,5,9,12], target = 9
  2. 输出: 4
  3. 解释: 9 出现在 nums 中并且下标为 4

示例 2:

  1. 输入: nums = [-1,0,3,5,9,12], target = 2
  2. 输出: -1
  3. 解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

解答:

  1. class Solution:
  2. def search(self, nums: List[int], target: int) -> int:
  3. low = 0
  4. high = len(nums) - 1
  5. while low high:
  6. mid = (low + high) // 2
  7. guess = nums[mid]
  8. if guess == target:
  9. return mid
  10. if guess > target:
  11. high = mid - 1
  12. else:
  13. low = mid + 1
  14. return -1

成功
显示详情
执行用时 : 68 ms , 在Binary Search的Python3提交中击败了 89.85% 的用户
内存消耗 : 14 MB , 在Binary Search的Python3提交中击败了 77.06% 的用户

832. 翻转图像

给定一个二进制矩阵 A ,我们想先水平翻转图像,然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转,即逆序。例如,水平翻转 [1, 1, 0] 的结果是 [0, 1, 1] 。

反转图片的意思是图片中的 0 全部被 1 替换, 1 全部被 0 替换。例如,反转 [0, 1, 1] 的结果是 [1, 0, 0] 。

示例 1:

  1. 输入:
  2. [[1,1,0],[1,0,1],[0,0,0]]
  3. 输出:
  4. [[1,0,0],[0,1,0],[1,1,1]]
  5. 解释:
  6. 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]];
  7. 然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 2:

  1. 输入:
  2. [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
  3. 输出:
  4. [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
  5. 解释:
  6. 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]];
  7. 然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

说明:

  • 1
  • 0

来源: https://leetcode-cn.com/problems/flipping-an-image/

解答:

思想:利用两层遍历对二维数组中每个元素进行操作,‘翻转’操作利用list中的[::-1],‘反转’利用判断条件:

  1. class Solution:
  2. def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
  3. length = len(A[0])
  4. for i in range(length):
  5. A[i] = A[i][::-1]
  6. for u in range(length):
  7. if A[i][u] == 0:
  8. A[i][u] = 1
  9. elif A[i][u] == 1:
  10. A[i][u] = 0
  11. return A

运行结果:

  1. 成功
  2. 显示详情
  3. 执行用时 : 116 ms , Flipping an ImagePython3提交中击败了 7.24% 的用户
  4. 内存消耗 : 13.2 MB , Flipping an ImagePython3提交中击败了 55.58% 的用户

发现耗时太多,准备进行改进,发现一个特别有意思的解法,直接利用列表生成式:

  1. class Solution:
  2. def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
  3. return [[j ^ 1 for j in i[::-1]] for i in A]

运行结果:

  1. 成功
  2. 显示详情
  3. 执行用时 : 72 ms , Flipping an ImagePython3提交中击败了 41.64% 的用户
  4. 内存消耗 : 13.1 MB , Flipping an ImagePython3提交中击败了 75.05% 的用户

用时还是有点长..

867. 转置矩阵

给定一个矩阵 A, 返回 A 的转置矩阵。

矩阵的转置是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。

  1. 示例 1
  2. 输入:[[1,2,3],[4,5,6],[7,8,9]]
  3. 输出:[[1,4,7],[2,5,8],[3,6,9]]
  1. 示例 2
  2. 输入:[[1,2,3],[4,5,6]]
  3. 输出:[[1,4],[2,5],[3,6]]

提示:

  1. 1
  2. 1

解答

思路:矩阵的转置,应该是以主对角线为对称轴,交换上下两边的元素,语法应该类似于 :A/[i]/[j] = B/[j]/[i]。

  1. class Solution:
  2. def transpose(self, A: List[List[int]]) -> List[List[int]]:
  3. B = [[None for i in range(len(A[1]))] for i in range(len(A[0]))]
  4. for i in range(len(A[0])):
  5. for j in range(len(A[1])):
  6. B[i][j] = A[j][i]
  7. return B

执行代码,通过:

  1. 输入
  2. [[1,2,3],[4,5,6],[7,8,9]]
  3. 输出
  4. [[1,4,7],[2,5,8],[3,6,9]]
  5. 预期结果
  6. [[1,4,7],[2,5,8],[3,6,9]]

但是提交后,却报错:

  1. IndexError: list index out of range
  2. Line 6 in transpose (Solution.py)
  3. Line 17 in __helper__ (Solution.py)
  4. Line 31 in _driver (Solution.py)
  5. Line 42 in (Solution.py)
  1. B[i][j] = A[j][i]

这一行报错列表的索引超出范围。

这是为什么呢?

正确解法

参考一位小姐姐类似的思路,解法如下,没有报错:

  1. class Solution:
  2. def transpose(self, A) :
  3. B = [[None for _ in range(len(A))]for _ in range(len(A[0]))] # 第二个for是行,第一个for是列
  4. for i in range(len(A)):
  5. for j in range(len(A[0])):
  6. B[j][i] = A[i][j] # [i][j]反过来对应
  7. return B
  1. 最近提交结果:通过
  2. 执行用时 :72 ms, 在所有Python3提交中击败了97.33%的用户
  3. 内存消耗 :13.6 MB, 在所有Python3提交中击败了
  4. 88.54%的用户

前后比对代码发现,这位小姐姐的代码在两次遍历len(A)时没有像我一样加上len(A[1]),这样就没报错,为什么?

905.按奇偶排序数组

给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例:

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">输入:[3,1,2,4]
输出:[2,4,3,1]
输出 [4,2,3,1],[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示:

  1. 1
  2. 0

解答

思想:两次遍历挑出符合要求的元素先后添加到新的列表中。

  1. class Solution:
  2. def sortArrayByParity(self, A: List[int]) -> List[int]:
  3. length = len(A)
  4. new_list = []
  5. for i in range(length):
  6. if A[i] % 2 == 0:
  7. new_list.append(A[i])
  8. for i in range(length):
  9. if A[i] % 2 != 0:
  10. new_list.append(A[i])
  11. return new_list

结果

  1. 成功
  2. [显示详情 ](https://leetcode-cn.com/submissions/detail/20099588/)
  3. 执行用时 : 88 ms, Sort Array By ParityPython3提交中击败了87.65% 的用户
  4. 内存消耗 : 13.7 MB, Sort Array By ParityPython3提交中击败了81.16% 的用户

更优解

使用双指针思想:左指针寻找奇数,右指针寻找偶数,再进行交换。

  1. class Solution {
  2. public:
  3. vector sortArrayByParity(vector& A) {
  4. int i = 0, j = A.size()-1;
  5. while(ij){
  6. while(A[i]%2==0&&ij) i++;
  7. while(A[j]%2==1&&ij) j--;
  8. swap(A[i],A[j]);
  9. }
  10. return A;
  11. }
  12. };
  13. 作者:Daning_NFH
  14. 链接:https://leetcode-cn.com/problems/two-sum/solution/an-qi-ou-pai-xu-shu-zu-by-daning_nfh/
  15. 来源:力扣(LeetCode
  16. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

试图只遍历一遍列表A

  1. class Solution:
  2. def sortArrayByParity(self, A: List[int]) -> List[int]:
  3. # return [e for e in A if e % 2 == 0] + [e for e in A if e % 2 == 1] #虽然只用了一行,但遍历了两次A
  4. return sorted(A, key=lambda x: x % 2 == 1) # 不知道sorted内部是怎么再现的,但这个题目本质是一个排序题,所以可以用内置排序函数来解
  5. # res = []
  6. # for x in A:
  7. # if x % 2 == 0:
  8. # res.insert(0, x)
  9. # else:
  10. # res.append(x)
  11. # return res
  12. # a, b = [], []
  13. # for x in A:
  14. # if x % 2 == 0:
  15. # a.append(x)
  16. # else:
  17. # b.append(x)
  18. # return a + b
  19. 作者:xie-yue-san-xing
  20. 链接:https://leetcode-cn.com/problems/two-sum/solution/li-yong-pai-xu-lai-jie-by-xie-yue-san-xing/
  21. 来源:力扣(LeetCode
  22. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

922. 按奇偶排序数组 II

给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。

对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

  1. 示例:
  2. 输入:[4,2,5,7]
  3. 输出:[4,5,2,7]
  4. 解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。
  1. 提示:
  2. 2 A.length 20000
  3. A.length % 2 == 0
  4. 0 A[i] 1000

解答

思路:先把列表中的奇偶数分类,用列表生成式,然后判断索引的奇偶性,逐个添加就好了。

  1. class Solution:
  2. def sortArrayByParityII(self, A: List[int]) -> List[int]:
  3. new_arry = []
  4. Ou_num = [A[i] for i in range(len(A)) if A[i] % 2 == 0]
  5. Ji_num = [A[i] for i in range(len(A)) if A[i] % 2 != 0]
  6. for i in range(len(A)):
  7. if i % 2 == 0:
  8. new_arry.append(Ou_num.pop()) #注意这里不能用new_arry[i] = Ou_num.pop()
  9. elif i % 2 != 0:
  10. new_arry.append(Ji_num.pop()) # #注意这里不能用new_arry[i] = Ou_num.pop()
  11. return new_arry

因为空数组不能直接指定位置:

  1. 解决方法1
  2. m1.append(1
  3. 解决方法2
  4. 先生成一个定长的list
  5. m1=[0]*len(data)
  6. m1[1]=1
  1. 执行用时 :200 ms, 在所有Python3提交中击败了41.69%的用户
  2. 内存消耗 :
  3. 15.2 MB, 在所有Python3提交中击败了90.87%的用户

更好的解法

留空

977. 有序数组的平方

给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

示例 1:

  1. 输入:[-4,-1,0,3,10]
  2. 输出:[0,1,9,16,100]

示例 2:

  1. 输入:[-7,-3,2,3,11]
  2. 输出:[4,9,9,49,121]

提示:

  1. 1 A.length 10000
  2. -10000 A[i] 10000
  3. A 已按非递减顺序排序。

解答:

遍历咯,sort()排序

  1. class Solution:
  2. def sortedSquares(self, A: List[int]) -> List[int]:
  3. array = []
  4. for i in A:
  5. array.append(i ** 2)
  6. array.sort()
  7. return array

结果

  1. 成功
  2. 显示详情
  3. 执行用时 : 216 ms , Squares of a Sorted ArrayPython3提交中击败了 64.24% 的用户
  4. 内存消耗 : 14.9 MB , Squares of a Sorted ArrayPython3提交中击败了 83.27% 的用户

更优办法

  1. class Solution(object):
  2. def sortedSquares(self, A):
  3. return sorted(x*x for x in A)

复杂度分析

时间复杂度: O(N \log N) O ( N lo g N ) ,其中 N N 是数组 A 的长度。
空间复杂度: O(N) O ( N ) 。

985. 查询后的偶数和

给出一个整数数组 A 和一个查询数组 queries。

对于第 i 次查询,有 val = queries[i][0], index = queries[i][1],我们会把 val 加到 A[index] 上。然后,第 i 次查询的答案是 A 中偶数值的和。

(此处给定的 index = queries[i][1] 是从 0 开始的索引,每次查询都会永久修改数组 A。)

返回所有查询的答案。你的答案应当以数组 answer 给出,answer[i] 为第 i 次查询的答案。

示例:

  1. 输入:A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
  2. 输出:[8,6,2,4]
  3. 解释:
  4. 开始时,数组为 [1,2,3,4]。
  5. 1 加到 A[0] 上之后,数组为 [2,2,3,4],偶数值之和为 2 + 2 + 4 = 8
  6. -3 加到 A[1] 上之后,数组为 [2,-1,3,4],偶数值之和为 2 + 4 = 6
  7. -4 加到 A[0] 上之后,数组为 [-2,-1,3,4],偶数值之和为 -2 + 4 = 2
  8. 2 加到 A[3] 上之后,数组为 [-2,-1,3,6],偶数值之和为 -2 + 6 = 4

提示:

  1. 1
  2. -10000
  3. 1
  4. -10000
  5. 0

解答

第一次看不懂题意。。。

正确的解法

方法:调整数组和
思路与算法

让我们尝试不断调整 S,即每一步操作之后整个数组的偶数和。

我们操作数组中的某一个元素 A[index] 的时候,数组 A 其他位置的元素都应保持不变。如果 A[index] 是偶数,我们就从 S 中减去它,然后计算 A[index] + val 对 S 的影响(如果是偶数则在 S 中加上它)。

这里有一些例子:

如果当前情况为 A = [2,2,2,2,2]、S = 10,并且需要执行 A[0] += 4 操作:我们应该先令 S -= 2,然后令 S += 6。最后得到 A = [6,2,2,2,2] 与 S = 14。

如果当前情况为 A = [1,2,2,2,2]、S = 8,同时需要执行 A[0] += 3 操作:我们会跳过第一次更新 S 的步骤(因为 A[0] 是奇数),然后令 S += 4。 最后得到 A = [4,2,2,2,2] 与 S = 12。

如果当前情况为 A = [2,2,2,2,2]、S = 10,同时需要执行 A[0] += 1 操作:我们先令 S -= 2,然后跳过第二次更新 S 的操作(因为 A[0] + 1 是奇数)。最后得到 A = [3,2,2,2,2] 与 S = 8。

如果当前情况为 A = [1,2,2,2,2]、S = 8,同时需要执行 A[0] += 2 操作:我们跳过第一次更新 S 的操作(因为 A[0] 是奇数),然后再跳过第二次更新 S 的操作(因为 A[0] + 2 是奇数)。最后得到 A = [3,2,2,2,2] 与 S = 8。

这些例子充分展现了我们的算法在每一次询问操作之后应该如何调整 S 。

  1. class Solution(object):
  2. def sumEvenAfterQueries(self, A, queries):
  3. S = sum(x for x in A if x % 2 == 0)
  4. ans = []
  5. for x, k in queries:
  6. if A[k] % 2 == 0: S -= A[k]
  7. A[k] += x
  8. if A[k] % 2 == 0: S += A[k]
  9. ans.append(S)
  10. return ans

复杂度分析

  • 时间复杂度:O(N+Q)O(N+Q),其中 NN 是数组 A 的长度, QQ 是询问 queries 的数量。
  • 空间复杂度:O(N+Q)O(N+Q),事实上我们只使用了 O(1)O(1) 的额外空间。

999. 车的可用捕获量

在一个 8 x 8 的棋盘上,有一个白色车(rook)。也可能有空方块,白色的象(bishop)和黑色的卒(pawn)。它们分别以字符 “R”,“.”,“B” 和 “p” 给出。大写字符表示白棋,小写字符表示黑棋。

车按国际象棋中的规则移动:它选择四个基本方向中的一个(北,东,西和南),然后朝那个方向移动,直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外,车不能与其他友方(白色)象进入同一个方格。

返回车能够在一次移动中捕获到的卒的数量。

示例 1:

  1. 输入:[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
  2. 输出:3
  3. 解释:
  4. 在本例中,车能够捕获所有的卒。

示例 2:

  1. 输入:[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
  2. 输出:0
  3. 解释:
  4. 象阻止了车捕获任何卒。

示例 3:

  1. 输入:[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
  2. 输出:3
  3. 解释:
  4. 车可以捕获位置 b5d6 f5 的卒。

提示:

  1. board.length == board[i].length == 8
  2. board[i][j] 可以是 ‘R’,’.’,’B’ 或 ‘p’
  3. 只有一个格子上存在 board[i][j] == ‘R’

解答

暂时没有思路,直接看看答案~

参考答案

思路:先找到车,再往上下左右移动

  1. class Solution:
  2. def numRookCaptures(self, board: List[List[str]]) -> int:
  3. # 先找到车
  4. for i in range(len(board[0])):
  5. for j in range(len(board[1])):
  6. if board[i][j] == 'R':
  7. x = i
  8. y = j
  9. count = 0
  10. # 向左(西)搜索
  11. for j in range(y - 1, -1, -1):
  12. if board[x][j] == 'p': # 抓到一只黑色的卒
  13. count += 1
  14. break
  15. elif board[x][j] == 'B':
  16. break # 碰到己方的象,停止
  17. # 向右(东)搜索:
  18. for j in range(y + 1, len(board[1])):
  19. if board[x][j] == 'p': # 抓到一只黑色的卒
  20. count += 1
  21. break
  22. elif board[x][j] == 'B':
  23. break # 碰到己方的象,停止
  24. # 向上(北)搜索
  25. for i in range(x - 1, -1, -1):
  26. if board[i][y] == 'p':
  27. count += 1
  28. break
  29. elif board[i][y] == 'B':
  30. break
  31. # 向下(南)搜索
  32. for i in range(x + 1, len(board[0])):
  33. if board[i][y] == 'p':
  34. count += 1
  35. break
  36. elif board[i][y] == 'B':
  37. break
  38. return count

注意缩进就好了,想清楚了很容易!

  1. 执行用时 :52 ms, 在所有Python3提交中击败了80.86%的用户
  2. 内存消耗 :13.1 MB, 在所有Python3提交中击败了72.50%的用户
赞赏
Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/193.html
首页      算法笔记      LeetCode      Leetcode 数组简单类解答集合(暂停更新)
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=monsterid&r=g

kanghaov

文章作者

推荐文章

发表评论

textsms
account_circle
email

Nemo

Leetcode 数组简单类解答集合(暂停更新)
1.两数之和 给定一个整数数组 nums 和一个目标值 target ,请你在该数组中找出和为目标值的那** 两个 **整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是…
扫描二维码继续阅读
2019-06-19