leetcode中的一些题解

SunXinFei commented 5 years ago

两数求和

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 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;
};

这个思路是一层循环，用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;
};

还是按照第二个思路，第二个思路缺点就是虽然用了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 commented 4 years ago

二叉树遍历

前序遍历为： 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 commented 3 years ago

排序

动画演示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 commented 3 years ago

对象扁平

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))

SunXinFei / sunxinfei.github.io