算法分类刷题

链表

• 两数相加 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head = new ListNode(0);
    // 虚拟头结点,其实也可以理解成另起一个新链表存储结果
    let current = head;
    let carry = 0;
    while(l1 || l2 || carry) {
        let v1 = l1? l1.val : 0;
        let v2 = l2? l2.val : 0;
        let sum = v1 + v2 + carry;
        carry = Math.floor(sum / 10);
        // 在新链表中存储结果
        current.next = new ListNode(sum % 10);
        current = current.next;
        l1 = l1? l1.next : null;
        l2 = l2? l2.next : null;
    }
    return head.next;
};

• 进阶两数相加 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    // 这个题和两数相加相比，其实就是多了一个入栈操作（因为这里是顺序的也就是从链表末位开始加和进位，但是两数相加就是逆序相加）
    // 大致思想是这样，创建两个栈分别存储两个链表的数
    let stack1 = [], stack2 = [];
    while(l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while(l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    let p = null, carry = 0;
    while(stack1.length || stack2.length || carry) {
        let sum = (stack1.pop() || 0) + (stack2.pop() || 0) + carry;
        let newNode = new ListNode(sum % 10);
        // 反转链表是在这里反的
        newNode.next = p;
        p = newNode;
        carry = Math.floor(sum / 10)
    }
    return p;
};

• 反转链表 (opens new window)

// 递归
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head === null || head.next === null) return head;
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

// 迭代
var reverseList2 = function(head) {
    // prev是上一个，curr是当前节点
    let prev = null, curr = head;
    while(curr) {
        // 因为断建，所以要预先存储这个next
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

• 链表比对

字符串

• 有效括号 (opens new window)
• 字符串中出现最多的字母

    var str = 'asdasddsfdsfadsfdghdadsdfdgdasd'
    str = str.split('');
    console.log(str);
    var newStr = {};
    // 数组去重 和计算出现的次数
    str.forEach(function (item) {
        if (newStr[item]) {
            newStr[item]++;
        } else {
            newStr[item] = 1;
        }
    })
    var max=0;
    var strkey=null;
    for(var key in newStr){
         if(newStr[key]>max){
            max=newStr[key];
            strkey=key;
         }
  }
   console.log("最多的字符是" + strkey);
  console.log("出现的次数是" + max);

• 有效回文 (opens new window)

// 正则
var isPalindrome = function(s) {
    s= s.replace(/[^A-Za-z0-9]/g, '').toLowerCase()
    let str = s.split("").reverse().join("")
    return str === s
};
// 双指针
var isPalindrome = function(s) {
    let str = s.toLowerCase();
    let len = str.length;
    let arr = [];
    for(let i=0; i<len; i++) {
        // 48-57小写  97-122大写
        if (str.charAt(i) >= 97 && str.charAt(i) <= 122) arr.push(str[i]);
        if(str.charAt(i) >= 48 && str.charAt(i) <= 57) arr.push(str[i]);
    }
    if(arr === []) return true;
    str = arr.join('');
    str2 = arr.reverse().join('');
    if(str === str2) return true;
    return false;
};

• 括号匹配 (opens new window)

var isValid = function(s) {
    const len = s.length;
    if(len < 2) return false;
    const pairs = new Map([
        ['(', ')'],
        ['[', ']'],
        ['{', '}']
    ])
    const stack = [];
    for(let item of s) {
        if(pairs.has(s)) {
            // 遇到右括号则判断右括号是否能和栈顶元素匹配
            if(!stack.length || stack[stack.length-1] !== pairs.get(item)) return false;
            stack.pop()
        } else {
            stack.push(item); //如果遇到左括号入栈
        }
    }
    return !stack.length; //循环结束的时候还要判断栈是否为空
};

树