欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

js解leetcode(46)-简单

程序员文章站 2022-03-11 11:59:24
1.逐步求和得到正数的最小值题目:给你一个整数数组 nums。你可以选定任意的正数 startValue 作为初始值。你需要从左到右遍历 nums数组,并将 startValue 依次累加上nums数组中的值。请你在确保累加和始终大于等于 1 的前提下,选出一个最小的正数作为 startValue 。思路:题目的要求,是对数组进行累加,并要求累加的和永远大于等于1.所以只需要对数组进行累加,计算累加过程中的最小值即可。注意的是该数要是正数,所以最小值是1/** * ......

1.逐步求和得到正数的最小值

题目:

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组,并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下,选出一个最小的 正数 作为 startValue 。

思路:题目的要求,是对数组进行累加,并要求累加的和永远大于等于1.所以只需要对数组进行累加,计算累加过程中的最小值即可。注意的是该数要是正数,所以最小值是1

/**
 * @param {number[]} nums
 * @return {number}
 */
var minStartValue = function(nums) {
      let min = 0;
  let sum = 0;
  for (const n of nums) {
    sum += n;
    min = sum < min ? sum : min;
  }
  return 1 - min;
};

2.重新格式化字符串

题目:

给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母。

请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同。也就是说,字母后面应该跟着数字,而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串;如果无法按要求重新格式化,则返回一个 空字符串 。

思路:先计算字符串中字母和数字的数量,判断是否能格式化,然后穿插即可

/**
 * @param {string} s
 * @return {string}
 */
var reformat = function(s) {
  const n = [];
  const u = [];
  for (const v of s) {
    if (v.charCodeAt() < 90) {
      n.push(v);
    } else {
      u.push(v);
    }
  }
  if (Math.abs(n.length - u.length) > 1) return "";
  let l1, l2;
  if (n.length >= u.length) {
    l1 = n;
    l2 = u;
  } else {
    l1 = u;
    l2 = n;
  }
  const res = [];
  while (l1.length && l2.length) {
    res.push(l1.shift());
    res.push(l2.shift());
  }
  res.push(...l1, ...l2);
  return res.join("");
};

3.分割字符串的最大得分

题目:

给你一个由若干 0 和 1 组成的字符串 s ,请你计算并返回将该字符串分割成两个 非空 子字符串(即 左 子字符串和 右 子字符串)所能获得的最大得分。

「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

思路:指针法。先计算字符串中1的数量,然后遍历字符串,得分为左侧0的数量和右侧1的数量

/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function(s) {
  const l = s.length;
  let max = 0;
  let left = 0;
  let right = 0;
  for (const n of s) {
    if (n == "1") {
      right++;
    }
  }
  for (let i = 0; i < l - 1; i++) {
    if (s[i] == "0") {
      left++;
    } else {
      right--;
    }
    max = Math.max(max, left + right);
  }
  return max;
};

4.拥有最多糖果的孩子

题目:

给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

思路:找出最大值即可

/**
 * @param {number[]} candies
 * @param {number} extraCandies
 * @return {boolean[]}
 */
var kidsWithCandies = function(candies, extraCandies) {
  const max = Math.max(...candies);
  return candies.map((item) => {
    return item + extraCandies >= max;
  });
};

5.旅行终点站

题目:

给你一份旅游线路图,该线路图中的旅行线路用数组 paths 表示,其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路,因此只会有一个旅行终点站。

思路:这题有点像拓扑排序,但是比拓扑排序简单很多。

因为不存在循环,也只有一个旅行终点,所以只需要找到一个节点,有入度但是没有出度即可

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function(paths) {
  const map = new Map();
  const set = new Set();
  for (const [from, to] of paths) {
    if (map.get(from)) {
      map.get(from).push(to);
    } else {
      map.set(from, [to]);
    }
    set.add(to);
  }
  for (const key of set) {
    if (!map.get(key)) return key;
  }
};

 

本文地址:https://blog.csdn.net/weixin_42733155/article/details/109272829