1. 167 Sum of two numbers — enter an ordered array
1. Title description:
Given an array of integers in ascending order numbers, find two numbers that add up to the target number.
Example output:
Numbers = [2,7,11,15] target = 9 output: [1,2] So index1 = 1, index2 = 2.
2. The answer key:
Use two Pointers, left and right, to point to the beginning and end of the array, respectively. The left pointer moves from left to right and the right pointer traverses from right to left. (Because the input array is an ordered array) then:
- If the sum of the numbers pointed to by the left and right Pointers is equal to target, we get the result;
- if
sum > target, then we need to reduce the value of sum, that is, move the right pointer right; - if
sum < target, then we need to increase the sum value, that is, move the left pointer right.
The array is traversed at most once, and the time complexity is O(n). I’m just using two extra Spaces, order one.
3. Code:
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers.length == 0) return null;
int left = 0;
int right = numbers.length - 1;
while(left < right){
int sum = numbers[left] + numbers[right];
if(sum == target) return new int[]{left + 1, right + 1};
if(sum > target) right--;
if(sum < target) left++;
}
return null; }}Copy the code2. Sum of squares
1. Title description:
Given a non-negative integer c, you need to determine whether there are two integers A and b such that a^2 + b^2 = c.
Example output:
Input: c = 5 Output: true Description: 1 * 1 + 2 * 2 = 5
2. The answer key:
Find two numbers between 0 and target with the sum of their squares equal to target. If found, return true, indicating that target is the sum of the squares of the two numbers.
Right = SQRT (target); the left pointer is fixed to 0.
The time complexity is O(SQRT (target)) because 0 to SQRT (target) is traversed at most once. And because only two additional variables are used, the space complexity is O(1).
3. Code:
class Solution {
public boolean judgeSquareSum(int c) {
if(c < 0) return false;// A non-negative integer
int left = 0;// The initial left pointer value
int right = (int) Math.sqrt(c);// Right pointer initial value
while(left <= right){/ / note
int sum = left * left + right * right;
if(sum == c) return true;
if(sum > c) right--;
if(sum < c) left++;
}
return false; }}Copy the code3. Reverse the vowels in the string
1. Title description:
Takes a string as input, reverses the vowels in that string.
Example output:
Input: “hello” Output: “holle”
2. The answer key:
Use the two-pointer method, with one pointer traversing the string from left to right and the other from right to left. When both Pointers traverse a vowel, swap the two.
To quickly determine if a character is a vowel character, we add all vowel characters to the collection HashSet in O(1) time complexity.
3. Code:
class Solution {
// Set of vowels
private final static HashSet<Character> vowels = new HashSet<>(
Arrays.asList('a'.'e'.'i'.'o'.'u'.'A'.'E'.'I'.'O'.'U'));
public String reverseVowels(String s) {
if (s == null) return null;
int i = 0, j = s.length() - 1;
char[] result = new char[s.length()];
while (i <= j) {
char ci = s.charAt(i);
char cj = s.charAt(j);
if(! vowels.contains(ci)) { result[i++] = ci; }else if(! vowels.contains(cj)) { result[j--] = cj; }else{ result[i++] = cj; result[j--] = ci; }}return newString(result); }}Copy the code4. 680 Verify the palindrome character string
1. Title description:
Given a non-empty string s, at most one character is deleted. Determines whether it can become a palindrome string.
Example 1: Input: “ABA” output: True
Example 2: Input: “abca” Output: True Explanation: You can remove the C character.
2. The answer key:
Double pointer can easily determine whether a string is a palindrome string: to traverse a pointer from left to right, traverse a pointer from right to left, the two Pointers move a position at the same time, every time judge whether the characters of the two Pointers point to the same, if all the same, the string is the characteristics to bilateral symmetry of palindrome string.
The key in this case is dealing with the deletion of a character. When traversing a string with a double pointer, if two Pointers point to different characters, we try to delete a character and determine whether the deleted string is a palindrome string.
When determining whether it is a palindrome string, we do not need to determine the entire string, because the characters to the left and right of the left pointer have already been determined to be symmetric, so we only need to determine the middle substring.
When trying to delete a character, we can delete both the character pointed to by the left pointer and the character pointed to by the right pointer.
3. Code:
class Solution {
public boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if(s.charAt(i) ! = s.charAt(j)) {return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j); }}return true;
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if(s.charAt(i++) ! = s.charAt(j--)) {return false; }}return true; }}Copy the code5. 88 Merge two ordered arrays
1. Title description:
Merge nums2 into nums1 to make nums1 an ordered array.
Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.
Example output:
Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]
2. The answer key:
Start at the end of the array, I = m-1,j = n-1, k = m + n-1, place the largest number at the end of num1, and iterate until you get the final result.
3. Code:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;/ / traverse num1
int j = n - 1;/ / traverse num2
int k = m + n - 1;// Store the result location
while(i >= 0 || j >= 0) {if(i < 0){
nums1[k] = nums2[j];
k--;
j--;
}else if(j < 0){
nums1[k] = nums1[i];
k--;
i--;
}else if(nums1[i] > nums2[j]){
nums1[k] = nums1[i];
k--;
i--;
}else{ nums1[k] = nums2[j]; k--; j--; }}}}Copy the code6. 141 Ring linked list
1. Title description:
Given a linked list, determine whether there are rings in the list.
2. The answer key:
With dual Pointers, one pointer moves one node at a time and one pointer moves two nodes at a time, and if there is a ring, the two Pointers must meet.
3. Code:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null)
return false;
ListNode slow = head;
ListNode fast = head.next;
while(slow ! =null&& fast ! =null&& fast.next ! =null) {if(slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false; }}Copy the code7. 524. Matches the longest word in the dictionary by deleting letters
1. Title description:
Given a string and a dictionary of strings, find the longest string in the dictionary, which can be obtained by deleting some characters from the given string. If there is more than one answer, return the string with the longest length and the smallest dictionary order. If the answer does not exist, an empty string is returned.
Example output:
Input: s = “abpcplea”, d = [” ale “, “apple”, “monkey”, “plea”] output: “apple”
Input: s = “abpcplea”, d = [” A “,”b”,”c”] output: “A”
2. The answer key:
By deleting a character from string S, we get string T, which can be considered a subsequence of S. We can use a double pointer to determine whether one string is a subsequence of another string.
3. Code:
class Solution {
public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for (String target : d) {
int l1 = longestWord.length(), l2 = target.length();
if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
continue;
}
if(isSubstr(s, target)) { longestWord = target; }}return longestWord;
}
// A double pointer determines whether a string is a subsequence of another string
private boolean isSubstr(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
returnj == target.length(); }}Copy the code