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 value
Are less than the root. Val
According to the BST property, p and q are both presentThe left subtree
- P and q value
Were greater than the root. Val
According 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