根据： github优秀创作者.
算法思想
1.双指针法
2.排序
3.贪心思想
4.二分查找
5.分冶
6.搜索
7.动态规划
8.数学
1. 双指针法：
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
1.1 有序数组的 Two Sum
题目描述：在有序数组中找出两个数，使它们的和为 target。
输入: numbers={2, 7, 11, 15}, target=9
输出: [1,2]
思路：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
class Solution:def twoSum(self,nums,target):i,j = 0,len(nums)-1while i<j:sum = nums[i]+nums[j]if sum < target:i += 1elif sum > target:j -= 1else:return [i+1,j+1]return None
1.2 两数平方和
题目描述：判断一个数是否为两个数的平方和。
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
思路：使用双指针，因为为两个数的平方和，一个指针指向较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
- 较小元素自定义为0，较大元素自定义为目标值的开平方
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，减小较大元素的值，使 sum 变小一些；
- 如果 sum < target，增大较小元素的值，使 sum 变大一些。
class Solution:def judgeSquareSum(self,target):i,j = 0,int(target**0.5)while i <= j:sum = i*i + j*jif sum < target:i += 1elif sum > target:j -= 1else:return Truereturn False
1.3 反转字符串中的元音字符
题目描述：编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
输入: "leetcode"
输出: "leotcede"
思路：使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。
class Solution:def reverseVowels(self, s: str) -> str:vowel = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']i, j = 0, len(s) - 1s = list(s)while i < j:if s[i] in vowel and s[j] in vowel:s[i], s[j] = s[j], s[i]i, j = i + 1, j - 1elif s[i] not in vowel:i = i + 1elif s[j] not in vowel:j = j - 1return ''.join(s)
1.4 回文字符串
题目描述：可以删除一个字符，判断是否能构成回文字符串。
输入: "aba"
输出: True
思路：使用双指针指向字符串，一个指针从头向尾遍历，一个指针从尾到头遍历。
- 如果双指针指着的两边的值不同的时候，选择跳过左边的或者右边的一个值，再去验证一遍
class Solution:def validPalindrome(self,strs):i,j = 0,len(strs)-1while i < j:if strs[i] != strs[j]:return self.isPalindrome(strs,i,j-1) | self.isPalindrome(strs,i+1,j)i += 1j -= 1return Truedef isPalindrome(self,strs,left,right):while left < right:if strs[left] != strs[right]:return Falseleft += 1right -= 1return True
本文内容根据github优秀创作者，仅仅是自己学习。
