Leetcode 3. Longest Substring Without Repeating Characters

继续做把第三题的解题思路放上来。第三题的目的是求字符串内最长的不重复子串,两个要求非常清晰。下面是题目的描述:

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.

思路:

假设子串的初始下标为 i,结束下标为 j。i 和 j 的初始值均为 0。j 开始一次往后遍历,如果这个字符串没有重复字符,那么 j 会一直走到最后,此时最长子串就是字符串本身。实际情况没有那么理想,我们主要分析这类场景。当处于 j 位置的字符和子串之前的字符重复(假设位置为 k),那么就应该停下,并且更新最长子串的长度(假设最长长度为 max),j 继续往后走,同时 i 的位置需要挪到重复字符之后,即 k+1 处。直到遍历到字符串的最后。

比如用第一个例子作为说明,初始状态 i = j = 0,最长子串长度 max = 0:

  1. j=0 处的字符是 a,无重复,当前子串长度为 1;
  2. j=1 处的字符是 b,无重复,当前子串长度为 2;
  3. j=2 处的字符是 b,无重复,当前子串长度为 3;
  4. j=3 处的字符是 a,发现重复,更新 max = 3,i = 0+1,当前子串长度为 3;
  5. j=4 处的字符是 b,发现重复,max 不变,i = 1+1,当前子串长度为 3;
  6. j=5 处的字符是 c,发现重复,max 不变,i = 2+1,当前子串长度为 3;
  7. j=6 处的字符是 b,发现重复,max 不变,i = 4+1,当前子串长度为 2;
  8. j=7 处的字符是 b,发现重复,max 不变,i = 6+1,当前子串长度为 1;

因此,"abcabcbb" 的最长子串长度是 3。

接下来我们写上代码:

func lengthOfLongestSubstring(s string) int {
	n := len(s)

	if n <= 1 {
		return n
	}

	tbl := make(map[byte]int, n)
	lo, longest, curr := 0, 0, 0

	for hi := 0; hi < n; hi++ {
		if k, ok := tbl[s[hi]]; ok && k >= lo {
			lo = k + 1
		}

		tbl[s[hi]] = hi
		curr = hi - lo + 1

		if curr > longest {
			longest = curr
		}
	}

	return longest
}

完整的代码参见这里,以及测试代码

LeetCode Problem 2 - Add Two Numbers

继续第二道题目,下面是问题描述:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个问题比较简单,基本上解题思路是比较清晰的。输入是两个链表,链表的元素都是单个数字(0-9),要求将两个列表的相应节点数字相加,并作为结果链表返回。

这个题咋看可以马上开始解答,但是在此之前还是有一些需要注意的地方。第一点是,题目并没有说明链表的长度,所以 A 和 B 两个链表可能不一定相同长度,那么如果一个链表更长,那么相加怎么处理呢?这里就考虑直接返回即可,相当于+0。第二点是,如果相加溢出怎么处理,其实题目的例子里面已经很清晰了,溢出会发生进位,依次向后处理。第三点是,如果最后一位发生进位呢,这点容易被遗忘,需要新增一个节点。

下面是具体的代码:

// Problem 2. Add Two Numbers
// URL: https://leetcode.com/problems/add-two-numbers/tabs/description

// ListNode defines a singly-linked list
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{0, nil} // sentinel node
	carry := 0                // carray bit

	for tail := head; l1 != nil || l2 != nil || carry != 0; tail = tail.Next {
		sum := carry

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		tail.Next, carry = &ListNode{sum % 10, nil}, sum/10
	}

	return head.Next // discard sentinel node
}

这里在链表加了一个哨兵节点,主要是为了处理方便。完整的代码参见这里,以及测试代码