给定一个整数数组 nums
和一个目标值 target
,找出数组中和为目标值的两个数,并返回它们的数组下标。
假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); //泛型参数只能用引用类型
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
class Solution(object):
def twoSum(self, nums, target):
buff_dict = {}
for i,num in enumerate(nums):
complement = target - num
if complement in buff_dict: # 判断键是否存在于字典中
return [buff_dict[complement], i]
buff_dict[nums[i]] = i
给定两个「非空」的链表,用来表示两个非负的整数。其中,低位在前,高位在后,并且每个节点只能存储「一位」数字。
将这两个数相加,返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
从链表头部开始,一位位相加即可,注意进位。
注意:我们使用「哑结点」来简化代码(防止需要额外判断表头是否为空)
伪代码如下:
carry
初始化为 0p
和 q
分别初始化为列表 l1
和 l2
的头部l1
和 l2
也可以,但会使其指向位置发生改变l1
和 l2
直至到达它们的尾端:x
设为结点 p
的值。如果 p
已经到达 l1
的末尾,则将其值设置为 0y
设为结点 q
的值。如果 q
已经到达 12
的末尾,则将其值设置为 0sum = x + y + carry
carry = sum / 10
sum mod 10
的新结点,并将其设置为当前结点的下一个结点p
和 q
前进到下一个结点carry = 1
是否成立,如果成立,则向返回列表追加一个含有数字 1 的新结点class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null){
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
}
class Solution(object):
def addTwoNumbers(self, l1, l2):
dummy = ListNode(0)
curr = dummy
p = l1
q = l2
carry = 0
while (p or q):
x = p.val if p else 0
y = q.val if q else 0
sum = x + y + carry
carry = sum // 10
curr.next = ListNode(sum % 10)
curr = curr.next
if p:
p = p.next
if q:
q = q.next
if (carry > 0):
curr.next = ListNode(carry)
return dummy.next
给定一个字符串,找出其中不含有重复字符的「最长子串」的长度。
示例:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
class Solution {
public int lengthOfLongestSubstring03(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
//左边界移动到相同字符的下一个位置和i当前位置中更靠右的位置(防止i向左移动)
i = Math.max(map.get(s.charAt(j)), i);
}
//比对当前无重复字段长度和储存的长度,选最大值并替换
//j-i+1是因为此时i,j索引仍处于不重复的位置,j还没有向后移动,取的[i,j]长度
ans = Math.max(ans, j - i + 1);
// 将当前字符作为key,下一个索引作为value放入map中(注意value会发生更新)
// value为j+1是为了当出现重复字符时,i直接跳到上个相同字符的下一个位置
map.put(s.charAt(j), j+1);
}
return ans;
}
}
class Solution(object):
def lengthOfLongestSubstring(self, s):
used = {}
max_length = start = 0
for i,c in enumerate(s):
if c in used:
start = max(used[c], start)
max_length = max(max_length, i - start + 1)
used[c] = i + 1
return max_length
给定两个大小为 m 和 n 的有序数组 nums1
和 nums2
。
你可以假设 nums1
和 nums2
不会同时为空。
示例:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
看到对数复杂度与有序数组,可以判断需要采用「二分法」求解。
在统计中,中位数的作用是:
❝将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。 ❞
基于上述思想,我们可以考虑对数组进行切分。
如下图所示,一个长度为 m 的数组,有 0 到 m 总共有 m + 1 个位置可以切。
对于本道题,我们把有序数组 A 和数组 B 分别在 i 和 j 进行切割:
将 i 的左边和 j 的左边组合成「左半部分」,将 i 的右边和 j 的右边组合成「右半部分」,如上图所示。
接下来我们根据两数组长度之和的「奇偶性」分开讨论:
「情况 1」:如果 A 数组和 B 数组的总长度是「偶数」,则中位数的选择条件为:
❝左半部分的长度等于右半部分,且左半部分最大的值小于等于右半部分最小的值。 ❞
「情况 2」:如果 A 数组和 B 数组的总长度是「奇数」,则中位数的选择条件为:
❝左半部分的长度比右半部分大 1,且左半部分最大的值小于等于右半部分最小的值。 ❞
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
return findMedianSortedArrays(B,A); // 保证 m <= n
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (i != m && B[j-1] > A[i]){ // i 需要增大
iMin = i + 1;
}
else if (i != 0 && A[i-1] > B[j]) { // i 需要减小
iMax = i - 1;
}
else { // 达到要求,并且将边界条件列出来单独考虑
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
}
}
return 0.0;
}
}
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type A: List[int]
:type B: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
if (m > n):
return self.findMedianSortedArrays(nums2,nums1)
i_min, i_max = 0, m # 注意与java赋值的格式区别
while i_min <= i_max:
i = (i_min + i_max) / 2 # python3下需设置为取整
j = (m + n + 1)/2 - i
if (i != m and nums2[j-1] > nums1[i]):
i_min = i + 1
elif (i != 0 and nums1[i-1] > nums2[j]):
i_max = i - 1
else:
max_left = 0
if (i == 0):
max_left = nums2[j-1]
elif (j == 0):
max_left = nums1[i-1]
else:
max_left = max(nums1[i-1],nums1[j-1])
if ((m + n) % 2 == 1):
return max_left
min_right = 0
if (i == m):
min_right = nums2[j]
elif (j == n):
min_right = nums1[i]
else:
min_right = min(nums2[j],nums1[i])
return (max_left + min_right) / 2.0 # python3下可设置为2
return 0
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
我们可以观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,关于中心对称。需要注意偶数回文串与奇数回文串的中心不同:
在实现时我们可以利用运算取整性质将奇偶情况合并,需要注意起始位置的计算公式。
动态规划算法的本质即将复杂的问题拆分为小问题,以空间换取时间,通过状态转移方程将结果传递下去。我们可以将动态规划算法理解为「填表格」(与递归有所区别),将表格中需要的部分填满就得到了最终的结果。
对于本题而言,状态转移方程可以由回文的性质得出:
❝一个回文去掉两头后,剩下的部分仍然是回文。(不考虑边界情况) ❞
在两头字符相等的情况下,一个字符串是否为回文取决于其子串是否为回文。因此我们将「状态」定义为「一个字符串的子串是否为回文」。基于以上思路,动态规划算法的关键步骤如下:
「1. 定义状态」。dp[i][j]
表示字符串 s[i,j]
是否为回文。
「2. 确定状态转移方程」。此时需要考虑边界情况:
对于「一般情况」,状态方程如下所示:
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
需要注意 i
和 j
的关系是 i <= j
,因此实际上只需要填表的上半部分。
对于「边界情况」,即 [i+1, j-1]
不构成区间,即 j-1-(i+1)+1 < 2
,整理得 j - i < 3
,此时 s[i, j]
一定是回文。
因此,在 s[i] == s[j]
且 j - i < 3
的前提下,可以直接得出 dp[i][j] = true
,否则执行状态转移。
「3. 初始化」。单个字符一定是回文子串,因此将表格的对角线初始化为 true
,即 dp[i][i] = 1
。实际上编码过程中单个字符作为输出的默认值,在动态规划中并不会利用到表格中的对应内容,只会考虑 i < j
的情况。
「4. 考虑输出」。只要一得到 dp[i][j] = true
,就记录该字符串的长度和起始位置,在输出时截取即可。
动态规划算法的时间和空间复杂度均为 。
Manacher 算法专门用于解决最长回文子串问题,其本质是一种中心扩散法,并利用了”以空间换取时间“的思想。其具体流程如下:
首先我们需要在原字符串的首尾和相邻字符中插入「分隔符」,该分隔符需要选择未在原始字符串中出现过的字符。例如对于 babad
,添加分隔符 #
,得到新字符串 #b#a#b#a#d#
。
新的字符串具有如下性质:
辅助数组 p
记录了新字符串中以每个字符为中心,向左右两边同时扩散能够达到的「最大步数」。
以字符串 abbabb
为例,其辅助数组 p
如下表所示:
辅助数组 p
具有如下性质:
❝辅助数组
p
的最大值即为原字符串「最长回文子串」的长度。 ❞
关于上述性质,可以分两种情况进行证明:
基于 i
与 maxRight
的大小关系,我们需要进行分类讨论:
「情况 1」:如果 i >= maxRight
,我们只能够进行原始的中心扩散,逐渐扩大 maxRight
;
「情况 2」:如果 i < maxRight
,我们可以对中心扩散进行优化,为 p[i]
设置初始值,减少一定的扩散次数。
首先我们需要定义循环变量 i
关于 center
对称的索引 mirror
,其计算公式为 mirror = 2 * center - i
。
根据 p[mirror]
的数值从小到大,可以分以下三种情况讨论:
p[mirror] < maxRight - i
,此时根据以 center
为中心的回文子串的对称性,可以直接得出结论 p[i] = p[mirror]
;
p[mirror] == maxRight - i
,此时根据对称性,p[i]
至少为 maxRight - i
,需要继续扩散;
p[mirror] > maxRight - i
,此时 p[i] = maxRight - i
,无需扩散;
关于以上三种情况,其示意图中前两张图的回文子串并没有完全对称,只要理解意思即可;关于第三种情况,可以利用回文子串的对称性,通过下图证明「红色箭头」对应的 c
和 e
必不相等:
综上所述,当 i < maxRight
时,可以为 p[i]
设定起始值,减少扩散次数:
p[i] = min(maxRight - i, p[mirror]);
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); // 奇数回文子串
int len2 = expandAroundCenter(s, i, i+1); // 偶数回文子串
int len = Math.max(len1, len2);
if (len > end - start + 1) {
start = i - (len - 1) / 2;
end = i + len / 2; // 上述两个公式利用运算取整的性质将奇偶情况合并
}
}
return s.substring(start, end + 1); // 取子串不包括结束索引
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1; //实际上公式为 R - L + 1 - 2,因为循环结束时两边各多了一个元素
}
}
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
boolean dp[][] = new boolean[n][n]; //默认false
int start = 0;
int maxLen = 1;
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i ++) {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && ((j - i < 3) || dp[i + 1][j - 1]);
if (dp[i][j]) {
if ((j - i + 1) > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
}
return s.substring (start, start + maxLen);
}
}
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
String str = addBoundaries(s, '#');
int sLen = 2 * len + 1;
int[] p = new int[sLen];
int maxRight = 0;
int center = 0;
int maxLen = 1;
int start = 0;
for (int i = 0; i < sLen; i++) {
int mirror = 2 * center - i;
if (i < maxRight) {
p[i] = Math.min(maxRight - i, p[mirror]); // 关键代码
}
// 执行中心扩散
int left = i - (1 + p[i]);
int right = i + (1 + p[i]);
while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
p[i]++;
left--;
right++;
}
// 更新辅助变量
if (i + p[i] > maxRight) {
maxRight = i + p[i];
center = i;
}
// 记录最长回文子串
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2; // 原始字符串中的位置为除以2向下取整
}
}
return s.substring (start, start + maxLen);
}
private String addBoundaries(String s, char divide) {
int len = s.length();
if (len == 0) {
return "";
}
if (s.indexOf(divide) != -1) {
throw new IllegalArgumentException("分隔符已存在于字符串中!");
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < len; i++) {
stringBuilder.append(divide);
stringBuilder.append(s.charAt(i));
}
stringBuilder.append(divide);
return stringBuilder.toString();
}
}
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if (s is None or len(s) < 1):
return ""
start, end = 0, 0
for i in range(len(s)):
len1 = self.expandAroundCenter(s,i,i)
len2 = self.expandAroundCenter(s,i,i+1)
leno = max(len1, len2)
if (leno > end - start + 1):
start = i - (leno - 1) / 2 # 注意这是 python2,会自动取整
end = i + leno / 2
return s[start:end + 1]
def expandAroundCenter(self, s, left, right):
L = left
R = right
while (L >= 0 and R < len(s) and s[L] == s[R]):
L -= 1
R += 1
return R - L - 1
class Solution:
def longestPalindrome(self, s: str) -> str: #python3
n = len(s)
if n < 2: #括号可以省略
return s
dp = [[False for _ in range(n)] for _ in range(n)]
maxLen = 1
start = 0
for j in range(1, n):
for i in range(0, j):
dp[i][j] = (s[i] == s[j]) and ((j - i < 3) or dp[i + 1][j - 1])
if (dp[i][j]):
if (j - i + 1) > maxLen:
maxLen = j - i + 1
start = i
return s[start:start + maxLen]
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
t = "#"
for i in range(n):
t += s[i]
t += "#"
t_len = 2 * n + 1
p = [0 for _ in range(t_len)]
max_right = 0
center = 0
max_len = 1
start = 0
for i in range(t_len):
if i < max_right:
mirror = 2 * center - i
p[i] = min(max_right - i, p[mirror])
left = i - (1 + p[i])
right = i + (1 + p[i])
while left >= 0 and right < t_len and t[left] == t[right]:
p[i] += 1
left -= 1
right += 1
if i + p[i] > max_right:
max_right = i + p[i]
center = i
if p[i] > max_len:
max_len = p[i]
start = (i - max_len) // 2
return s[start:start + max_len]