Alan's Site

Life is a journey.

2025-01-03
前端面试常见手撕JS代码题

前端面试常见手撕JS代码题

codes

1. 数组，用 reduce​ 方法实现 map​ 方法

  • ​array.map(callback(element, index, array), thisArg)​
  • ​array.reduce(callback(accumulator, currentValue, index, array), initialValue​
1
2
3
4
5
6
7
function mapUsingReduce(arr, func) {
	return arr.reduce((pre, cur, index, arr) => {
		// return [...pre, func(ele)];
		pre.push(func(cur, index, arr));
		return pre;
	}, [])
}

2. 实现函数repeat​

需要实现的函数repeat()

1
2
3
4
5
function repeat (func, times, wait){} 
// 使下面代码能正常工作 
const repeatFunc = repeat(console.log, 4, 3000)  
repeatFunc('helloworld') 
//会输出 4 次 hellworld，每次间隔 3 秒

实现如下:

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
function repeat (func, times, wait) {
	return function(...args) {
		let count = 0;
		const interval = setInterval(() => {
			if(count < times) {
				func(...args);
				count ++;
			} else {
				clearInterval(interval);
			}

		}, wait);
	}

} 

function repeat(func, times, wait) {
	return function(...args) {
		let count = 0;

		function exec() {
			if(count < times) {
				func(...args);
				count ++;
				setTimeout(exec, wait);
			}
		}

		exec();
	}
}

3. Vue 组件：实现搜索框自动补全功能

以下是一个实现类百度搜索框功能的 Vue 3 组件。此组件会监听用户的输入，并根据输入动态显示相关的自动补全下拉列表。

组件代码

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
<template>
  <div class="search-box">
    <input 
      type="text" 
      v-model="query" 
      @input="onInput" 
      placeholder="请输入搜索内容..." 
      class="search-input"
    />
    <ul v-if="suggestions.length" class="suggestions-list">
      <li 
        v-for="(suggestion, index) in suggestions" 
        :key="index" 
        @click="selectSuggestion(suggestion)"
        class="suggestion-item"
      >
        {{ suggestion }}
      </li>
    </ul>
  </div>
</template>

<script>
import { ref } from 'vue';

export default {
  setup() {
    const query = ref(""); // 用户输入的查询内容
    const suggestions = ref([]); // 自动补全列表

    // 模拟从后台获取数据
    const fetchSuggestions = (query) => {
      const allData = ["苹果", "香蕉", "橙子", "葡萄", "菠萝", "草莓", "蓝莓", "芒果"];
      if (!query) {
        return [];
      }
      return allData.filter(item => item.includes(query));
    };

    // 用户输入时触发
    const onInput = () => {
      suggestions.value = fetchSuggestions(query.value);
    };

    // 用户点击某个推荐项时
    const selectSuggestion = (suggestion) => {
      query.value = suggestion; // 将选中的内容填充到输入框
      suggestions.value = []; // 清空下拉列表
    };

    return {
      query,
      suggestions,
      onInput,
      selectSuggestion
    };
  }
};
</script>

<style scoped>
.search-box {
  width: 300px;
  margin: 0 auto;
  position: relative;
}

.search-input {
  width: 100%;
  padding: 10px;
  font-size: 16px;
  border: 1px solid #ccc;
  border-radius: 4px;
}

.suggestions-list {
  margin: 0;
  padding: 0;
  list-style: none;
  border: 1px solid #ccc;
  border-top: none;
  background: #fff;
  position: absolute;
  width: 100%;
  max-height: 200px;
  overflow-y: auto;
  z-index: 1000;
}

.suggestion-item {
  padding: 10px;
  cursor: pointer;
  border-bottom: 1px solid #eee;
}

.suggestion-item:hover {
  background: #f0f0f0;
}
</style>

功能说明

  1. 输入框绑定:
    • 使用 v-model​ 实现输入框的双向绑定。
  2. 自动补全逻辑:
    • 模拟一个后台数据源，通过 fetchSuggestions​ 方法过滤与用户输入匹配的内容。
  3. 下拉列表展示:
    • 使用 v-if​ 控制是否显示推荐列表。
    • 使用 v-for​ 动态渲染列表内容。
  4. 点击补全:
    • 用户点击某个推荐项时，填充到输入框并清空列表。
  5. 样式:
    • 输入框和下拉列表的样式使用 CSS 定义，保证视觉清晰整洁。

示例效果

  1. 用户输入 “苹” 后，下拉列表会显示 “苹果”。
  2. 用户输入 “蓝” 后，下拉列表会显示 “蓝莓”。
  3. 用户点击某个推荐项时，该项会自动填充到输入框中，并隐藏列表。

‍

4. JavaScript常见函数API实现

4.1 实现 map()​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Array.prototype.myMap = function(callback) {
  const result = [];
  for (let i = 0; i < this.length; i++) {
    if (this.hasOwnProperty(i)) {
      result.push(callback(this[i], i, this));
    }
  }
  return result;
};

// 示例
const arr = [1, 2, 3];
const doubled = arr.myMap(x => x * 2);
console.log(doubled); // [2, 4, 6]

4.2 实现 reduce()​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Array.prototype.myReduce = function(callback, initialValue) {
  let accumulator = initialValue !== undefined ? initialValue : this[0];
  let startIndex = initialValue !== undefined ? 0 : 1;

  for (let i = startIndex; i < this.length; i++) {
    if (this.hasOwnProperty(i)) {
      accumulator = callback(accumulator, this[i], i, this);
    }
  }
  return accumulator;
};

// 示例
const sum = arr.myReduce((acc, x) => acc + x, 0);
console.log(sum); // 6

4.3 实现 filter()​

1
2
3
4
5
6
7
8
9
10
11
12
13
Array.prototype.myFilter = function(callback) {
  const result = [];
  for (let i = 0; i < this.length; i++) {
    if (this.hasOwnProperty(i) && callback(this[i], i, this)) {
      result.push(this[i]);
    }
  }
  return result;
};

// 示例
const filtered = arr.myFilter(x => x > 1);
console.log(filtered); // [2, 3]

4.4 实现 push()​

1
2
3
4
5
6
7
8
9
10
Array.prototype.myPush = function(...args) {
  for (let i = 0; i < args.length; i++) {
    this[this.length] = args[i];
  }
  return this.length;
};

// 示例
const lengthAfterPush = arr.myPush(4, 5);
console.log(arr, lengthAfterPush); // [1, 2, 3, 4, 5], 5

4.5 实现 pop()​

1
2
3
4
5
6
7
8
9
10
Array.prototype.myPop = function() {
  if (this.length === 0) return undefined;
  const lastElement = this[this.length - 1];
  this.length -= 1;
  return lastElement;
};

// 示例
const lastElement = arr.myPop();
console.log(arr, lastElement); // [1, 2, 3, 4], 5

4.6 实现 sort()​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Array.prototype.mySort = function(compareFunction) {
  for (let i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - i - 1; j++) {
      if (compareFunction ? compareFunction(this[j], this[j + 1]) > 0 : this[j] > this[j + 1]) {
        [this[j], this[j + 1]] = [this[j + 1], this[j]];
      }
    }
  }
  return this;
};

// 示例
const sorted = [3, 1, 2].mySort((a, b) => a - b);
console.log(sorted); // [1, 2, 3]

4.7 实现 splice()​

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
Array.prototype.mySplice = function(start, deleteCount, ...items) {
  const deletedItems = [];
  start = start < 0 ? Math.max(this.length + start, 0) : start;

  for (let i = 0; i < deleteCount; i++) {
    deletedItems.push(this[start + i]);
  }

  const tail = this.slice(start + deleteCount);
  this.length = start;

  for (let i = 0; i < items.length; i++) {
    this[this.length] = items[i];
  }

  for (let i = 0; i < tail.length; i++) {
    this[this.length] = tail[i];
  }

  return deletedItems;
};

// 示例
const spliced = arr.mySplice(1, 1, 99);
console.log(arr, spliced); // [1, 99, 3, 4], [2]

4.8 实现 new()​

1
2
3
4
5
6
7
8
9
10
11
12
13
function myNew(constructor, ...args) {
  const obj = Object.create(constructor.prototype);
  const result = constructor.apply(obj, args);
  return typeof result === 'object' && result !== null ? result : obj;
}

// 示例
function Person(name) {
  this.name = name;
}

const person = myNew(Person, 'Alice');
console.log(person.name); // Alice

4.9 实现 bind()​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Function.prototype.myBind = function(context, ...args) {
  const fn = this;
  return function(...innerArgs) {
    return fn.apply(context, [...args, ...innerArgs]);
  };
};

// 示例
function greet(greeting, name) {
  return `${greeting}, ${name}`;
}

const sayHelloToAlice = greet.myBind(null, 'Hello', 'Alice');
console.log(sayHelloToAlice()); // Hello, Alice

4.10 实现 call()​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Function.prototype.myCall = function(context, ...args) {
  context = context || globalThis;
  const fnSymbol = Symbol();
  context[fnSymbol] = this;
  const result = context[fnSymbol](...args);
  delete context[fnSymbol];
  return result;
};

// 示例
function sayName(age) {
  return `${this.name} is ${age} years old`;
}

const obj = { name: 'Alice' };
console.log(sayName.myCall(obj, 25)); // Alice is 25 years old

4.11 实现 apply()​

1
2
3
4
5
6
7
8
9
10
11
Function.prototype.myApply = function(context, args) {
  context = context || globalThis;
  const fnSymbol = Symbol();
  context[fnSymbol] = this;
  const result = context[fnSymbol](...(args || []));
  delete context[fnSymbol];
  return result;
};

// 示例
console.log(sayName.myApply(obj, [30])); // Alice is 30 years old

‍5. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid; // 找到目标，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右侧
        } else {
            right = mid - 1; // 目标在左侧
        }
    }
    return -1; // 未找到目标
}

// 示例
const sortedArray = [1, 2, 5, 5, 6, 9];
const target = 5;
console.log("二分查找结果索引:", binarySearch(sortedArray, target));

返回数组中首次出现目标数字的位置，没有则返回-1 . (二分)

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
function binarySearchFirstOccurrence(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1; // 初始化为 -1 表示未找到

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            result = mid; // 找到目标值，记录当前索引
            right = mid - 1; // 继续向左查找，确保是首次出现
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标值在右侧
        } else {
            right = mid - 1; // 目标值在左侧
        }
    }

    return result;
}

// 示例用法
const arr = [1, 2, 2, 2, 3, 4, 5];
console.log(binarySearchFirstOccurrence(arr, 2)); // 输出: 1
console.log(binarySearchFirstOccurrence(arr, 3)); // 输出: 4
console.log(binarySearchFirstOccurrence(arr, 6)); // 输出: -1

‍

6. 排序算法

1. 冒泡排序 (Bubble Sort)

原理：
比较相邻的两个元素，如果它们的顺序错误就交换，重复此过程直到整个数组有序。

代码：

1
2
3
4
5
6
7
8
9
10
11
function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换
            }
        }
    }
    return arr;
}

时间复杂度：

  • 最坏情况：O(n²)
  • 最好情况：O(n) （数组已排序）
  • 平均情况：O(n²)

空间复杂度：O(1)

2. 选择排序 (Selection Sort)

原理：
在未排序部分中找到最小的元素，与当前未排序部分的第一个元素交换，逐步将数组分为已排序和未排序两部分。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换
    }
    return arr;
}

时间复杂度：

  • 最坏情况：O(n²)
  • 最好情况：O(n²)
  • 平均情况：O(n²)

空间复杂度：O(1)

3. 插入排序 (Insertion Sort)

原理：
将数组分为已排序和未排序部分，将未排序部分的第一个元素插入到已排序部分的正确位置。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

时间复杂度：

  • 最坏情况：O(n²)
  • 最好情况：O(n) （数组已排序）
  • 平均情况：O(n²)

空间复杂度：O(1)

4. 快速排序 (Quick Sort)

原理：
选择一个基准元素，将数组分为两部分，小于基准的放左边，大于基准的放右边，递归排序两部分。

代码：

1
2
3
4
5
6
7
8
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const right = arr.filter(x => x > pivot);
    const middle = arr.filter(x => x === pivot);
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // 数组长度小于等于1时，直接返回
    }
    const pivot = arr[Math.floor(arr.length / 2)]; // 选择中间元素作为基准
    const left = [];
    const right = [];
    const equal = [];

    for (let num of arr) {
        if (num < pivot) {
            left.push(num); // 小于基准的元素放在左侧
        } else if (num > pivot) {
            right.push(num); // 大于基准的元素放在右侧
        } else {
            equal.push(num); // 等于基准的元素放在中间
        }
    }
    return [...quickSort(left), ...equal, ...quickSort(right)];
}

// 示例
const array = [5, 2, 9, 1, 5, 6];
console.log("快速排序结果:", quickSort(array));

时间复杂度：

  • 最坏情况：O(n²) （已排序数组时）
  • 最好情况：O(n log n)
  • 平均情况：O(n log n)

空间复杂度：O(n)（递归调用栈）

5. 归并排序 (Merge Sort)

原理：
将数组分为两部分，递归排序两部分，然后合并两部分为一个有序数组。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

时间复杂度：

  • 最坏情况：O(n log n)
  • 最好情况：O(n log n)
  • 平均情况：O(n log n)

空间复杂度：O(n)（辅助数组）

6. 堆排序 (Heap Sort)

原理：
利用堆（最大堆或最小堆）的性质，反复取堆顶元素并调整堆，直到数组有序。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function heapSort(arr) {
    const heapify = (arr, n, i) => {
        let largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest !== i) {
            [arr[i], arr[largest]] = [arr[largest], arr[i]];
            heapify(arr, n, largest);
        }
    };

    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

时间复杂度：

  • 最坏情况：O(n log n)
  • 最好情况：O(n log n)
  • 平均情况：O(n log n)

空间复杂度：O(1)

7. TEMPLATE模版函数

1
2
3
4
5
6
7
function template(templateStr, obj) {
    return templateStr.replace(/\{(\w+)\}/g, (_, key) => obj[key] || '');
}

// 示例用法：
const result = template("{name} is {age}", { name: "tom", age: 20 });
console.log(result); // 输出: "tom is 20"

解释：

  1. 正则表达式：

    • ​\{(\w+)\}​ 是正则表达式，用于匹配模板字符串中形如 {key}​ 的占位符：
      • ​\{​ 和 \}​ 匹配花括号 {}​。
      • ​(\w+)​ 表示一个或多个由字母、数字或下划线组成的单词字符。括号表示捕获组，用于提取占位符中的键名（例如 name​ 或 age​）。
    • ​g​ 是全局匹配标志，表示替换模板字符串中的所有占位符。

  2. ​​replace​​ 方法：

    • ​replace​ 方法会查找模板字符串中的占位符，并通过提供的回调函数替换这些占位符。
    • 回调函数的参数：
      • 第一个参数 _​ 是完整匹配到的字符串，例如 {name}​。
      • 第二个参数 key​ 是捕获组的内容，例如 name​。
    • 在回调函数中，通过 obj[key]​ 获取对应的值。如果对象中不存在该键，则默认返回空字符串 ''​。

  3. 处理逻辑：

    • 替换占位符 {key}​ 为 obj​ 中对应键的值，例如 {name}​ 被替换为 tom​。
    • 如果模板字符串中的键在 obj​ 中不存在，使用空字符串代替。

示例说明：

1
template("{name} is {age}", { name: "tom", age: 20 });
  • 模板字符串为 "{name} is {age}"​。
  • 对象为 { name: "tom", age: 20 }​。
  • 正则表达式匹配：
    • ​{name}​ 被替换为 tom​。
    • ​{age}​ 被替换为 20​。
  • 最终结果为 "tom is 20"​。

8. AJAX 的基本实现

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
function ajax({ method, url, data, headers = {}, async = true, success, error }) {
    const xhr = new XMLHttpRequest(); // 创建 XMLHttpRequest 对象

    // 处理 GET 请求的 URL 参数拼接
    if (method.toUpperCase() === 'GET' && data) {
        const queryParams = new URLSearchParams(data).toString();
        url += (url.includes('?') ? '&' : '?') + queryParams;
    }

    xhr.open(method, url, async); // 初始化请求

    // 设置请求头
    for (const key in headers) {
        xhr.setRequestHeader(key, headers[key]);
    }

    // 监听请求状态变化
    xhr.onreadystatechange = () => {
        if (xhr.readyState === 4) { // 请求完成
            if (xhr.status >= 200 && xhr.status < 300) {
                success && success(xhr.responseText); // 成功回调
            } else {
                error && error(xhr.status, xhr.statusText); // 错误回调
            }
        }
    };

    // 发送请求
    if (method.toUpperCase() === 'POST' && data) {
        // 如果是 POST 请求，发送 JSON 数据
        xhr.setRequestHeader('Content-Type', 'application/json');
        xhr.send(JSON.stringify(data));
    } else {
        xhr.send(); // GET 请求无需发送请求体
    }
}

// 示例用法
ajax({
    method: 'GET',
    url: '/api/users',
    data: { id: 1, name: 'Alice' },
    success: (response) => console.log('Success:', response),
    error: (status, statusText) => console.error('Error:', status, statusText),
});

ajax({
    method: 'POST',
    url: '/api/login',
    data: { username: 'admin', password: '123456' },
    success: (response) => console.log('Logged in:', response),
    error: (status, statusText) => console.error('Error:', status, statusText),
});

9. 实现instanceof

​instanceof​​ 原理

  • instanceof​ 的主要作用是检查一个对象是否存在于某个构造函数的原型链上。

语法：

1
obj instanceof Constructor;

工作原理：

  1. 获取对象 obj​ 的原型链（__proto__​）。
  2. 依次向上查找，是否有原型等于构造函数 Constructor.prototype​。
  3. 如果找到相同的原型，返回 true​；如果到原型链顶端（null​）还未找到，返回 false​。

手写实现

可以根据原理，用循环实现一个简单的 instanceof​：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function myInstanceof(obj, constructor) {
    // 如果 obj 是 null 或 undefined，直接返回 false
    if (obj == null) return false;

    // 获取对象的原型
    let proto = Object.getPrototypeOf(obj);

    // 遍历原型链
    while (proto) {
        if (proto === constructor.prototype) {
            return true; // 找到匹配的原型
        }
        proto = Object.getPrototypeOf(proto); // 继续向上查找
    }

    return false; // 未找到匹配的原型
}

// 测试
console.log(myInstanceof([], Array)); // true
console.log(myInstanceof([], Object)); // true
console.log(myInstanceof({}, Array)); // false
console.log(myInstanceof(null, Object)); // false
console.log(myInstanceof(new Date(), Date)); // true

深入优化和特殊情况处理

1. 考虑非函数的构造函数

​instanceof​ 的右操作数必须是一个函数，如果不是函数会抛出 TypeError。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function myInstanceof(obj, constructor) {
    if (typeof constructor !== 'function') {
        throw new TypeError('Right-hand side of instanceof is not callable');
    }

    if (obj == null) return false; // 处理 null 和 undefined

    let proto = Object.getPrototypeOf(obj);
    while (proto) {
        if (proto === constructor.prototype) return true;
        proto = Object.getPrototypeOf(proto);
    }

    return false;
}

// 测试
try {
    console.log(myInstanceof([], null)); // 抛出 TypeError
} catch (e) {
    console.error(e.message); // 输出: Right-hand side of instanceof is not callable
}

2. 与原生 ​instanceof​​ 的一致性测试

1
2
3
4
console.log(myInstanceof([], Array) === ([] instanceof Array)); // true
console.log(myInstanceof([], Object) === ([] instanceof Object)); // true
console.log(myInstanceof(new Date(), Date) === (new Date() instanceof Date)); // true
console.log(myInstanceof(null, Object) === (null instanceof Object)); // true

10. 合并两个有序数组

Leetcode: 88. 合并两个有序数组

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]
解释： 需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]
解释： 需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入： nums1 = [0], m = 0, nums2 = [1], n = 1
输出： [1]
解释： 需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解答

1. 合并+排序

1
2
3
4
var merge = function(nums1, m, nums2, n) {
	nums1.splice(m, nums1.length - m, ...nums2);
	nums1.sort((a, b) => a - b);
}

2. 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var merge = function(nums1, m, nums2, n) {

    let res = [];
    let p = 0, q = 0;
    while(p < m || q < n) {
        if(p === m) {
            res.push(nums2[q++]);
        } else if (q === n) {
            res.push(nums1[p++]);
        } else if(nums1[p] <= nums2[q]) {
            res.push(nums1[p++]);
        } else {
            res.push(nums2[q++]);
        }
    }
    // nums1 = res;
    for (let i = 0; i < m + n; ++i) {
        nums1[i] = res[i];
    }
};

3. 双指针(优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
var merge = function(nums1, m, nums2, n) {
    let p = m - 1;
    let q = n - 1;
    let i = m + n - 1;

    while(q >= 0) {
        if(p >= 0 && nums1[p] > nums2[q]) {
            nums1[i--] = nums1[p--];
        } else {
            nums1[i--] = nums2[q--];
        }
    }
};

11. 移动元素

Leetcode: 27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入： nums = [3,2,2,3], val = 3
输出： 2, nums = [2,2,_,_]
解释： 你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入： nums = [0,1,2,2,3,0,4,2], val = 2
输出： 5, nums = [0,1,4,0,3,_,_,_]
解释： 你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

解答

1
2
3
4
5
6
7
8
9
10
var removeElement = function(nums, val) {  
    let len = nums.length;   
    let k = 0;  
    for(let i = 0; i < len; i++) {  
        if(nums[i] !== val) {  
            nums[k++] = nums[i];  
        }  
    }  
    return k;  
};

12. 删除有序数组中的重复项

Leetcode: 26. 删除有序数组中的重复项

题目描述

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

 
示例 1：

输入： nums = [1,1,2]
输出： 2, nums = [1,2,_]
解释： 函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入： nums = [0,0,1,1,1,2,2,3,3,4]
输出： 5, nums = [0,1,2,3,4]
解释： 函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let n = nums.length;
    // nums[0] 一定保留
    let k = 1;
    for (let i = 1; i < n; i++) {
        if(nums[i] !== nums[k - 1]){
            nums[k++] = nums[i];
        }
    }
    return k;
};

13. 多数元素

Leetcode: 169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入： nums = [3,2,3]
输出： 3

示例 2：

输入： nums = [2,2,1,1,1,2,2]
输出： 2

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

 进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)]
};

var majorityElement = function(nums) {
    let half = nums.length / 2;
    let map = new Map();
    for(let n of nums) {
        if(map.has(n)) {
            let cur = map.get(n);
            map.set(n, cur + 1);
        } else {
            map.set(n, 1);
        }
        if(map.get(n) > half) return n;
    }
}

14. 轮转数组

Leetcode: 189. 轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [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]

示例 2:

输入： nums = [-1,-100,3,99], k = 2
输出： [3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解答

  1. 裁剪+拼接
1
2
3
4
5
6
7
var rotate = function(nums, k) {  
    k = k % nums.length;  
    let f = nums.slice(0, nums.length - k);  
    let b = nums.slice(nums.length - k);  
    // nums = b.concat(f);  
    nums.splice(0, nums.length, ...b.concat(f));  
};
  1. 翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var rotate = function(nums, k) {
    k = k % nums.length; // 防止 k 大于数组长度
    nums.reverse(); // 第一步：反转整个数组
    reverse(nums, 0, k - 1); // 第二步：反转前 k 个元素
    reverse(nums, k, nums.length - 1); // 第三步：反转剩余部分
};

function reverse(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]]; // 交换两个元素
        start++;
        end--;
    }
}

15. [!] 无重复字符的最长子串

Leetcode: 3. 无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 **最长 **

子串

****的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列， 不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let occ = new Set();
    const len = s.length;
    let r = 0, maxLen = 0;
    for(let l = 0; l < len; l++){
        if(l !== 0) occ.delete(s.charAt(l - 1));
        while(r < len && !occ.has(s.charAt(r))) {
            occ.add(s.charAt(r));
            r++;
        }
        maxLen = Math.max(maxLen, r - l);
    } 
    return maxLen;
};

16. 两数之和

Leetcode: 1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入： nums = [2,7,11,15], target = 9
输出： [0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入： nums = [3,2,4], target = 6
输出： [1,2]

示例 3：

输入： nums = [3,3], target = 6
输出： [0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let hashmap = {};
    // key: number 
    // val: number index
    // for(i in nums) {
    for (let i = 0; i < nums.length; i++) {
        let n = target - nums[i];
        if(hashmap.hasOwnProperty(n)) {
            return [hashmap[n], i];
        }
        else {
            hashmap[nums[i]] = i;
        }   
    }
    return [];
};

17. [进阶] 三数之和

Leetcode: 15. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组

示例 1：

输入： nums = [-1,0,1,2,-1,-4]
输出： [[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入： nums = [0,1,1]
输出： []
解释： 唯一可能的三元组和不为 0 。

示例 3：

输入： nums = [0,0,0]
输出： [[0,0,0]]
解释： 唯一可能的三元组和为 0 。

提示：

  • $3 <= nums.length <= 3000$
  • $-10^5 <= nums[i] <= 10^5$

解答

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

18. 合并区间

Leetcode: 56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入： intervals = [[1,3],[2,6],[8,10],[15,18]]
输出： [[1,6],[8,10],[15,18]]
解释： 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入： intervals = [[1,4],[4,5]]
输出： [[1,5]]
解释： 区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

解答

  • 思路: 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if(intervals.length === 0) return [];
    intervals = intervals.sort((a, b) => {
        return a[0] - b[0];
    })
    // console.log(intervals);
    let merged = [];
    for(let i = 0; i < intervals.length; i++){
        let l = intervals[i][0];
        let r = intervals[i][1];
        if(merged.length === 0 || merged[merged.length - 1][1] < l){
            merged.push([l,r]);
        } else {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], r)
        }
    }
    return merged;
};

19. 有效的括号

Leetcode: 20. 有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

  • 输入： s = "()"
  • 输出： true

示例 2：

  • 输入： s = "()[]{}"
  • 输出： true

示例 3：

  • 输入： s = "(]"
  • 输出： false

示例 4：

  • 输入： s = "([])"
  • 输出： true

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    for(let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if(c === '(' || c === '[' || c === '{') stack.push(c);
        else if (c === ')' && stack.pop() !== '(') return false;
        else if (c === ']' && stack.pop() !== '[') return false;
        else if (c === '}' && stack.pop() !== '{') return false;
    }
    return !stack.length;
};

20. 环形链表

Leetcode: 141. 环形链表

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解答

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let f = s = head;
    while(f && f.next){
        f = f.next.next;
        s = s.next;
        if(s === f)
        {
            return true;
        }
    }
    return false;

};

21. 两数相加

Leetcode: 2. 两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解答

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let ans = new ListNode();
    let current = ans;
    let d = 0;
    while(l1 || l2){
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        d = d + n1 + n2;
        // console.log("dd "+d);
        // current.val =  (l1.val + l2.val + d) % 10;
        // d = (l1.val + l2.val + d) / 10;
        current.next = new ListNode(d % 10);
        // console.log("DD "+d%10)
        current = current.next;
        d = Math.floor(d / 10);
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    if(d){
        current.next = new ListNode(d);
    }
    return ans.next;

};

22. 合并两个有序链表

Leetcode: 21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解答

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let m = list1;
    let n = list2;
    let ans = new ListNode();
    let a = ans;
    while(m && n){
        if(m.val < n.val){
            a.next = m;
            m = m.next;
        }
        else{
            a.next = n;
            n = n.next;
        }
        a = a.next;
    }
    if(m){
        a.next = m;
    } else if(n){
        a.next = n;
    }
    return ans.next;
};

23. 反转链表

Leetcode:

题目描述

  1. 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
  2. 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
  3. 给你链表的头节点 head ，每 k **个节点一组进行翻转，请你返回修改后的链表。
    • k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k **的整数倍，那么请将最后剩余的节点保持原有顺序。
    • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解答

  1. easy
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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head === null){
        return null;
    }
    let cur = head;
    let pre = null;
    while(cur !== null){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};
  1. medium
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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    // 1 -> 2 -> [3 -> 4 -> 5] -> 6 -> 7
    // 1 -> 2 -> [5 -> 4 -> 3] -> 6 -> 7
    // start: 2
    // end: 3
    // last step: pre: 5 & cur: 6
    let p = dummyHead = new ListNode();
    p.next = head;
    let pre, cur, start, end;
    for(let i = 0; i < left - 1; i++) {
        p = p.next;
    }
    start = p;
    end = pre = p.next;
    cur = pre.next;
    for(let i = 0; i < right - left; i++) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    start.next = pre;
    end.next = cur;
    return dummyHead.next;
};
  1. hard
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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let pre = null, cur = head;
    let p = head;
    for(let i = 0; i < k; i ++){
        if(p == null) return head;
        p = p.next;
    }
    for(let i = 0; i < k; i ++){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    head.next = reverseKGroup(cur, k);
    return pre;
};

24. 二叉树的层序遍历相关

二叉树的最大深度

Leetcode: 104. 二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数

示例:

image.png

输入： root = [3,9,20,null,null,15,7]
输出： 3

解答

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(root == null) {
        return 0;
    }
    /* 递归
    return Math.max(maxDepth(root.left)+1, maxDepth(root.right)+1);
    */
    let queue = [root];
    let lev = 0;
    while(queue.length) {
        let size = queue.length;
        while(size --) {
            let front = queue.shift();
            if(front.left) queue.push(front.left);
            if(front.right) queue.push(front.right);
        }
        lev ++;
    }
    return lev;
};

二叉树的层序遍历

Leetcode: 102. 二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例:

image.png

输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]

解答

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return [];
    let queue = [root];
    let res = [];
    let level = 0;
    while (queue.length) {
        res.push([]);
        let size = queue.length;
        while (size --) {
            let cur = queue.shift(); // 当前节点出队
            res[level].push(cur.val); 
            if (cur.left) queue.push(cur.left); // 左儿子入队
            if (cur.right) queue.push(cur.right); // 右儿子入队
        }
        level ++;
    }
    return res;
};

二叉树的右视图

Leetcode: 199. 二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

  • 输入： root = [1,2,3,null,5,null,4]
  • 输出： [1,3,4]

解释：

示例 2：

  • 输入： root = [1,2,3,4,null,null,null,5]
  • 输出： [1,3,4,5]

解释：

示例 3：

  • 输入： root = [1,null,3]
  • 输出： [1,3]

示例 4：

  • 输入： root = []
  • 输出： []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

解答

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
    if (!root) return [];
    let queue = [root];
    let res = [];
    while (queue.length) {
        res.push(queue[0].val); // 一层只取队首(即最右侧节点)
        let size = queue.length;
        while (size --) {
            let cur = queue.shift(); // 当前节点出队
            if (cur.right) queue.push(cur.right); // 右先儿子入队
            if (cur.left) queue.push(cur.left); // 左儿子入队
        }
    }
    return res;
};

25. [回溯与全排列] 无重复字符串的排列组合

Leetcode: 面试题 08.07. 无重复字符串的排列组合

题目描述

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例 1：

 输入：S = "qwe"
输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例 2：

 输入：S = "ab"
输出：["ab", "ba"]

提示：

  1. 字符都是英文字母。
  2. 字符串长度在[1, 9]之间。

解答

  • 思路:

    image.png

    图片取自RyanSKJ题解

  • 代码实现:

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
/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function(S) {
    // string to array
    let temp = S.split('');
    let len = temp.length;
    let res = [];
    dfs(0);
    return res;

    // 定义DFS递归函数
    function dfs(k) {
        // end condition
        if(k === len) {
            res.push(temp.join(''));
            return;
        }
        for(let i = k; i < len; i++) {
            [temp[i], temp[k]] = [temp[k], temp[i]];
            dfs(k + 1);
            [temp[i], temp[k]] = [temp[k], temp[i]];
        }
    }
};

全排列实现(LCR 083. 全排列)

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1：

输入： nums = [1,2,3]
输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入： nums = [0,1]
输出： [[0,1],[1,0]]

示例 3：

输入： nums = [1]
输出： [[1]]

注意:
在 res.push([...nums]) 中使用扩展运算符生成 nums 的副本，确保结果中存储的每个排列是独立的，不会受到后续递归的修改影响

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    // this.nums = nums;
    let len = nums.length;
    let res = [];
    dfs(0);
    return res;

    // 定义DFS递归函数
    function dfs(k) {
        // end condition
        if(k === len) {
            res.push([...nums]);
            return;
        }
        for(let i = k; i < len; i++) {
            [nums[i], nums[k]] = [nums[k], nums[i]];
            dfs(k + 1);
            [nums[i], nums[k]] = [nums[k], nums[i]];
        }
    }
};

To Be Continue…

Read More
▲