- 167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
class Solution {
public int[] twoSum(int[] numbers, int target){
int i = 0;
int j = numbers.length - 1;
while(i < j){
int sum = numbers[i] + numbers[j];
if(sum == target){
return new int[]{i+1,j+1};
}else if(sum > target){
j--;
}else{
i++;
}
}
return null;
}
}
- 633. Sum of Square Numbers
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
class Solution {
public boolean judgeSquareSum(int c) {
int i = 0;
int j = (int)Math.sqrt(c);
while(i <= j){
int Powsum = i*i + j*j;
if(Powsum == c){
return true;
}else if(Powsum > c){
j--;
}else{
i++;
}
}
return false;
}
}
- 345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Input: "hello"
Output: "holle"
Example 2:
Input: "leetcode"
Output: "leotcede"
class Solution {
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) {
int i = 0;
int 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 new String(result);
}
}
- Longest Word in Dictionary through Deleting
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:"apple"
class Solution {
public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for(String target : d){
int l1 = longestWord.length();
int l2 = target.length();
if(l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)){
continue;
} //遍历字符串集合中的每个元素，并进行比较，如果发现所返回的已经较大或相同大但字典序较大，则跳过本次循环。
if(isValid(s,target)){
longestWord = target;
}
}
return longestWord;
}
private boolean isValid(String s, String target) {
int i = 0;
int j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
}
- Valid Palindrome II
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution {
public boolean validPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return isPalindrome(s,i,j-1) || isPalindrome(s,i+1,j);
}
i++;
j--;
}
return true;
}
public boolean isPalindrome(String s,int i,int j){
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}
网友评论