データ構造とアルゴリズムを再起動します.
9472 ワード
# 1
> ， Deno TypeScript
1. [ 1](https://github.com/guokangf/m-dream/issues/6)
##
>
-
- _ ， _
： 、 、 、
##
： 、 、 ， 、
---
##
> 0， ，
：
- ，
- ，
###
：
/**
* 11 * 11
* 0:
* 1:
* 2:
*/
private chessArr1: SparseArrayType;
constructor() {
this.chessArr1 = [];
for (let i = 0; i < 11; i++) {
this.chessArr1[i] = new Array(11).fill(0);
}
this.chessArr1[1][2] = 1;
this.chessArr1[2][4] = 2;
//
console.table(this.chessArr1);
}
/** */
public ready() {
const decoder = new TextDecoder("utf-8");
const data = Deno.readFileSync(dataFileName);
console.log(' : ');
console.table(JSON.parse(decoder.decode(data)));
}
/** */
public save(arr: SparseArrayType) {
const encoder = new TextEncoder();
const data = encoder.encode(JSON.stringify(arr));
Deno.writeFileSync(dataFileName, data);
}
/** */
toSparseArray(): SparseArrayType {
// 1 0
let sum = 0;
for (let i = 0; i < 11; i++) {
for (let j = 0; j < 11; j++) {
if (this.chessArr1[i][j] !== 0) {
sum++;
}
}
}
console.log(`sum -> ${sum}`);
// 2.1
let intSparseArray: number[][] = [[11, 11, sum]];
// 2.2 0
let count = 0; //
for (let i = 0; i < 11; i++) {
for (let j = 0; j < 11; j++) {
if (this.chessArr1[i][j] !== 0) {
intSparseArray[++count] = [i, j, this.chessArr1[i][j]];
}
}
}
console.table(' ：');
console.table(intSparseArray);
return intSparseArray;
}
/** */
recover(sp: SparseArrayType): SparseArrayType {
let chessArr2: SparseArrayType = [];
// 1.
let [rowCount, columnCount, valueCount] = sp[0]; // 0 ， ，
for (let i = 0; i < columnCount; i++) {
chessArr2[i] = new Array(rowCount).fill(0);
}
// 2.
for (let i = 1; i < sp.length; i++) {
const [rowIndex, columnIndex, value] = sp[i];
chessArr2[rowIndex][columnIndex] = value
}
console.table(' ：');
console.table(chessArr2);
return chessArr2;
}
##
， ` ` ` ` ， ` ` 。 ： ， 。
###
public queue: number[];
private front: number;
private rear: number;
private maxSize: number;
constructor(maxSize: number) {
this.queue = [];
this.front = -1;
this.rear = -1;
this.maxSize = maxSize;
}
public isFull() {
return this.rear === this.maxSize - 1;
}
public isEmpty() {
return this.front === this.rear;
}
public add(value: number) {
if (this.isFull()) {
console.log(' ');
return;
}
this.queue[++this.rear] = value;
}
public pop(): number | undefined {
if (this.isEmpty()) {
console.log(' ');
return;
}
return this.queue[++this.front];
}
public show() {
if (this.isEmpty()) {
console.log(' ');
return;
}
console.log(this.queue.slice(this.front + 1, this.rear + 1).join(','));
}export default Queueue Aray;
：
- ，
- ， ** ** ：%
//環状キューclass Circure ArayQue｛
private maxSize: number;
private queue: number[];
private front: number;
private rear: number;
constructor(maxSize: number) {
this.maxSize = maxSize;
this.queue = [];
this.front = 0;
this.rear = 0;
}
private isFull() {
return (this.rear + 1) % this.maxSize === this.front;
}
private isEmpty() {
return this.front === this.rear;
}
public add(value: number) {
if (this.isFull()) {
console.log(' ');
return;
}
this.queue[this.rear++] = value;
}
public pop() {
if (this.isEmpty()) {
console.log(' ');
return;
}
const ret = this.queue[this.front];
this.front++;
return ret;
}
public show() {
if (this.isEmpty()) {
console.log(' ');
return;
}
const printList = [];
let count = 0;
for (let i = this.front; i < this.front + this.size() - 1; i++) {
printList[count++] = this.queue[i];
}
console.table(printList);
}
/** */
private size() {
return this.rear - this.front + 1;
}const command Dict={
a: 'add - ',
p: 'pop - ',
s: 'show - ',
'-h': 'help - ',console.table(commandDict);
const q = new CircleArrayQueue(4); // ，4 rear
for await (const line of readLines(Deno.stdin)) {
switch (line) {
case '-h':
console.table(commandDict);
break
case 'a':
console.log(' :');
const ret = await readLines(Deno.stdin).next();
const value = Number(ret.value.trim());
if (typeof value !== 'number' || isNaN(value)) {
console.log(' ！');
break;
}
q.add(value);
break;
case 'p':
const valuePop = q.pop();
console.log(`${valuePop}， `);
break;
case 's':
q.show();
break;
}
}
##
> ** **（Linked list） ， [ ](https://zh.wikipedia.org/wiki/ )， ， [ ](https://zh.wikipedia.org/wiki/ _( ))(Pointer)。 ， O(1) [ ](https://zh.wikipedia.org/wiki/ )， [ ](https://zh.wikipedia.org/wiki/ ) ， O(n) ， O(logn) O(1)。
###
， ， ：
public no: number;
public name: string;
public nickName: string;
public next: HeroNode | null;
constructor(no: number, name: string, nickName: string) {
this.no = no;
this.name = name;
this.nickName = nickName;
this.next = null;
}
public show() {
console.log(`no = ${this.no}; name = ${this.name}; nickName = ${this.nickName}`);
}class Single LinkdList｛
private head: HeroNode;
constructor() {
this.head = new HeroNode(0, '', '');
}
/** */
public add(node: HeroNode) {
let temp = this.head;
while (temp.next) {
temp = temp.next;
}
temp.next = node;
}
/**
*
* 1.
* */
public addByOrder(heroNode: HeroNode) {
let temp: HeroNode | null = this.head;
let flag = false; //
//
while (temp.next !== null) {
if (temp.next.no === heroNode.no) {
flag = true;
break;
}
if (temp.next.no > heroNode.no) {
break;
}
temp = temp.next;
}
if (flag) {
console.log(` ：${heroNode.no}， `)
return;
}
heroNode.next = temp.next;
temp.next = heroNode;
}
/** */
public update(newHeroNode: HeroNode) {
let temp = this.head;
let flag = false; //
while (temp.next !== null) {
if (temp.no === newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
return;
}
console.log(' ');
}
/** */
public del(no: number) {
let temp = this.head;
let flag = false; //
//
while (temp.next) {
if (temp.next.no === no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag && temp.next !== null) {
temp.next = temp.next.next;
return;
}
console.log(' ');
}
/** */
public show() {
let temp = this.head;
while (temp.next) {
temp = temp.next;
temp.show();
}
}window.onload=function main(){
const hero1 = new HeroNode(1, ' ', ' ');
const hero2 = new HeroNode(2, ' ', ' ');
const hero3 = new HeroNode(3, ' ', ' ');
const hero4 = new HeroNode(4, ' ', ' ');
const singleLinkedList = new SingleLinkedList();
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero3);
singleLinkedList.del(5);
singleLinkedList.show();
##
：
-
- k
-
-
Stack
- ，