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
}

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

LeetCode Problem 1 - Two Sum

最近开始在 LeetCode 网站上刷题,准备练练脑子。因为经常不动脑,感觉快生锈了。这个是第一题,比较简单。所有的解题代码都放在 Github 上。

问题描述:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目描述的很清楚了,就是要从整数列表里面找出符合需求的两个数字,他们之和等于给定的目标值。输入是整数列表,输出是两个数字下标的列表。从给的例子上看,我们可以假设返回的列表,下标小的放在前面,比如是 [0, 1] 而不是 [1, 0]。那假如没有找到符合要求的数字呢,应该返回什么呢?题目里面没有明确说明,我自己觉得这里应该返回一个空值。

思路一

首先,我们可以想到一种最简单的方法,就是遍历所有组合,这种方法比较暴力也很有效。下面的代码用 go 语言编写:

func twoSum(nums []int, target int) []int {
	n := len(nums)

	if n < 2 {
		return nil
	}

	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

这个方法没什么好解释的,它的时间复杂度是O(n^2)

思路二

如果我们要降低时间复杂度,就必须减少迭代的次数。可以想到的一个优化思路是,针对数组进行排序,然后定义两个指针,分别从头和尾两个方向逼近,看起来有点像快速排序。如果指针指向的两个数之和大于目标值,则右边的指针左移。反之,左边的指针右移。直到找到符合需求的两个数。因为排序的最佳时间复杂度可以达到O(nlogn),接下来只遍历一次,时间复杂度是O(n),所以总的时间复杂度为 O(nlogn)。

这是一个不错的思路,但是这道题目要返回数字的下标,但是如果我们先排序会导致顺序就和初始状态不一样,所以还得想办法记录,所以这个思路最终实现也挺别扭的,就放弃了。

思路三

回到题目,我们要求出 a+b=target,反过来看,如果我们当前遍历的数字是 a,也就是我们要看 target - a 这个结果在数组里面是否存在。为了加快查找的效率,我们可以用额外的空间换时间效率,哈希表是一个很好的策略。在遍历的时候我们把每个数字和它对应的坐标保存到一个哈希表中。相应的代码如下:

func twoSum(nums []int, target int) []int {
	tbl := make(map[int]int, len(nums))

	for i, v := range nums {
		if j, ok := tbl[target-v]; ok {
			return []int{j, i}
		}

		tbl[v] = i
	}

	return nil
}

完整代码

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