每日一道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 第 76 题：输出以下代码运行结果

// example 1
var a = {},
  b = "123",
  c = 123;
a[b] = "b";
a[c] = "c";
console.log(a[b]); // 'c'

// ---------------------
// example 2
var a = {},
  b = Symbol("123"),
  c = Symbol("123");
a[b] = "b";
a[c] = "c";
console.log(a[b]); // 'b'

// ---------------------
// example 3
var a = {},
  b = { key: "123" },
  c = { key: "456" };
a[b] = "b";
a[c] = "c";
console.log(a[b]); // 'c'

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* 第 77 题：旋转数组算法题

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4] */

const rotateAry = (ary, k) => {
  let len = ary.length;
  let rotateNum = k % len;
  if (rotateNum === 0) {
    return ary;
  }
  let tmpAry = new Array(len);
  ary.forEach((el, index) => {
    if (index + rotateNum >= len) {
      tmpAry[index + rotateNum - len] = el;
    } else {
      tmpAry[index + rotateNum] = el;
    }
  });
  return tmpAry;
};
console.log(rotateAry([1, 2, 3, 4, 5, 6, 7], 3));

// 牛逼写法
// 考虑用slice截取数组
function rotate(arr, k) {
  const len = arr.length;
  const step = k % len;
  return arr.slice(-step).concat(arr.slice(0, len - step));
}
// rotate([1, 2, 3, 4, 5, 6], 7) => [6, 1, 2, 3, 4, 5]

// 每次取出尾元素并插入到数组首部
var arr = [-1, -100, 3, 99];
var k = 5;
for (let i = 0; i < k; i++) {
  let val = arr.pop();
  arr.unshift(val);
}
console.log(arr);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* 第 82 题：算法题「移动零」

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。 */

const moveZeroToEnd = (nums) => {
	let length = nums.length
	for (let i = 0; i < nums.length; i++) {
		let el = nums[i]
		if (el === 0) {
			nums.splice(i, 1)
			i--
		}
	}
	let tmpAry = new Array((length - nums.length)).fill(0)
	return [...nums, ...tmpAry]
}
moveZeroToEnd([1,2,0,0,0,0,0,0,3,0,4])

// 核心思想：
// 非零元素和零元素交换位置，重点是保证非零元素下标大于等于零元素下标
const moveZeroToEnd_Upgrade = (nums) => {
	for (let i = 0, zero = 0; i < nums.length && zero < nums.length; i++) {
		if (nums[zero] !== 0) {
			zero++
		} else {
			if (nums[i] !== 0) {
				[nums[i], nums[zero]] = [nums[zero], nums[i]]
				zero++
			}
		}
	}
	// return nums
}
let p = [1,2,0,0,0,0,0,0,3,0,4]
moveZeroToEnd_Upgrade(p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：

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

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

var twoSum = function(nums, target) {
  const map = {}
  for (let i = 0; i < nums.length; i++) {
    const n = nums[i]
    if (target - n in map) {
      return [map[target - n], i]
    } else {
      map[n] = i
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/* 
第88题
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];
*/
// 伪代码
/* 
	map = new Map()
	for i in list
		map.set(i[id], i)
	map = {
		1: {id:1,name:'',parentId:0}
		2: {...}
		3: {...}
	}
	for i in list
		parent = map.get(i[parentId])
		parent[children] ? parent[children].push(i) : parent[children] = []
*/

const convert = list => {
  let map = new Map();
  let result = [];
  list.forEach(el => {
    map.set(el.id, el);
  });
  list.forEach(el => {
    if (el.parentId === 0) {
      result.push(el);
    } else {
      let parent = map.get(el.parentId);
      if (parent.hasOwnProperty('children')) {
        parent.children.push(el);
      } else {
        parent['children'] = [];
        parent.children.push(el);
      }
    }
  });
  return result;
};
let list = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 0 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 1 },
  { id: 5, name: '部门E', parentId: 2 },
  { id: 6, name: '部门F', parentId: 3 },
  { id: 7, name: '部门G', parentId: 2 },
  { id: 8, name: '部门H', parentId: 4 }
];
convert(list);