#44 同字母异序
同字母异序指的是两个字符串字母种类和字母的数量相同，但是顺序可能不同。
完成 isAnagram，接受两个字符串作为参数，返回true 或者 false 表示这两个字符串是否同字母异序。例如：
isAnagram("anagram", "nagaram") // => return true.
isAnagram("rat", "car") // => return false.
我的解法
const isAnagram = (str1, str2) => /* TODO */
//1.先判断两个单词的个数是否相同
//2.for循环匹配单词是否一致
{
if(str1.length==str2.length){
var len=str1.length;
for(var i=0;i<len;i++){
if(str2.indexOf(str1[i])<0){
return false;
}
}
return true;
}else{
return false;
}
}
大神解法
//参考答案，先拆分排序再合并，最后比较
const isAnagram = (str1, str2) => str1.split('').sort().join('') === str2.split('').sort().join('');
#53 你会被谷歌拒绝吗？
使用广度优先的原则用数组的表示就是 [4, 3, 2, 7, 1, 2, 3, 6, 5, 9, null, null, null, null, null]，二叉树中的空位用 null 表示。
进行反转以后会变成[4, 2, 3, 3, 2, 1, 7, null, null, null, null, null, 9, 5, 6]
我的思路
1.将数组按照2的n次方切割成多个数组
2.将着多个数据反序
4.再合并多个数组
ps.有思路但是一直写得报错，下面是和我思路一样的小伙伴写得
const invertTree = (tree) => {
let i = 1;
if(tree.length<1)
return [];
let newTree = [tree[0]];
while(Math.pow(2,i)<=tree.length+1){
newTree.push(...tree.slice(Math.pow(2, i)-1,Math.pow(2, i+1)-1).reverse());
//写成 newTree.push(...tree.slice(xxx, yyy)) 和写成 newTree = newTree.concat(tree.slice(xxx, yyy)) 作用是一样的
i++;
}
return newTree;
}
某神解法
const invertTree = (tree) => {
/* TODO
这里面用了很多我好像没见过的写法，很方，我要去求解，后续整理放上
*/
let ret = []
for(let cur=1; tree.length > cur; cur<<=1) {
let mask = cur - 1
for(let x=0; x < cur; ++x)
ret.push(tree[mask+(mask^x)])
}
return ret
}
大神详解
大神说翻转二叉树，向来都不会是像我那样这么写的= =！
可以用递归，BFS 或者 DFS 写。这两个思路，效率都会很低。因为涉及到 push。第一种还用了 reverse。
一般来说，二叉树的题会给你 TreeNode （节点）的构造器。哪怕不给你，自己也要会写：
function TreeNode(value) {
this.value = value;
this.left = this.right = null;
}
一个节点只需要三个属性就够：value 表示当前节点值，left 表示左边的节点，right 表示右边
用递归写就很容易了：
function invertTree(root) {
if (root === null) {
return root;
}
var _temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(_temp);
return root;
}
//ps大神这个方法适合面试的时候回答，但是针对scriptoj 这题来说不能直接用
官方解法
//可以看出代码和大神说的有异曲同工之妙
const parseTree = (tree) => {
if(tree.length <= 3) {
const [root, left, right] = tree
return [root, [right], [left]]
}
const left = []
const right = []
let floor
tree.slice(1).forEach((value, index) => {
floor = ~~(Math.log(index + 2) / Math.LN2)
if (left.length < Math.pow(2, floor) - 1) {
left.push(value)
} else {
right.push(value)
}
})
return [tree[0], parseTree(right), parseTree(left)]
}
const flatTree = (tree) => {
if (tree.every(node => !Array.isArray(node))) return tree
const roots = tree.filter(node => !Array.isArray(node))
const children = tree.filter(node => Array.isArray(node)).reduce(
(children, child) => children.concat(child), [])
return roots.concat(flatTree(children))
}
const invertTree = (tree) => {
const parsedInvertedTree = parseTree(tree)
return flatTree(parsedInvertedTree)
}
大神针对此题的解法
/*
需要翻转的子数组，index 范围存在这样的关系：
1, 2^1;
1 + 2^1, 2^1 + 2^2;
1 + 2^1 + 2^2, 2^1 + 2^2 + 2^3;
swapInRange 用了双指针 + 递归。其实不用也行。
这里面，空间复杂度是 1，因为只用到了常数。时间复杂度貌似没啥优化=。=
*/
const invertTree = (tree) => {
var _index=1;
var i=1;
var j=Math.pow(2,i);
while(j<tree.length){
swapInRange(i,j);
i=j+1;
_index++;
j+=Math.pow(2,_index)
}
return tree;
function swapInRange(start,end){
if(start < end){
var temp=tree[start];
tree[start]=tree[end];
tree[end]=temp;
swapInRange(start+1,end-1)
}
}
}
这道题，二叉树的表示方法并不标准，这是用层先遍历的方式，遍历二叉树生成的数组
因此有一部分小伙伴会和我一样，直接把这题当数组题处理，把数组进行切片反转拼接
但此题主题是二叉树，那我们得先了解二叉树
二叉树，数据结构很简单。就是节点的值，左节点，右节点。
参考https://www.cnblogs.com/tugenhua0707/p/4361051.html
