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,the result=9
• $18=9+1+8=9+9$
• $38=10+10+10+8$ ifnum=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

  1. number1
  2. number2
  3. number3

• PersonB :can take as much as he want

  1. number1
  2. number2
  3. number3

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 win
• n=2 A take 2,A win
• n=3 A take 3,A win

• n=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

So this question is a game problem.Code it is very easy and intersting

Solution2

  public boolean canWinNim(int n) {
    return n % 4 != 0;
  }