javascriptコードを使ってプログラミングします(1-65)

牛客ネット上の判定システムを採用しています.javascript(V 8 6.0.0)とNode.jsです.
1.二次元配列の検索

function Find(target, array)
{
    // write code here
     var row = array.length;  //   
    var col = array[0].length;  //   
    
    //         
    var r = 0;
    var c = col-1;
   
    while(r <=row-1 && c >= 0) { //         
        if (target > array[r][c]) {
            r++;
        }
        else if (target < array[r][c]) {
            c--;
        }
        else {
            return true;
        }
    }
    return false;
}

 
2.スペースの置換

function replaceSpace(str)
{
    // write code here
   return str.replace(/\s+?/g,'%20')
}

 
3.端からチェーンシートを印刷する

function printListFromTailToHead(head)
{
    // write code here
    var res = [];
    while(head!=null){
        res.push(head.val);
        head = head.next;
    }
    return res.reverse();
}

 
4.二叉樹を再構築する

function reConstructBinaryTree(pre, vin)
{
    // write code here
   if (!pre || pre.length === 0) {
        return;
    }
    
    var treeNode = {
        val: pre[0]
    }
    for(var i = 0; i < pre.length; i++) {
        if (vin[i] === pre[0]) {
            treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
            treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
        }
    }
    return treeNode;
}

 
5.2つのスタックでキューを実現する

var result=[];
function push(node)
{
    // write code here
    result.push(node)

}
function pop()
{
    // write code here
    return result.shift()
}

 
6.回転配列の最小数

function minNumberInRotateArray(rotateArray)
{
    // write code here
    rotateArray.sort(function(a,b){
        if(a<b){
            return -1;
        }
        else
            return 1;
        
    })
    return rotateArray[0];
}

 
7.フィボナッチ数列(循環方法)

function Fibonacci(n)
{
    // write code here
    if(n==0||n==1){
        return n;
    }
    var f1 = 0;
    var f2 = 1;
    for(var i =2;i<=n;i++){
        var tmp = f1 + f2;
        f1 = f2;
        f2 = tmp;
    }
    return tmp;
}

 
8.階段を上がる

function jumpFloor(number)
{
    // write code here
    if(number==1){
        return 1;
    }
    if(number==2){
        return 2;
    }
    var f1 = 1;
    var f2 = 2;
    for(var i=2;i){
        var tmp = f1+ f2;
        f1 = f2;
        f2 = tmp;
    }
    return f2;
}

 
9.変態ジャンプステップ

function jumpFloorII(number)
{
    // write code here
    if(number==1){
        return 1;
    }
    if(number==2){
        return 2;
    }
    else
        return 2*jumpFloorII(number-1);
}

 
10.長方形のカバー

function rectCover(number)
{
    // write code here
    if(number<=0){
        return 0;
    }
    if(number==1||number==2){
        return number;
    }
       
    var f1 = 0;
    var f2 = 1;
    for(var i=1;i<=number;i++){
        var tmp = f1 + f2;
        f1 = f2;
        f2 = tmp;
    }
    return f2;
}

 
11.バイナリの1の個数
 

function NumberOf1(n)
{
    // write code here
    var count = 0;
    while(n!=0){
        n = n&(n-1);
        count++
    }
    return count;
}

 
 
12.数値の整数乗

function Power(base, exponent)
{
    // write code here
    if(exponent==0){
        return 1;
    }
    var result = 1;
    if(exponent>0){
        for(var i=1;i<=exponent;i++){
            result *= base;
        }
        return result;
    }
    if(exponent<0){
        exponent = Math.abs(exponent);
         for(var i=1;i<=exponent;i++){
            result *= base;
        }
        result = 1/result;
        return result;
    }
}

 
13.配列要素の順序を調整し、奇数を偶数より前に配置する

function reOrderArray(array)
{
    // write code here
    var result1 = [];
    var result2 = [];
    for(var i=0;i){
        if(array[i]%2==0){
            result1.push(array[i]);
        }
        else{
            result2.push(array[i]);
        } 
    }
    return result2.concat(result1);
}

 
 14.チェーン表の最後からk番目の結点

function FindKthToTail(head, k)
{
    // write code here
    if(head==null||k<=0) return null;
    var prev = head;
    var tail = head;

    for(var index=0;index){
        if(tail.next!=null){
            tail=tail.next;
        }else{
            return null;
        }        
    }    
    while(tail.next!=null){
        prev=prev.next;
        tail=tail.next;
    }
    return prev;
}
module.exports = {
    FindKthToTail : FindKthToTail
};

 
15.逆転リスト

function ReverseList(pHead)
{
    // write code here
    if(pHead==null||pHead.next==null) return pHead;
    var prev=null;
    var next=null;
    while(pHead!=null){
        next=pHead.next;
        pHead.next=prev;
        prev=pHead;
        pHead=next;
    }
    return prev;
}
module.exports = {
    ReverseList : ReverseList
};

 
16.2つの並べ替えチェーンを結合する

function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)
{
    // write code here
    var head=new ListNode(0);
    var pHead=head;
    while(pHead1!=null && pHead2!=null){
        if(pHead1.val>=pHead2.val){
            head.next=pHead2;
            pHead2=pHead2.next;
        }else{
            head.next=pHead1;
            pHead1=pHead1.next;
        }
        head=head.next;
    }
    if(pHead1!=null){
        head.next=pHead1;
    }
    if(pHead2!=null){
        head.next=pHead2;
    }
    return pHead.next;
}
module.exports = {
    Merge : Merge
};

 
17.木のサブ構造

 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function isSubtree(pRoot1,pRoot2){
    if (pRoot2 == null) return true;//pRoot2 null，         
    if (pRoot1 == null) return false;
    if(pRoot1.val==pRoot2.val){
        return isSubtree(pRoot1.left,pRoot2.left) && isSubtree(pRoot1.right,pRoot2.right);
    }else{
        return false;
    }
}

function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(pRoot1==null||pRoot2==null) return false;   
    return isSubtree(pRoot1,pRoot2)||HasSubtree(pRoot1.left,pRoot2)||HasSubtree(pRoot1.right,pRoot2);
}
module.exports = {
    HasSubtree : HasSubtree
};

 
18.二叉樹の鏡像

function Mirror(root)
{
    // write code here
    if(root==null) return null;
    //          
    var  tmp = root.left;
    root.left=root.right;
    root.right=tmp;
    //  
    Mirror(root.left);
    Mirror(root.right)
}
module.exports = {
    Mirror : Mirror
};

 
19.行列を時計回りに印刷する

function printMatrix(matrix)
{
    // write code here
    if(matrix==null || matrix.length==0) return;
    var rows = matrix.length;
    var cols = matrix[0].length;
    var start=0;
    var result=[];

    while(cols>start*2 && rows>start*2){
        //x，y     
        var endX = cols-1-start;
        var endY = rows-1-start;
        //   
        for(var i = start;i<=endX;i++){
            result.push(matrix[start][i])
        }
        //   
        if(start<endY){
            for(var i = start+1;i<=endY;i++){
                result.push(matrix[i][endX])
            }
        }        
        //   
        if(startendY){
            for(var i = endX-1;i>=start;i--){
                result.push(matrix[endY][i])
            }
        }

        //   
        if(start){
            for(var i = endY-1;i>=start+1;i--){
                result.push(matrix[i][start])
            }
        }

        start++
    }
    return result;
}
module.exports = {
    printMatrix : printMatrix
};

 
20.min関数を含むスタック

var result=[]
function push(node)
{
    // write code here
    return result.push(node)
}
function pop()
{
    // write code here
    return result.pop()
}
function top()
{
    // write code here
    return result.length>0?result[result.length-1]:null;
}
function min()
{
    // write code here
    if(result.length==0||result==null) return;
    var min=result[0];
    result.map(function(a){
        if(a<min){
            min=a;
        }
    })
    return min;
}

 
21.スタックの圧入、ポップアップシーケンス

function IsPopOrder(pushV, popV)
{
    // write code here
    var tmp=[];
    for(var i=0,j=0;i){
        tmp.push(pushV[i]);
        while(tmp.length&&tmp[tmp.length-1]==popV[j]){
            tmp.pop();
            j++;
        }
    }
    return tmp.length==0;
}

 
22.二叉木を上から下に印刷する

function PrintFromTopToBottom(root)
{
    // write code here
     if(root==null) return [];
    var result=[];    
    result.push(root.val);
    function travel(root){
        if(root.left==null && root.right==null) return;
        if(root.left!=null) result.push(root.left.val)
        if(root.right!=null) result.push(root.right.val)
        if(root.left!=null) travel(root.left);
        if(root.right!=null) travel(root.right);
    }
    travel(root);
    return result;
}

 
23.二叉樹の検索とその後の遍歴

function VerifySquenceOfBST(sequence)
{
    // write code here
    if(sequence.length<=0) return;
    return test(sequence,0,sequence.length-1)
}
function test(sequence,start,end){
    if(start>=end) return true;
    var i=end-1;
    while(i>=start && sequence[i]>sequence[end]){
        i--;
    }
    for(var j=i;j>=start;j--){
        if(sequence[j]>sequence[end]){
            return false;
        }
    }
    return test(sequence,start,i)&&test(sequence,i+1,end-1)
}

 
24.二叉樹と中和のいずれかの値の経路

function FindPath(root, expectNumber)
{
    // write code here

    var result=[];
    if(root==null) return result;
    dfs(root,0,[]);
    function dfs(root,current,path){
        current+=root.val;
        path.push(root.val)
        if(current==expectNumber && root.left==null && root.right ==null){
            result.push(path.slice(0))
        }
        if(root.left!=null){
            dfs(root.left,current,path)
        }
        if(root.right!=null){
            dfs(root.right,current,path)
        }
        path.pop()
    }
    return result;
}

 
25.複雑なチェーンのコピー

function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}
function Clone(pHead)
{
    // write code here    
    if (!pHead) {
        return null;
    }
    //      
    var node = new RandomListNode(pHead.label);
    node.random = pHead.random;
    //       
    node.next = Clone(pHead.next);
    return node;
}

 
26.二叉サーチツリーと双方向リンク表

function Convert(pRootOfTree)
{
    // write code here
    if(pRootOfTree==null){
        return null;
    }
    var lastNode=null;
    lastNode=convertNode(pRootOfTree,lastNode);
    var head=lastNode;
    while(head && head.left){//     
        head=head.left;
    }
    return head;
}
function convertNode(root,lastNode){
    if(root==null) return;
    if(root.left){//   
        lastNode=convertNode(root.left,lastNode)
    }
    root.left=lastNode;
    if(lastNode){
        lastNode.right=root;
    }
    lastNode=root;
    if(root.right){//   
        lastNode=convertNode(root.right,lastNode)
    }
    return lastNode;
}

 
27.文字列の配列

function Permutation(str)
{
    // write code here
    var result=[];
    if(str.length<=0){
        return [];
    }
    var sortTemp='';
    var arr = str.split('');
    result=sortString(arr,sortTemp,[]);
    return result

}
function sortString(arr,sortTemp,result){
    if(arr.length==0){
        result.push(sortTemp)
    }else{
        var isRepeat={};
        for(var i=0;i){
            if(!isRepeat[arr[i]]){
                var temp=arr.splice(i,1)[0];//       
                sortTemp+=temp;
                sortString(arr,sortTemp,result);
                arr.splice(i,0,temp);//  
                sortTemp=sortTemp.slice(0,sortTemp.length-1)//  
                isRepeat[temp]=true;
            }
        }
    }
    return result;
}

 
28.配列中の出現回数が半分以上の数字

function MoreThanHalfNum_Solution(numbers)
{
    // write code here   
    var obj={};
    var len = numbers.length;
    numbers.map(function(num){
        if(obj[num]){
            obj[num]++
        }else{
            obj[num]=1;
        }
    })
    for (var i in obj){
        if(obj[i]>Math.floor(len/2)) return i
    }
    return 0;
}

 
29.最小のk個数

function GetLeastNumbers_Solution(input, k)
{
    // write code here
    if(input==null){
        return null;
    }
    if(input.length<k){
        return [];
    }
    input.sort(function(a,b){
        return a>b;
    })
    var result = [];
    for(var i=0;i){
        result.push(input[i]);
    }
    return result;
}

 
30.連続サブ行列の最大和

function FindGreatestSumOfSubArray(array)
{
    // write code here
    if (array.length === 0) return 0;
  var max = array[0];
  var temp = array[0];
  for (var i = 1; i < array.length; i++) {
    temp = temp > 0 ? temp + array[i] : array[i];
    max = max > temp ? max : temp;
  }
  return max；
}

 
31.1からnまでの数字のうち1の出現回数

function NumberOf1Between1AndN_Solution(n)
{
    // write code here
     if(n<0){
        return 0;
    }
    var count=0;
  for(var i = 1;i<=n;i++){
    var number = i;
    while(number>0){
        if(number%10==1){
            count++;
        }
        number = Math.floor(number/10);
       // console.log(number);
    }
  }
     
  return count;
    
}

 
32.配列を最小にする数

function PrintMinNumber(numbers)
{
    // write code here
    if (!numbers.length)
        return "";
    min=Number.POSITIVE_INFINITY;
    return Sort(numbers, 0);
}
 
function Sort(numbers, index) {
    for (var i = index, l = numbers.length; i < l; ++i) {
        var temp = numbers[i];
        numbers[i] = numbers[index];
        numbers[index] = temp;
 
        if (index != numbers.length - 1)
            Sort(numbers, index + 1, min);
        else {
            var tempS = numbers.join("").toString();
            if (min > tempS) {
                min = tempS;
            }
        }
 
        temp = numbers[i];
        numbers[i] = numbers[index];
        numbers[index] = temp;
    }
    return min;
}

 
33.丑数

function GetUglyNumber_Solution(index)
{
    // write code here
    var res = [],
        multiply2 = 0,
        multiply3 = 0,
        multiply5 = 0,
        nextIndex = 1
     
    res[0] = 1
     
    if(index <= 0)
        return 0
         
    while(nextIndex < index)
    {
        res[nextIndex] = min( res[multiply2] * 2, res[multiply3] * 3, res[multiply5] * 5 )
         
        while( res[multiply2] * 2 <= res[nextIndex] )
        {
            ++multiply2
        }
         
        while( res[multiply3] * 3 <= res[nextIndex] )
        {
            ++multiply3
        }
         
        while( res[multiply5] * 5 <= res[nextIndex] )
        {
            ++multiply5
        }
         
        ++nextIndex
    }
     
    return res[--nextIndex]
      
}
 
function min(a,b,c)
{
    var min
     
    min = (a < b) ? a : b
    min = (min < c) ? min : c
     
    return min
}

 
34.一回目の文字

function FirstNotRepeatingChar(str)
{
    // write code here
    if(!str){
        return -1;
    }
    var flag = {};
    var len = str.length;
    for(var i = 0;i){
        if(flag[str[i]]){
            if(flag[str[i]]>2){
                continue;
            }else{
                flag[str[i]]++;
            }
        }else{
            flag[str[i]] = 1;
        }
    }
    for(var i = 0;i){
        if(flag[str[i]] == 1){
            return i;
        }
    }
}
module.exports = {
    FirstNotRepeatingChar : FirstNotRepeatingChar
};

 
35.配列の逆順のペア

function InversePairs(data)
{
    // write code here
      if(!data || data.length < 2){
        return 0;
    }
    var copy = data.concat(), count = 0;
    count = MergeSort(data, copy, 0, data.length-1);
    return count % 1000000007;
}
function MergeSort(data, copy, start, end){
    if(end === start){
        return 0;
    }
    var len = Math.floor((end - start) / 2);
    var left = MergeSort(copy, data, start, start+len);
    var right = MergeSort(copy, data, start+len+1, end);
    var count = 0;
    var p = start+len, q = end, copyIndex = end;
    while(p >= start && q >= start+len+1){
        if(data[p] > data[q]){
            count += q - start - len;
            copy[copyIndex--] = data[p--];
        }else{
            copy[copyIndex--] = data[q--];
        }
    }
    while(p >= start){
        copy[copyIndex--] = data[p--];
    }
    while(q >= (start+len+1)){
        copy[copyIndex--] = data[q--];
    }
    return left + right + count;
}
module.exports = {
    InversePairs : InversePairs
};

 
36.二つのチェーンの最初の共通点

function ListNode(x){
    this.val = x;
    this.next = null;
}
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    var arr1 = [],
        arr2 = [],
        p1 = pHead1,
        p2 = pHead2,
        index = -1;
    while(p1){
        arr1.push(p1.val);
        p1 = p1.next;
    }
    while(p2){
        arr2.push(p2.val);
        p2 = p2.next;
    }
     
    for(var i = 0 ; i < arr1.length; i ++){
        var arr = arr1.slice(i);
        var str1 = arr.join("-");
        var str2 = arr2.join("-");
         
        if(str2.indexOf(str1) > -1){
            index = i;
            break;
        }
    }
     
    if(index < 0){return null;}
    var p = pHead1;
    while(index > 0){
        p = p.next;
        index --;
    }
    return p;
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};

 
37.並べ替え配列に数字が現れる回数

function GetNumberOfK(data, k)
{
    // write code here
    if (data == null) {
        return 0;
    }
 
    var leftIndex = leftIndexOfKeyInSortedArray(data, k);
    if (leftIndex == -1) {
        return 0;
    }
    var rightIndex = rightIndexOfKeyInSortedArray(data, k);
    return rightIndex - leftIndex + 1;
}
function leftIndexOfKeyInSortedArray(data, key) {
    if (data == null) {
        return -1;
    }
    var low = 0;
    var high = data.length - 1;
    var ret = -1;
    while (low <= high) {
        var mid = Math.floor((low + high) / 2);
        if (data[mid] == key) {
            ret = mid;
            high = mid - 1;
        } else if (data[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ret;
}
 
function rightIndexOfKeyInSortedArray(data, key) {
        if (data == null) {
            return -1;
        }
        var low = 0;
        var high =data.length - 1;
        var ret = -1;
        while (low <= high) {
            var mid = Math.floor((low + high) / 2);
            if (data[mid] == key) {
                ret = mid;
                low = mid + 1;
            } else if (data[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ret;
}
module.exports = {
    GetNumberOfK : GetNumberOfK
};

 
38.二叉樹の深さ

function TreeDepth(pRoot)
{
    // write code here
    if(pRoot == null){
        return 0;
    }
    var left = TreeDepth(pRoot.left)+1;
    var right = TreeDepth(pRoot.right)+1;
    return Math.max(left, right);

    
}

 
39.二叉樹のバランスを取る

var isBalanced = true;
 
function isBalancedCore(pRoot) {
  if (!pRoot) {
    return 0;
  }
  var leftCount = 0;
  var rightCount = 0;
  if (pRoot.left) {
    leftCount = isBalancedCore(pRoot.left);
  }
  if (pRoot.right) {
    rightCount = isBalancedCore(pRoot.right);
  }
  if (Math.abs(leftCount - rightCount) > 1) {
    isBalanced = false;
  }
  return leftCount > rightCount ? leftCount + 1 : rightCount + 1;
}
 
function IsBalanced_Solution(pRoot)
{
    // write code here
    if (!pRoot) {
      return true;
    }
    isBalancedCore(pRoot);
    var ret = isBalanced;
    isBalanced = true;
    return ret;
}
module.exports = {
    IsBalanced_Solution : IsBalanced_Solution
};

 
40.行列には一回だけの数字が表示されます.

function FindNumsAppearOnce(array)
{
    // write code here
    // return list,   [a,b]，  ab          
    var len = array.length,
        num1,
        num2,
        resXOR = 0,
        indexOf1
     
    if( len < 2 )
        return
    for(var i=0; i)
    {
        resXOR ^= array[i]
    }
     
    indexOf1 = find1( resXOR )
     
    for(var j=0; j)
    {
        if(IsBit1( array[j], indexOf1 ))
        {
            num1 ^= array[j]
        } else {
            num2 ^= array[j]
        }
    }
     
    return [ num1, num2 ]
}
 
function find1(bit)
{
    var index = 0
     
    while((bit & 1) == 0)
    {
        bit = bit >> 1
        index++
    }
     
    return index
}
 
function IsBit1(bit, index)
{
    var num = bit >> index
     
    return (num & 1)
}
module.exports = {
    FindNumsAppearOnce : FindNumsAppearOnce
};

 
41.とsの連続正の整数系列

function FindContinuousSequence(sum)
{
    // write code here
     var low=1,high=2;
    array=[];
    while(high>low){
        var cur=(high+low)*(high-low+1)/2;
        if(cur<sum){
            high++;
        }
        if(cur===sum){
            var arr=[];
            for(var i=low;i<=high;i++){
                arr.push(i);
            }
            array.push(arr);
            low++;
        }
        if(cur>sum){
            low++;
        }
    }
    return array;
}
module.exports = {
    FindContinuousSequence : FindContinuousSequence
};

 
41.とsの2つの数字

function FindNumbersWithSum(array, sum)
{
    // write code here
    var len = array.length,
        small = 0,
        big = len - 1,
        curSum = 0,
        curMul,
        mul = 9007199254740991,
        res = []
     
    if(len < 2)
        return res
         
    while(small < big)
    {
 
        curSum = array[small] + array[big]
 
        if(curSum == sum)
        {
            curMul = array[small] * array[big]
            if( curMul < mul )
            {
                mul = curMul
                res.push( array[small], array[big] )
            }
 
            small ++
 
        }
 
        if(curSum < sum)
        {
            small++
        } else if(curSum > sum)
        {
            big --
        }
    }
     
    return res
}
module.exports = {
    FindNumbersWithSum : FindNumbersWithSum
};

 
42.左回転文字列

function LeftRotateString(str, n)
{
    // write code here
    if(!str||n<0) return "";
     
    var strArr = str.split(""),
        len = strArr.length;
     
    if(n>len) return "";
     
    var front = strArr.slice(0, n).reverse(),
        behind = strArr.slice(n, len).reverse(),
        newArr = front.concat(behind);
        return newArr.reverse().join("");
     
}
module.exports = {
    LeftRotateString : LeftRotateString
};

 
43.単語の順序を反転

function ReverseSentence(str)
{
    // write code here
    if(!str||!str.trim()) return str;
    var strArr = str.split(" "), //      
        len = strArr.length;
 
    var start = 0,
        end = len - 1,
        temp;
    while (start < end) {
        temp = strArr[start];
        strArr[start] = strArr[end];
        strArr[end] = temp;
        ++start;
        --end;
    }
    return strArr.join(" ").trim();
}
module.exports = {
    ReverseSentence : ReverseSentence
};

 
44.トランプの順子

function IsContinuous(numbers)
{
    // write code here
     if (numbers.length==0) return false;
 
    //        
    numbers.sort(function(a, b) {
        return a - b;
    });
 
    var numberOfZero = 0, //0   
        numberOfGap = 0; //    
    var len = numbers.length;
    for (var i = 0; i < len && (numbers[i] === 0); ++i) {
        ++numberOfZero;
    }
 
    var small = numberOfZero,
        big = small + 1;
    while (big < len) {
        if (numbers[small] === numbers[big]) return false;
        numberOfGap += numbers[big] - numbers[small] - 1;
        small = big;
        ++big;
    }
    return numberOfGap <= numberOfZero ? true : false;
}
module.exports = {
    IsContinuous : IsContinuous
};

 
45.子供たちの遊び

function LastRemaining_Solution(n, m)
{
    // write code here
    if(n === 0) {
        return -1;
    }
    if(n === 1) {
        return 0;
    }
    return (LastRemaining_Solution(n-1, m)+m) % n;
}
module.exports = {
    LastRemaining_Solution : LastRemaining_Solution
};

 
46.1+2+3++nを求める

function Sum_Solution(n)
{
    // write code here
     // write code here
    if(n==1){
        return 1;
    }else{
        return n+Sum_Solution(n-1);
    }
}

 
47.足し算なしで足し算をする

function Add(num1, num2)
{
    // write code here
     var sum = 0, tmp;
    do{
        sum = num1^num2;
        tmp = num1&num2;
        num1 = tmp << 1;
        num2 = sum;
    }while(tmp != 0);
    return sum;
}

 
48.文字列を整数に変換する

function StrToInt(str)
{
    // write code here
    if(/[a-zA-Z]/.test(str)){
        return 0;
    }
    var reg = /([\+|\-]?\d+)/;
    if(reg.test(str)){
        str = str.replace(reg, "$1");
        return str;
    }else{
        return 0;
    }
}
module.exports = {
    StrToInt : StrToInt
};

 
49.配列内で繰り返される数字

function duplicate(numbers, duplication)
{
    // write code here
    //       ~              duplication[0]
    //    True/False
    if(numbers==null) return false;
    if(numbers.length==1) return false;
    for(var i=0;i){
        if(numbers.indexOf(numbers[i]) != numbers.lastIndexOf(numbers[i])){
            duplication[0]=numbers[i];
            return true;
        }
    }
    return false;
    // write code here
    //       ~              duplication[0]
    //    True/False
}
module.exports = {
    duplicate : duplicate
};

 
50.積配列の構築

function multiply(array)
{
    // write code here
     var B=[];
    B[0]=1;
    B[1]=array[0];
    for(var i=2;i){
        B[i]=B[i-1]*array[i-1];
    }
    var sum=1;
    for(var i=array.length-2;i>=0;i--){
        sum=sum*array[i+1];
        B[i]=B[i]*sum;
    }
    return B;
}
module.exports = {
    multiply : multiply
};

 
51.正規表現のマッチング

//s, pattern     
function match(s, pattern)
{
    // write code here
     var patt=new RegExp('^'+pattern+'$');
  return   patt.test(s);
}
module.exports = {
    match : match
};

 
52.数値を表す文字列

//s   
function isNumeric(s)
{
    // write code here
    var reg = !isNaN(Number(s));
    return reg
}
module.exports = {
    isNumeric : isNumeric
};

 
53.文字ストリームの最初の重複しない文字

//Init module if you need
function Init()
{
    // write code here
    global.result = [];
    return global.result
}
//Insert one char from stringstream
function Insert(ch)
{
    // write code here
    if(result[ch]){
        result[ch]++
    } else {
        result[ch] = 1;
    }
}
//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
    // write code here
    for(var i in result){
        if(result[i] === 1){
            return i;
        };
    };
    return '#';
}
module.exports = {
    Init : Init,
    Insert : Insert,
    FirstAppearingOnce: FirstAppearingOnce
};

 
54.チェーン表の中環の入り口結点

function EntryNodeOfLoop(pHead)
{
    // write code here
    var cur =pHead,obj={},lt;
    while(cur!=null){
        lt=cur.val;
        if(!obj[lt]){
            obj[lt]=1;
            cur=cur.next;
        }else{
            return cur;
        }
    }
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

 
55.チェーンの重複する結点を削除する

function deleteDuplication(pHead)
{
    // write code here
    if(pHead === null) return null;
    if(pHead !== null && pHead.next === null) return pHead;
      
    var first = {
        val: -1,
        next: pHead
    }
        cur = pHead,
        prev = first;
      
    first.next = pHead;
    while(cur !== null && cur.next !== null){
        if(cur.val === cur.next.val){
            var val = cur.val;
            while(cur !== null && cur.val === val){
                cur = cur.next;
                prev.next = cur;
            };
        } else {
            prev = cur;
            cur = cur.next;
        };
    };
    return first.next;
}
module.exports = {
    deleteDuplication : deleteDuplication
};

 
56.二叉樹の次の結点

function GetNext(pNode)
{
    // write code here                     
    if(pNode==null){
        return null;
    }
    //     ：1         ，                 ，                          
     
    if(pNode.right!=null){
        var p=pNode.right;
        while(p.left!=null){
            p=p.left;
        }
        return p;
    }
    //2                                          
    while(pNode.next!=null){
        if(pNode==pNode.next.left){//                         
            return pNode.next;
        }
        pNode=pNode.next;
    }
}
module.exports = {
    GetNext : GetNext
};

 
57.対称な二叉樹

function isSymmetrical(pRoot)
{
    // write code here
    //                   ，               
    //                          
     
    if(pRoot==null){
        return true;
    }
    return comRoot(pRoot.left,pRoot.right);
     
}
 
function comRoot(left,right){
    if(left==null&&right==null){
        return true;
    }
    if(left!=null&&right!=null){
        if(left.val==right.val){
            return comRoot(left.left,right.right)&&comRoot(left.right,right.left);
        }
    }
}
module.exports = {
    isSymmetrical : isSymmetrical
};

 
58.二叉樹をタイプ別に印刷する

function Print(pRoot)
{
    var result=[];
    // write code here
    if(pRoot==null){
        return result;
    }
    var queue=[];
    var nextLevel=0;
    queue.push(pRoot);
    var toBePrinted=1;
    var level=0;
    var arr=[];
    while(queue.length){
        var temp=queue.shift();
        toBePrinted--;
        arr.push(temp.val);
        if(temp.left){
               queue.push(temp.left);
            nextLevel++;
        }
        if(temp.right){
            queue.push(temp.right);
            nextLevel++;
        }
        if(toBePrinted==0){
            toBePrinted=nextLevel;
            nextLevel=0;
            level++;
            if(level%2==0){
                arr.reverse();
            }
            result.push(arr);
            arr = [];
        }
         
    }
    return result;
  
     
         
}

 
59.二叉樹を複数行に印刷する

function Print(pRoot)
{
    // write code here
    var res=[]
    if(!pRoot)return res
    var q=[]
    q.push(pRoot)
      
    while(q.length!=0){
        var l=0
        var h=q.length
        var arr=[]
        while(l++<h){
            var t=q.shift()
              
            arr.push(t.val)
            if(t.left)q.push(t.left)
            if(t.right)q.push(t.right)
        }
        res.push(arr)
    }
    return res
}

 
60.プロローグ二叉樹

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
var arr = [];
function Serialize(pRoot)
{
    // write code here
    if(pRoot==null){
        arr.push('a');
    }else{
        arr.push(pRoot.val);
        Serialize(pRoot.left);
        Serialize(pRoot.right);
    }
       
}
function Deserialize(s)
{
    // write code here
    var node = null;
    if(arr.length<1){
        return null;
    }
    var number = arr.shift();
    if(typeof number == 'number'){
        node = new TreeNode(number);
        node.left = Deserialize(arr);
        node.right = Deserialize(arr); 
    }
    return node;
}

 
61.二叉サーチツリーのk番目の結点

function KthNode(pRoot, k)
{
    // write code here
    var arr=[];
    if(pRoot===null||k<1){
        return null;
    }
    function midInorder(root){
        if(root.left!==null){
             midInorder(root.left);
        }
        arr.push(root);
        if(root.right!==null){
            midInorder(root.right);
        }
    }
    midInorder(pRoot);
    return arr[k-1];
}

 
62.データストリームの中央値

var arr=[];
function Insert(num)
{
   arr.push(num);
   arr.sort();
}
function GetMedian(){
   /*if(arr==null){
        return 0；
    }*/
    var len=arr.length;
    if(len==0){
        return 0;
    }
    if(len%2==1){
        return arr[Math.floor(len/2)];
    }
    if(len%2==0){
        //var a=Math.floor(len/2);
       // var b=Math.ceil(len/2);
        //return (arr[a]+arr[b])/2;
        return (arr[len/2]+arr[len/2-1])/2;
    }
     
}

 
63.スライドウィンドウの最大値

function maxInWindows(num, size)
{
    // write code here
    var q=[];
    var max=-1;
    var v=[];
    var i=0;
    if(size>num.length||size<=0) return v;
    while(size--){
        q.push(num[i]);
        if(num[i]>max) max=num[i];
        i++;
    }
    v.push(max);
    while(i<num.length){
        var m=q.shift();
        if(m==max){
            max=getMax(q);
        }
        q.push(num[i]);
        if(num[i]>max) max=num[i];
        v.push(max);
        i++;
    }
    return v;
}
function getMax(q){
    var max=-1;
    for(var i=0;i){
        if(q[i]>max){
            max=q[i];
        }
    }
    return max;
}

 
64.行列のパス

function hasPathCore(matrix, rows, cols, row, col, path, pathIndex, visited) {
  var hasPath = false;
  if (row < rows && col < cols && row >= 0 && col >= 0 && visited[row][col] === false) {
    if (matrix[row * cols + col] === path[pathIndex]) {
      visited[row][col] = true;
      if (pathIndex === path.length - 1) {
        hasPath = true;
      } else {
        hasPath = hasPathCore(matrix, rows, cols, row - 1, col, path, pathIndex + 1, visited) ||
                  hasPathCore(matrix, rows, cols, row + 1, col, path, pathIndex + 1, visited) ||
                  hasPathCore(matrix, rows, cols, row, col - 1, path, pathIndex + 1, visited) ||
                  hasPathCore(matrix, rows, cols, row, col + 1, path, pathIndex + 1, visited);
         
        if (!hasPath) {
          visited[row][col] = false;
        }
      }
    }
  }
  return hasPath;
}
 
function hasPath(matrix, rows, cols, path)
{
    // write code here
    if (path.length <= 0) {
      return true;
    }
    var visited = [];
    var temp = [];
    var i, j;
    for (i = 0; i < rows; i++) {
      temp = [];
      for (j = 0; j < cols; j++) {
        temp.push(false);
      }
      visited.push(temp);
    }
    for (i = 0; i < rows; i++) {
      for (j = 0; j < cols; j++) {
        if (hasPathCore(matrix, rows, cols, i, j, path, 0, visited)) {
          return true;
        }
      }
    }
    return false;
}
module.exports = {
    hasPath : hasPath
};

 
65.ロボットの動き範囲

 function movingCount(threshold, rows, cols)
{
    // write code here
    var count=0;
    if(threshold<1||rows<1||cols<1){
        return count;
    }
    var visited=[];
    for(var i=0; i){
        visited[i]=[];
        for(var j=0; j){
            visited[i][j]=false;
        }
    }
    count = movingCountSum(threshold,0,0,rows,cols,visited);
    return count;
}
function movingCountSum(threshold,m,n,rows,cols,visited){
    var count = 0;
    if(m>=0&&m=0&&nthreshold){
        visited[m][n]=true;
        count = 1+movingCountSum(threshold,m,n-1,rows,cols,visited)+
                movingCountSum(threshold,m,n+1,rows,cols,visited)+
                movingCountSum(threshold,m-1,n,rows,cols,visited)+
                movingCountSum(threshold,m+1,n,rows,cols,visited);
    }
    return count;
}
function getSum(m,n){
    var str = [].concat(m,n).join('');
    var sum=0;
    for(var i=0; i){
        sum+=Number(str[i]);
    }
    return sum;
}
 
module.exports = {
    movingCount : movingCount
};

 
転載先:https://www.cnblogs.com/xulei-web/p/7441105.html