剑指offerjs（未完）

2019-04-16 本文已影响0人一包

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

未考虑边界

function duplicate(numbers, duplication)
{
    // write code here
    //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    //函数返回True/False
     if(!numbers || !numbers.length){
        return false;
    }
    for(let i=0;i<numbers.length;i++){
        if(numbers.indexOf(numbers[i])==i&&numbers.lastIndexOf(numbers[i])!==i){
            duplication[0]=numbers[i];
            return true;
        }
    }
    return false;
    
}

作者：faremax
链接：https://www.nowcoder.com/discuss/49349?type=0&order=0&pos=6&page=1
来源：牛客网

function duplicate(numbers, duplication){
    if(!numbers || !numbers.length){
        return false;
    }
    var len = numbers.length;
    for(var i = 0; i < len; i++){
        var curr = numbers[i];
        if(numbers.indexOf(curr) !== i){
            duplication[0] = curr;
            return true;
        }
    }
    return false;
}

2.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

function MoreThanHalfNum_Solution(numbers)
{
      if(numbers.length==0)return 0;
   
    // write code here
    let obj={};
    for(let i=0;i<numbers.length;i++){
        let cur=numbers[i];
        if(obj[cur]){
            obj[cur]++;
        }else{
            obj[cur]=1;
        }
    }
    let max=0;
    let index=0;
    for(let key in obj){
        if(obj[key]>max){
            max=obj[key];
            index=key;
        }
    }
    return max>(numbers.length)/2?index:0;
}

3.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

参考https://blog.csdn.net/weixin_33894640/article/details/87343536
若ab > ba 则 a > b，
若ab < ba 则 a < b，
若ab = ba 则 a = b；
比较3和31时，'331' > '313'，所以返回结果是'3' > '31'。
根据指定排序规则对数组进行排序，然后从小到大拼接即为所求结果

//参考https://www.cnblogs.com/wuguanglin/p/PrintMinNumber.html
function PrintMinNumber(numbers)
{
    // write code here
    numbers.sort(function(a,b){
        const str1=`${a}${b}`;
        const str2=`${b}${a}`;
        return str1>str2;
    })
    var min="";
    numbers.forEach(function(item){
        min+=item;
    })
    return min;
}

4.在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

function FirstNotRepeatingChar(str)
{
   if(str.length < 1 || str.length > 10000)return -1;
    for(let i=0;i<str.length;i++){
        
        if(str.indexOf(str.charAt(i))==i&&str.lastIndexOf(str.charAt(i))==i){
            return i;
            break;
        }
    }
   
}

//https://www.cnblogs.com/wuguanglin/p/FirstNotRepeatingChar.html
function FirstNotRepeatingChar(str) {
  if (str.length < 1 || str.length > 10000) return -1;
  const map = {};
  for (let i = 0; i < str.length; i++) {
    if (!map[str[i]]) {
      map[str[i]] = 1;
    } else {
      map[str[i]]++;
    }
  }
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]] === 1) {
      return i;
    }
  }
  return -1;
}

5.翻转字符串

function ReverseSentence(str)
{
    if(!str||str.length==0)return "";
   var arr=str.split(" ");
    return arr.reverse().join(" ");
}

6.输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

function reOrderArray(array)
{ 
    if(!array||array.length==0)return [];
    var left=[];
    var right=[];
    for(let i=0;i<array.length;i++){
        if(array[i]%2==0){
            right.push(array[i]);
        }else{
            left.push(array[i]);
        }
    }
    return left.concat(right);
}

function reOrderArray(array)
{
    let temp = 0;
    for(let i = 0;i < array.length;i++){
        for(let j = array.length-1; j>i;j--){
            if(array[j]%2==1&&array[j-1]%2==0){
                temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            }
        }
    }
    return array;
}

7.对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

function LeftRotateString(str, n)
{
    if(!str||str.length==0)return "";
    if(n==0)return str;
    var len=str.length;
   return str=str.substr(n,len-1)+str.substr(0,n);
  
}

8. 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

function Permutation(str)
{
    // write code here
    if(!str||str.length<0||str.length>9)return "";
    let res=handle(str);
    console.log([...new Set(res)]);
    
}
function handle(str){
    if(str.length==1)return [str];
    let res=[];
    for(let i=0;i<str.length;i++){
       
        let arr=handle(str.replace(str[i],""));
        for(let j=0;j<arr.length;j++){
            res.push(str[i]+arr[j]);
        }
    }
  return res;
}

9.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function Find(target, array)
{
    let n=array.length;
    let m=array[0].length;
    if(m==0&&n==0)return false;
    let row=n-1;
    let col=0;//左下角开始查，比target大往上，比他小往右
    
    while(row>=0&&col<m){
        if(array[row][col]>target){
            row--;
        }else if(array[row][col]<target){
            col++;
        }else{
            return true;
        }
    }
    return false;
}

10.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    // write code here
    const res=[];
    let pNode=head;
    if(pNode==null)return [];
    while(pNode!==null){
        res.unshift(pNode.val);
        pNode=pNode.next;
    }
    return res;
}

11.用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

const inStack=[];
const outStack=[];

function push(node)
{
   inStack.push(node);
    
}
function pop()
{
     if (outStack.length==0) {
    while (inStack.length) {
      outStack.push(inStack.pop());
    }
  }
  return outStack.pop();
}

12.把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

有个分界点，就是那个最小的值，时间复杂度n

function minNumberInRotateArray(rotateArray)
{
   if(rotateArray.length==0)return 0;
   
    for(let i=0;i<rotateArray.length;i++){
       if(rotateArray[i]>rotateArray[i+1])return rotateArray[i+1];
    }
}

二分查找法，nlogn

13.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

//前两个不用循环了，所以n-2
function Fibonacci(n)
{

 var a = 1, b = 1, temp;
    if(n <= 0) return 0;
    for(var i = 1; i <= n-2; i++){
      temp = b;
      b = a + b;
      a = temp;
    }
    return b;
}

14.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

function jumpFloor(number)
{
    if(number<1)return 0;
    if(number==1)return 1;
    if(number==2)return 2;
    var temp,a=1,b=2;
    for(var i=3;i<=number;i++){
        //temp=a+b;
       // a=b;
       // b=temp;
        temp=b;
        b=a+b;
        a=temp;
        
    }
    return b;
}

15. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

青蛙只跳1或2可以得出是一个斐波那契问题，即a[n]=a[n-1]+a[n-2],那么能跳1,2,3个台阶时a[n]=a[n-1]+a[n-2]+a[n-3],......
那么有：

a[n]=a[n-1]+a[n-2]+......+a[1];..........................①
a[n-1]=        a[n-2]+......+a[1];..........................②
两式相减可知：a[n]=2*a[n-1];

function jumpFloorII(number)
{
    let i=1;
    while(--number){
        i=i*2;
    }
    return i;
}

16.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    if(pre.length==0||vin.length==0)return null;
    let index = vin.indexOf(pre[0]);
    let left = vin.slice(0,index);
    let right = vin.slice(index+1);
    let node = new TreeNode(pre[0]);
    node.left = reConstructBinaryTree(pre.slice(1,index+1),left);
    node.right = reConstructBinaryTree(pre.slice(index+1),right);
    return node;
   
}

17.操作给定的二叉树，将其变换为源二叉树的镜像（翻转二叉树）

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Mirror(root)
{
    if(!root) return null;
    let tmp;
    tmp=root.left;
    root.left=root.right;
    root.right=tmp;
    if(root.left){
        Mirror(root.left);
    }
    if(root.right){
        Mirror(root.right);
    }
    return root;
}

18.从上往下打印出二叉树的每个节点，同层节点从左至右打印。

广度遍历

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function PrintFromTopToBottom(root)
{
    let queue=[];
    let res=[];
    if(root==null){
        return [];
    }
    queue.push(root);
    while(queue.length){
        let pnode=queue.shift();
        if(pnode.left)queue.push(pnode.left);
        if(pnode.right)queue.push(pnode.right);
        res.push(pnode.val);
    }
    return res;
    
}

19.输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

function FindNumbersWithSum(array, sum)
{
    if (array.length < 2) return [];
      let left = 0,
    right = array.length - 1;
      const res = [];
      while (left < right) {
    if (array[left] + array[right] < sum) {
      left++;
    } else if (array[left] + array[right] > sum) {
      right--;
    } else {
      res.push(array[left], array[right]);
      break;
    }
  }
  return res;
}

剑指offerjs（未完）

2.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

3.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

4.在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

5.翻转字符串

6.输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

7.对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

8. 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

9.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

10.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

11.用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

13.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

14.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

15. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

16.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

17.操作给定的二叉树，将其变换为源二叉树的镜像（翻转二叉树）

18.从上往下打印出二叉树的每个节点，同层节点从左至右打印。

19.输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

猜你喜欢

热点阅读

剑指offerjs（未完）

2.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

3.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

4.在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

5.翻转字符串

6.输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

7.对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

8. 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

9.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

10.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

11.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

13.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

14.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

15. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

16.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

17.操作给定的二叉树，将其变换为源二叉树的镜像（翻转二叉树）

18.从上往下打印出二叉树的每个节点，同层节点从左至右打印。

19.输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

猜你喜欢

热点阅读

11.用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。