数组
1. 实现一个支持动态扩容的数组
class MyArray {
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 数组的容量
getCapacity() {
return this.data.length;
}
// 是否为空
isEmpty() {
return this.size === 0;
}
resize(size) {
let newArray = new Array(size);
for (let i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
this.data = newArray;
}
insert(index, element) {
// 判断数组是否满了
if (this.size == this.getCapacity) {
this.resize(this.size * 2);
}
// 判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error('insert error! require index < 0 || index > size');
}
// 从索引出开始所有元素后移一位
for (let i = this.size - 1; i < index; i--) {
this.data[i + 1] = this.data[i];
}
// 指定索引处，插入元素
this.data[index] = element;
// 维护size
this.size++;
}
push(element) {
// this.data[this.size++] = data;
this.insert(this.size, element);
}
unshift(element) {
this.insert(0, element);
}
// 添加元素，相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity) {
throw new Error('add error! Array is full');
}
this.data[this.size++] = element;
}
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 || index >= this.size');
}
return this.data[index];
}
set(index, element) {
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 || index >= this.size');
}
this.data[index] = element;
}
// 包含
// 若元素存在，返回 true;否则，返回 false
contain(element) {
for (let i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// 搜索功能
// return 元素的索引
find(element) {
for (let i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// 搜索全部 element
// 返回等价于 element元素的所有索引
findAll(element) {
let indexArray = new MyArray(this.size);
for (let i = 0; i < this.size; i++) {
if (this.data[i] === element) {
indexArray.push(i);
}
}
return indexArray;
}
// 删除指定索引元素
remove(index) {
if (index < 0 || index >= this.size) {
throw new Error('remove error, index < 0 || index >= this.size')
}
let element = this.data[index];
// 索引后面的元素往前移一位
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.data[this.size - 1] = undefined;
this.size--;
// Resize
// 若 size 为容量一半，则进行缩容
if (Math.floor(this.getCapacity() / 2) === this.size
&& this.size !== 0
) {
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
shift() {
return this.remove(0);
}
pop() {
return this.remove(this.size - 1);
}
removeElement() {
}
removeAllElement() {
}
}
2. 实现一个大小固定的有序数组，支持动态增删改操作
class MyArray {
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 查
find(index) {
if (index < 0 || index >= this.size) {
throw new Error('find error. index < 0 || index >= this.size');
}
return this.data[index];
}
// 插入
insert(index, element) {
if(this.size == this.data.length) {
this.resize(this.size * 2);
}
if (index < 0 || index > this.size) {
throw new Error('insert error!');
}
// 从索引位后往后移一位
for (let i = index; i < this.size; i++) {
this.data[i + 1] = this.data[i];
}
this.data[index] = element;
this.size++;
}
// 添加
add(element) {
this.insert(this.size, element);
}
// 删除
remove(index) {
if (index < 0 || index >= this.size) {
throw new Error('remove error');
}
let element = this.data[index];
for (let i = index; i < array.length; i++) {
this.data[i] = this.data[i + 1];
}
this.data[this.size - 1] = undefined;
this.size--;
if (Math.floor(this.getCapacity() / 2) === this.size
&& this.size !== 0
) {
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 动态扩容
resize(capacity) {
const newArray = new Array(capacity);
for (let i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
this.data = newArray;
}
}
3. 实现两个有序数组合并为一个有序数组
const merge = (array1, m, array2, n) => {
// 交换数组位置和大小
// 始终保证 n > m
if (m > n) {
const temp = array1;
const temp_size = m;
m = n;
n = temp_size;
array1 = array2;
array2 = temp;
}
let num = m + n - 1;
--m;
--n;
while (m >= 0 && n >= 0) {
if (array2[n] > array1[m]) {
array1[num--] = array2[n--];
} else {
array1[num--] = array1[m--];
}
}
// 将剩余元素加入到 array1 中
while(n >= 0) {
array1[num--] = array2[n--];
}
return array1;
};
// TEST
// [ 1, 7, 10, 20, 39, 45, 46, 49, 80 ]
console.log(merge([1,20,39,46], 4, [7,10, 45, 49,80], 5))
字符串
1. 实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树
class TrieNode {
constructor(data){
this.data = data;
this.children = new Array(26);
this.isEndingChar = false
}
}
class TrieTree {
constructor(data){
this.root = new TrieNode('/')
}
insert (text) {
let node = this.root;
for (let char of text) {
let index = char.charCodeAt() - 'a'.charCodeAt();
if(!node.children[index]) {
node.children[index] = new TrieNode(char);
}
node = node.children[index];
}
node.isEndingChar = true;
}
find (text) {
let node = this.root;
for(let char of text) {
let index = char.charCodeAt() - 'a'.charCodeAt();
if(node.children[index]) {
node = node.children[index];
} else {
return false;
}
}
return node.isEndingChar;
}
}
2. 实现朴素的字符串匹配算法
参考资料
