双指针167. 两数之和 II - 输入有序数组1.要求2.思路633. 平方数之和1.要求2.思路345. 反转字符串中的元音字母1.要求2.思路680. 验证回文字符串 Ⅱ1.要求2.思路88. 合并两个有序数组1.要求2.思路141. 环形链表1.要求2.思路524. 通过删除字母匹配到字典里最长单词1.要求2.思路167. 两数之和 II - 输入有序数组1.要求给定一个已按照升序排列 的有序数组找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2其中 index1 必须小于 index2。说明:返回的下标值index1 和 index2不是从零开始的。你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。示例:输入: numbers [2, 7, 11, 15], target 9输出: [1,2]解释: 2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。2.思路给定两个指针一个指针指向值较小的元素一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历指向较大元素的指针从尾向头遍历。如果sum为target 达到要求结果如果大于target,移动较大的元素如果小于target 移动较小的元素。classSolution{publicint[]twoSum(int[]numbers,int target){int i0;int jnumbers.length-1;while(ij){int sumnumbers[i]numbers[j];if(sumtarget){returnnewint[]{i1,j1};}elseif(sumtarget){i;}else{j--;}}returnnull;}}classSolution:deftwoSum(self,numbers:List[int],target:int)-List[int]:i0jlen(numbers)-1whileij:sum1numbers[i]numbers[j];ifsum1target:return[i1,j1]elif sum1target:i1else:j-1returnnull参考https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8F%8C%E6%8C%87%E9%92%88.md633. 平方数之和1.要求给定一个非负整数 c 你要判断是否存在两个整数 a 和 b使得 a2 b2 c。示例1:输入: 5输出: True解释: 1 * 1 2 * 2 5示例2:输入: 3输出: False2.思路两个指针一个指向小的元素一个指向大的元素最大就是本身如果小于就使得小的指针向大移动大于就使得大的指针向小的移动。改进 大的指针的数不可能是target** -2所以大的指针最多到target**-2.即小于平方根。classSolution{publicbooleanjudgeSquareSum(int c){int i0;int j(int)Math.sqrt(c);while(ij){int sumi*ij*j;if(sumc){returntrue;}elseif(sumc){i;}else{j--;}}returnfalse;}}classSolution:defjudgeSquareSum(self,c:int)-bool:i0jmath.floor(math.sqrt(c))print(j)whileij:sum1i**2j**2ifsum1c:returnTrue elif sum1c:j-1else:i1returnFalse345. 反转字符串中的元音字母1.要求编写一个函数以字符串作为输入反转该字符串中的元音字母。示例 1:输入: “hello”输出: “holle”示例 2:输入: “leetcode”输出: “leotcede”说明:元音字母不包含字母y。2.思路元音字符 aeiou双指针法一个记录小的元音字符一个记录大的元音字符然后交换。如果不包含就跳过。classSolution{privatefinalstaticHashSetCharactervowelsnewHashSet(Arrays.asList(a,e,i,o,u,A,E,I,O,U));publicStringreverseVowels(String s){int i0;int js.length()-1;char[]resultnewchar[s.length()];while(ij){char cis.charAt(i);char cjs.charAt(j);if(!vowels.contains(ci)){result[i]ci;}elseif(!vowels.contains(cj)){result[j--]cj;}else{result[i]cj;result[j--]ci;}}returnnewString(result);}}classSolution:defreverseVowels(self,s:str)-str:a1aeiouAEIOU;i0resultlist(copy.copy(s))jlen(s)-1whileij:print(s[i])ifs[i]notina1:result[i]s[i]i1elif s[j]notina1:result[j]s[j]j-1else:result[i]s[j]result[j]s[i]i1j-1return.join(result)680. 验证回文字符串 Ⅱ1.要求给定一个非空字符串 s最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: “aba”输出: True示例 2:输入: “abca”输出: True解释: 你可以删除c字符来源力扣LeetCode链接https://leetcode-cn.com/problems/valid-palindrome-ii著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。2.思路回文串就是从前到后和从后到前写都一样例如‘aba’’ 从后向前也是‘aba’,双指针问题一个指向最小一个指向最大不断向中间移动当两个指针指向的字符不同的时候判断两种情况是否满足小的增大一个位置看两端的字符是否相同或者大的位置减小一个是否相同。classSolution{publicbooleanispalindrome(String s,int i,int j){while(ij){if(s.charAt(i)!s.charAt(j--)){returnfalse;}}returntrue;}publicbooleanvalidPalindrome(String s){int js.length()-1;int i0;while(ij){if(s.charAt(i)!s.charAt(j)){returnispalindrome(s,i,j-1)||ispalindrome(s,i1,j);}i;j--;}returntrue;}}classSolution:defisPalindrom(self,s,i,j):returns[i:j1]s[i:j1][::-1]defvalidPalindrome(self,s:str)-bool:i0;jlen(s)-1whileij:ifs[i]!s[j]:returnself.isPalindrom(s,i1,j)or self.isPalindrom(s,i,j-1)i1j-1returnTrue88. 合并两个有序数组1.要求给定两个有序整数数组 nums1 和 nums2将 nums2 合并到 nums1 中使得 num1 成为一个有序数组。说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间空间大小大于或等于 m n来保存 nums2 中的元素。示例:输入:nums1 [1,2,3,0,0,0], m 3nums2 [2,5,6], n 3输出: [1,2,2,3,5,6]来源力扣LeetCode链接https://leetcode-cn.com/problems/merge-sorted-array著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。2.思路1.将数组先放入一个数组中然后排序太简单了效果不是很好。2.双指针法由于num1 已经提供了可以装下两个数组的空间因此可以直接在上边操作。由于是有序的因此标记两个数组最大的元素倒着装填nums1数组。有以下四种情况1.是num1 数组的指针小于0就装填另外一个数组2.反之亦然3.如果其中num1数组指针的元素小于num2数组指针指向的元素那么就将num2数组指针指向的元素装填到nums1当前的装填指针位置。classSolution{publicvoidmerge(int[]nums1,int m,int[]nums2,int n){int p1m-1;int p2n-1;int pnums1.length-1;while(p10||p20){if(p10){nums1[p--]nums2[p2--];}elseif(p20){nums1[p--]nums1[p1--];}elseif(nums2[p2]nums1[p1]){nums1[p--]nums1[p1--];}else{nums1[p--]nums2[p2--];}}}}141. 环形链表1.要求给定一个链表判断链表中是否有环。为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。示例 1输入head [3,2,0,-4], pos 1输出true解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出true解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出false解释链表中没有环。2.思路快慢指针如果有环快的终会追上慢的。publicclassSolution{publicbooleanhasCycle(ListNode head){if(headnull){returnfalse;}ListNode l1head;ListNode l2head.next;while(l1!nulll2!nulll2.next!null){if(l1l2){returntrue;}l1l1.next;l2l2.next.next;}returnfalse;}}524. 通过删除字母匹配到字典里最长单词1.要求给定一个字符串和一个字符串字典找到字典里面最长的字符串该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个返回长度最长且字典顺序最小的字符串。如果答案不存在则返回空字符串。示例 1:输入:s “abpcplea”, d [“ale”,“apple”,“monkey”,“plea”]输出:“apple”示例 2:输入:s “abpcplea”, d [“a”,“b”,“c”]输出:“a”说明:所有输入的字符串只包含小写字母。字典的大小不会超过 1000。所有输入的字符串长度不会超过 1000。2.思路1.将所有的可能存储起来然后查找。2.直接在未排序的字典 d 中查找字符串 target满足 target是 s的子序列。如果 target被找到了我们将它与其他匹配的字符串做比较直到找到长度最长、字典序最小的单词为止。classSolution{publicbooleanisSubtr(String s,String target){int i0;int j0;while(is.length()jtarget.length()){if(s.charAt(i)target.charAt(j)){j;}i;}returnjtarget.length();}publicStringfindLongestWord(String s,ListStringd){System.out.println(d);String longword;for(String target:d){int l1longword.length(),l2target.length();if(l1l2||(l1l2longword.compareTo(target)0)){//如果参数字符串等于此字符串则返回值 0如果此字符串按字典顺序小于字符串参数则返回一个小于 0 的值如//果此字符串按字典顺序大于字符串参数则返回一个大于 0 的值。continue;}if(isSubtr(s,target)){longwordtarget;}}returnlongword;}}