Published on

基础算法题

Authors

找出这个数组中的所有素数

  • 1 什么是素数？
    素数（质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。换句话说，素数只能被1和自己整除。

  • 2 判断一个数是否为素数的基本方法是：

  • 如果数小于2，它不是素数。

  • 从2开始，一直到这个数的平方根，检查是否有任何数能整除它。

  • 如果找到任何一个除数，则不是素数。

  • 如果没有找到任何除数，则是素数。

//  最新一次更新时间为：2025-04-17
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

const isPrime = (num) =>{
   // 1 直接排除
   if(num === 1) return false
   // 2 直接返回true
   if(num === 2) return true
   // 排除偶数 能被2整除一定不是素数
   if(num % 2 ===0) return false
   // 遍历奇数 从3开始。这里这个num一定是奇数 
   for(let i = 3; i<=Math.sqrt(num);i+=2){
       if(num % i ===0) return false 
   }
   return true
}

const findPrime = (nums) =>{

  return nums.filter((i)=>isPrime(i))
}


const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];
const result = findPrime(nums)
console.log(result)

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

function isPrime(num) {
  if (num <= 1) return false
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false
  }
  return true
}

const result = function getPrimes(arr) {
  return arr.filter(isPrime)
}

console.log(result(numbers)) // [2,3,5,7,11,13]

其他答案：

// 面试者1
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
const main = (arr) => {
  return arr.filter((item) => {
    if (item <= 1) return false
    let count = 0
    for (let i = 1; i < item; i++) {
      if (item % i === 0) {
        count++
      }
    }
    return count < 2
  })
}

console.log(main(numbers))

// 面试者2
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
const main = (arr) => {
  return arr.filter((item) => {
    if (item <= 1) return false
    for (let i = 2; i < item; i++) {
      if (item % i === 0) {
        return false
      }
    }
    return true
  })
}

console.log(main(numbers))

Marscode 1. 找单独的数

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求

设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。 尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2

输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：数字 2 只出现一次，是独特的卡片。

样例3

输入：cards = [7, 3, 3, 7, 10]
输出：10
解释：10 是班级中唯一一个不重复的数字卡片。

function solution(cards) {
    // Edit your code here
    
    let result = 0
    for(let i=0;i<cards.length;i++){
        result = result^cards[i]
    }
    return result
}

function main() {
    // Add your test cases here
    console.log(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) === 4);
    console.log(solution([0, 1, 0, 1, 2]) === 2);
}

main();

解题思路

要解决这个问题，我们可以利用异或（XOR）操作的特性。异或操作有一个非常有用的性质：对于任何整数 x，x ^ x = 0，并且 x ^ 0 = x。这意味着如果我们对数组中的所有元素进行异或操作，所有出现两次的数字会相互抵消，最终剩下的就是那个只出现一次的数字。

  • 按位异或^

let a = 1

//1 两个相同的整数异或
a^a = 0

//2 异或0
a^0 = a


//3 两个不同的整数按位交换
let a = 5;
let b = 3;

a = a ^ b;
b = a ^ b;
a = a ^ b;

console.log(a); // 输出 3
console.log(b); // 输出 5

Marscode 2. 徒步旅行中的补给问题

问题描述

小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。幸运的是，小R在路途中每天都会经过一个补给站，可以先购买完食物后再消耗今天的1份食物。然而，每个补给站的食物每份的价格可能不同，并且小R在购买完食物后最多只能同时携带 K 份食物。

现在，小R希望在保证每天食物消耗的前提下，以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗？

输入

  • n 总路程需要的天数
  • k 小R最多能同时携带食物的份数
  • data[i] 第i天补给站每份食物的价格

输出

  • 返回完成这次徒步旅行的最小花费

测试样例

  • 样例1
输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
输出：9
  • 样例2
输入：n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]
输出：9
  • 样例3
输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
输出：10

解题


function solution(n, k, data) {
    // Edit your code here
    let stock = 0
    let cost = 0

    for(let i =0; i <n; i ++){
        const price = data[i];

        // 未来几天 更便宜的索引
        let cheaperDay = -1;
        for(let j = i+1; j < Math.min(n,i+k+1);j++){
            if(data[j] < price){
                cheaperDay = j;
                break
            }
        }

        // 到下次购买的天数
        const daysAhead = cheaperDay !== -1 ?cheaperDay - i : k;
        const daysLeft = n - i;
        const needToHave = Math.min(daysAhead,daysLeft)
        const desired = needToHave - stock
        let buy = Math.min(desired,k-stock)
        if(buy < 0) buy = 0
        
        cost += buy * price
        stock += buy
        stock--
    }

    return cost;
}

function main() {
    // Add your test cases here
    console.log(solution(5, 2, [1, 2, 3, 3, 2]));
}

main();

Marscode 3. 数字字符串格式化

问题描述

小M在工作时遇到了一个问题，他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式，并且保留小数部分。小M还发现，有时候输入的数字字符串前面会有无用的 0，这些也需要精简掉。请你帮助小M编写程序，完成这个任务。

测试样例

  • 样例1
输入：s = "1294512.12412"
输出：'1,294,512.12412'
  • 样例2
输入：s = "0000123456789.99"
输出：'123,456,789.99'
  • 样例3
输入：s = "987654321"
输出：'987,654,321'

解题

function solution(s) {
    // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
    // write code here
    
    const [intPart,decPart] = s.split('.')
    let result = intPart.replace(/(^0+)/g,'').replace(/\B(?=(\d{3})+(?!\d))/g,',')
    if(decPart){
        result=  result+'.'+decPart
    }
    return result ;
}

function main() {
    console.log(solution("1294512.12412") === '1,294,512.12412');
    console.log(solution("0000123456789.99") === '123,456,789.99');
    console.log(solution("987654321") === '987,654,321');
    console.log(solution("77134900601876576"))
}

main();

Marscode 4. 数字分组求偶数和

问题描述

小M面对一组从 1 到 9 的数字，这些数字被分成多个小组，并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。

numbers: 一个由多个整数字符串组成的列表，每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。 例如对于[123, 456, 789]，14个符合条件的数为：147 149 158 167 169 248 257 259 268 347 349 358 367 369。

测试样例

  • 样例1
输入：numbers = [123, 456, 789]
输出：14
  • 样例2
输入：numbers = [123456789]
输出：4
  • 样例3
输入：numbers = [14329, 7568]
输出：10

解题

function solution(numbers) {
  
  // Please write your code here
  const result = []

  const dfs = (index,path) =>{

    if(index === numbers.length){

      const digitSum = path.reduce((sum,current)=>sum+=parseInt(current),0)
      if(digitSum % 2 ===0){
        result.push(digitSum)
      }

      return
    }


    for(const ch of String(numbers[index])){
        dfs(index+1,[...path,ch])
    }
  }

  dfs(0,[])


  return result.length;
}

function main() {
  // You can add more test cases here
  console.log(solution([123, 456, 789]) === 14);
  console.log(solution([123456789]) === 4);
  console.log(solution([14329, 7568]) === 10);
}

main();
  • 简易执行草图帮助理解 img4
Discuss on Twitter • View on GitHub