This is the fourth day of my participation in the wenwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

110. Valid-anagram

The label

  • hash
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S. You can assume that strings contain only lowercase letters.

Example 1:

Input: s = "anagram", t = "nagaram" Output: trueCopy the code

Example 2:

Input: s = "rat", t = "car" output: falseCopy the code

The basic idea

In fact, it is to compare two words whether they use the same letters, but in different order. When it comes to order, the first thing that comes to mind is sorting. The code is very simple, but sorting (fast sorting) is at least order NLogN in average time.

A faster way to do this is to use the hashMap counting method, which uses a map to count the number of occurrences of each letter and then compares them.

Easy problem. Let’s just look at the code

Writing implement

The sorting

var isAnagram = function(s, t) {
    return s.length == t.length && s.split(' ').sort().join(' ') === t.split(' ').sort().join(' ')};let s = "anagram", t = "nagaram"
console.log(isAnagram(s, t))
Copy the code

The Map count

var isAnagram = function(s, t) {
    // The first step is to determine the length
    if(s.length ! == t.length) {return false;
    }
    // Since the string contains only 26 lowercase letters, we can maintain a hashTable of length 26
    // Initialize to 0 to indicate that the letter has occurred 0 times
    const table = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        table[s.codePointAt(i) - 'a'.codePointAt(0)] + +; }// console.log(table)
    // a ,b, c, d, e, ... , z
    // [3, 0, 0, 1, 0... 0
    // the corresponding a has 3, d has 1...

    // Then iterate over the t string, subtracting the corresponding position
    for (let i = 0; i < t.length; i++) {
        // The number of corresponding positions is reduced by 1
        table[t.codePointAt(i) - 'a'.codePointAt(0] -;T contains an extra character that is not in s. Return false
        if (table[t.codePointAt(i) - 'a'.codePointAt(0)]"0) {
            return false; }}return true;
}

let s = "anagramd", t = "nagaradm"
console.log(isAnagram(s, t)) // true
Copy the code

The nearest common ancestor of binary search tree (lowest-common-method-a-binary-search tree)

The label

  • BST
  • Binary search tree

The title

Leetcode portal

Let’s just open leetCode.

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the code

The basic idea

We did a very similar problem before, called the nearest common ancestor of a binary tree

Of course, a binary search tree is also a binary tree, and this is perfectly possible, but it’s easier to use the binary search tree property.

Root = root; root = root; root = root;

  • P and q valueAre less than the root. ValAccording to the BST property, p and q are both presentThe left subtree
  • P and q valueWere greater than the root. ValAccording to the BST property, p and q are both presentThe right subtree
  • Or if one is greater than the other and one is less than the other, that means they split, so root is their closest common ancestor, and they bifurcated

Writing implement

var lowestCommonAncestor = function(root, p, q) {
  // both p and q are less than root.val, p and q are in the left subtree
  if (root.val > p.val && root.val > q.val) {
    // Continue recursing the left subtree
    return lowestCommonAncestor(root.left, p, q)
  }
  if (root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q)
  }
  // Forked, root is the most recent common ancestor, return
  return root
};
Copy the code

Write an iteration, not a word count, but 20% faster

var lowestCommonAncestor = function(root, p, q) {
  while (root) {
    if (root.val > p.val && root.val > q.val) {
      root = root.left
    } else if (root.val < p.val && root.val < q.val) {
      root = root.right
    } else {
      return root
    }
  }
};
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference