167.两数之和Ⅱ- 输入有序数组 （easy） 2021-01-27
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明: 返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2]
这个题如果使用一个指针就需要循环遍历且浪费数组已经排序好的信息。使用两个指针一头一尾，对比目标值不断变化即可。
public int[] twoSum(int[] numbers, int target) { int[] ret = new int[2]; int low = 0, high = numbers.length - 1; while(numbers[low] + numbers[high] != target){ if((numbers[low] + numbers[high]) > target) high--; if((numbers[low] + numbers[high]) < target) low++; } ret[0] = low + 1; ret[1] = high + 1; return ret; }
633. 平方数之和 （medium） 2021-01-28
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
public boolean judgeSquareSum(int c) { int low = 0, high = (int)Math.sqrt(c); while(low <= high){ if(low * low + high * high == c){ return true; } if(low * low + high * high < c){ low ++; } if(low * low + high * high > c){ high--; } } return false; }
345. 反转字符串中的原因字母 （easy） 2021-01-28
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。示例 1：
输入："hello" 输出："holle"
class Solution { public String reverseVowels(String s) { char[] arr = s.toCharArray(); int i = 0, j = arr.length - 1; while(i < j){ if(isVowel(arr[i]) && isVowel(arr[j]) ){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } if(isVowel(arr[i]) && !isVowel(arr[j])){ j--; } if(!isVowel(arr[i]) && isVowel(arr[j])){ i++; } if(!isVowel(arr[i]) && !isVowel(arr[j])){ i++; j--; } } return new String(arr); } public boolean isVowel(char c){ if(c == ‘a‘ | c == ‘e‘ || c == ‘i‘ || c == ‘o‘ || c == ‘u‘ || c == ‘A‘ || c == ‘E‘ || c == ‘I‘ ||c == ‘O‘ || c == ‘U‘){ return true; }else{ return false; } } }
680. 验证回文字符串Ⅱ （easy） 2021-01-28
给定一个非空字符串
s，最多删除一个字符。判断是否能成为回文字符串。示例 1:
输入: "aba" 输出: True
class Solution { public boolean validPalindrome(String s) { int i = 0, j = s.length() - 1; while(i < j){ if(s.charAt(i) == s.charAt(j)){ i++; j--; }else{ return isValidPalindrome(s.substring(i + 1, j + 1)) | isValidPalindrome(s.substring(i, j));//本来是（i， j + 1） } } return true; } //这个函数判断的是不删除字符，判断是否能成为回文字符串 private boolean isValidPalindrome(String s){ int i = 0, j = s.length() - 1; while(i < j){ if(s.charAt(i) == s.charAt(j)){ i++; j--; }else{ return false; } } return true; } }
88. 合并两个有序数组 （easy） 2021-01-28
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
我的思维还是太僵化，首先想到的思路就是新建一个数组，然后从头开始比较nums1 和nums2 的值放进新数组中，最后在全部转移到1中。
题目中暗示直接放在nums1 中，所以从后往前遍历，会节约数组空间。
public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while(i >= 0 && j >= 0){ if(nums1[i] >= nums2[j]){ nums1[k] = nums1[i]; i--; k--; } if(i >= 0 && nums1[i] < nums2[j]){ nums1[k] = nums2[j]; j--; k--; } } while(i == -1 && j >= 0){ nums1[k] = nums2[j]; j--; k--; } }
141. 环形链表 （easy）2021-01-28
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
我想到的是快慢指针的算法。如果有环，快慢指针一定会相遇。
public boolean hasCycle(ListNode head) { if(head == null || head.next == null || head.next.next == null) { return false; } ListNode low = head.next; ListNode fast = head.next.next; while(fast != low){ if(fast.next == null || fast.next.next == null) { return false; } low = low.next; fast = fast.next.next; } return true; }
524. 通过删除字母匹配到字典里最长单词 （medium）2021-01-28
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]输出:
"apple"
我的解法是，先写一个是否为子字符串的函数，然后遍历字典。
这个题有歧义，地方在于它所说的字典顺序并不是在字典中的顺序，而是字面意思的字典序。ab > ba， 使用compareTo 函数比较即可。
class Solution { public String findLongestWord(String s, List<String> d) { String ret = new String(); Iterator<String> iterator = d.iterator( ); while(iterator.hasNext( )){ //用hasNext()判断iterator的下一个是否有数据 String temp = iterator.next() ; if(isSubString(s, temp) && temp.length() > ret.length()){ ret = temp; } if(isSubString(s, temp) && temp.length() == ret.length() && temp.compareTo(ret) < 0){ ret = temp; } } return ret; } //次函数判断s2 是否为 S1 的子字符串 private boolean isSubString(String s1, String s2){ int i = 0, j = 0; while(i < s1.length() && j < s2.length()){ if(s1.charAt(i) == s2.charAt(j)){ i++; j++; }else{ i++; } } return j == s2.length() ? true : false; } }
原文：https://www.cnblogs.com/nobita/p/14337619.html