Python|每日一练|数组|回溯|二分查找|排序和顺序统计量|.update方法 |单选记录：组合总和|寻找峰值|编程通过键盘输入每一位运动员

1、组合总和（数组、回溯）

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。 

示例 1：

输入：candidates = [2,3,6,7], target = 7,
输出：[[7],[2,2,3]]

示例 2：

输入：candidates = [2,3,5], target = 8,
输出：[[2,2,2,2],[2,3,3],[3,5]]

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

选项代码：

class Solution(object):def combinationSum(self, candidates, target):candidates.sort()dp = [[] for _ in range(target + 1)]dp[0].append([])for i in range(1, target + 1):for j in range(len(candidates)):if candidates[j] > i:breakfor k in range(len(dp[i - candidates[j]])):temp = dp[i - candidates[j]][k][:]if len(temp) > 0 and temp[-1] > candidates[j]:continuetemp.append(candidates[j])dp[i].append(temp)return dp[target]
if __name__ == '__main__':s = Solution()print (s.combinationSum([8,7,4,3], 11))

2、寻找峰值（数组，二分查找）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]

输出：2

解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]

输出：1 或 5

解释：你的函数可以返回索引 1，其峰值元素为 2；

     或者返回索引 5， 其峰值元素为 6。

 

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

选项代码（加入测试用例）：

from typing import List
class Solution:def findPeakElement(self, nums: List[int]) -> int:low = 0high = len(nums) - 1while low < high:mid = int(low - (low - high) / 2)if nums[mid] < nums[mid + 1]:low = mid + 1else:high = midreturn lowif __name__ == '__main__':nums =[1,2,1,3,5,6,4]s = Solution()print (s.findPeakElement(nums))

3、编程通过键盘输入每一位运动员

（算法初阶，排序和顺序统计量）

贡献者：chenalens

体操比赛成绩统计。多名运动员，多个评委打分，去掉一个最高分和去掉一个最低分，对其余分数求平均分作为一个运动员成绩。 编程通过键盘输入每位运动员编号和每个评委的成绩，求出运动员的最终成绩，并将运动员编号和最终成绩保存在一个字典中，形如{编号1:最终成绩1,学号2:最终成绩2.....，并将结果输出。

选项代码：

t = int(input('请输入评委人数（不得少于3人）：'))
s = int(input('请输入学生人数（不得少于1人）：'))
stus = []
for i in range(s):stu = {'score':[]}stu.update({'sn':str(input('----\n请输入学生学号：'))})for j in range(t):stu['score'].append(input('请输入评委'+str(j+1)+'的评分：'))stu['score'].sort()stu.update({'min':stu['score'].pop(0)})stu.update({'max':stu['score'].pop()})stu.update({'avg':eval('+'.join(stu['score']))/len(stu['score'])})stus.append(stu)
r = {n['sn']:n['avg'] for n in stus}
print(r)

PS:python字典update方法详解

http://www.coolpython.net/method_topic/dict/dict-update.html

update功能作用

python字典的update方法可以根据一个新的字典来更新原有的字典。新字典的key如果不在原字典中，update方法会插入新的key与value；如果新字典的key也在原字典中，update方法会根据新字典的key所对应的value更新原字典。

update语法

dict.update(dict2)

参数

• dict2 用于更新原字典的新字典

返回值

update方法没有返回值，它原地更新字典

示例代码

一般的使用模式是dic1.update(dic2)，将dic2的内容更新到dic1

score_dict = {'小明': 96,'小刚': 98,'小红': 94
}score_dict2 = {'小明': 100,'小丽': 98,
}score_dict.update(score_dict2)
print(score_dict)

如果一个key，在两个字典中都存在，则value的最终结果取决于dic2