JavaScript学习过程中遇到的经典算法题

说明：这个帖子旨在记录在学习JavaScript期间遇到的一些有趣的编程题。

平衡括号

题目描述：在编写代码并且编译时，难免会因为少写了一个’)’和被编译器报错。也就是说，编译器会去匹配括号是否匹配。当你输入了一个’(‘，很自然编译器回去检查你是否有另一个’)’符号与之匹配。如果所有的括号都能够成对出现，那么编译器是能够通过的。否则编译器会报错。

算法描述：创建一个空栈，读取字符给定的字符串序列直到结尾，如果字符是开放符号’(‘,’[‘,’{‘则入栈，如果是’)’,’]’,’}’,首先判断当前栈是否为空，如果为空，则返回false，如果不为空，则判断栈顶元素是否是当前字符匹配的括号，如果不匹配，则返回false，如果匹配，则讲当前栈顶元素弹出。依次循环遍历完字符串，如果此时栈为空，则该字符串是一个括号平衡的字符串。

//定义一个栈
function Stack(){
    let items = [];
    //压栈
    this.push=function(element){
        items.push(element);
    };
    //出栈
    this.pop=function(){
        return items.pop();
    };
    //返回栈顶元素
    this.peek = function(){
        return items[items.length-1];
    };
    //判断栈是否为空
    this.isEmpty = function(){
        return items.length ==0;
    }
}
//判断函数
function balanceSigned(str){
    var stack = new Stack();
    var arr = [...str];
    var flag = true;
    for(var i=0;i<arr.length;i++){
        switch(arr[i]){
            case '(':{
                stack.push(arr[i]);
                break;
            }
            case '[':{
                stack.push(arr[i]);
                break;
            }
            case '{':{
                stack.push(arr[i]);
                break;
            }
            case ')':{
                if(stack.isEmpty()){
                    flag = false;
                    return flag;
                }else if(stack.peek()!='('){
                    flag = false;
                    return flag;
                }else {
                    stack.pop();
                    break;
                }
            }
            case ']':{
                if(stack.isEmpty()){
                    flag = false;
                    return flag;
                }else if(stack.peek()!='['){
                    flag = false;
                    return flag;
                }else {
                    stack.pop();
                    break;
                }
            }
            case '}':{
                if(stack.isEmpty()){
                    flag = false;
                    return flag;
                }else if(stack.peek()!='{'){
                    flag = false;
                    return flag;
                }else {
                    stack.pop();
                    break;
                }
            }        
        }
    }
    flag = stack.isEmpty;
    return flag;
}

硬币找零

问题描述：给出要找零的钱数，以及可用的硬币面额，找到所需最少的硬币个数。

算法描述：采用贪心算法，从面额最大的硬币开始，拿尽可能多的这种硬币找零，当无法再拿更多的这种面值的硬币时，开始拿第二大价值的硬币。

function change(coins,amount) {
    //coins是面值数组，排序是为了防止给定的面值集合数组是无序的。
    //amount是需要找零的面值
    coins.sort((a,b)=>b-a);
    //最终结果放在res里面
    var res = [];
    //count是当前选择完后累计的钱数。
    var count = 0;
    for(var i =0;i<coins.length;i++){
        while(count+coins[i]<=amount){
            res.push(coins[i]);
            count+=coins[i];
        }
    }
    return res;
}

大数加法

问题描述：JavaScript和任何一门语言一样，对其数值的范围有限制。如果我们想要对一个超大的整数进行加法运算，但是又想输出一般形式，那么使用 + 是无法达到的一旦数字超过 Number.MAX_SAFE_INTEGER 数字会被立即转换为科学计数法，并且数字精度相比以前将会有误差。在此时就需要自己实现一套加法算法。

function sumBigNumber(a, b) {
  var res = '',
    temp = 0;
  a = a.split('');
  b = b.split('');
  while (a.length || b.length || temp) {
    temp += ~~a.pop() + ~~b.pop();//使用 ~~a 而不是Number(a)来进行格式转换。
    res = (temp % 10) + res;
    temp = temp > 9;
  }
  return res.replace(/^0+/, '');
}

算法解释：

1. 首先我们用字符串来保存大数，就保证了其在数学表示上不会发生变化。
2. 初始化res, temp变量来保存中间计算的结果，在将两个字符串split为数组，以便我们进行每一位的运算。
3. 循环的第一次就是进行 “个位” 的运算，将二者最末尾的两个数相加，由于每一位数字是0 - 9，所以需要进行进位，在进过取余数操作后，将结果保留在个位。
4. 判断 temp 是否大于 10，若是则将 temp 赋值为 true。
5. 在两个大数中的一个还有数字没有参与运算，或者前一次运算发生进位后，进行下一次循环。
6. 接着除了对新的两个数字相加还要加上 temp，若上次发生了进位，则此时 temp 为 true，JavaScript因为存在隐式转换，所以 true 转换为 1，我们借用 JavaScript的类型转换，完成了逻辑上的逢10进1操作。