242. Valid Anagram
This question is similar to question 205. Isomorphic Strings. They have similarities.We can also use ASCII table to solve it.
Solution1
public boolean isAnagram(String s, String t) {
//different length,just return false
if (s.length() != t.length()) {
return false;
}
//26 letters
int[] ch = new int[26];
//traversal s and t
for (int i = 0; i < s.length(); i++) {
ch[s.charAt(i) - 'a']++;
ch[t.charAt(i) - 'a']--;
}
//traversal the arrays
for (int i = 0; i < 26; i++) {
if (ch[i] != 0) {
return false;
}
}
return true;
}
But this question also ask us what to do if the input string contains unicode characters.So this time we have to use HashMap.Because HashMap can mark each characters in the string.
Solution2
public boolean isAnagram(String s, String t) {
//different length,just return false
if (s.length() != t.length()) {
return false;
}
//character is the charAt,integer is the number of the character
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//if is the first time find the character,so use the defaultValue 0 and plus 1
hashMap.put(ch, hashMap.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
//and minus 1
hashMap.put(ch, hashMap.getOrDefault(ch, 0) - 1);
//it means they are different string,just return false
if (hashMap.get(ch) < 0) {
return false;
}
}
return true;
}
257. Binary Tree Paths
This question is very similar to question 144. Binary Tree Preorder Traversal. It is also traversal this tree.You only need to store the found Tree Nodes.And also determine whether it is the last leaf node.
So we can use two java class.ArrayList
to store all paths,LinkedList
to store the current node.
Solution
/**
* store all paths
*/
ArrayList<String> result = new ArrayList<String>();
/**
* store the current node
*/
LinkedList<String> path = new LinkedList<>();
public List<String> binaryTreePaths(TreeNode root) {
traverse(root);
return result;
}
/**
* just like Binary Tree Preorder Traversal
*/
private void traverse(TreeNode node) {
//if node is null,just return
if (node == null) {
return;
}
//String.valueOf make this value become String,and add into the path
path.add(String.valueOf(node.val));
//Return leaf node
if (node.left == null && node.right == null) {
//add into the result,"->path"
result.add(String.join("->", path));
}
if (node.left != null) {
traverse(node.left);
}
if (node.right != null) {
traverse(node.right);
}
//Delete and return the last element
path.removeLast();
}
258. Add Digits
This problem has two solutions.The first one solution is a easy math thinking.We can update the num when we finish the calculation.
Solution1
public int addDigits(int num) {
int result = 0;
while (num > 0) {
//get every digit
result += num % 10;
num /= 10;
//if num is 38,so result is 11,we need to update the num and the result
if (num == 0 && result > 9) {
num = result;
result = 0;
}
}
return result;
}
The second solution is a very clever solution,because this question requires us to think about the time cost $O(N)$.We all know that in mathematical addition,9 plus 1 carry to 10.So i make a example.
- $18=10+8$.If
num=18
,theresult=9
- $18=9+1+8=9+9$
- $38=10+10+10+8$ if
num=38
,theresult=2
- $38=9+1+9+1+9+1+8=9+9+9+9+2$
So we found the pattern
- If this number is divided by 9 there is no remainder,the result is 9
- If this number is divided by 9 there is a remainder,the result is remainder
Solution2
public int addDigits(int num) {
if (num == 0) {
return 0;
}
if (num % 9 == 0) {
return 9;
} else {
return num %= 9;
}
}
263. Ugly Number
This problem is a very easy math problem.As we all know if n>0
and n is the ugly number,$n=2^a\times3^b\times5^c$,if a b d are all 0
,so the n is 1
.And because multiplication satisfies the commutative law.So no matter which number we divide first.If its remainder is not 0
,so it's not ugly number.
Solution
public boolean isUgly(int n) {
//n<=0 are all false
if (n <= 0) {
return false;
}
//n will become 1 at last
while (n > 1) {
if (n % 2 == 0) {
n /= 2;
continue;
}
if (n % 3 == 0) {
n /= 3;
continue;
}
if (n % 5 == 0) {
n /= 5;
continue;
}
//it's not ugly number
if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0) {
return false;
}
}
return true;
}
268. Missing Number
This problem is a easy math problem.We can find a constrains in the problem,all the number of the nums
are unique
.So we can use Gauss Summation to solve this problem.We have the length of the nums
,and we can calculate the synthesis of all the elements.And minus each elements,the result is the answer.
Solution
public int missingNumber(int[] nums) {
//calculate the synthesis of all the elements
int n = (1 + nums.length) * nums.length / 2;
//minus all the elements
for (int num : nums) {
n -= num;
}
return n;
}
278. First Bad Version
This test point for this question if Binary Search.If you want to understand the Binary Search method carefully,you can read my Blog LeetCode EasyTopic Notes2.We just need to determine whether the elements is bad version.And use Binary Search.
Solution
public int firstBadVersion(int n) {
int head = 1;
while (head < n) {
int mid = (n - head) / 2 + head;
if (!isBadVersion(mid)) {
head = mid + 1;
} else {
n = mid;
}
}
return head;
}
283. Move Zeroes
This problem has two easy solution.This problem require us must do this in-place without making a copy of the array.
Solution1
We can traversal the array twice.Begin from the head,while the element isn't 0
,put it to the head.So the non-zero elements are all sorted at the head.And let all tail elements be 0
public void moveZeroes(int[] nums) {
int n = 0;
//let [0,n] are all non-zero elements
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[n] = nums[i];
n++;
}
}
//[n+1,nums.length] are all 0
for (int i = n; i < nums.length; i++) {
nums[i] = 0;
}
}
Solution2
We can solve it like quick sort.0
as a demarcation point.When the element is not 0
,exchange with the previous element.
public void moveZeroes(int[] nums) {
int n = 0;
for (int i = 0; i < nums.length; i++) {
//while the element is not 0,exchange with the previous element
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[n];
nums[n++] = temp;
}
}
}
290. Word Pattern
This question is an upgraded version of the difficulty of question 205.If you want to know how to solve this question,you must know how to solve 205,you can read my notes about 205 LeetCode EasyTopic Notes6.
This question we also use HashMap and HashSet.And the main idea is similar with 205.We still iterate over the string.And verify in turn whether it has appeared.If it has appeared but the data recorded on both sides are different just return false.Else update the record.
Solution
public boolean wordPattern(String pattern, String s) {
//such as <a,dog> <c,cat>
HashMap<Character, String> pMap = new HashMap<>();
//such as <dog> <cat>
HashSet<String> sSet = new HashSet<>();
//Remove the spaces in the string,and change it to array,such as array[0] is dog,array[1] is cat
String res[] = s.split(" ");
//if the length is not equal,just return false
if (res.length != pattern.length()) {
return false;
}
//traversal the string
for (int i = 0; i < pattern.length(); i++) {
//if a letter has appeared
if (pMap.containsKey(pattern.charAt(i))) {
//compare whether the current array element are the same as the previous ones
if (!res[i].equals(pMap.get(pattern.charAt(i)))) {
return false;
}
} else {
//if the letter is the first time appear,just add the array element
if (!sSet.add(res[i])) {
//if the element has been added,so just return false
return false;
}
//HashMap put the new <s,ship>
pMap.put(pattern.charAt(i), res[i]);
}
}
return true;
}
292. Nim Game
This is a very interesting question.When i first time read this question,i thought it is a recursion solution.
I did a reasoning.
Person
A
:can take as much as he want- number
1
- number
2
- number
3
- number
Person
B
:can take as much as he want- number
1
- number
2
- number
3
- number
When A
has taken it.So this question can change to B
take n-1
or n-2
or n-3
And the n
become n<=3
,the next person to take it will win.So i write this code first.
if (n <= 3) {
return true;
}
And if the number is 5
.PersonA
can choose how many what he take.He can only take 1
,and the n
become 4
.So no matter how many what personB
take,personA
will always win.
So if personB
must win situation is no matter how many what personA
take.It is always n>3
,must return false.So the opposite situation is A
always win,the number always n<3
.So you can come up with all the recursion code.
Solution1
public boolean canWinNim(int n) {
//n<=3,it will win,so return true
if (n <= 3) {
return true;
} else {
//if n==4,no matter hwo many A take.B will always win.So get the opposite situation !(B win)
return !(canWinNim(n - 1) && canWinNim(n - 2) && canWinNim(n - 3));
}
}
But the recursion will over time,because the number of n is 1<=n<=2^31-1
.So i change this code.
We can find a pattern
n=1
A take 1,A winn=2
A take 2,A winn=3
A take 3,A winn=4
- A take 1,B take 3,B win
- A take 2,B take 2,B win
- A take 3,B take 1,B win
n=5
- A take 1,
n=4
,A always win
- A take 1,
So this question is a game problem.Code it is very easy and intersting
Solution2
public boolean canWinNim(int n) {
return n % 4 != 0;
}