374. Guess Number Higher or Lower
This question is also a Binary Search question.We can notice one thing.1 <= pick <= n.So this question is search 1 between n.We can search their mid number.If is less than the target just need to update the head.If is bigger than the target just need to update the tail.
Solution
public int guessNumber(int n) {
int head = 1, tail = n;
while (head < tail) {
int mid = head + (tail - head) / 2;
//mid > n
if (guess(mid) == -1) {
tail = mid - 1;
} else if (guess(mid) == 1) {
//mid < n
head = mid + 1;
} else {
//find the target
return mid;
}
}
//while head==tail
return head;
}383. Ransom Note
This question is a little similar to 349. Intersection of Two Arrays We can also use HashMap. The number of occurrences of each letter corresponds to a value.And find all the letters that appear in the first string.
Solution1
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < magazine.length(); i++) {
int value = magazine.charAt(i) - 'a';
//if is the first time appear,just set initial value
if (!hashMap.containsKey(value)) {
hashMap.put(value, 1);
} else {
//calculate the number of occurrences
hashMap.put(value, hashMap.get(value) + 1);
}
}
for (int i = 0; i < ransomNote.length(); i++) {
int value = ransomNote.charAt(i) - 'a';
//if don't include this letter,just return false
if (!hashMap.containsKey(value)) {
return false;
} else {
//the number of occurrences is less than the number of times needed
if (hashMap.get(value) - 1 < 0) {
return false;
} else {
hashMap.put(value, hashMap.get(value) - 1);
}
}
}
return true;
}But the efficiency of HashMap is not high,we can notice consist of lowercase English letters So we can use array to store the number of occurrences.This solution is simplified.But the core solution idea has not changed.
Solution2
public boolean canConstruct(String ransomNote, String magazine) {
//26 letters
int[] result = new int[26];
for (int i = 0; i < magazine.length(); i++) {
result[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if (result[ransomNote.charAt(i) - 'a'] == 0) {
return false;
} else {
result[ransomNote.charAt(i) - 'a']--;
}
}
return true;
}387. First Unique Character in a String
This question is very similar to 383. Ransom Note.If you understand that question,you can also solve this question easily.We can also use HashMap or ASCII to solve it.
Solution1
public int firstUniqChar(String s) {
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
//count the number of occurrences
hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
//if the number is 1,just return the location of the letter
if (hashMap.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}Solution2
public int firstUniqChar(String s) {
int[] result = new int[26];
for (int i = 0; i < s.length(); i++) {
//use ASCII table to judge the letter
result[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
//if the letter's occurrences is 1,just return the location of the letter
if (result[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}389. Find the Difference
This question is similar to 136. Single Number.We can just traverse the string once.The main idea is XOR or use ASCII.We can set a value to store the difference between each of their elements.It is seems like commutative law of addition.Add the last element of T in the end.
Solution1
public char findTheDifference(String s, String t) {
int result = 0;
for (int i = 0; i < s.length(); i++) {
//char - char the result is int
result += t.charAt(i) - s.charAt(i);
}
//use ASCII table to get the letter
return (char) (result + t.charAt(t.length() - 1));
}Solution2
public char findTheDifference(String s, String t) {
int result = 0;
for (int i = 0; i < s.length(); i++) {
//use XOR,just like question 136
result ^= s.charAt(i);
result ^= t.charAt(i);
}
return (char) (result ^ t.charAt(t.length() - 1));
}392. Is Subsequence
This question is also a double pointer question.We can search from the head of s and t.If there are equal,just continue.
Solution
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
//if there are equal,just update the i
if (s.charAt(i) == t.charAt(j)) {
i++;
}
//j must update each time
j++;
}
//verify that the value of i is equal to the length of s
return i == s.length();
}401. Binary Watch
This question is not a easy question.When i thought about it for the first time,i have no idea.But i gradually discovered that this is an enumeration problem.We can use two HashMap to store hour and minute values separately.Then pair with the other party and verify that it meets the specifications.
Solution1
public List<String> readBinaryWatch(int turnedOn) {
//make two HashMap to store hour and minutes values separately
HashMap<Integer, List<String>> hashHour = new HashMap<>();
HashMap<Integer, List<String>> hashMins = new HashMap<>();
//such as hour : 1,2,4,8 only have one 1
for (int i = 0; i < 12; i++) {
int hours = numberOf1(i);
hashHour.putIfAbsent(hours, new ArrayList<String>());
hashHour.get(hours).add(i + "");
}
//count the minute,get the number of 1
for (int i = 0; i < 60; i++) {
int mins = numberOf1(i);
hashMins.putIfAbsent(mins, new ArrayList<String>());
//if the minute is 01,02,04,08
if (i < 10) {
hashMins.get(mins).add("0" + i);
} else {
hashMins.get(mins).add(i + "");
}
}
ArrayList<String> result = new ArrayList<>();
//if the hour's number of 1 is n,so minute's number of 1 is m-n
for (int i = 0; i <= turnedOn; i++) {
//non-existent situation,just continue
if (!hashHour.containsKey(i) || !hashMins.containsKey(turnedOn - i)) {
continue;
}
//enumeration method,paired with each other
for (String s : hashHour.get(i)) {
for (String s1 : hashMins.get(turnedOn - i)) {
result.add(s + ":" + s1);
}
}
}
return result;
}
/**
* count the number of 1 in binary
*/
private int numberOf1(int num) {
int count = 0;
while (num != 0) {
++count;
num &= (num - 1);
}
return count;
}But this question can also be enumerated directly without storing the result of enumeration.The idea of solving the problem as a whole is still the same.
Solution2
public List<String> readBinaryWatch(int turnedOn) {
ArrayList<String> strings = new ArrayList<>();
//hour
for (int i = 0; i < 12; i++) {
//minute
for (int j = 0; j < 60; j++) {
//if n + m = turnedOn
if (numberOf1(i) + numberOf1(j) == turnedOn) {
//judge the minute
strings.add(i + ":" + ((j < 10) ? "0" + j : j));
}
}
}
return strings;
}
/**
* count the number of 1 in binary
*/
private int numberOf1(int num) {
int count = 0;
while (num != 0) {
++count;
num &= (num - 1);
}
return count;
}