电子商务网站网络拓扑,德州哪里做网站,wordpress自动标签,网站制作学习网站目录
1. 二分查找
2. 有序数组中寻找两个数和等于某数
3. 两数平方和
4. 翻转字符串中的元音字符
5. 判断是否为回文字符串#xff08;最多可以删除一个字符#xff09;
6. 归并两个有序数组
7. 判断链表是否有环
8. 最长子序列 1. 二分查找
从有序数组 nums 中查找…目录
1. 二分查找
2. 有序数组中寻找两个数和等于某数
3. 两数平方和
4. 翻转字符串中的元音字符
5. 判断是否为回文字符串最多可以删除一个字符
6. 归并两个有序数组
7. 判断链表是否有环
8. 最长子序列 1. 二分查找
从有序数组 nums 中查找等于 v 的索引
示例
输入nums[1,3,6,8,9], v3
输出1
二分查找表面上非常简单但是实际编程还是有几个点需要注意否则极易出现 bug。如果我们处理的是连续数值那就容易的多但本题目是离散整数值所以需要注意当左指针 left 与右指针 right 相差仅仅为 1 时的处理处理办法就是分别在左值和右值上加一和减一。
def fun(nums, v):left 0right len(nums) - 1while left right: # 注意加入等号mid (left right) // 2if nums[mid] v: right mid - 1 # 注意需要 -1elif nums[mid] v:left mid 1 # 注意需要 1else:return midreturn None
2. 有序数组中寻找两个数和等于某数
给你一个下标从 1 开始的整数数组 numbers 该数组已按非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。你可以假设每个输入只对应唯一的答案 而且你不可以 重复使用相同的元素。
示例
输入numbers [2,7,11,15], target 9
输出[1,2] 解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2]
def twoSum(numbers, target):low, high 0, len(numbers)-1while low high:sum numbers[low] numbers[high]if sum target:return [low1, high1]if sum target:high - 1else:low 1return [-1, -1]
3. 两数平方和
给定一个非负整数 c 你要判断是否存在两个整数 a 和 b使得 a2 b2 c
示例
输入c 5
输出true 解释1 * 1 2 * 2 5
在 python 中开根号有三种方式math.sqrt()、cmath.sqrt()、pow(,)推荐使用最后一种的内置函数。
def judgeSquareSum(c):low 0high int(pow(c, 0.5))while low high:res pow(low, 2) pow(high, 2)if res c:return Trueelif res c:high - 1else:low 1return False
4. 翻转字符串中的元音字符
给你一个字符串 s 仅反转字符串中的所有元音字母并返回结果字符串。
元音字母包括 a、e、i、o、u且可能以大小写两种形式出现不止一次。
示例
输入s hello
输出holle
在 python 中字符串不支持 a,bb,a 所以需要提前将字符串转换为 List。
def reverseVowels(s):left, right 0, len(s)-1vowel [a, e, i, o, u, A, E, I, O, U]s_list list(s)while left right:if s_list[left] in vowel and s_list[right] in vowel:s_list[left], s_list[right] s_list[right], s_list[left]left 1right - 1if s[left] not in vowel:left 1if s[right] not in vowel:right - 1return .join(s_list)
5. 判断是否为回文字符串最多可以删除一个字符
给你一个字符串 s最多可以从中删除一个字符。请你判断 s 是否能成为回文字符串如果能返回 true 否则返回 false 。
示例
输入s aba
输出true
def validPalindrome(s):def check(s, low, high):while low high:if s[low] s[high]:low 1high - 1else:return Falsereturn Truelow 0high len(s) - 1while low high:if s[low] s[high]:low 1high - 1else:if check(s, low, high-1) or check(s, low1, high):return Truereturn Falsereturn True
6. 归并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。
def merge(nums1, m, nums2, n):p1, p2 m - 1, n - 1tail m n - 1while p1 0 and p2 0:if nums1[p1] nums2[p2]:nums1[tail] nums1[p1]p1 - 1else:nums1[tail] nums2[p2]p2 -1tail - 1while p1 0:nums1[tail] nums1[p1]p1 - 1tail - 1while p2 0:nums1[tail] nums2[p2]p2 -1tail - 1
7. 判断链表是否有环
给你一个链表的头节点 head 判断链表中是否有环。
该问题有两个思路第一个思路是搭建一个哈希表存储访问过的每一个 node 的地址然后每访问一个 node就检查一遍哈希表。第二个思路是快慢指针如果链表有环那快慢指针一定会相遇。这两个思路都需要解决同一个问题即怎么判断两个 node 是同一个 nodeleetcode 原生代码是推荐使用 运算法直接判断但是这样判断只能说明两个 node 的值相等不能保证是同一个 node所以还是推荐使用 id() 函数比较 node 的地址。哈希表在运算时间上有优势双指针在所用内存上有优势。
def hasCycle(head):if head None:return Falseslow, fast head, headwhile fast ! None and fast.next ! None:slow slow.nextfast fast.next.nextif id(fast) id(slow): # 原生代码是 fast slowreturn Truereturn False
8. 最长子序列
给你一个字符串 s 和一个字符串数组 dictionary 找出并返回 dictionary 中最长的字符串该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个返回长度最长且字母序最小的字符串。如果答案不存在则返回空字符串。
示例
输入s abpcplea, dictionary [ale,apple,monkey,plea]
输出apple
def findLongestWord(s, dictionary):def fun(s, target):len_s, len_target len(s), len(target)p1, p2 0, 0while p1 len_s and p2 len_target:if s[p1] target[p2]:p2 1p1 1return p2 len_targetres for target in dictionary:if fun(s, target):if len(target) len(res):res targetelif len(target) len(res) and target res:res targetreturn res
