Xinrui's personal website that shares my work and thoughts

# Blog Grid Light

- Home
- Blog Grid Light

## 430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional **child pointer**. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a **multilevel data structure** as shown in the example below.

Given the `head`

of the first level of the list, **flatten** the list so that all the nodes appear in a single-level, doubly linked list. Let `curr`

be a node with a child list. The nodes in the child list should appear **after** `curr`

and **before** `curr.next`

in the flattened list.

Return *the *`head`

* of the flattened list. The nodes in the list must have all of their child pointers set to *

`null`

.

**Example 1:**

Input:head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]Output:[1,2,3,7,8,11,12,9,10,4,5,6]Explanation:The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:

**Example 2:**

Input:head = [1,2,null,3]Output:[1,3,2]Explanation:The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:

**Example 3:**

Input:head = []Output:[]Explanation:There could be empty list in the input.

**Constraints:**

- The number of Nodes will not exceed
`1000`

. `1 <= Node.val <= 10`

^{5}

**How the multilevel linked list is represented in test cases:**

We use the multilevel linked list from **Example 1** above:

1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

### Problem Explanation

The goal is to flatten a multilevel doubly linked list. Each node has `next`

, `prev`

, and `child`

pointers. The `child`

pointer points to another doubly linked list, which might have its own `child`

pointers. We need to flatten this structure into a single-level doubly linked list.

### Approach

- Traverse the linked list using a pointer
`current`

. - Whenever we encounter a node with a
`child`

, we need to:- Temporarily store the
`next`

node. - Flatten the
`child`

list recursively. - Insert the flattened
`child`

list between the current node and the next node. - Update all the necessary pointers (
`next`

and`prev`

). - Ensure the
`child`

pointer is set to`null`

.

- Temporarily store the
- Continue this process until the entire list is flattened.

Code with Detailed Comments

```
var flatten = function(head) {
if (head === null) return null;
// Start traversing from the head node
let current = head;
// Traverse the entire linked list
while (current !== null) {
// If the current node has a child, we need to flatten it
if (current.child !== null) {
// Store the next node temporarily
let next = current.next;
// Recursively flatten the child list
let child = flatten(current.child);
// Insert the flattened child list
current.next = child;
child.prev = current;
// Find the tail of the flattened child list
while (child.next !== null) {
child = child.next;
}
// Connect the tail of the flattened child list to the next node
if (next !== null) {
next.prev = child;
}
child.next = next;
// Remove the child pointer
current.child = null;
}
// Move to the next node
current = current.next;
}
return head;
};
```

### Step-by-Step Explanation

**Initialization**:- Check if
`head`

is`null`

. If it is, return`null`

immediately. - Initialize
`current`

to start from the`head`

node.

- Check if
**Traversal**:- Use a
`while`

loop to traverse the entire linked list.

- Use a
**Handling the**:`child`

- If
`current`

has a`child`

, perform the following steps:- Temporarily store the
`next`

node (`current.next`

). - Recursively flatten the
`child`

list by calling`flatten(current.child)`

. - Insert the flattened
`child`

list between the`current`

node and the`next`

node:- Set
`current.next`

to the head of the flattened`child`

list. - Update the
`prev`

pointer of the flattened`child`

list head to point to`current`

.

- Set
- Find the tail of the flattened
`child`

list by iterating through it until`child.next`

is`null`

. - Connect the tail of the flattened
`child`

list to the`next`

node:- Set
`next.prev`

to the tail of the flattened`child`

list (if`next`

is not`null`

). - Set the
`next`

pointer of the tail of the flattened`child`

list to`next`

.

- Set
- Set
`current.child`

to`null`

as it is now flattened and integrated into the main list.

- Temporarily store the

- If
**Continue Traversal**:- Move
`current`

to the next node (`current.next`

) and repeat the process until the end of the list is reached.

- Move

### Complexity Analysis

**Time Complexity**: O(n), where n is the total number of nodes in the list. Each node is processed once, and the child lists are flattened and inserted in linear time.**Space Complexity**: O(d), where d is the maximum depth of the multilevel list. This space is used by the recursion stack due to the depth-first search approach.

This approach ensures that all pointers are correctly updated, maintaining the doubly linked structure while flattening the multilevel list into a single-level list.

## TypeScript Data Structure: Implementing a Doubly Linked List

## 用Typescript实现一个双向链表

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: `val`

and `next`

. `val`

is the value of the current node, and `next`

is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute `prev`

to indicate the previous node in the linked list. Assume all nodes in the linked list are **0-indexed**.

Implement the `MyLinkedList`

class:

`MyLinkedList()`

Initializes the`MyLinkedList`

object.`int get(int index)`

Get the value of the`index`

node in the linked list. If the index is invalid, return^{th}`-1`

.`void addAtHead(int val)`

Add a node of value`val`

before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.`void addAtTail(int val)`

Append a node of value`val`

as the last element of the linked list.`void addAtIndex(int index, int val)`

Add a node of value`val`

before the`index`

node in the linked list. If^{th}`index`

equals the length of the linked list, the node will be appended to the end of the linked list. If`index`

is greater than the length, the node**will not be inserted**.`void deleteAtIndex(int index)`

Delete the`index`

node in the linked list, if the index is valid.^{th}

**Example 1:**

Input["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]]Output[null, null, null, null, 2, null, 3]ExplanationMyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3

**Constraints:**

`0 <= index, val <= 1000`

- Please do not use the built-in LinkedList library.
- At most
`2000`

calls will be made to`get`

,`addAtHead`

,`addAtTail`

,`addAtIndex`

and`deleteAtIndex`

.

### Analysis of Doubly Linked List Implementation

In computer science, linked lists are a fundamental data structure, and a doubly linked list is a variation that allows traversal in both directions—forward and backward. Each node in a doubly linked list contains a reference to both the next and the previous node, providing flexibility and efficiency for operations that require frequent access to both ends of the list.

#### Requirements Analysis

In this task, the goal is to implement a doubly linked list with basic functionalities such as:

- Retrieving the value of the node at a specific index.
- Inserting a node at the beginning of the list.
- Inserting a node at the end of the list.
- Inserting a new node at a specified position in the list.
- Deleting a node at a specified index.

#### Thought Process and Algorithm Implementation

**1. Initialization**

We start by defining a `Node`

class, which will have three properties: `val`

(the value stored in the node), `next`

(a reference to the next node), and `prev`

(a reference to the previous node). We also define a `MyLinkedList`

class to manage these nodes, including properties for the `head`

(the first node), `tail`

(the last node), and `size`

(the length of the list).

```
class Node {
val: number;
next: Node | null;
prev: Node | null;
constructor(val: number) {
this.val = val;
this.next = null;
this.prev = null;
}
}
```

**2. Retrieving a Node Value**

The `get`

method straightforwardly traverses the list from the `head`

to the desired `index`

. It’s important to handle invalid indices by returning -1 if the index is out of bounds.

```
get(index: number): number {
if (index < 0 || index >= this.size) return -1;
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.val;
}
```

**3. Adding a Node at the Head**

When adding at the head, we create a new node and adjust the `head`

pointer to point to this new node. If the list is not empty, we also need to update the previous head’s `prev`

to reference the new node. If the list is empty, the new node also becomes the `tail`

.

```
addAtHead(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
```

**4. Adding a Node at the Tail**

Adding at the tail involves creating a new node and adjusting the `tail`

pointer. The new node’s `prev`

points to the current `tail`

, and if the list is empty, the new node will serve as both the `head`

and `tail`

.

```
addAtTail(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size++;
}
```

**5. Inserting a Node at a Specified Position**

This operation is more complex, as it involves handling several cases:

- Inserting at index 0, which is equivalent to
`addAtHead`

. - Inserting at index
`size`

, equivalent to`addAtTail`

. - For other positions, find the node before the desired position and insert the new node accordingly.

```
addAtIndex(index: number, val: number): void {
if (index < 0 || index > this.size) return;
if (index == 0) {
this.addAtHead(val);
} else if (index == this.size) {
this.addAtTail(val);
} else {
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
const newNode = new Node(val);
newNode.next = prev.next;
newNode.prev = prev;
if (prev.next) {
prev.next.prev = newNode;
}
prev.next = newNode;
this.size++;
}
}
```

**6. Deleting a Node at a Specified Position**

Deletion requires careful pointer adjustments. Special attention is needed when deleting the head or tail node to update the `head`

and `tail`

pointers accordingly.

```
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return;
if (index === 0) {
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null; // list became empty
}
} else {
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
const toDelete = prev.next;
prev.next = toDelete.next;
if (prev.next) {
prev.next.prev = prev;
} else {
this.tail = prev; // deleting the last node
}
}
this.size--;
}
```

### Conclusion

This analysis not only illustrates how to implement each fundamental operation of a doubly linked list but also discusses handling edge cases and special conditions. Understanding these operations is key to mastering the linked list data structure. Hopefully, this breakdown will help you gain a deeper understanding of the implementation and application of doubly linked lists.

### 双向链表的实现分析

在计算机科学中，链表是一种常用的数据结构，双向链表是链表的一种变形，其中每个节点除了有指向下一个节点的指针`next`

外，还包含一个指向上一个节点的指针`prev`

。这种结构提供了向前和向后两种遍历方式，使得某些操作更为高效。

#### 需求分析

在这个题目中，需要实现一个双向链表，包括以下基本操作：

- 获取链表中第
`index`

个节点的值。 - 在链表头部插入一个节点。
- 在链表尾部插入一个节点。
- 在链表中的第
`index`

个位置插入一个新节点。 - 删除链表中的第
`index`

个节点。

#### 思维过程与算法实现

**1. 初始化**

首先，我们需要一个`Node`

类来定义节点，包括`val`

（节点存储的值），`next`

（指向下一个节点的引用）和`prev`

（指向上一个节点的引用）。其次，定义`MyLinkedList`

类来管理这些节点，包括`head`

（头节点），`tail`

（尾节点），以及`size`

（链表长度）。

```
class Node {
val: number;
next: Node | null;
prev: Node | null;
constructor(val: number) {
this.val = val;
this.next = null;
this.prev = null;
}
}
```

**2. 获取节点值**

获取节点值的操作相对直接，从`head`

开始，遍历链表直到到达指定的`index`

位置。需要注意的是，如果`index`

无效（即超出链表范围），则返回-1。

```
get(index: number): number {
if (index < 0 || index >= this.size) return -1;
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.val;
}
```

**3. 添加节点到头部**

在头部添加节点时，需要创建一个新节点，并将其`next`

指针指向当前的`head`

。同时，如果链表本身不为空，更新原有头节点的`prev`

指向新节点。如果链表为空，则同时更新`tail`

。

```
addAtHead(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
```

**4. 添加节点到尾部**

尾部添加类似于头部添加，但是新节点的`prev`

将指向当前的`tail`

，并更新`tail`

的`next`

。

```
addAtTail(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size++;
}
```

**5. 在指定位置添加节点**

这是一个稍微复杂的操作，需要分多种情况处理：

- 如果
`index`

等于0，相当于`addAtHead`

。 - 如果
`index`

等于`size`

，相当于`addAtTail`

。 - 其他情况，需要找到第
`index-1`

个节点，然后在其后插入新节点。

```
addAtIndex(index: number, val: number): void {
if (index < 0 || index > this.size) return;
if (index === 0) {
this.addAtHead(val);
} else if (index === this.size) {
this.addAtTail(val);
} else {
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
const newNode = new Node(val);
newNode.next = prev.next;
newNode.prev = prev;
prev.next.prev = newNode;
prev.next = newNode;
this.size++;
}
}
```

**6. 删除指定位置的节点**

删除操作需要更新`prev`

和`next`

指针。特别要注意当删除的是头节点或尾节点时，还需要更新`head`

或`tail`

。

```
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return;
if (index === 0) {
this.head = this.head.next;
if (this.size === 1) {
this.tail = null;
} else {
this.head.prev = null;
}
} else {
let prev = this.head;
for (let i = 0; i < index - 1; i++) {
prev = prev.next;
}
const toDelete = prev.next;
prev.next = toDelete.next;
if (prev.next) {
prev.next.prev = prev;
} else {
this.tail = prev;
}
}
this.size--;
}
```

### 总结

通过逐步解析每个操作，我们不仅展示了如何实现双向链表的各个基本功能，还深入讨论了边界情况和特殊情况的处理。理解这些基本操作是掌握链表数据结构的关键。希望这篇分析可以帮助你更好地理解双向链表的实现和应用。

Full Code, this code can also be used at Leetcode 707. Design Linked List

```
class Node {
val: number;
next: Node;
prev: Node;
constructor(val: number) {
this.val = val;
this.prev = null;
this.next = null;
}
}
class MyLinkedList {
size: number;
head: Node;
tail: Node;
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
get(index: number): number {
if (index < 0 || index >= this.size ) return -1;
let curr = this.head;
while (index > 0) {
curr = curr.next;
index--;
}
return curr.val;
}
addAtHead(val: number): void {
let newHead = new Node(val);
if (this.size === 0) {
this.head = newHead;
this.tail = newHead;
} else {
this.head.prev = newHead;
newHead.next = this.head;
this.head = newHead;
}
this.size++;
}
addAtTail(val: number): void {
let newTail = new Node(val);
if (this.size === 0) {
this.head = newTail;
this.tail = newTail;
} else {
this.tail.next = newTail;
newTail.prev = this.tail;
this.tail = newTail;
}
this.size++;
}
addAtIndex(index: number, val: number): void {
if (index < 0 || index > this.size) return;
if (index === 0) {
this.addAtHead(val);
} else if (index === this.size) {
this.addAtTail(val);
} else {
let newNode = new Node(val);
let prev = this.head;
while (index - 1 > 0) {
prev = prev.next;
index--;
}
newNode.prev = prev;
newNode.next = prev.next;
prev.next.prev = newNode;
prev.next = newNode;
this.size++;
}
}
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return;
if (index === 0) {
this.head = this.head.next;
if (this.size === 1) {
this.tail = null;
}
this.size--;
} else {
let prev = this.head;
while (index - 1 > 0) {
prev = prev.next;
index--;
}
prev.next = prev.next.next;
if (prev.next) { // tail 不变
prev.next.prev = prev;
} else {
this.tail = prev;
}
this.size--;
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/
```

## Typescript Data Structures: Linked List

In the vast expanse of data structures available to developers, the LinkedList holds a unique place. Known for its efficiency in insertion and deletion operations, it’s a staple in algorithm design and application development. This post explores how to implement a LinkedList in TypeScript, bringing together the efficiency of this data structure with the strong typing and object-oriented features of TypeScript.

#### Understanding LinkedLists

Before diving into the code, let’s grasp the basics of a LinkedList. At its core, a LinkedList is a collection of nodes, where each node contains data and a reference (or a pointer) to the next node in the sequence. This structure allows for efficient additions and deletions as it avoids the necessity of reindexing elements, a common performance bottleneck in array manipulations.

#### Implementing Nodes in TypeScript

The foundation of our LinkedList is the node. Each node will store a value and a pointer to the next node. Here’s how we define it in TypeScript:

```
class Node {
val: number;
next: Node | null;
constructor(val: number) {
this.val = val; // The value stored in the node
this.next = null; // Pointer to the next node, initially null
}
}
```

This `Node`

class is straightforward: it initializes with a value and sets the pointer to the next node as null.

#### The MyLinkedList Class

With our nodes defined, we next construct the LinkedList class, `MyLinkedList`

. This class will manage our nodes and provide methods to interact with the list.

##### Constructor and Properties

```
class MyLinkedList {
head: Node | null;
tail: Node | null;
size: number;
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
```

Our LinkedList starts empty, signified by a `null`

head and tail, with a size of 0.

##### Adding Elements

We provide three methods to add elements to our list: at the head, at the tail, and at a specific index.

**addAtHead(val: number):**Inserts a new node with the provided value at the beginning of the list.**addAtTail(val: number):**Appends a new node with the provided value at the end of the list.**addAtIndex(index: number, val: number):**Inserts a new node at the specified index.

Each method updates the `head`

, `tail`

, and `size`

properties accordingly to maintain the integrity of the list.

##### Retrieving and Deleting Elements

**get(index: number):**Returns the value of the node at the specified index.**deleteAtIndex(index: number):**Removes the node at the specified index.

These methods ensure our LinkedList is dynamic, allowing retrieval and modification post-initialization.

#### Conclusion

Implementing a LinkedList in TypeScript is a rewarding exercise that deepens our understanding of both TypeScript and fundamental data structures. This guide has walked you through creating a flexible, type-safe LinkedList, suitable for various applications requiring efficient insertions and deletions. Whether you’re building a complex application or brushing up on data structures, the combination of TypeScript and LinkedLists is a powerful tool in your development arsenal.

#### Next Steps

Now that you’ve implemented a basic LinkedList, consider extending its functionality. Try adding methods to reverse the list, detect cycles, or merge two sorted lists. Each addition will not only improve your understanding of LinkedLists but also enhance your problem-solving skills in TypeScript.

#### Full Code

```
class Node {
val: number;
next: Node | null;
constructor(val: number) {
this.val = val; // The value stored in the node
this.next = null; // Pointer to the next node, initially null
}
}
class MyLinkedList {
head: Node | null;
tail: Node | null; // Pointer to the last node
size: number; // The number of nodes in the list
constructor() {
this.head = null; // Initialize the head to null for an empty list
this.tail = null; // Likewise for the tail
this.size = 0; // Start with a list size of 0
}
// Adds a node at the front of the list
addAtHead(val: number): void {
const newNode = new Node(val);
newNode.next = this.head;
this.head = newNode;
if (this.size === 0) {
this.tail = newNode; // If the list was empty, this new node is also the tail
}
this.size++;
}
// Adds a node at the end of the list
addAtTail(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
// Adds a node at the specified index
addAtIndex(index: number, val: number): void {
if (index < 0 || index > this.size) return; // Check for valid index
if (index === 0) {
this.addAtHead(val);
return;
}
if (index === this.size) {
this.addAtTail(val);
return;
}
const newNode = new Node(val);
let current = this.head;
for (let i = 0; i < index - 1; i++) { // Iterate to the node before the desired index
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.size++;
}
// Gets the value of the node at the specified index
get(index: number): number {
if (index < 0 || index >= this.size) return -1; // Check for valid index
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.val;
}
// Deletes the node at the specified index
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return; // Check for valid index
if (index === 0) {
this.head = this.head.next;
if (index === this.size - 1) { // If there was only one node, update tail to null
this.tail = null;
}
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
if (index === this.size - 1) { // If deleting the last node, update tail
this.tail = current;
}
}
this.size--;
}
}
```

Also this one can let you pass the Leetcode question: 707. Design Linked List

这个博客讲的就是TypeScript的单链表的实现方法啦，可以看看 抄抄，这个能让你直接通过Leetcode的第707题

## 448. Find All Numbers Disappeared in an Array

Given an array `nums`

of `n`

integers where `nums[i]`

is in the range `[1, n]`

, return *an array of all the integers in the range* `[1, n]`

*that do not appear in* `nums`

.

**Example 1:**

Input:nums = [4,3,2,7,8,2,3,1]Output:[5,6]

**Example 2:**

Input:nums = [1,1]Output:[2]

**Constraints:**

`n == nums.length`

`1 <= n <= 10`

^{5}`1 <= nums[i] <= n`

**Follow up:** Could you do it without extra space and in `O(n)`

runtime? You may assume the returned list does not count as extra space.

**Problem Analysis:** The task is to find all the numbers missing from 1 to n in a given array, which might contain duplicate numbers and should be solved without using extra space (except for the output).

**Solution Approach:** We can leverage the array itself by marking the presence of numbers. Specifically, we traverse the array and turn the number at the index corresponding to each encountered number into negative as a mark. Since the numbers in the array are all supposed to be between 1 and n, we can directly use the number value as the array index.

**Time and Space Complexity Analysis:** The time complexity is O(n), as we only need to traverse the array twice. The space complexity is O(1), as no extra space is used apart from the output.

**Conclusion:** This method effectively utilizes the structure of the array itself to mark the presence of numbers, thereby identifying the missing ones, while avoiding the use of extra space.

**题目分析：** 这个问题要求我们找出在1到n之间但没有出现在给定数组中的所有数字。数组中可能有重复数字，且没有额外空间使用（除了输出结果之外）。

**解题思路：** 我们可以利用数组自身，通过标记已存在的数字来找出缺失的数字。具体来说，我们可以遍历数组，并将出现的数字对应位置上的数值变为负数，作为标记。因为数组中的数字都应该在1到n之间，所以可以直接用数字值作为数组索引。

**代码实现：**

```
function findDisappearedNumbers(nums: number[]): number[] {
let res = [];
for (let num of nums) {
let index = Math.abs(num) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
res.push(i + 1);
}
}
return res;
}
```

**时间和空间复杂度分析：** 时间复杂度为O(n)，因为我们只需要遍历数组两次。空间复杂度为O(1)，因为除了输出结果外，我们没有使用额外的空间。

**测试用例：**

`console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // 输出 [5,6]`

**总结：** 这个方法有效地利用了数组本身的结构来标记存在的数字，从而找出缺失的数字，同时避免了额外的空间使用。

#### 414. Third Maximum Number

## 414. Third Maximum Number

Given an integer array `nums`

, return *the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number*.

**Example 1:**

Input:nums = [3,2,1]Output:1Explanation:The first distinct maximum is 3. The second distinct maximum is 2. The third distinct maximum is 1.

**Example 2:**

Input:nums = [1,2]Output:2Explanation:The first distinct maximum is 2. The second distinct maximum is 1. The third distinct maximum does not exist, so the maximum (2) is returned instead.

**Example 3:**

Input:nums = [2,2,3,1]Output:1Explanation:The first distinct maximum is 3. The second distinct maximum is 2 (both 2's are counted together since they have the same value). The third distinct maximum is 1.

**Constraints:**

`1 <= nums.length <= 10`

^{4}`-2`

^{31}<= nums[i] <= 2^{31}- 1

**Follow up:**Can you find an

`O(n)`

solution?## Approach 1:

## Three pointers

**Problem Analysis:** LeetCode problem 414 “Third Maximum Number” asks us to find the third largest number in an array. If it doesn’t exist, return the largest number. While this could be solved by sorting, we aim for a more efficient approach.

**Solution Approach:**

- Use three variables to track the first, second, and third largest numbers.
- Iterate through the array, updating these variables as needed.
- Pay attention to duplicates and special cases.

**Time and Space Complexity Analysis:**

- Time Complexity: O(n), as we only need to pass through the array once.
- Space Complexity: O(1), as we use a fixed amount of extra space.

**题目分析：** LeetCode问题414 “Third Maximum Number” 要求我们在数组中找到第三大的数。如果不存在，返回最大的数。这个问题可以通过排序来解决，但是我们希望找到一种更有效的方法。

**解题思路：**

- 使用三个变量来追踪第一大、第二大和第三大的数。
- 遍历数组，更新这三个变量。
- 注意去重和特殊情况处理。

**时间和空间复杂度分析：**

- 时间复杂度：O(n)，我们只需要遍历一次数组。
- 空间复杂度：O(1)，我们只用到有限的额外空间。

```
function thirdMax(nums: number[]): number {
// Initialize three variables to track the largest, second largest, and third largest numbers
let first = Number.MIN_SAFE_INTEGER, second = Number.MIN_SAFE_INTEGER, third = Number.MIN_SAFE_INTEGER;
for (let num of nums) {
// Skip duplicate numbers
if (num === first || num === second || num === third) continue;
if (num > first) { // Update the first, second, and third largest numbers
[third, second, first] = [second, first, num];
} else if (num > second) {
[third, second] = [second, num];
} else if (num > third) {
third = num;
}
}
return third !== Number.MIN_SAFE_INTEGER ? third : first;
}
```

#### 487. Max Consecutive Ones II

## 487. Max Consecutive Ones II

Given a binary array `nums`

, return *the maximum number of consecutive *`1`

*‘s in the array if you can flip at most one* `0`

.

**Example 1:**

Input:nums = [1,0,1,1,0]Output:4Explanation:- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.

**Example 2:**

Input:nums = [1,0,1,1,0,1]Output:4Explanation:- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones. The max number of consecutive ones is 4.

**Constraints:**

`1 <= nums.length <= 10`

^{5}`nums[i]`

is either`0`

or`1`

.

**Follow up:** What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?

**题目分析：** 这道题目要求我们找出在最多可以翻转一个0的情况下，最长的连续1的长度。这是一个典型的滑动窗口问题，也涉及到了数组的遍历。

**解题思路：**

- 初始化两个指针left和right，用于标记窗口的左右边界，以及一个变量zeros来记录窗口中0的数量。
- 移动right指针扩展窗口，如果遇到0，则zeros增加。
- 当窗口内的0的数量超过1时，移动left指针以缩小窗口，直到窗口内再次只有一个0或没有0。
- 在每一步中，如果窗口内的0的数量不超过1，更新最大长度。

**时间复杂度：**O(n)，其中n是数组的长度，因为每个元素只被访问一次。

**空间复杂度：**O(1)，只使用了固定的额外空间。

**Problem Analysis:** This problem asks us to find the maximum length of consecutive 1s that can be achieved by flipping at most one 0. This is a classic sliding window problem, also involving array traversal.

**Solution Approach:**

- Initialize two pointers, left and right, to mark the boundaries of the window, and a variable zeros to count the number of zeros within the window.
- Move the right pointer to expand the window, increase zeros if encountering a 0.
- When the number of zeros within the window exceeds one, move the left pointer to reduce the window until there is only one or no zero within it again.
- At each step, if the number of zeros within the window does not exceed one, update the maximum length.

**Time Complexity:** O(n), where n is the length of the array, as each element is visited only once.

**Space Complexity:** O(1), as only a fixed amount of extra space is used.

```
function findMaxConsecutiveOnes(nums: number[]): number {
if (nums.length === 1) return 1;
let left = 0, right = 0, zeros = 0;
let max = 0;
for (; right < nums.length; right++) {
if (nums[right] === 0) {
zeros++;
}
if (zeros <= 1) { // valid, continue
max = Math.max(max, right - left + 1);
} else {
// Move left until it escapse a 0
while (nums[left] !== 0) {
left++;
}
left++;
zeros--;
}
}
return max;
};
```

#### 905. Sort Array By Parity

## 905. Sort Array By Parity

Given an integer array `nums`

, move all the even integers at the beginning of the array followed by all the odd integers.

Return * any array that satisfies this condition*.

**Example 1:**

Input:nums = [3,1,2,4]Output:[2,4,3,1]Explanation:The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

**Example 2:**

Input:nums = [0]Output:[0]

**Constraints:**

- 1 <= nums.length <= 5000
- 0 <= nums[i] <= 5000

**题目分析：** 题目要求我们按奇偶排序数组，所有的偶数应该在所有的奇数之前。这是一个很常见的数组操作问题，可以通过双指针的方法来解决。

**解题思路：**

- 设置两个指针，
`left`

和`right`

，其中`left`

从数组的开始处向后移动，`right`

从数组的末尾向前移动。 - 当
`left`

指向偶数，`left++`

，向右移动；当`right`

指向奇数，`right--`

，向左移动。 - 如果
`left`

指向奇数且`right`

指向偶数，则交换这两个元素。 - 重复上述过程，直到
`left >= right`

。

### 时间和空间复杂度分析：

**时间复杂度：**这个算法的时间复杂度是O(n)，其中n是数组的长度。这是因为我们使用两个指针从数组的两端向中间扫描，每个元素最多被访问一次。

**空间复杂度：**这个算法的空间复杂度是O(1)，因为我们只是在原数组上进行交换操作，没有使用额外的数组或数据结构。

### 为什么双指针方法在此问题上有效：

双指针方法之所以有效，是因为它利用了问题的特性：我们需要将偶数和奇数分开。通过设置两个指针，一个从开始处向后扫描寻找奇数，另一个从末尾向前扫描寻找偶数，我们可以有效地在一次遍历中将偶数和奇数分到数组的两边。

这种方法之所以高效，是因为它直接在原数组上进行操作，减少了额外的内存分配和移动，同时确保了每个元素都只被查看和移动一次。因此，它是对数组进行分类的一种快速而内存高效的方法。

**Problem Analysis:** The task is to sort an array by parity, with all even elements preceding all odd ones. This is a common array manipulation issue that can be addressed using the two-pointers technique.

**Solution Idea:**

- Set two pointers,
`left`

and`right`

, where`left`

moves forward from the start of the array and`right`

moves backward from the end of the array. - Move
`left`

forward when it points to an even number; move`right`

backward when it points to an odd number. - If
`left`

points to an odd number and`right`

points to an even number, swap these two elements. - Repeat the above steps until
`left >= right`

.

### Time and Space Complexity Analysis:

**Time Complexity:** The time complexity of this algorithm is O(n), where n is the length of the array. This is because we use two pointers to scan from both ends of the array towards the center, with each element being visited at most once.

**Space Complexity:** The space complexity of this algorithm is O(1), as we are merely swapping elements within the original array without using any additional arrays or data structures.

### Why the Two-Pointer Approach is Effective for this Problem:

The two-pointer approach is effective for this problem because it leverages the specific nature of the task: separating even and odd numbers. By setting one pointer to scan forward from the beginning for odd numbers and another to scan backward from the end for even numbers, we can efficiently separate the evens and odds within the array in a single pass.

This method is efficient because it operates directly on the original array, reducing extra memory allocation and movement while ensuring that each element is only examined and moved once. Therefore, it is a fast and memory-efficient method for partitioning an array.

**TypeScript代码：**

```
function sortArrayByParity(nums: number[]): number[] {
let l = 0, r = nums.length - 1;
while (l < r) {
while (l < r && nums[l] % 2 === 0) l++;
while (l < r && nums[r] % 2 !== 0) r--;
if (l < r) {
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return nums;
};
```

#### Check If N and Its Double Exist

## Check If N and Its Double Exist

Given an array arr of integers, check if there exist two indices i and j such that:

- i != j
- 0 <= i, j < arr.length
- arr[i] == 2 * arr[j]

**Example 1:**

Input:arr = [10,2,5,3]Output:trueExplanation:For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

**Example 2:**

Input:arr = [3,1,7,11]Output:falseExplanation:There is no i and j that satisfy the conditions.

**Constraints:**

- 2 <= arr.length <= 500
- -10
^{3}<= arr[i] <= 10^{3}

题目 1346. “Check If N and Its Double Exist” 要求我们检查一个给定的整数数组中是否存在某个数 N 以及其值的两倍存在。换句话说，我们需要检查是否存在两个不同的索引 i 和 j，使得 `arr[i] == 2 * arr[j]`

或 `arr[j] == 2 * arr[i]`

。

### 思路和解题步骤（中文）：

**初始化**: 创建一个哈希集合（HashSet）来存储数组中的每个元素，以便快速检查某个数或其两倍是否存在。**遍历数组**: 遍历给定的整数数组。对于每个元素`n`

，我们做以下操作：- 检查
`n`

的两倍或`n / 2`

（当`n`

是偶数时）是否在哈希集合中。如果是，返回`true`

，因为我们找到了满足条件的一对数。 - 将
`n`

添加到哈希集合中，以供后续查找。

- 检查
**返回结果**: 如果整个数组都遍历完毕，没有找到符合条件的数对，则返回`false`

。

### Thought Process and Steps (English):

**Initialization**: Create a hash set to store each element of the array for quick checking whether a number or its double exists.**Traverse the Array**: Iterate through the given integer array. For each element`n`

, we do the following:- Check if the double of
`n`

or`n / 2`

(when`n`

is even) exists in the hash set. If yes, return`true`

as we have found a pair satisfying the condition. - Add
`n`

to the hash set for future lookup.

- Check if the double of
**Return the Result**: If we have traversed the entire array without finding any satisfying pair, then return`false`

.

为什么这个代码可以满足i != j？

我们确保了`i != j`

的条件通过以下方式得到满足：

当我们遍历数组 `arr`

中的每个元素时，我们检查当前元素的两倍或当前元素的一半是否已经存在于`seen`

这个集合中。这里的关键是，**在我们将当前元素添加到 seen集合之前**，我们会先进行检查。

这意味着，如果我们发现当前元素的两倍或一半已经在`seen`

中，那么这两个数字一定是来自数组中的**不同位置**。为什么呢？因为我们还没有将当前元素加入到`seen`

集合中，所以`seen`

集合中的任何元素都是之前遍历过的，也就是说，它们来自当前元素的前面的数组索引。

因此，当我们在`seen`

集合中找到当前元素的两倍或一半时，这相当于说我们找到了数组中的另一个元素（即之前遍历过的，索引比当前元素小的元素），它满足了题目中的条件，同时也确保了这两个元素（`arr[i]`

和 `arr[j]`

）是不同的元素（因为它们位于数组的不同位置）。

在逻辑上，我们始终是在检查当前索引之前的元素（通过集合`seen`

），所以当找到匹配项时，这个匹配必然来源于一个不同的索引，即满足了`i != j`

的条件。

```
function checkIfExist(arr: number[]): boolean {
const seen: Set<number> = new Set();
for (const num of arr) {
if (seen.has(2 * num) || (num % 2 === 0 && seen.has(num / 2))) {
return true;
}
seen.add(num);
}
return false;
};
```

## 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the **longest** substring without repeating characters.

**Example 1:**

Input:s = "abcabcbb"Output:3Explanation:The answer is "abc", with the length of 3.

**Example 2:**

Input:s = "bbbbb"Output:1Explanation:The answer is "b", with the length of 1.

**Example 3:**

Input:s = "pwwkew"Output:3Explanation:The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

**Constraints:**

- 0 <= s.length <= 5 * 10
^{4} - s consists of English letters, digits, symbols, and spaces.

## The Best Ways to Do Market Research For Your Business Plan.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

##### First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

## The Easiest Way to Become a Successful Writer and Authors.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

##### First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

## The Quickest Way to Deliver Your Message? Make It Visual.

##### First, solve the problem. Then write the code.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .