mananl / algorithm Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 0.0 0 B

跟着剑指Offer学习数据结构与算法

algorithm's People

Contributors

Watchers

algorithm's Issues

数组中重复的数字

题目1：找出数组中重复的数字。
在一个长度为n的数组的所有数字都在1~n-1的范围内。数组中某些数字是重复的，但不知道有哪几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出应该是重复的数字2或者3。

除了排序数组遍历找出重复的数字（时间复杂度为nLogn），以及创建一个哈希表（时间复杂度O(1)空间复杂度O(n)）两个方法外。还可以有别的方法，综合时间复杂度与空间复杂度来看比前面两个方法更优。

由于限定了数字的最大值不会超过数组长度，可以从头到尾依次扫描数组中每个数字，当下标i与数组下标为i的值（记为m）不相等时，如果arr[m]与arr[arr[m]]两个值相等，则找到了重复数字，否则交换下标为m的数字与下标为i的数字。如果相等则继续扫描下一个。

代码实现如下：

function duplicate(arr){
    if(!(arr instanceof Array)) return;   
    const length = arr.length;
    if(length===0) return;
    for(let i of arr){
        if(i<0||i>length-1){
            return false;
        }     
    }

    for(let i=0;i<length;i++){
        while(arr[i]!=i){
            if(arr[i] == arr[arr[i]]){
                return arr[i];
            }else{
                var tmp = arr[i];
                arr[i] = arr[tmp];
                arr[tmp] = tmp;
            }
        }
    }
    return false; 
}

[JS]回溯算法之矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左右上下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

思路：
第n个字符满足在字符串的第n个位置相等，如果第n个字符的上下左右也就是n+1路径上没有符合条件的话，就倒退到n-1位置重新匹配。

代码实现：

function hasPath(arr, rows, cols, str) {
    if (rows <= 0 || cols <= 0 || !str) return false;
    let strLength = 0;//当前要匹配的字符串下标
    var visitedArr = new Array();
    //初始化标记数组
    for (let i = 0; i < rows; i++) {
        visitedArr[i] = new Array();
        for (let j = 0; j < cols; j++) {
            visitedArr[i][j] = false;
        }
    }
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (hasPathCore(arr, rows, cols, str, strLength, row, col, visitedArr))
                return true;
        }
    }
    return false;
}

function hasPathCore(arr, rows, cols, str, strLength, row, col, visitedArr) {
    if (str[strLength] == undefined) return true;

    var hasPath = false;
    if (row >= 0 && row < rows && col >= 0 && col < cols && arr[row][col] == str[strLength] && !visitedArr[row][col]) {
        visitedArr[row][col] = true;
        ++strLength;
        hasPath = hasPathCore(arr, rows, cols, str, strLength, row, col + 1, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row, col - 1, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row + 1, col, visitedArr) ||
            hasPathCore(arr, rows, cols, str, strLength, row - 1, col, visitedArr)

        if (!hasPath) {
            --strLength;
            visitedArr[row][col] = false;
        }
    }
    return hasPath;

}

测试case：

var arr_ = new Array();
var stack = ['a','v','x','s','a','w','s','d','a'];
for(let i=0;i<3;i++){
	arr_[i] = new Array();
	for(let j=0;j<3;j++){
		arr_[i][j] = stack.shift();
	}
}
arr_
(3) [Array(3), Array(3), Array(3)]0: (3) ["a", "v", "x"]1: (3) ["s", "a", "w"]2: (3) ["s", "d", "a"]length: 3__proto__: Array(0)
hasPath(arr_, 3, 3, 'aa')
false
hasPath(arr_, 3, 3, 'asad')
true

重建二叉树

题目：输入某二叉树的前序遍历和中序遍历结果，请重建该二叉树。假设输入的前序遍历和中序遍历结果中都不包含重复的数字。例如，输入前序结果“1,2,4,7,3,5,6,8”和中序遍历“4,7,2,1,5,3,8,6”。

思路：
二叉树的前序遍历顺序是DLR（根-》左-》右），中序遍历顺序为LDR。所以可以通过先序遍历得到根节点，又可以通过根节点在中序遍历的位置，将中序遍历分割为左子树与右子树。
剩下的过程就是递归的去处理。

代码实现：

function TreeNode (val) {
  this.value = val;
  this.left = null;
  this.right = null;
}
 function reConstructCore(pre, mid) {
        if(pre.length === 0){
            return null;
        }
        if(pre.length === 1){
            return new TreeNode(pre[0]);
        }
        const value = pre[0];
        const index = mid.indexOf(value);
        const midLeft = mid.slice(0,index);
        const midRight = mid.slice(index+1);
        const preLeft = pre.slice(1,index+1);
        const preRight = pre.slice(index+1);
        const node = new TreeNode(value); //二叉树节点定义函数
        node.left = reConstructCore(preLeft, midLeft );
        node.right = reConstructCore(preRight, midRight );
        return node;
    }

常规思路是遍历整个链表，找到当前节点的next与待删除节点相等的节点后，将当前节点的next指向待删除的节点的next，然后删除节点。时间复杂度为O（n）。
另一种思路，将待删除节点的值设置成他的下个节点值，指针也指向下个节点的next，是不是实际上也相当于去掉了待删除节点~
这种方法的时间复杂度为O（1），显而易见比上面方法好的多，有了大体思路后，还要考虑的更全面一些，将一些边界情况考虑到，待删除节点是尾结点，整个链表只有一个节点，这样才能让面试官肯定你的能力。

function deleteNode(pHead, pToDeleteNode){
  if(!pHead || !pToDeleteNode) return ;
  //要删除的节点不是尾节点
  if(pToDeleteNode.next != null){
    var pNext = pToDeleteNode.next;
    pToDeleteNode.value = pNext.value;
    pToDeleteNode.next = pNext.next;
    delete pNext;
  }else if(pHead == pToDeleteNode){
    delete pToDeleteNode;
  }
  //多个节点，删除尾节点
  else{
    var pNext = pHead.next;
    while(pNext.next != pToDeleteNode){
      pNext = pNext.next;
    }

    delete pToDeleteNode;
    pNext.next = null;
  }
}

链表反转

写出一个完整的链表反转的程序，总计在10行左右的代码，且链表是通过指针关联的，比较考验思维逻辑能力，所以在面试中是比较高频的面试题。
其核心**是，将下一个节点指向逻辑头节点之前，最开始链表头节点是逻辑头，当执行完一遍操作后，第二个节点变为逻辑头结点，如此循环到最后。
代码如下：

function reverseList(pHead){
  var head = pHead;
  var currentNode;
  while(pHead&& pHead.next){
    currentNode = pHead.next;
    pHead.next = currrentNode.next;
    currentNode.next = pHead;
    head = currentNode;
  }
  return head;
}

对称的二叉树

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一个二叉树和它的镜像二叉树一样，那么他是对称的。

思路：
如果一个二叉树和它的镜像二叉树一样，从前序遍历来看，会发现两个序列是相同的。

代码实现：

function isSymmetrical(pRoot1, pRoot2){
  if(!pRoot1 && !pRoot2){
    return true;
  }
  if(!pRoot1 || !pRoot2){
    return false;
  }
  if(pRoot1.value != pRoot2.value){
    return false;
  }
  return isSymmetrical(pRoot1.left, pRoot2.right)&&isSymmetrical(pRoot1.right, pRoot2.left);
}

二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1.因此，如果输入9，则该函数输出2。

思路：

把一个整数减去1，再和原整数做与运算，会把改整数最右边的1变成0。那么能进行多少次这样的计算，就可以得知有多少个1。

代码实现：

function get1Num(n){
	var count = 0;
	while(n){
		count++;
		n= n & (n-1);
	}
	return count;
}

链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点？

思路：
首先需要确定链表是否包含环。可以通过快慢两个指针来判断，如果两个指针不同速度却能相遇则证明有环。
接下来，确定环的长度。可以把相遇的点当做起点，移动指着，当指针再次回到起点时，累计的次数即为环的长度。
最后，定义两个指针，一个指针先移动环的长度的位置，之后两个指针以相同速度移动，当两个指针相遇时，即为环的入口点。

代码实现：

function meetingNode(pHead){
    if(!pHead) return null;
    var slowHead = pHead.next;
    var fastHead = pHead.next;
    while(fastHead.next){
        if(fastHead == slowHead){
            return fastHead;
        }
        slowHead = slowHead.next;
        fastHead = fastHead.next;
        if(fastHead.next){
            fastHead = fastHead.next;
        }       
    }
    return null;
}

function entryNode(pHead){
    var meetHead = meetingNode(pHead);
    if(!meetHead) return null;
    var count = 1;
    var tHead = meetHead;
    while(tHead.next!=meetHead){
        count++;
        tHead = tHead.next;
    }
    var head1 = pHead;
    var head2 = pHead;
    for(let i=0;i<count;i++){
        head1 = head1.next;
    }
    while(head1!=head2){
        head1 = head1.next;
        head2 = head2.next;
    }
    return head1;
}

mananl / algorithm Goto Github PK

algorithm's People

Contributors

Watchers

algorithm's Issues

数组中重复的数字

数组中重复的数字

[JS]回溯算法之矩阵中的路径

重建二叉树

删除链表的节点

链表反转

对称的二叉树

二进制中1的个数

链表中环的入口节点

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent