算法笔记：最大数，加油站，无重复最长子串
source link: https://zhuanlan.zhihu.com/p/94067390
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法笔记：最大数，加油站，无重复最长子串
本文列举的都是LeetCode上middle难度的题最大数（Largest Number）
>> 思想
排序>> 题目
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number/这里考的其实是排序，我们需要定义一种新的“大小”规则，这个规则是：
当两个数字组合在一起时候，会有两种组合，数值大的那个组合的第一个数就是“大数”，第二个数就是“小数”。
举个例子，9和888这两个数字，会产生两种组合，9888 和 8889，我们知道，888 > 9，但是在这里，9放在前面会让组合的数值整体变大，所以在这个大小比较规则里，9才是“大数”，而888是“小数”。
我们可以根据上面的比较规则编写一个大小比较的函数，然后把它传递给一个排序函数，当然不同语言的机制不一样，但是大体是类似的
在JavaScript里面，array.sort方法就接受一个排序函数，这个函数先后有两个参数num1和num2，分别代表待排序数组里的任意两个值，而返回值则决定了排序的时候哪一个参数会排在前面，返回负数则num1在num2前面，返回正数则num1在num2后面。
// 排序函数
function sortBy(num1, num2) {
const str1 = num1 + '';
const str2 = num2 + '';
// 数字组合1
let result1 = str1 + str2;
// 数字组合2
let result2 = str2 + str1;
// 将字符串数字转化为数字类型
result1 = Number(result1);
result2 = Number(result2);
// 比较大小，返回负数则num1在num2前面
// 返回正数则num1在num2后面
if (result1 >= result2) {
return -1;
} else {
return 1;
}
}
// 排序后拼接成字符串输出
var largestNumber = function (nums) {
// 特殊处理，如果每个数都是0，那么返回的"00","000"等显然是非法的，要统一返回0
if (nums.every(num => num === 0)) return "0";
// 对数组排序
nums.sort(sortBy);
// 将数组拼接成字符串
return nums.join("");
};
无重复字符的最长子串
Longest Substring Without Repeating Characters
>> 思想
滑动窗口 | 哈希表 | 双指针>> 题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 2:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters>> 目的
题目暴力解出是会超时的，所以这一题考的是计算效率和性能
>> 思路
滑动窗口 + 哈希表 + 双指针
>> 具体
滑动窗口 && 双指针
- 用两个指针：左游标和右游标，分别表示当前“无重复子串”的左边界和右边界，然后两个游标都会分别按不同的逻辑流程右移，构成了滑动窗口
- 然后每次移动时，也即窗口滑动时，判断一下这个子串长度是否要覆盖之前的最大长度就可以了
哈希表
关键在于无重复这一点到底该如何判断和处理，我们从一个中间过程来思考：
- 有字符串：baca
- 上一个滑动窗口：bac
- 下一个字符： a
- 得出的下一个滑动窗口: ca
为什么下一个滑动窗口是 ca 呢？ 这是因为a的加入和之前的前一个a重复了，所以呢，前一个a字符连同之前的b构成的ba字段都要抛弃，才能得到我们要的无重复
那么这些无重复的字符怎么存储呢？ 答案是： 哈希表
如图所示
Code
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
// 如果字符串小于1，那么肯定没有重复字符，所以直接返回长度就可以
if (s.length <= 1) {
return s.length;
}
// 哈希表，存储每个字符的数量
let map = new Map();
map.set(s.charAt(0), 1);
let start = 0, end = 1;
let maxLen = 0, maxStr = null;
// 当到达字符串结尾则跳出循环
while (end < s.length) {
const c = s.charAt(end);
let startC = s.charAt(start);
// 当前子串没有这个字符，则加入，子串长度 + 1
if (!map.has(c)) {
map.set(c, 1);
} else {
// 当前子串已经有这个字符了，则子串中前一个字符之前的要抛弃
// 'bac'(上一个子串) + 'a'（新字符） => 'ca'（下一个子串,ba被抛下）
const count = map.get(c) + 1;
map.set(c, count);
while (map.get(c) > 1) {
startC = s.charAt(start);
if (startC === c) {
map.set(c, 1);
} else {
map.delete(startC);
}
// 左游标前进
start++;
}
}
// 右游标前进
end++;
// 当前子串长度 = 右游标 - 左游标
if (end - start >= maxLen) {
maxStr = s.slice(start, end);
maxLen = end - start;
}
}
return maxLen
};
加油站(gas station）
>> 思想
贪心算法>> 题目
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明
- 如果题目有解，该答案即为唯一答案。
- 输入数组均为非空数组，且长度相同。
- 输入数组中的元素均为非负数。
Example
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gas-station首先，我们的思路是，车如果想要持续开下去，那么，到达每一个站的时候，加满油后的车油的存余量肯定要大于或等于到达下一个站所需要的耗油量。
那么我们会有一个直接的想法，就是把gas和cost两个数组相减，然后等下一步处理，我们假设gas和cost数组如下图所示，那么：
rests数组得到rests数组后，接下来怎么做？
那当然是从出发的某一个索引开始，走完整个rests数组的长度，然后不断计算rests元素的累加值，这个累加值在走到的任何一个数组元素节点都要 >= 0, 如果一次遍历满足这个条件，那么就说明可以走完，然后把初始的rests的数组下标返回就可以了
但是如果当前这个出发点不行，我们就要换下一个出发点再试一次，如果我们有n个元素，就要尝试n次，这样无疑是低效的
>> 低效的做法
>> 通过贪心的思想进行改进
我们发现一点，假设从初始点出发后能经过不止一个车站，这说明，刚开始的那个车站，所对应的rests数组元素肯定是>=0的（如果是负的那么车在第一站出发就没有油停在中间了）。这说明如果我们计算到没油的位置时还没有走完一圈的话，那就说明：在这段出发点到结束点间的任何一个车站出发，都不可能走完一圈的（因为总的油量更少了）。
通过这种贪心思想改造后，我们就少了很多个遍历轮次了，如下图所示（大家可以对下上下两幅图的区别）
var canCompleteCircuit = function (gas, cost) {
// 存储每个车站的净油量：本站加满油 - 到达下一个车站耗油
const rests = [];
const len = gas.length;
// 初始化rests
for (let i = 0; i < gas.length; i++) {
rests[i] = gas[i] - cost[i];
}
// 用来判断是否走完了一圈
let tryCount = 0;
// 出发点
let start = 0;
// tryCount < len这个外层判断条件是有点问题的，我待会修改一下
while (tryCount < len) {
let index = start;
let rest = rests[start];
let end = index;
let flag = false;
while (rest >= 0) {
// next表示下一个加油站，加上%取余构成循环数组
// 可以从数组尾部再次走到头部
let next = (index + 1) % len;
// 从出发点走完一圈，成功，返回出发点索引
if (next === end) {
return start;
}
// 获得下一个车展的信心
rest += rests[next];
index = next;
}
// 上一次尝试失败了,重置start,增加tryCount
start = index + 1;
tryCount++;
}
// 全部尝试失败，无法走完一圈，返回 -1
return -1
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gas-station
备注：虽然运行通过了，但突然发现我这个外层while循环是有点问题的，待会再改一下，hhh
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK