1. 一个数组，有2n个元素，其中有个数字重复出现了n次。其他n个数字都是不相同的。 空间复杂度O(1)。时间复杂度O(n)。找出这个重复的数字。
function findNumber(array) {
var findArr = [];
for(var i=0;i<array.length;i++){
if(findArr.indexOf(array[i]) != -1){
return array[i];
}
if(findArr.indexOf(array[array.length-1-i]) != -1){
return array[array.length-1-i];
}
array.push(array[i]);
array.push(array[array.length-1-i]);
}
}
2.如何判断一个链表是否存在环？时间复杂度为n，空间复杂度为1。
快慢指针法：
function judge(list) {
//创建快慢指针
var fast = list.next.next;
var slow = list.next;
while(list) {
if(fast === slow){
return true;
}
fast = fast.next.next;
slow = show.next;
}
}
3. 如何判断一个数组符合前序遍历/后续遍历？
后续遍历：数组中最后一个节点是根节点；除根节点的那部分，左半部分是左子树，右半部分是右子树。左子树小于根节点，右子树大于根节点。
思路：找到左右子树的分割点，如果当一个数小于后一个数，则后一个数的后半部分为右子树，如果右子树有小于根节点的则不符合。
代码：
function judge(array) {
if(array.length <= 0){
return false;
}
var len = array.length;
var root = array[len-1];//找到根节点
var i;
for(i=0;i<len-1;i++){
//从最开始，找到第一个 大于根节点的数时，跳出循环
if(root < array[i])
break;
}
var j;
for(j=i;j<len-1;j++){
//开始测试后半部分数据
if(root > array[j])
return false;// 后半部分若小于 根节点 ，则该数组不是后序遍历
}
// 设置左半部分的数据标志
var left = true;
if(i>0){
// 采用递归 ，测试前半部分数组是否满足后序遍历
//数组的 slice 方法 ，不会改变原数组 ，会返回一个新数组 ，会从原数组中截取 从 0 到 i的新数组
left = judge(array.slice(0,i))
}
var right = true;
if(i<len - 1){
// 采用递归 ，测试后半部分数组是否满足后序遍历
right = judge((array.slice(i,len-1));
}
// 只有 leftFlag 和 rightFlag 都为 true 时，说明 该数组是 后序遍历
return left && right;
}
同理前序遍历，只需把根节点是最后一个元素改成根节点是第一个元素即可：
function judge(array)
{
if(array.length <= 0){
return false;
}
var len = array.length;
var root = array[0];//找到根节点
var i;
for(i=1;i<len;i++){
//找到第一个大于根节点的数时，跳出循环
if(root < array[i])
break;
}
var j;
for(j=i;j<len;j++){
//开始测试后半部分数据
if(root > array[j])
return false;// 后半部分若小于 根节点 ，则该数组不是前序遍历
}
// 设置左半部分的数据标志
var left = true;
if(i>1){
// 采用递归 ，测试前半部分数组是否满足前序遍历
//数组的 slice 方法 ，不会改变原数组 ，会返回一个新数组 ，会从原数组中截取 从 0 到 i的新数组
left = judge(array.slice(1,i))
}
var right = true;
if(i<len){
// 采用递归 ，测试后半部分数组是否满足前序遍历
right = judge((array.slice(i,len));
}
// 只有 leftFlag 和 rightFlag 都为 true 时，说明 该数组是前序遍历
return left && right;
}
4. 实现一个二分查找
二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。
思路：从数组中间元素查起，如果中间元素就是目标元素，返回；如果不是，目标元素小于中间元素，往左找，大于中间元素，往右找。
代码：
递归法：
function judge(array,key) {
if(array.length <= 0){
return -1;
}
var mid = parseInt((array.length) / 2);
if(array[mid] === key){
return mid;
}else if (array[mid] > key){
var leftArray = array.slice(0,array[min-1]);
return judge(leftArray, key);
}else if (arr[mid] < key){
var rightArray = array.slice(array[min+1],array.length);
return judge(rightArray, key);
}
}
5.二叉树前序遍历
//定义节点
function Node(element,left,right){
this.element=element;
this.left=left;
this.right=right;
this.show=function () {
return this.element;
}
}
//定义树结构
function BST() {
this.root = null;
//插入节点（insert node)
this.insert=function (element) {
var n = new Node(element, null, null);
if (this.root == null) {
this.root = n;
}else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (element < current.element) {
//待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
current = current.left;
//如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次while循环。
if (current == null) {
parent.left = n;
break;
}
}else {
//待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的右节点
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
//前序遍历
this.preSort = function (node) {
if(node != null){
console.log(node.show());
this.preSort(node.left);
this.preSort(node.right);
}
}
//中序遍历
this.inSort = function (node) {
if(node != null){
this.inSort(node.left);
console.log(node.show());
this.inSort(node.right);
}
}
//后序遍历
this.nextSort = function (node) {
if(node != null){
this.nextSort(node.left);
this.nextSort(node.right);
console.log(node.show());
}
}
6.实现大数相加求和
- 什么是大数？
在32位系统下最大只能表示2^31-1,也就是2147483647，想要表示更大的数可以使用字符串。 - 思路：逐位相加并进位。
function sumStrings(a,b) {
// 操作数类型判断, 要求为字符串
if (typeof a !== 'string' || typeof b !== 'string') {
return false;
}
//通过补零让a和b对齐
//若a比b短，则对a补零
while(a.length < b.length){
a = "0" + a;
}
//若b比a短，则对b补零
while(b.length < a.length){
b = "0" + b;
}
//是否有进位
var addOne = 0;
//结果数组
var result = [];
//从个位开始相加
for(var i=a.length-1;i>=0;i--){
var c1 = a.charAt(i) - 0;
var c2 = b.charAt(i) - 0;
var sum = c1 + c2 + addOne;
//若数字相加大于9，则进位
if(sum > 9){
result.unshift(sum - 10);
addOne = 1;
}
else{
result.unshift(sum);
addOne = 0;
}
}
//如果还有进位，最后要把进位进完
if(addOne){
result.unshift(addOne);
}
//移除第一位的"0"
if(result[0] == 0){
result.splice(0,1);
}
return result.join("");
}
7. 请实现如下函数，可以批量请求数据。所有的url地址都在urls参数中，同时可以通过max控制请求的并发度，当所有请求结束后，调用callback回调函数。请求直接用fetch就可以。
var urls = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
const limit = 5;
// 主函数
function sendRequest(urls, limit , callback) {
function _send (urls) {
return fetch(urls.shift())
.finally(() => {
if(urls.length) {
return _send(urls)
}
})
}
let asyncList = [];
while(limit--) {
asyncList.push(_send(urls));
}
return Promise.all(asyncList).then(callback);
}
sendRequest(urls, limit, function() {
console.log('finish')
});
