首页 > 编程语言 >算法练习题-系列一

算法练习题-系列一

时间：2024-01-13 19:45:45浏览次数：36  
标签：练习题 arr 系列 nums len 算法 let return const

目录

柯里化

实现柯里化函数

var currying = function(fn) {
    // fn 指官员消化老婆的手段
    var args = [].slice.call(arguments, 1);
    // args 指的是那个合法老婆
    return function() {
        // 已经有的老婆和新搞定的老婆们合成一体，方便控制
        var newArgs = args.concat([].slice.call(arguments));
        // 这些老婆们用 fn 这个手段消化利用，完成韦小宝前辈的壮举并返回
        return fn.apply(null, newArgs);
    };
};

// 下为官员如何搞定7个老婆的测试
// 获得合法老婆
var getWife = currying(function() {
    var allWife = [].slice.call(arguments);
    // allwife 就是所有的老婆的，包括暗渡陈仓进来的老婆
    console.log(allWife.join(";"));
}, "合法老婆");

// 获得其他6个老婆
getWife("大老婆","小老婆","俏老婆","***蛮老婆","乖老婆","送上门老婆");

// 换一批老婆
getWife("超越韦小宝的老婆");

柯里化函数作用

  1. 参数复用；2. 提前返回；3. 延迟计算/运行

扁平化

请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果

// 输入
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
// 输出
[1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]
n = 1

方法一: Array.flat

方法二: 递归

/* 
1. 创建一个递归函数 flattening，该函数接受数组 nums 和层级 l 作为参数
2. 在 flattening 中，我们使用 for...of 循环来迭代 nums 数组的元素
3. 对于每个元素，我们检查它是否是数组以及层级 l 是否在指定范围内（l > 0 且 l <= n）。
    如果元素是数组且满足层级条件，我们会递归调用 flattening，并将嵌套数组和层级减小 1（即 l - 1）传递给它。

    如果元素不是数组或层级条件不满足，我们将元素推送到结果数组 res 中
*/
// 递归
var flat = function (arr, n) {
    const res = [];
    const flatting = (nums, l) => {
        for(const num of nums) {
            if(Array.isArray(num) && l > 0) {
                flatting(num, l-1);
            } else {
                res.push(num)
            }
        }
    }
    flatting(arr, n);
    return res;
};
// 队列
var flat = function (arr, n) {
    let nestedArrayElement = true; // 仍然有嵌套数组需要扁平化
    let queue; // 扁平化过程中存储元素
    let depth = 0; // 当前深度级别
    // 只要还有单个数组元素需要处理（nestedArrayElement 为 true），且深度小于 n
    while(nestedArrayElement && depth < n) {
        nestedArrayElement = false; 
        queue = [];
        // for 循环遍历数组 arr 中的每个元素
        for(let i = 0; i < arr.length; i++) {
            // 如果元素是数组，将其元素展开到队列 queue 中
            // 并将 nestedArrayElement 设置为 true，表示遇到嵌套数组
            if(Array.isArray(arr[i])) {
                queue.push(...arr[i]);
                nestedArrayElement = true; // 只要还有单个数组元素需要处理
            } else {
                queue.push(arr[i]);
            }
        }
        // 处理完数组 arr 的所有元素后，将数组 arr 更新为队列中的元素
        arr = [...queue];
        depth++; // 增加深度 depth
    }

    return arr;
};

[双指针]有序数组合并

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素

// var merge = function(nums1, m, nums2, n) {
//     let i = m - 1; // nums1 行尾
//     let j =  n -1; // nums2 行尾
//     let len = m + n - 1; // 记录被赋值的位置
//     while (i >= 0 && j >=0) {
//         if (nums1[i] > nums2[j]) {
//             nums1[len] = nums1[i]; 
//             i--;
//         } else {
//             nums1[len] = nums2[j];
//             j--;
//         }
//         len--;
//     }
//     if (j + 1 !== 0) {
//         let restNum2 = nums2.slice(0, j + 1);
//         nums1.splice(0, j + 1, ...restNum2);
//     }
//     return nums1;
// };

/**
解法二
 */

// 从后往前确定两组中该用哪个数字
var merge = function(nums1, m, nums2, n) {
    let len = nums1.length - 1;
    let i = m - 1;
    let j = n - 1;
    var update = function(i, j, vi, vj) {
        nums1[i] = vi;
        nums1[j] = vj;
    }
    // 第二个数组全都插入进去为止
    while (j >= 0) {
        while (i >= 0 && nums1[i] > nums2[j]) {
            update(i, len, 0, nums1[i]);
            i--;
            len--;
        }
        nums1[len] = nums2[j]
        j--;
        len--;
    }
    return nums1;
}

判断一个字符串是否是回文字符串

// 双指针 字符串的开头和结尾开始，向中间移动，并比较对应位置的字符是否相同。在比较字符时，可以将字符转换为小写字母来忽略大小写。
var isPalindrome = function(s) {
    s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    let left = 0;
    let right = s.length - 1;
    while(left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
};

[字符串]两个版本号 version1 和 version2

示例 1：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
示例 2：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"
示例 3：
输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
const compareVersion = function (version1, version2) {
    const versions1s = version1.split('.');
    const versions2s = version2.split('.');
    const v1Len = versions1s.length;
    const v2Len = versions2s.length;
    const len = Math.max(v1Len, v2Len);
    let flag = 0;

    for (let i = 0; i < len; i++) {
        // let x = 0, y = 0;
        // if (i < v1Len) {
        //     x = parseInt(versions1s[i])
        // }
        // if (i < v2Len) {
        //     y = parseInt(versions2s[i])
        // }
        // if (x > y) {
        //     flag = 1;
        // }
        // if (x < y) {
        //     flag = -1;
        // }
        if ((parseInt(versions1s[i]) || 0) > (parseInt(versions2s[i]) || 0)) {
            flag = 1;
            break;
        }
        if ((parseInt(versions1s[i]) || 0) < (parseInt(versions2s[i]) || 0)) {
            flag = -1;
            break;
        }
    }
    return flag;
};

[字符串]版本号大小比较排序 ['1.45.0','1.5','6','3.3.3.3.3.3.3'] => ['1.5','1.45.0','3.3.3.3.3.3','6']

function sortVersions(versions) {
  return versions.sort(compareVersion);
}

const versions = ['1.45.0', '1.5', '6', '3.3.3.3.3.3.3'];
const sortedVersions = sortVersions(versions);
console.log(sortedVersions);

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

示例 1:

输入: a = "11", b = "10"
输出: "101"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

// 逐位相加的方法，并考虑进位
var addBinary = function (a, b) {
    let result = '';
    let carry = 0;
    let i = a.length - 1;
    let j = b.length - 1;
    while (i >= 0 || j >= 0 || carry > 0) {
        const digitA = i >= 0 ? parseInt(a[i]) : 0;
        const digitB = j >= 0 ? parseInt(b[j]) : 0;
        const sum = digitA + digitB + carry;

        result = (sum % 2) + result;
        carry = Math.floor(sum / 2);

        i--;
        j--;
    }
    return result;
};

[双指针 哈希]无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

var lengthOfLongestSubstring1 = function(s) {
    if (s === '') {
        return 0;
    }
    if (s.length === 1) {
        return 1;
    }
    let i = 0; // 左指针
    let j = i + 1; // 右指针
    const results = []; // 记录长度 最终选择最长的输出

    while(j < s.length) {
        let temRes = s[i] + '';
        while (!temRes.includes(s[j]) && j < s.length) {
            temRes+= s[j];
            j++;
        }
        let curLen = j - i;
        results.push(curLen);
        i = i + 1;
        j = i + 1;
    }
    const max = results.reduce((pre, cur, initial) => {
        return pre > cur ? pre : cur;
    });
    return max;
};

var lengthOfLongestSubstring = function(s) {
    // hash集合
    const hash = new Set();
    let rp = -1; // 右指针
    let temp = 0; // 比较的结果
    const len = s.length;
    for (i = 0; i < len; i++) {
        if (i !== 0) {
            hash.delete(s[i - 1]);
        }
        while (rp + 1 < len && !hash.has(s[rp + 1])) {
            hash.add(s[rp + 1]);
            rp++;
        }
        temp = Math.max(temp, rp - i + 1);
    }
    return temp;
};

[哈希]两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

var twoSum1 = function(nums, target) {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
};

var twoSum2 = function(nums, target) {
    const len = nums.length;
    let rp = 0;
    for (let i = 0; i < len; i++) {
        rp = i + 1;
        while (rp < len) {
            if (nums[i] + nums[rp] === target) {
                return [i, rp];
            }
            rp++;
        }
    }
    return [];
};
// hash
var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        }
        map.set(nums[i], i);
    }
    return [];
};

[栈]有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false

/**
判断字符串是否有效的问题可以使用栈来解决。我们可以遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，检查栈顶元素是否与当前右括号匹配。如果匹配，则将栈顶元素弹出，继续遍历；如果不匹配或者栈为空，则说明字符串无效。最后，如果栈为空，且字符串遍历完毕，则字符串有效。
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const pairs = {
        '{': '}',
        '[': ']',
        '(': ')',
    };
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        } else {
            const top =  stack.pop();
            if (pairs[top] !== char) {
                return false;
            }
        }
    }
    return stack.length === 0;
};

[双指针]三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

解决这个问题的一种常见方法是使用双指针。首先，对数组进行排序，然后遍历排序后的数组。在遍历过程中，固定一个元素，然后使用双指针从当前元素的下一个位置和数组末尾开始向中间移动，寻找满足条件的三个元素

var threeSum = function (nums) {
    const result = [];
    let sortNums = nums.sort((a, b) => a - b);
    const len = sortNums.length
    for (let i = 0; i < len - 2; i++) {
        let m = i + 1;
        let n = len - 1;
        let cur = nums[i];
        while (m < n) {
            const sum = cur + nums[m] + nums[n];
            if (sum === 0) {
                result.push([cur, nums[m], nums[n]]);
                // 跳过重复的元素
                while (m < n && nums[m] === nums[m+1]) {
                    m++;
                }
                while (m < n && nums[n] === nums[n-1]) {
                    n--;
                }
                m++;
                n--;
            } else if(sum < 0) {
                m++;
            } else {
                n--;
            }
        }
    }
    return Array.from(new Set(result.map(JSON.stringify)), JSON.parse);
};

[回溯 递归] 全排列 (再A一遍)

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]

/**回溯算法来生成全排列。通过不断地选择一个数字，将其添加到当前排列中，并递归生成剩余数字的排列，然后撤销选择，继续尝试下一个数字，直到所有数字都被使用。最终，所有可能的排列都被生成并存储在 result 数组中，然后返回给调用者。
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
  const result = [];

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push(current.slice()); // 将当前排列添加到结果中
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      const num = remaining[i];
      current.push(num); // 将当前数字添加到当前排列中
      remaining.splice(i, 1); // 从剩余数字中移除当前数字
      backtrack(current, remaining); // 递归生成排列
      remaining.splice(i, 0, num); // 恢复剩余数字的原始顺序
      current.pop(); // 移除当前数字
    }
  }

  backtrack([], nums);
  return result;
}

[排序 二分]手撕快速排序

/*快速排序*/
function quikSort(arr) {    
    if (arr.length <= 1) {
        return arr;
    }
    //取中间数值
    var standardNum = arr.splice(Math.floor(arr.length / 2), 1);
    var leftArr = [];
    var rightArr = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= standardNum[0]) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }
    return quikSort(leftArr).concat(standardNum, quikSort(rightArr));
}
quikSort([5, 100, 6, 3, -12]); //[-12, 3, 5, 6, 100]
//冒泡
function sort(arr) {
    for(let i = 1; i < arr.length; i++) {
        for(let j = 0; j < i; j++) {
            if(arr[j] > arr[i]) {
                let temp;
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    console.log(arr)
    return arr;
}

标签：练习题,arr,系列,nums,len,算法,let,return,const
From： https://www.cnblogs.com/Iona/p/17962812

相关文章

  • 【教3妹学编程-算法题】构造限制重复的字符串
    3妹：“太阳当空照，花儿对我笑，小鸟说早早早，你为什么背上炸药包”2哥:3妹，什么事呀这么开森。3妹：2哥你看今天的天气多好啊，最近一周都是大晴天，艳阳高照2哥：是啊，天气不冷不热的，很适合生活3妹：据说南方的小土豆都跑到北方滑雪了，哈哈哈哈2哥：泼水成冰好玩是好玩，但是一定要注意防寒哦，看新闻都有......
  • 算法学习Day26组合总和、分割回文串
    Day26组合总和、分割回文串ByHQWQF2024/01/13笔记39.组合总和给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。说明：所有数字（包括target）都是正整数。解集......
  • 【SPFA】最短路的一种算法
    SPFA算法是在bellman-ford算法基础上优化而来，所以我们先讨论bellman-ford算法bellman-ford算法的核心是‘松弛’。那么什么是松弛呢？以下图为例：假设数组d[i]表示源点s到达结点i的最短路径长度，那么松弛指的就是当d[a]+w<d[b]，也就是说，这时候通过a到达b比原来的路径更......
  • （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的
    题目：思路：这一道题其实和高精度加法的思路是差不多的，都是使用算式进行模拟。重点：关于代码怎么写，在高精度加法那里还看不太出来（我也没有写），但是在高精度减法这里就完全可以看出来了。我们在加法算式里面，一般是A[i]+B[i]+t，但是也可以这么写：t+A[i]+B[i]，我们可以先写进位......
  • Binder系列-5-binder_mmap—1—mmap()分析
    一、manmmap1.函数声明#include<sys/mman.h>void*mmap(void*addr,size_tlength,intprot,intflags,intfd,off_toffset);intmunmap(void*addr,size_tlength);intmsync(void*addr,size_tlength,intflags)作用：将文件或设备向内存中进行映射或取消映......
  • VB6的OfficeMenu控件 - 开源研究系列文章
          这次将原来VB6中喜欢和使用到的OfficeMenu的控件做一个使用介绍。      上次介绍了VB6中的控件引擎，但是那个只针对基本的控件，这个OfficeMenu控件在当时是收费的，笔者找度娘好不容易才下载到一个免费版本，而且使用起来也非常的方便，在当时那个年代是笔者对于VB6......
  • 文心一言 VS 讯飞星火 VS chatgpt （170）-- 算法导论13.2 3题
    三、用go语言，设在图13-2左边一棵树中，a、b和c分别为子树a、β和γ中的任意结点。当结点x左旋之后，a、b和c的深度会如何变化？文心一言：在二叉树中，左旋操作是改变节点的子节点顺序。原本的子节点β变为新的左子节点，原本的左子节点γ变为新的右子节点。对于给定的节点a、b和c，我们首......
  • 文心一言 VS 讯飞星火 VS chatgpt （168）-- 算法导论13.2 1题
    一、用go语言，写出RIGHT-ROTATE的伪代码。文心一言：在计算机科学中，右旋转（RIGHT-ROTATE）是一种常见的操作，通常用于数组或链表。以下是一个使用Go语言实现右旋转的伪代码：funcrightRotate(arr[]int,kint)[]int{n:=len(arr)k%=n//防止k大于n的情况rev......
  • 微服务系列之分布式事务理论
    概述事务是由一组操作构成的可靠的独立的工作单元，事务具备ACID的特性，即原子性、一致性、隔离性和持久性。分类大多数情况下，分类是没有意义的一件事。但是分类可以一定程度上，加深理解。实现从实现角度来看，Java事务的类型有三种：JDBC事务、JTA（JavaTransactionAPI）事务、容器事务。一......
  • 基于融合语义信息改进的内容推荐算法。Improved content recommendation algorithm in
    引言路漫漫其修远兮，吾将上下而求索。每天一篇论文，做更好的自己。本文读的这篇论文为发表于2023年5月28日的一篇名为《基于融合语义信息改进的内容推荐算法》（基于融合语义信息改进的内容推荐算法）的文章，文章主要介绍了基于内容的推荐技术在电子商务和教育领域的广泛应用，以及传统基......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99