js解leetcode(46)-简单

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