含标签 "Algorithm" 的文章

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

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 处。直到遍历到字符串的最后。

继续阅读

继续第二道题目，下面是问题描述：

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。第二点是，如果相加溢出怎么处理，其实题目的例子里面已经很清晰了，溢出会发生进位，依次向后处理。第三点是，如果最后一位发生进位呢，这点容易被遗忘，需要新增一个节点。

继续阅读

最近开始在 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]。那假如没有找到符合要求的数字呢，应该返回什么呢？题目里面没有明确说明，我自己觉得这里应该返回一个空值。

继续阅读