LeetCode题解3.longestSubstringWithoutRepeatingCharacters

题目地址

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目描述

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

用一个hashmap来建立字符和其出现位置之间的映射。

维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

（1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；

（2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；

（3）重复（1）（2），直到左边索引无法再移动；

（4）维护一个结果res，每次用出现过的窗口大小来更新结果res，最后返回res获取结果。

(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)

关键点

1. 用一个mapper记录出现过并且没有被删除的字符
2. 用一个滑动窗口记录当前index开始的最大的不重复的字符序列
3. 用res去记录目前位置最大的长度，每次滑动窗口更新就去决定是否需要更新res

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const mapper = {}; // 记录已经出现过的charactor
  let res = 0;
  let slidingWindow = [];

  for (let c of s) {
    if (mapper[c]) {
      // 已经出现过了
      // 则删除
      const delIndex = slidingWindow.findIndex(_c => _c === c);

      for (let i = 0 ; i < delIndex; i++) {
        mapper[slidingWindow[i]] = false;
      }

      slidingWindow = slidingWindow.slice(delIndex + 1).concat(c);
    } else {
      // 新字符
      if (slidingWindow.push(c) > res) {
        res = slidingWindow.length;
      }
    }
    mapper[c] = true;
  }
  return res;
};

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈

LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。

10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924

LeetCode题解微信红包

微信红包 如何分配 让每个人在数学期望上是一样的？在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。