aras-ax / algorithm Goto Github PK

View Code? Open in Web Editor NEW

0.0 2.0 0.0 53 KB

常用算法JS实现，LeetCode算法题

JavaScript 100.00%

algorithm's Introduction

Algorithm

常用算法 JS 实现，LeetCode 算法题

位运算

&（按位与）

两个都为真才为真

1&1=1 , 1&0=0 , 0&1=0 , 0&0=0

3&5 = 1 <=> 011&101 = 001

&&（逻辑与）

左右两边的表达式为真则为真，且&&左边的表达式为真的情况下才计算右边的表达式

|（按位或）

一个为真就为真

1|0 = 1 , 1|1 = 1 , 0|0 = 0 , 0|1 = 1

6||2 = 6 <=> 0110||0010 = 0110

||（逻辑或）

两边的表达式有一个为真则为真，且&&左边的表达式为真的情况下不去计算右边的表达式

^（异或运算符）

同为假，异为真

1^0 = 1 , 1^1 = 0 , 0^1 = 1 , 0^0 = 0

5^9 = 12 <=> 0101^1001 = 1100

>>（右移运算符）

5>>2的意思为5的二进制位往右挪两位，正数左边补0，负数补1

0101 >> 2 -> 0001 = 1 

-5>>2 
// -5的二进制表示 1111 1011
源码: 0000 0101
取反: 1111 1010
补码: 1111 1011 (补码=取反+1)
 
-5>>2: 1111 1110
-1 : 1111 1101
取反: 0000 0010  
-5>>2 = -2

-2 = 1111 1111
-2>>2: 1111 1111
-1 : 1111 1110
取反: 0000 0001  
-5>>2 = -1

<<（左移运算符）

5<<2的意思为5的二进制位往左挪两位，右边补0

0101 << 2 -> 010100 = 20

~（取反运算符）

取反就是1为0,0为1

~5 = -6 <=> 0000 0101 -> 1111 1010

排序算法

查找算法

顺序查找

顺序查找算是最简单的了，无论是有序的还是无序的都可以，也不需要排序，只需要一个个对比即可，但其实效率很低.

function search(arr, value){
    for(let i = 0, l = arr.length - 1; i < l; i++){
        if(arr[i] === value){
            return i;
        }
    }
    return -1;
}

// 使用哨兵，免去每次的越界判断
function search(arr, value){
    let l = arr.length - 1;
    if(arr[l] === value){
        return l;
    }
    let i = 0;
    while(arr[i++] !== value);
    return i === l + 1 ? -1 : i-1;
}

二分查找

二分法查找适用于大的数据，但前提条件是数据必须是有序的，他的原理是先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找

function binarySearch(arr, value){
    let start = 0,
        end = arr.length - 1;
    
    while(start <= end){
        // let mid = (start + end) >> 1; //数据可能会溢出
        let mid = start + ((end - start)>> 1);
        if(arr[mid] === value){
            return mid;
        } else if(arr[mid] > value){
            end = mid - 1;
        } else{
            start = mid + 1;
        }
    }

    return -1;
}

// 递归写法
function binarySearch(arr, value){
    let start = 0,
        end = arr.length - 1;
    
    return searchmy(arr, start, end, value);
}

function searchmy(arr, start, end, value){
    if(start > end){
        return -1;
    }
    let mid = start + ((end - start)>>1);
    if(arr[mid] === value){
        return mid;
    }else if(arr[mid] > value){
        return searchmy(arr, start, mid-1, value);
    }else {
        return searchmy(arr, mid+1, end, value);
    }
}

插值查找

插值查找与二分查找的区别是，我们比较值得位置不同，二分查找是与中间值进行比较，但是如果我们知道要查找的值大概在数组的最前面或最后面的时候使用二分法查找显然是不明智的，这时候可以选择插值查找。插值查找的时候我们比较的不是中间值，是mid = start + (value - arr[start])/(arr[end] - arr[start])*(end - start)。

function insertSearch(arr, value){
    let start = 0,
        end  = arr.length - 1;

    while(start <= end){
         if (arr[end] == arr[start]) {
            if (arr[end] == value){
                return end;
            }
            else {
                return -1;
            }
        }

        let mid = start + Math.floor((value - arr[start])/(arr[end] - arr[start])*(end - start));
        if(arr[mid] === value){
            return mid;
        } else if(arr[mid] > value){
            end = mid - 1;
        } else{
            start = mid + 1;
        }
    }
    return -1;
}

斐波那契查找

使用场景

algorithm's People

Contributors

Watchers

algorithm's Issues

最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解答

var largestNumber = function(nums){
    nums.sort((a, b) => (b.toString() + a.toString()) - (a.toString() + b.toString()));
    return nums[0] === 0 ? '0' : nums.join('');
}

//或者
var largestNumber = function(nums) {
    quickSort(nums);
    return nums.join('').replace(/^0+/, '0');
};

function quickSort(nums, left = 0, right = nums.length - 1) {
    if (left >= right) {
        return;
    }
    let l = left,
        r = right,
        mid = Math.floor((l + r) / 2);
    mid = nums[mid] + '';

    while (l <= r) {
        while (l <= r && compare(nums[l] + '', mid)) {
            l++;
        }

        while (l <= r && compare(mid, nums[r] + '')) {
            r--;
        }

        if (l <= r) {
            let temp = nums[l];
            nums[l++] = nums[r];
            nums[r--] = temp;
        }
    }

    quickSort(nums, left, r);
    quickSort(nums, l, right);
}

function compare(a, b) {
    return (a + b) > (b + a);
}

存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解答

function containsNearbyDuplicate(nums, k) {
    let hashMap = {};
    return nums.some((item, i) => {
        let j = hashMap[item];
        if (j !== undefined) {
            if (i - j <= k) {
                return true;
            }
        }
        hashMap[item] = i;
    });
}

各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶:

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

解答

function addDigits(num) {
    return num == 0 ? 0 : (num % 9 == 0 ? 9 : (num % 9));
}

寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组nums，其中nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

解答

var findPeakElement = function(nums) {
    let l = nums.length;
    if(l === 1){
        return 0;
    }
    
    if(nums[1] < nums[0]){
        return 0;
    }
    
    
    if(nums[l-2] < nums[l-1]){
        return l-1;
    }
    
    let left = 0,
        right = l - 1;
    
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(nums[mid - 1] < nums[mid] && nums[mid] > nums[mid+1]){
            return mid;
        }
        
        if(nums[mid] > nums[mid - 1]){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return -1;
};

同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明:

你可以假设s 和 t 具有相同的长度。

解答

// 解法一
function isSame(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }

    let hashA = {},
        hashB = {};
    for (let i = 0; i < s1.length; i++) {
        let a = s1[i],
            b = s2[i];

        if (hashA[a] === hashB[b]) {
            hashA[a] = hashB[b] = (hashB[b] || 0) + 1;
            continue;
        }
        return false;
    }
    return true;
}

//解法二
function isSame(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }

    let hashA = {},
        hashB = {};
    for (let i = 0; i < s1.length; i++) {
        let a = s1[i],
            b = s2[i];

        if (!hashA[a] && !hashB[b]) {
            hashA[a] = b;
            hashB[b] = a;
        } else if (hashA[a] !== b || hashB[b] !== a) {
            return false;
        }
    }

    return true;
}

最大公约数

给定两个数，求它们的最大公约数？

示例 1

输入：2, 3
输出：1

示例 2

输入：24, 16
输出：8

解答

//  greatest common divisor
function gcd(a, b) {
    if (a < b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }

    let c = a % b;
    while (c !== 0) {
        a = b;
        b = c;
        c = a % b;
    }

    return b;
}

旋转数组

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

解答

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
};

function reverse(nums, start, end){
    while(start < end){
        nums[start] = nums[start] ^ nums[end];
        nums[end] = nums[start] ^ nums[end];
        nums[start] = nums[start] ^ nums[end];
        start++;
        end--;
    }
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解答

动态规划问题，用斐波那契数

function climbStairs(n) {
    if (n <= 2){
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

// 或者
function climbStairs(n) {
    if (n < 0) return -1;
    if (n <= 2) return n;
    let first = 1, second = 2, sum = 0;
    while (n-- > 2) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return sum;
}

移动零

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

解答

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums){
    let i = 0,
        j = 0,
        l = nums.length;
    
    while(i < l){
        if(nums[i] !== 0){
            nums[j++] = nums[i];
        }
        i++;
    }
    while(j < l){
        nums[j++] = 0;
    }
}

分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解答

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    let res = [];

    if (s === null || s.length === 0) {
        return res;
    }

    let len = s.length,
        arr = [];

    function palindrome(s, start) {
        if (start === len) {
            res.push([...arr]);
            return;
        }
        for (let i = start; i < len; i++) {
            let curStr = s.substring(start, i + 1);
            if (isPalindrome(s, start, i)) {
                arr.push(curStr);
                palindrome(s, i + 1);
                arr.pop();
            }
        }
    }

    palindrome(s, 0);
    return res;
}


/**
 * 是否是回文
 */
function isPalindrome(s, left, right) {
    while (left < right && s[left] === s[right]) {
        left++;
        right--;
    }
    return left >= right;
}

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中

解答

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function lowestCommonAncestor(root,  p, q){
    while((root.val - p.val) * (root.val - q.val) > 0){
        root = root.val > p.val ? root.left: root.right;
    }
    return root;
}

Nim游戏

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

解答

function nim(num){
    return num%4 !== 0;
}

// 或
function nim(num){
    if(num <= 3 ){
        return true;
    }

    let res = [true, true, true];

    for(let i = 3; i < num; i++){
        res[i] = !(res[i-1] && res[i-2] && res[i-3]);
    }

    return res[num-1];
}

递增的三元子序列

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true

示例 2:

输入: [5,4,3,2,1]
输出: false

解答

贪心算法

var increasingTriplet = function(nums) {
    let l = nums.length,
        min,
        midMin,
        moreMin,
        moreLittleFlag = false;
    
    if(l < 3){
        return false;
    }
    min = midMin = moreMin= nums[0];
    for(let i = 1; i < l; i++){
        let item = nums[i];
        if(item > midMin){
            if(min === midMin){
                midMin = item;
            }else{
                return true;
            }
        }else if(item <= midMin && item > min){
            midMin = item;
        }else{
            if(!moreLittleFlag){
                moreLittleFlag = true;
                moreMin = item;
            }else{
                if(item > moreMin){
                    midMin = item;
                    min = moreMin;
                    moreLittleFlag = false;
                }else{
                    moreMin = item;
                }
            }
        }
    }
    
    return false;
};

赎金信 (ransom)

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

解答

function canConstruct(ransomNote, magazine) {
    let hasMap = {};
    magazine.split('').forEach(str => {
        if (hasMap[str]) {
            hasMap[str]++;
        } else {
            hasMap[str] = 1;
        }
    });

    for (let i = 0, l = ransomNote.length; i < l; i++) {
        if (hasMap[ransomNote[i]] && hasMap[ransomNote[i]] > 0) {
            hasMap[ransomNote[i]]--;
        } else {
            return false;
        }
    }
    return true;
}

2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 2^0 = 1

示例 2:

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

输入: 218
输出: false

解答

function  isPowerOfTwo(num) {
    return num > 0 &&  (n & (n - 1)) == 0;
}

快乐数

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

**示例: **

输入: 19
输出: true

解释:
1*1 + 9*9 = 82;
8*8 + 2*2 = 68;
6*6 + 8*8 = 100;
1*1 + 0*0 + 0*0 = 1;

解答

// 实现一 记录已计算过的值，出现重复则进入了循环，返回false
function isHappy(num) {
    let sum = 0,
        hash = {};
    while (!hash[num]) {
        hash[num] = true;
        while (num > 0) {
            let t = num % 10;
            sum += t * t;
            num = Math.floor(num / 10);
        }
        if (sum === 1) {
            return true;
        }
        num = sum;
        sum = 0;
    }
    return false;
}

// 实现二 循环链表，快指针和慢指针
function isHappy(num) {
    let slow = num,
        fast = calculate(num);

    while (slow !== fast) {
        slow = calculate(slow);
        if (slow === 1) {
            return true;
        }
        fast = calculate(fast);
        fast = calculate(fast);
        if (fast === 1) {
            return true;
        }
    }
    return slow === 1;
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

解答

function moveZeroes(nums){
    let count = 0;
    for(let i = 0, l = nums.length; i < l; i++){
        if(nums[i] === 0){
            count++;
        }else if(count > 0){
            nums[i - count] = nums[i];
            nums[i] = 0;
        }
    }
}

移除链表元素

删除链表中等于给定值val的所有节点。

示例：

输入:head =  1->2->6->3->4->5->6, target= 6
输出: 1->2->3->4->5

解答

// 节点对象
function listNode(val) {
    this.val = val;
    this.next = null;
}
// head = new ListNode(x)
function removeNode(head, target) {
    if (head === null) {
        return null;
    }

    head.next = removeNode(head.next, target);
    return head.val === target ? head.next : head;
}

最小公倍数

给定两个整数，求他们的最小公倍数？

示例 1

输入： 2, 3
输出：6

示例 2

输入： 2, 8
输出：8

解答

// least common multiple
function lcm(a, b) {
    if (a < b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }

    for (let i = a, l = a * b; i <= l; i += a) {
        if (i % b === 0) {
            return i;
        }
    }
    return 0;
}

存在重复的元素

给定一个整数数组，判定是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回true。如果数组中每个元素都不相同，则返回false。

示例 1

输入：[1, 2, 3, 1]
输出：true

示例 2

输入：[1, 2, 3, 4]
输出：false

解答

function hasRepeat(nums) {
    let hashMap = {};
    return nums.some(item => {
        if (hashMap[item]) {
            return true;
        }
        hashMap[item] = true;
    });
}

3的幂

给定一个整数，编写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 1
输出: true
解释: 3^0 = 1

示例 2:

输入: 27
输出: true
解释: 3^3 = 27

示例 3:

输入: 218
输出: false

解答

function isPowerOfThree(num) {
    if (num >= 1) {
        return num === 1 || (num % 3 === 0 && isPowerOfThree(num / 3));
    }
    return false;
}

区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

解决

class NumArray {
    constructor(nums) {
        this._init(nums);
    }

    _init(nums) {
        let sums = this.sums = [nums[0] || 0];
        for (let i = 1, l = nums.length; i < l; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
    }

    sumRange(start, end) {
        if (start === 0) {
            return this.sums[end];
        }
        return this.sums[end] - this.sums[start - 1];
    }
}

反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 迭代
var reverseList = function(head) {
    let last,
        next = head;

    while(next){
        next = head.next;
        head.next = last;
        last = head;
        head = next ? next : head;
    }

    return head;
};

// 递归
function reverseList(head) {
    if (head === null) {
        return null;
    }

    return reverse(head);
}

function reverse(head, last) {
    if (head) {
        let next = head.next;
        head.next = last;
        last = head;
        return reverse(next, last);
    }
    return last;
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解答

动态规划问题

function maxVal(val){
    return rob(val, val.length - 1);
}

function rob(val, index){
    if(index < 0){
        return 0;
    }
    return Math.max(rob(val, index - 2) + val[index], rob(val, index - 1));
}

maxVal([3,5,6,1,2,3]);

丑数

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

解答

function isUgly(num) {
    if (num <= 0) {
        return false;
    }
    if (num == 1) {
        return true;
    }
    if (num % 2 == 0) {
        return isUgly(num / 2);
    }
    if (num % 3 == 0) {
        return isUgly(num / 3);
    }
    if (num % 5 == 0) {
        return isUgly(num / 5);
    }
    return false;
}

两个数组的交集II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？

解答

function intersection(nums1, nums2) {
    let res = [],
        hasMap = {},
        count = 0;
    if (nums1.length > nums2.length) {
        let temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }

    count = nums1.length;
    nums1.forEach(num => {
        if (hasMap[num]) {
            hasMap[num]++;
        } else {
            hasMap[num] = 1;
        }
    });

    for (let i = 0, l = nums2.length; i < l; i++) {
        let cur = nums2[i];
        if (hasMap[cur] > 0) {
            res.push(cur);
            count--;
            hasMap[cur]--;
        }

        if (count <= 0) {
            break;
        }
    }

    return res;
}

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解答

var singleNumber = function(nums) {
    let res = 0;
    nums.forEach(item => {
        res ^= item;
    });
    return res;
};

两整数之和

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

输入: a = 1, b = 2
输出: 3

示例 2:

输入: a = -2, b = 3
输出: 1

解答

function getSum(a, b) {
    if (a === 0 || b === 0) {
        return a ^ b;
    }
    // 处理进位操作
    return getSum(a ^ b, (a & b) << 1);
}

猜数字大小

我们正在玩一个猜数字游戏。游戏规则如下：
我从 1 到 n 选择一个数字。你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：

-1 : 我的数字比较小
1 : 我的数字比较大
0 : 恭喜！你猜对了！
示例 :

输入: n = 10, pick = 6
输出: 6

解答

function guessNumber(n) {
    let i = 0,
        l = n;
    while (i < l) {
        let mid = i + Math.floor((i - i) / 2),
            res = guess(mid);
        if (res === 0) {
            return mid;
        } else if (res === 1) {
            i = mid + 1;
        } else {
            l = mid;
        }
    }
    return i;
}

字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何库，也不能直接将输入的字符串转换为整数形式。

解答

function stringPlus(str1, str2) {
    let l1 = str1.length - 1,
        l2 = str2.length - 1,
        res = '';

    // 从最后一位开始相加
    let carry = 0; // 进位
    while (l1 >= 0 || l2 >= 0) {
        let a = 0,
            b = 0,
            sum = 0;

        if (l1 >= 0) {
            a = +str1[l1--];
        }
        if (l2 >= 0) {
            b = +str2[l2--];
        }
        sum = a + b + carry;
        carry = Math.floor(sum / 10);
        res = sum % 10 + res;
    }
    return res;
}

找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：
-字母异位词指字母相同，但排列不同的字符串。
-不考虑答案输出的顺序。

示例 1:

输入:s: "cbaebabacd" p: "abc"
输出:[0, 6]
解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:s: "abab" p: "ab"
输出:[0, 1, 2]
解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

解答

function findAnagrams(s, p) {
    let res = [];
    if (!s || !p) {
        return res;
    }

    let hashMap = {};
    p.split('').forEach(item => {
        hashMap[item] = (hashMap[item] || 0) + 1;
    });

    let l = s.length,
        start = 0,
        end = 0,
        count = p.length;
    while (end < l) {
        let charAt = s[end++];
        // 若当前的字符串不存在，则直接掉过前面的字符，从下一个开始
        if (hashMap[charAt] === undefined) {
            while (start < end - 1) {
                hashMap[s[start++]]++;
                count++;
            }
            start = end;
        } else {
            if ((hashMap[charAt]--) > 0) {
                count--;
            }

            if (count === 0) {
                res.push(start);
            }

            // hashMap[s[start++]]++ >= 0保证start-end之间的字符对应的count是有效字符剩余个数
            if ((end - start) === p.length && hashMap[s[start++]]++ >= 0) {
                count++;
            }
        }
    }

    return res;
}

4的幂

给定一个整数，编写一个函数来判断它是否是 4 的幂次方。

示例 1:

输入: 1
输出: true
解释: 4^0 = 1

示例 2:

输入: 16
输出: true
解释: 4^2 = 16

示例 3:

输入: 32
输出: false

解答

function isPowerOfFour(num) {
    if (num >= 1) {
        return num === 1 || (num % 4 === 0 && ((num & num - 1) === 0) && isPowerOfFour(num / 4));
    }
    return false;
}

缺失的数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解答

function missingNumber(num){
    let res = 0,
        l = num.length;
    num.forEach((item, i) => {
        res ^= item ^ (i+1);
    });
    return res;
}

单词模式

给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false

说明:

你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

解答

function wordPattern(pattern, str){
    let words = str.split(' ');
    if(pattern.length !== words.length){
        return false;
    }

    let hashMap1 = {},
        hashMap2 = {};

    for(let i = 0, l = words.length; i < l; i++){
        let key = pattern[i], 
            word = words[i];

        if(hashMap1[key] !== hashMap2[word]){
            return false;
        }

        if(hashMap1[key] === undefined){
            hashMap1[key] = i;
            hashMap2[word] = i;
        }
    }
    return true;
}

计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解答

一个数如果是质数，那么他的倍数肯定都不是质数

function countPerim(n) {
    let hash = {},
        count = 0;
    for (let i = 2; i < n; i++) {
        if (hash[i]) {
            continue;
        }

        count++;
        for (let j = i; j < n; j = j + i) {
            hash[j] = true;
        }
    }
    return count;
}

x 的平方根

实现 sqrt(x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

解答

function intersection(nums1, nums2) {
    let res = [];
    nums1 = nums1.sort((a, b) => a - b);
    nums2 = nums2.sort((a, b) => a - b);

    let l1 = nums1.length,
        l2 = nums2.length,
        i = 0,
        j = 0,
        cur;

    while (i < l1 && j < l2) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else if (nums1[i] === nums2[j]) {
            if (nums1[i] !== cur) {
                res.push(nums1[i]);
                cur = nums1[i];
            }
            i++;
            j++;
        }
    }

    return res;
}

aras-ax / algorithm Goto Github PK

algorithm's Introduction

Algorithm

位运算

&（按位与）

&&（逻辑与）

|（按位或）

||（逻辑或）

^（异或运算符）

>>（右移运算符）

<<（左移运算符）

~（取反运算符）

排序算法

查找算法

顺序查找

二分查找

插值查找

斐波那契查找

algorithm's People

Contributors

Watchers

algorithm's Issues

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解决

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

解答

Recommend Projects

Recommend Topics

Recommend Org