leetcode中的一些题解

[SunXinFei]

两数求和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题：

1. 非常简单的暴力破解法，两层循环，一层是循环最外面的nums，内层循环nums只不过角标比外层多一。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var result = [];
    var size = nums.length;
    for(var i=0;i<size; i++){
       for(var j=i+1;j<size; j++){
           if(nums[i] + nums[j] === target){
              result= [i,j];
              return result;
            }
        }
    }
    return result;
};

2. 这个思路是一层循环，用target减去当前的元素的值，然后从nums数组中找一下有没有这个剩下元素

var twoSum = function(nums, target) {
    let size = nums.length;
    let result = [];
    for(let i=0;i<size; i++){
       let tmpR = target - nums[i];
        let targetIndex = nums.lastIndexOf(tmpR);
        if( targetIndex !== -1 && targetIndex !== i){
          return retult = [i, targetIndex]
        }
    }
    return result;
};

3. 还是按照第二个思路，第二个思路缺点就是虽然用了lastIndexOf这个方法，但是还是太慢了，毕竟用indexof这种方法还是循环了一次数组。所以我们这里使用上map。我们在循环的时候，边给map添加我们要找到的减去的值，并记录下当前的角标，这样在我们在循环到数组的下个数就在map里面，那么这就是我们要的结果，把map中的角标和下一个元素角标返回即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = {};
    for (let i = 0; i < nums.length - 1; i++) {
        map[target-nums[i]] = i;
        if (nums[i+1] in map) return [map[nums[i+1]], i+1];
    }
};

[SunXinFei]

二叉树遍历

前序遍历为：
ABDGHECKFIJ
中序遍历为：
GDHBEAKCIJF
后序遍历为：
GHDEBKJIFCA

先序遍历

let result = [];
let dfs = function (node) {
    if(node) {
        result.push(node.value);
        dfs(node.left);
        dfs(node.right);
    }
}

dfs(tree);
console.log(result); 

中序遍历

let result = [];
let dfs = function (node) {
     if(node) {
        dfs(node.left);
        result.push(node.value); // 直到该结点无左子树 将该结点存入结果数组 接下来并开始遍历右子树
        dfs(node.right);
    }
}

dfs(tree);
console.log(result);

后序遍历

result = [];
function dfs(node) {
    if(node) {
        dfs(node.left);
        dfs(node.right);
        result.push(node.value);
    }
}
dfs(tree);
console.log(result);

广度遍历

let result = [];
let stack = [tree]; // 先将要遍历的树压入栈
let count = 0; // 用来记录执行到第一层
let bfs = function () {
    let node = stack[count];
    if(node) {
        result.push(node.value);
        if(node.left) stack.push(node.left);
        if(node.right) stack.push(node.right);
        count++;
        bfs();
    }
}
bfs();
console.log(result);

[SunXinFei]

排序

动画演示https://visualgo.net/zh/sorting
时间复杂度记忆-
冒泡、选择、直接 排序需要两个循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）
稳定性记忆-“快希选堆”（快牺牲稳定性）
排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

[SunXinFei]

对象扁平

var entryObj = {
	a: {
		b: {
			c: {
				dd: 'abcdd'
			}
		},
		d: {
			xx: 'adxx'
		},
		e: 'ae'
	}
}
// 要求转换成如下对象
var outputObj = {
	'a.b.c.dd': 'abcdd',
	'a.d.xx': 'adxx',
	'a.e': 'ae'
}

function isObject(ob) {
        return Object.prototype.toString.call(ob) === '[object Object]';
}
function flat(entryObj) {
        let result = {};
        fn(entryObj);
        return result;

        function fn(obj, tmp='') {
            for (let key in obj) {
                if (isObject(obj[key])) {
                    fn(obj[key], tmp + key);
                } else {
                    result[tmp + key] = obj[key];
                }
            }
        }
    }
  console.log(flat(entryObj))