3. 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。   请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 解法1 思路:使用双层循环,外层循环取字符串s的每个位置,内层循环取外层循环的值至字符串末尾。在内层循环中创建一个范围为0-255的boolean数组用来判断字符是否重复出现,这比HashMap更加轻量。最后,使用一个名为maxLen的变量存放最终结果,我们在内层循环更新这个变量。 解法2 解法一采用了双重循环,时间复杂度是O(n^2)的,我们可以使用滑动窗口方法,维护一个[i, j),0<=i<j<=|s|的窗口,确保窗口内的字串不含重复字符。窗口的前沿是j,后沿是i。前沿滑动,直到加入到窗口内的字符出现重复。此时,我们滑动窗口后沿,直到窗口内不含重复字符。我们在窗口前沿滑动时,计算maxLen = max(maxLen, i – j). 因为是左闭右开区间,直接用i-j就是窗口的大小。 参考:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/

Read more

2. 两数相加

题目描述 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807 https://leetcode-cn.com/problems/add-two-numbers/ 思路1 首先链表是倒叙的,这就启发了我们可以用按位相加的方法逐步地求得结果。链表l1与l2相加,对应位相加后大于10,我们需要向前进位。下面的实现思路较为清晰,且易理解,但是有点笨拙。因为这涉及了三次的链表扫描。 直接将l1与l2对应位相加 扫描相加后的结果,如果大于等于10,向前进位 重新扫描,将添加的多余节点剔除 对于这种解法涉及到3次扫描,运行时间为29ms,“我的提交执行用时已经战胜 93.99 % 的 java 提交记录”。我们还有优化的空间,争取一次扫描就能够完成计算。 思路2 我们能不能只用一个while循环就实现整个算法所需要的流程呢?我们使用while循环,条件为链表l1与l2任意之一遍历到尽头。在while内部有三种可能 l1与l2均未遍历到尽头 只有l1未遍历到尽头 只有l2未遍历到尽头 对于情况1,我们只需要将相应位置到数相加,保存的新建的链表节点中即可。需要注意的是,我们不能直接使用“=”覆盖新建链表节点到val字段,而是应该使用“+=”操作符。这样做是为了利用上,上次循环产生到进位符。对于情况2与3,我们用上次进位符与l1或l2到节点值相加即可。 为了处理相加后可能产生的进位情况,我们在后面判断新建节点的值是否大于等于10.若大于等于10,下一个新建的节点赋予初值1,否则赋初值0.

Read more