几道算法题记录

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
})

rl.question('请输入要转换的值：', function(answer) {
    
    if (/^\d+$/.test(answer)) {
        var str = encode(answer);
        console.log(answer + ' 的 varint 二进制是：' + str);       
    } else {
        console.log('input is error. please input again.')
    }   

    rl.close();
});

function encode(num) {
    // 0x80 的二进制表示是 1000 0000, 通过 | 运算最高位补 1 
    var MSB = 0x80;

    // 0x7F的二进制表示是 0111 1111
    var REST = 0x7F;
    var MSBALL = ~REST;

    var out = [];
    var offset = 0;

    while (num & MSBALL) {
        out[offset++] = ((num & 0xFF) | MSB).toString(2);
        num >>>= 7;
    }

    out[offset] = ('00000000' + (num | 0).toString(2)).slice(-8);

    return out;
}

/*
关于ZigZag编码：
正数
假设数据类型为byte的正数11，其二进制表示为： 00001011
数据左移一位: 00010110
符号位（正数的符号为0）放到最后一位： 00010110
负数
假设数据类型为byte的负数-11，其二进制在计算机中是用补码表示的，计算过程如下
正数原码： 00001011
反码： 11110100
补码（反码加1）： 11110101
 
处理过程：
左移一位： 11101010
符号位放到最后一位: 11101011
除最后一位外全部取反: 00010101
*/

function encode32(n) {
    return (n << 1) ^ (n >> 31);
}

function decode32(n) {
    return (n >>> 1) ^ -(n & 1);
    // return (n >> 1) ^ (~(n & 1) + 1);
}

~(function() {
    var arr = [parseInt(0x268cb43, 16), parseInt(0x7ff, 16), parseInt(0x2b7b, 16), parseInt(0x123a, 16), parseInt(0xf6, 16), parseInt(0x282, 16)];
    // var arr = [parseInt('00010110', 2), parseInt('00010101', 2)];
    // var arr = [parseInt('1000000010000100010001000010001', 2)];

    for (var i = 0, len = arr.length; i < len; i++) {        
        var a = decode32(arr[i]);
        var b = encode32(a);

        console.log(a, b, arr[i])
    }
})();

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

rl.question('请输入值：', function(answer) {
    rl.close();

    var str = answer.slice(1, -1);

    if (!/^\d.+\d$/.test(str)) {
        console.log('输入错误');
        return;
    }

    var arr = str.split(',');
    var result = canJump(arr);

    console.log(result ? 'true' : 'false');
});

// https://allenmistake.top/2019/04/20/leetcode55dp/
function canJump(arr) {
    for (var i = 0, len = arr.length; i < len; i++) {
        arr[i] = parseInt(arr[i], 10);
    }

    var lastPos = arr.length -1;
    for (var i = arr.length - 1; i >= 0; i--) {
        if (i + arr[i] >= lastPos) {
            lastPos = i;
        }
    }

    return lastPos == 0;
}

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

rl.question('请输入 P 的值：', function(answer) {
    rl.close();

    if (!/\%$/.test(answer)) {
        console.log('输入错误');
        return ;
    }   

    var result = P2C(answer);
    console.log(result)
});

// http://www.yoonper.com/post.php?id=104
function P2C(P) {
    // 先计算出次数
    P = parseFloat(P) * 0.01;
    
    var low = 0;
    var high = P;

    var last = 0;

    var min = 1 / Math.pow(10, 14);
    while (true) {
        // 二分查找
        var middle = (high + low) / 2;
        var pr = parseFloat(C2P(middle)) * 0.01;

        if (Math.abs(pr - last) <= min) break;
        
        pr > P ? (high = middle) : (low = middle);
        
        last = pr;
    }

    return Math.floor(middle * 100) + '%';
}

function C2P(C) {   
    var expectationP = 0;
    var successP = 0;
    var currentP = 0;

    // C * N >= 100;
    var times = Math.ceil(1 / C);
    for (var n = 1; n <= times; n++) {
        currentP = (1 - successP) * Math.min(1, C * n);
        successP += currentP;
        expectationP += currentP * n;
    }
    
    return Math.round(1 / expectationP * 100) + '%';
}

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

rl.question('请输入值：', function(answer) {
    rl.close();

    var arr = answer.split(',');
    var binaryArr = [];
    for (var i = 0, len = arr.length; i < len; i++) {
        binaryArr.push(parseInt(arr[i], 16));
    }

    var result = validUTF8(binaryArr);    
    console.log('result : ', result ? '1' : '0');

    var cnt = calcAmount(binaryArr);
    console.log('amount :', cnt);
});

// https://www.cnblogs.com/grandyang/p/5847597.html
// https://leetcode.com/problems/utf-8-validation/discuss/87464/Bit-Manipulation-Java-6ms
function validUTF8(arr) {
    if (arr.length < 1) return false;

    var left = 0;
    for (var i = 0, len = arr.length; i < len; i++) {
        var d = arr[i];

        if (left == 0) {
            if ((d >> 5) == 0b110) left = 1; // 后面跟一个字节  110xxxxx 10xxxxxx
            else if ((d >> 4) == 0b1110) left = 2;  // 后面跟二个字节 1110xxxx 10xxxxxx 10xxxxxx
            else if ((d >> 3) == 0b11110) left = 3; // 后面跟三个字节 11110xxx 10xxxxxx 10xxxxxx
            else if ((d >> 7) == 1) return false;
        } else {
            if ((d >> 6) != 0b10) return false; // 非标识符不是以 10 开头
            
            --left;
        }
    }
    
    return left == 0;
}

function calcAmount(arr) {
    var count = 0;

    for (var i = 0, len = arr.length; i < len; i++) {
        var d = arr[i];

        // 以 0 开头且
        if ((d >> 7) == 0) {
            count++;
            continue;
        }

        if ((d >> 5) == 0b110) {
            // 以110开头
            if ((i + 1 < arr.length) && (arr[i + 1] >> 6) == 0b10) {
                ++count;
                
                i += 1;
            }
        } else if ((d >> 4) == 0b1110) {
            // 以1110开头
            if (
                (i + 2 < arr.length) && 
                (arr[i + 1] >> 6) == 0b10 && 
                (arr[i + 2] >> 6) == 0b10
            ) {
                ++count;
                
                i += 2;
            }
        } else if ((d >> 3) == 0b11110) {
            if (
                (i + 3 < arr.length) && 
                (arr[i + 1] >> 6) == 0b10 && 
                (arr[i + 2] >> 6) == 0b10 && 
                (arr[i + 3] >> 6) == 0b10
            ) {
                ++count;

                i += 3;
            }
        }
    }

    return count;
}