Leetcode 1

Description

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.

Solution

• 使用temp节点进行节点的后移，返回的l3其实是temp的前一个节点
• 在创建新节点时直接将carray的值赋给新节点
• 当进行到最后一位时不再创建新节点

3.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.

Solution

• 使用HashMap存储字符及索引
• 遇到重复元素时，可能碰到重复元素索引值+1比原来的i值小的情况，此时不更新i
• 子序列的长度取最大的那个值
算法的时间复杂度为$O(n)$

5.Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Solution

1. Manacher算法
1. 动态规划
动态规划解法较为经典，采用一个转移矩阵p[i][j]来存储s[i] ~s[j]的子字符串是否为回形字符串。当s[i] ~s[j]为回形字符串时，其判断依据为：
• s[i]必然等于s[j]

• s[i] ~s[j]的上一组s[i+1] ~s[j-1]仍然是回形字符串。或者是碰到“bb”这种情况或“bab”，此时的j - i < 3。
采用动态规划仍然会有$O(n^{2})$的时间复杂度。

• 算法从后向前遍历，防止在边界条件时，s[i+1] ~s[j-1]溢出。

6. ZigZag Conversion

Description

The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line:"PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

Solution

1. 较为复杂的解法，首先需要将原字符串补全为可以被周期整除的字符串，并在后面补上'*'。然后可以观察到一个周期内访问字符串的顺序，根据这个顺序可以发现除了头部和尾部的字符，其他地方的字符在一个周期内是关于底部字符对称访问的。这里为了省去边界判断，直接在底部字符和周期尾部字符处插入'*'，使得在一个周期内字符的访问都是一个是周期头部，一个是周期末尾字符。
1. 分好周期后分情况讨论。

12. Integer to Roman

Description

Roman numerals are represented by seven different symbols: IVXLCD and M.

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

13. Roman to Integer

Description

Roman numerals are represented by seven different symbols: IVXLCD and M.

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Solution

• 将每一个字母对应为整型数字
• 动态规划，从后向前判断当前数字和其后面的数字的大小
Author: NYY