算法 -- Part1

质数因子

输入描述：

输入一个整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

示例1

输入：

1
180

输出：

1
2 2 3 3 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const readline = require('readline');
 
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    let target = parseInt(line)
    let res = []
    for (let i = 2; i <= Math.sqrt(line, 2); i++) {
        while (target % i === 0) {
            target /= i
            res.push(i)
        }
    }
    //  若本身就是质数的
    if (target > 1) res.push(target)
    console.log(res.join(' ').trim())

});

背包问题

见牛客 HJ16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//背包公式：
// if (j < w[i]) {
//     dp[i][j] = dp[i-1][j]
// } else {
//     dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i])
// }
//还有就是因为是从1开始赋值的，所以数组需要第一项需要赋值
//整体思路就是先用背包公式套没有附件的，然后再加判断是否有附件
let line = readline()
let money = parseInt(line.split(' ')[0])  // 自己拥有的钱
let sum = parseInt(line.split(' ')[1]) // 自己可以买多少物品
let index = 0 //用于接收输入的数组
let goodSatisfaction = [-1] //自己购买这件物品的满意度
let goodIsKey = [-1] //自己购买的这件物品是不是主件
let goodSum = [-1] //自己购买这件物品的价格
while (index < sum) { // 使用循环把数据拿到
    let line1 = readline().split(' ')
    goodSum.push(parseInt(line1[0])) //每件物品的价格
    goodSatisfaction.push(parseInt(line1[1])) //每件物品的满意度
    goodIsKey.push(parseInt(line1[2])) //每件物品是否为主件
    index++
}
//构建dp数组
//构建二维dp数组，横坐标为自己买的物品数目，纵坐标为自己花费的价格，全部初始化为0
const test = (money, sum, goodSatisfaction, goodIsKey, goodSum) => {
    const dp = new Array(sum + 1).fill(0).map(() => new Array(money + 1).fill(0))
    //开始递推
    let res = 0
    for (let i = 1; i <= sum; i++) { //横坐标逐渐增加的过程，模拟自己的钱越来越多
        for ( let j = 0; j <= money; j++) { //纵坐标逐渐增加的过程，模拟自己能买物品的数量越来越多
            //如果是正常的背包问题现在套用公式即可，但是现在添加的是否为主副件
            if (!goodIsKey[i]) { //如果现在是主件
                if (j >= goodSum[i]) {
                    const sub = [] //收集主件后的附件
                    for (let k = 1; k <=goodIsKey.length; k++ ) {
                        if (goodIsKey[k] == i) {
                            sub.push(k) // 这个主件有几个附件，就以1，2的形式push进数组
                        }
                    }
                    //在没有附件的情况下就是套用背包公式dp数组
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-goodSum[i]] + goodSatisfaction[i] * goodSum[i])
                    //之后分类讨论，因为题目说了只有1，2附件就依次写出来
                    //如果有一个附件，比较是否买
                    if (sub[0] && j >= goodSum[i] + goodSum[sub[0]]) {
                        //判断是否买不买这件物品，还是基于背包公式的else部分
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goodSum[i] - goodSum[sub[0]]] + goodSatisfaction[i] * goodSum[i] + goodSatisfaction[sub[0]] * goodSum[sub[0]])     
                    }
                    if (sub[1] && j >= goodSum[i] + goodSum[sub[1]]) {
                        //如果有两个附件，比较是否买（注意是if依次判断）
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goodSum[i] - goodSum[sub[1]]] + goodSatisfaction[i] * goodSum[i] + goodSatisfaction[sub[1]] * goodSum[sub[1]])     
                    } //如果还有空余
                    if (sub.length == 2 && j >= goodSum[i] + goodSum[sub[1]] + goodSum[sub[0]]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goodSum[i] - goodSum[sub[0]] - goodSum[sub[1]]] + goodSatisfaction[i] * goodSum[i] + goodSatisfaction[sub[0]] * goodSum[sub[0]] + goodSatisfaction[sub[1]] * goodSum[sub[1]])
                    }
                    res = Math.max(res, dp[i][j])
                } else dp[i][j] = dp[i-1][j] //不要放进去
            } else dp[i][j] = dp[i-1][j] //不要放进去
        }
     }
    return res
}
console.log(test(money, sum, goodSatisfaction, goodIsKey, goodSum))

统计 IP 地址

统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开。

判断IP地址是否合法，如果满足下列条件之一即为非法地址

  • 数字段数不为4
  • 存在空段，即【192..1.0】这种
  • 某个段的数字大于255

判断子网掩码是否合法，如果满足下列条件之一即为非法掩码

  • 不是一个合格的IP地址
  • 在二进制下，不满足前面连续是1，然后全是0
  • 在二进制下，全为0或全为1

如何判断一个掩码地址是不是满足前面连续是1，然后全是0？

  • 二进制下全为0或者1 — 违法 err++
  • 直接找 str 中是否存在 01 子串 — 违法 err++

扁平数据结构转 Tree

https://juejin.cn/post/6983904373508145189

正则

大小写字母,数字,特殊字符中的至少3种.8位以上,正确返回true

1
let regEx  = /^(?![a-zA-Z]+$)(?![A-Z0-9]+$)(?![A-Z\W_]+$)(?![a-z0-9]+$)(?![a-z\W_]+$)(?![0-9\W_]+$)[a-zA-Z0-9\W_]{8,20}$/;

桶排序

排序算法

冒泡

冒泡

1
2
3
4
5
6
7
8
9
10
11
// 冒泡排序
function sortArray2 (nums) {
    for (let i = nums.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j+1]) {
                [nums[j], nums[j+1]] = [nums[j+1], nums[j]]
            }
        }
    }
    return nums
}

插入排序

将数组分为 已排序区 和 未排序区， 将 未排序区间 的元素拿到，然后在 已排序区间 寻找插队的位置即可。这里我们可以模拟一下过程，在前面是有序队伍的情况下，姗姗来迟的你 拿着预定好的号牌，依次和前面有序的人比较，发现你的号牌比他靠前，就跟他说，兄弟，我在你前面，我们换一下位置。直到插队到合适的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function sortArray3 (nums) {
    for (let i = 1; i < nums.length; i++) {
        let j = i - 1
        while (nums[j] > nums[j+1]) {
            [nums[j], nums[j+1]] = [nums[j+1], nums[j]]
            j--
        }
    }
    return nums
}
// 或者
function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

归并排序

一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 算法描述 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var sortArray = function(nums) {
    // 快速排序
    quickSort(0, nums.length-1, nums)
    return nums

};

var quickSort = function (start, end, nums) {
    if (start < end) {
        let mid = sort(start, end, nums)
        quickSort(start, mid-1,nums);
        quickSort(mid+1, end,nums);
    }
}


var sort = function (start,end,nums) {
    let privot = nums[end]
    let pIdx = end
    while (start < end) {
        // 先从左往右（因为基准点在右边） 找比基准值大的，停止
        while (privot >= nums[start] && start < end) {
            start++
        }
        // 从右往左 找比基准值小的，停止
        while (privot <= nums[end] && start < end) {
            end--
        }
        if (start >= end ) break
        // 交换 start 和 end 两个指针的位置
        [nums[start], nums[end]] = [nums[end], nums[start]]
    }
    // 将重叠点和基准点交换位置
    [nums[end], nums[pIdx]] = [nums[pIdx], nums[end]]
    return end
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] > maxValue) {
          // 输入数据的最大值
          maxValue = arr[i];              
      }
      if (arr[i] < minValue) {
          // 输入数据的最小值
          minValue = arr[i]               
      }
    }

    // 桶的初始化
    // bucketSize 这个如何理解？ 每一段的数值范围
    var n = arr.length
    bucketSize = Math.max(1, Math.floor((maxValue - minValue) / (n-1))) || bucketSize
  
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = []; // 二维数组
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
         // 对每个桶进行排序，这里的排序方法自己选择哦铁汁
        insertionSort(buckets[i]);                   
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                    
        }
    }

    return arr;
}

括号生成

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
1
2
3
4
5
6
7
8
9
10
11
12
var generateParenthesis = function(n) {
    let res = []
    // 广度遍历
    function fn (leftNums, rightNums, str){
        if (leftNums === n && rightNums === n) res.push(str)
        if (leftNums < n) fn(leftNums + 1, rightNums, str + '(')
        if (rightNums < leftNums) fn(leftNums, rightNums + 1, str + ')')
    }
    fn(0, 0, '')
    return res
  
};

找最大k个数

两数之和

三数之和

算法
#面试 #算法
算法 -- Part1
http://example.com/2023/08/03/算法-00/
作者
lyric
发布于
2023年8月3日
许可协议