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

阅读量: 次  文章字数: 10.2k字  阅读时长: 49分钟

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…

文章作者： Alan Zeng

最后更新：

原始链接： https://alanzeng.com/blogs/65449/

版权说明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 4.0许可协议 。获得许可后，要求转载时注明文章出处和网站链接，谢谢！

Comments

2025-01-03
  1. codes
    1. 1. 数组，用 reduce​ 方法实现 map​ 方法
    2. 2. 实现函数repeat​
    3. 3. Vue 组件：实现搜索框自动补全功能
    4. 4. JavaScript常见函数API实现
      1. 4.1 实现 map()​
      2. 4.2 实现 reduce()​
      3. 4.3 实现 filter()​
      4. 4.4 实现 push()​
      5. 4.5 实现 pop()​
      6. 4.6 实现 sort()​
      7. 4.7 实现 splice()​
      8. 4.8 实现 new()​
      9. 4.9 实现 bind()​
      10. 4.10 实现 call()​
      11. 4.11 实现 apply()​
    5. ‍5. 二分查找
    6. 6. 排序算法
      1. 1. 冒泡排序 (Bubble Sort)
      2. 2. 选择排序 (Selection Sort)
      3. 3. 插入排序 (Insertion Sort)
      4. 4. 快速排序 (Quick Sort)
      5. 5. 归并排序 (Merge Sort)
      6. 6. 堆排序 (Heap Sort)
    7. 7. TEMPLATE模版函数
    8. 8. AJAX 的基本实现
    9. 9. 实现instanceof
      1. 手写实现
      2. 深入优化和特殊情况处理
        1. 1. 考虑非函数的构造函数
        2. 2. 与原生 ​instanceof​​ 的一致性测试
    10. 10. 合并两个有序数组
      1. 题目描述
      2. 解答
    11. 11. 移动元素
      1. 题目描述
      2. 解答
    12. 12. 删除有序数组中的重复项
      1. 题目描述
      2. 解答
    13. 13. 多数元素
      1. 题目描述
      2. 解答
    14. 14. 轮转数组
      1. 题目描述
      2. 解答
    15. 15. [!] 无重复字符的最长子串
      1. 题目描述
      2. 解答
    16. 16. 两数之和
      1. 题目描述
      2. 解答
    17. 17. [进阶] 三数之和
      1. 题目描述
      2. 解答
    18. 18. 合并区间
      1. 题目描述
      2. 解答
    19. 19. 有效的括号
      1. 题目描述
      2. 解答
    20. 20. 环形链表
      1. 题目描述
      2. 解答
    21. 21. 两数相加
      1. 题目描述
      2. 解答
    22. 22. 合并两个有序链表
      1. 题目描述
      2. 解答
    23. 23. 反转链表
      1. 题目描述
      2. 解答
    24. 24. 二叉树的层序遍历相关
      1. 二叉树的最大深度
        1. 题目描述
        2. 解答
      2. 二叉树的层序遍历
        1. 题目描述
        2. 解答
      3. 二叉树的右视图
        1. 题目描述
        2. 解答
    25. 25. [回溯与全排列] 无重复字符串的排列组合
      1. 题目描述
      2. 解答
      3. 全排列实现(LCR 083. 全排列)
▲