Xinrui's personal website that shares my work and thoughts
Blog Grid Light
- Home
- Blog Grid Light
Implementing a Priority Queue in TypeScript: A Step-by-Step Guide
Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.
Introduction
A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.
Why TypeScript?
TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.
Step 1: Define the Priority Queue Class
First, let’s create a PriorityQueue
class that will hold our heap.
class PriorityQueue<T> {
private heap: T[] = [];
constructor(private comparator: (a: T, b: T) => number) {}
}
- heap: An array representing the binary heap.
- comparator: A function to compare two elements, defining the priority.
Step 2: Implement the Helper Methods
Swap Method
We need a method to swap two elements in the heap.
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
Parent and Child Index Methods
Calculate the indices of parent and child nodes.
private parentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
private leftChildIndex(index: number): number {
return 2 * index + 1;
}
private rightChildIndex(index: number): number {
return 2 * index + 2;
}
Step 3: Implement the Push Method
Add a new element to the heap and reorder it to maintain the heap property.
push(item: T): void {
this.heap.push(item);
this.heapifyUp();
}
Heapify Up
Move the new element up to its correct position.
private heapifyUp(): void {
let index = this.heap.length - 1;
while (
index > 0 &&
this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
Step 4: Implement the Pop Method
Remove and return the element with the highest priority.
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const item = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown();
return item;
}
Heapify Down
Reorder the heap after removing the root element.
private heapifyDown(): void {
let index = 0;
const length = this.heap.length;
while (this.leftChildIndex(index) < length) {
let smallestChildIndex = this.leftChildIndex(index);
const rightChildIdx = this.rightChildIndex(index);
if (
rightChildIdx < length &&
this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
) {
smallestChildIndex = rightChildIdx;
}
if (
this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
) {
break;
}
this.swap(index, smallestChildIndex);
index = smallestChildIndex;
}
}
Step 5: Implement Peek and Size Methods
Get the element with the highest priority without removing it and get the size of the queue.
peek(): T | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
Step 6: Implement the Update Method
Now, we’ll implement an update()
method that allows us to update the priority of an element, either by its index or by its value.
Update by Index
updateAt(index: number, newValue: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error("Index out of bounds");
}
const oldValue = this.heap[index];
this.heap[index] = newValue;
if (this.comparator(newValue, oldValue) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.
Update by Value
Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.
update(value: T, newValue: T): void {
const index = this.heap.findIndex((element) => element === value);
if (index === -1) {
throw new Error("Value not found in heap");
}
this.updateAt(index, newValue);
}
Explanation: We find the index of the value in the heap and then call updateAt()
to update it.
Remove and Remove By Index
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
Step 7: Implement the Heapify Function
We’ll add a heapify()
method to build a heap from an existing array.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Step 8: Use the Priority Queue to Solve LeetCode 215
Now, let’s use our PriorityQueue
to find the Kth largest element in an array.
Problem Statement
Given an integer array nums
and an integer k
, return the kth
largest element in the array.
Solution
We’ll use a min-heap (priority queue) to keep track of the largest k
elements.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => a - b);
for (const num of nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.peek() as number;
}
Comparator: (a, b) => a - b
ensures a min-heap.
Logic: Maintain a heap of size k
. The root will be the kth largest element.
Full Code Listing with small changes in variable names
class PriorityQueue<T> {
private heap: T[];
constructor(private compare: (a: T, b: T) => number) {
this.heap = [];
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
private parent(i: number): number {
return Math.floor((i - 1) / 2);
}
private left(i: number): number {
return 2 * i + 1;
}
private right(i: number): number {
return 2 * i + 2;
}
private heapifyUp(index: number): void {
while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
this.swap(index, this.parent(index));
index = this.parent(index);
}
}
private heapifyDown(index: number): void {
const length = this.heap.length;
while (this.left(index) < length) {
let smallest = this.left(index);
const rightIndex = this.right(index);
if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
smallest = rightIndex;
}
if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
break;
}
this.swap(index, smallest);
index = smallest;
}
}
public push(item: T): void {
this.heap.push(item);
this.heapifyUp(this.heap.length - 1);
}
public pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown(0);
return root;
}
public peek(): T | undefined {
return this.heap[0];
}
public size(): number {
return this.heap.length;
}
public updateAtIndex(index: number, newItem: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
this.heap[index] = newItem;
if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
public update(item: T, newItem: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.updateAtIndex(index, newItem);
}
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
public isEmpty(): boolean {
return this.heap.length === 0;
}
public heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
}
Testing the Solution
Let’s test our implementation with an example.
const nums = [3, 2, 1, 5, 6, 4];
const k = 2;
const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5
Testing the Update and Heapify Methods
Using heapify()
to Build a Heap from an Array
typescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);
console.log(pq.peek()); // Output: 1
Rewriting the findKthLargest
Function Using heapify()
We can optimize our earlier findKthLargest
function by using heapify()
.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap
pq.heapify(nums);
for (let i = 0; i < k - 1; i++) {
pq.pop();
}
return pq.peek() as number;
}
Why Use heapifyDown()
in heapify()
?
That’s a great question! In the heapify()
method, we use heapifyDown()
instead of heapifyUp()
because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.
When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown()
on each node. This process is known as the heapify algorithm or build heap.
Reasons:
- Higher Efficiency:
- Lower Time Complexity: Using
heapifyDown()
, the overall time complexity of building the heap is O(n). If we were to useheapifyUp()
, the time complexity would increase to O(n log n) in the worst case. - Fewer Node Movements:
heapifyDown()
can fix all violations of the heap property from the current node down to the leaves in one pass, whereasheapifyUp()
might require multiple passes for each node.
- Lower Time Complexity: Using
- Suitable for Building the Entire Heap:
heapifyDown()
is more appropriate when you need to adjust the heap starting from the internal nodes downwards.heapifyUp()
is typically used when inserting a new element into an already built heap.
Detailed Explanation
When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
- Calculating the Starting Index:
Math.floor(this.heap.length / 2) - 1
- This formula gives us the index of the last non-leaf node.
- In a binary heap, nodes with indices from
Math.floor(n/2)
ton - 1
are all leaf nodes.
- Why Not Use
heapifyUp()
?heapifyUp()
is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.- Using
heapifyUp()
during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels. - In contrast,
heapifyDown()
can adjust the subtree rooted at a node in one pass.
An Example
Suppose we have an array [3, 2, 1, 5, 6, 4]
and we want to build a min-heap.
- Initialize the Heap:typescriptCopy code
this.heap = [3, 2, 1, 5, 6, 4];
- Start from the Last Non-Leaf Node:
- The array length is 6, so the index of the last non-leaf node is
Math.floor(6 / 2) - 1 = 2
.
- The array length is 6, so the index of the last non-leaf node is
- Perform
heapifyDown()
on Index 2:- The node at index 2 has a value
1
, and its children are out of bounds, so no action is needed.
- The node at index 2 has a value
- Perform
heapifyDown()
on Index 1:- The node at index 1 has a value
2
, with left child5
and right child6
. - Since
2
is less than its children, no action is needed.
- The node at index 1 has a value
- Perform
heapifyDown()
on Index 0:- The node at index 0 has a value
3
, with left child2
and right child1
.The right child1
is the smallest, so we swap3
with1
.
- The heap now looks like
[1, 2, 3, 5, 6, 4]
.
- The node at index 0 has a value
- Continue
heapifyDown()
on the Swapped Node:- The node at index 2 (now with value
3
) has a left child4
, but since3
is less than4
, no further action is needed.
- The node at index 2 (now with value
Summary
- Using
heapifyDown()
:- Ideal for building a heap from an array.
- Overall time complexity is O(n).
- Using
heapifyUp()
:- Suitable for inserting a single element into an existing heap.
- Each insertion has a time complexity of O(log n).
Therefore, in the heapify()
method, we choose heapifyDown()
to efficiently build a valid heap from the bottom up.
Additional Notes
- Why Not Use
heapifyUp()
?- If we used
heapifyUp()
on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity. heapifyDown()
allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.
- If we used
- Time Complexity Comparison:
- Using
heapifyDown()
: Total time complexity is O(n). - Using
heapifyUp()
: Total time complexity is O(n log n).
- Using
Conclusion
We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.
References
使用TypeScript实现优先队列 (Priority Queue)
使用TypeScript实现优先队列 (Priority Queue)
前言
大家好!今天我想和大家分享如何使用TypeScript实现一个优先队列(Priority Queue),并利用它来解决LeetCode第215题——数组中的第K个最大元素。在算法面试中,优先队列是一个非常常用的数据结构,理解并能熟练实现它对我们解决一系列问题都有帮助。
问题描述
LeetCode第215题:数组中的第K个最大元素
给定一个未排序的整数数组 nums
,找到其中第 k
个最大的元素。
示例:
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
- 1 ≤ k ≤ nums.length ≤ 10^4
- -10^4 ≤ nums[i] ≤ 10^4
解题思路
要找到第 k
个最大的元素,我们可以采用多种方法:
- 排序法:将数组排序,然后取第
k
个最大的元素。时间复杂度为 O(n log n)。 - 基于堆的优先队列:使用一个大小为
k
的最小堆来维护当前最大的k
个元素。时间复杂度为 O(n log k)。 - 快速选择算法:类似快速排序的分区思想,平均时间复杂度为 O(n)。
在这篇文章中,我们重点介绍使用最小堆实现的优先队列,因为它在实际应用中非常高效,且实现相对简单。
什么是优先队列?
优先队列是一种特殊的队列,元素按照优先级进行出入队操作。常用的实现方式是堆,根据堆的性质,可以快速地获取当前的最值(最大值或最小值)。
在我们的问题中,我们需要维护一个大小为 k
的最小堆,堆顶元素就是当前第 k
个最大的元素。
TypeScript中实现最小堆
堆的基本操作
- 插入元素(insert):将新元素添加到堆的末尾,然后向上调整位置(上浮)。
- 删除堆顶元素(extractMin):移除堆顶元素,将末尾元素放到堆顶,然后向下调整位置(下沉)。
- 查看堆顶元素(getMin):获取堆顶元素的值。
- 获取堆的大小(size):返回堆中元素的数量。
实现代码
class MinHeap {
private heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
this.bubbleUp();
}
private bubbleUp(): void {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin(): number | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const end = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return min;
}
private sinkDown(): void {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * index + 1;
let rightChildIdx = 2 * index + 2;
let swapIdx: number | null = null;
if (leftChildIdx < length) {
if (this.heap[leftChildIdx] < element) {
swapIdx = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(swapIdx === null && this.heap[rightChildIdx] < element) ||
(swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
) {
swapIdx = rightChildIdx;
}
}
if (swapIdx === null) break;
[this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
index = swapIdx;
}
}
getMin(): number | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
}
代码解释
- insert(val: number):将元素添加到堆末尾,然后调用
bubbleUp
进行上浮操作,保持最小堆性质。 - bubbleUp():从新添加的元素开始,与父节点比较,如果小于父节点则交换位置,直到满足最小堆性质。
- extractMin():移除并返回堆顶元素,将堆末尾元素放到堆顶,然后调用
sinkDown
进行下沉操作。 - sinkDown():从堆顶开始,与子节点比较,如果大于子节点则交换位置,直到满足最小堆性质。
- getMin():返回堆顶元素,不修改堆。
- size():返回堆中元素的数量。
利用最小堆解决第K个最大元素问题
实现思路
- 创建一个大小为
k
的最小堆。 - 遍历数组,将元素逐一插入堆中。
- 当堆的大小超过
k
时,移除堆顶元素(最小值)。 - 遍历完成后,堆顶元素就是第
k
个最大元素。
实现代码
function findKthLargest(nums: number[], k: number): number {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.size() > k) {
minHeap.extractMin();
}
}
return minHeap.getMin()!;
}
代码解释
- 遍历数组:将每个元素插入到最小堆中。
- 维护堆的大小:如果堆的大小超过
k
,则移除堆顶元素,确保堆中始终只包含当前最大的k
个元素。 - 返回结果:遍历结束后,堆顶元素即为第
k
个最大元素。
测试代码
const nums1 = [3, 2, 1, 5, 6, 4];
const k1 = 2;
console.log(findKthLargest(nums1, k1)); // 输出: 5
const nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
const k2 = 4;
console.log(findKthLargest(nums2, k2)); // 输出: 4
时间复杂度分析
- 插入和移除操作:每次操作的时间复杂度为 O(log k)。
- 总时间复杂度:对于长度为
n
的数组,总的时间复杂度为 O(n log k),当k
远小于n
时,效率较高。
空间复杂度分析
- 空间复杂度:使用了额外的堆空间,最大为 O(k)。
总结
通过使用最小堆实现的优先队列,我们可以高效地找到数组中的第 k
个最大元素。这种方法在处理大规模数据时非常实用,因为我们不需要对整个数组进行排序,只需维护一个大小为 k
的堆即可。
优点
- 高效性:时间复杂度为 O(n log k),比直接排序的 O(n log n) 更优。
- 适用性强:当需要实时处理数据流并获取第
k
个最大元素时,此方法非常适用。
缺点
- 实现复杂度:相比内置排序函数,手动实现堆需要更多的代码和调试。
后记
希望这篇文章能帮助大家理解如何在TypeScript中实现优先队列,并应用于实际问题。如果有任何疑问或改进建议,欢迎在评论区与我交流!
参考资料
感谢阅读!如果觉得有帮助,请点赞支持。
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 <= 105
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
andprev
). - Ensure the
child
pointer is set tonull
.
- 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
isnull
. If it is, returnnull
immediately. - Initialize
current
to start from thehead
node.
- Check if
- Traversal:
- Use a
while
loop to traverse the entire linked list.
- Use a
- Handling the
child
:- If
current
has achild
, perform the following steps:- Temporarily store the
next
node (current.next
). - Recursively flatten the
child
list by callingflatten(current.child)
. - Insert the flattened
child
list between thecurrent
node and thenext
node:- Set
current.next
to the head of the flattenedchild
list. - Update the
prev
pointer of the flattenedchild
list head to point tocurrent
.
- Set
- Find the tail of the flattened
child
list by iterating through it untilchild.next
isnull
. - Connect the tail of the flattened
child
list to thenext
node:- Set
next.prev
to the tail of the flattenedchild
list (ifnext
is notnull
). - Set the
next
pointer of the tail of the flattenedchild
list tonext
.
- Set
- Set
current.child
tonull
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 theMyLinkedList
object.int get(int index)
Get the value of theindexth
node in the linked list. If the index is invalid, return-1
.void addAtHead(int val)
Add a node of valueval
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 valueval
as the last element of the linked list.void addAtIndex(int index, int val)
Add a node of valueval
before theindexth
node in the linked list. Ifindex
equals the length of the linked list, the node will be appended to the end of the linked list. Ifindex
is greater than the length, the node will not be inserted.void deleteAtIndex(int index)
Delete theindexth
node in the linked list, if the index is valid.
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] Explanation MyLinkedList 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 toget
,addAtHead
,addAtTail
,addAtIndex
anddeleteAtIndex
.
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 toaddAtTail
. - 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 <= 105
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: 1 Explanation: 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: 2 Explanation: 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: 1 Explanation: 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 <= 104
-231 <= nums[i] <= 231 - 1
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: 4 Explanation: - 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: 4 Explanation: - 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 <= 105
nums[i]
is either0
or1
.
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
andright
, whereleft
moves forward from the start of the array andright
moves backward from the end of the array. - Move
left
forward when it points to an even number; moveright
backward when it points to an odd number. - If
left
points to an odd number andright
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: true Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]
Example 2:
Input: arr = [3,1,7,11] Output: false Explanation: There is no i and j that satisfy the conditions.
Constraints:
- 2 <= arr.length <= 500
- -103 <= arr[i] <= 103
题目 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
orn / 2
(whenn
is even) exists in the hash set. If yes, returntrue
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: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: 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 * 104
- 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.
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 Quickest Way to Deliver Your Message? Make It Visual.
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.
Why We Don’t Have Technical Interviews for Technical Roles at Buffer.
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.
Why Successful People Wear The Same Thing Every Day.
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.
What I Learned From Being a Broke, Unemployed Graduate.
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.