刷leetcode算法总结（四）
2016-09-20
3. Longest Substring Without Repeating Characters
我最开始设计了一个双重循环，复杂度为O(n^2)的算法来解决这一问题，想对每个位置的字符找到对应的最长的没用重复字符的子串，但是这一设计之后无法满足时间上的要求，必须要在时间复杂度为O(n)的情况下才能完成。
之后，我想到算法课上曾经讲过类似的问题，利用start和end代表子串的头尾位置，用O(2*n)的复杂度就可以遍历字符串的所有最长无重复子串。
同时，利用一个exist数组保存字符是否出现（假设char set是ascii），从前向后遍历数组，如果遇到已存在的字符，应该回退到这个字符上次出现的下一个位置从新开始统计（如下图），同时注意exist数组的同步更新。
如下图：
最后代码设计如下：
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
int res = 1;
boolean[] exist = new boolean[256];
int start = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (exist[ch]) {
res = Math.max(res, i - start);
for (int k = start; k < i; k++) {
if (s.charAt(k) == ch) {
start = k + 1;
break;
}
exist[s.charAt(k)] = false;
}
} else
exist[ch] = true;
}
res = Math.max(res, s.length() - start);
return res;
}
}
2. Add Two Numbers
这道题是用链表的方式表示了数字，最开始我把这道题想的复杂了，想先把链表表示成int型数，求和之后再把和用链表的形式表示，但是发现把一个整数表示成链表的形式有些困难，于是放弃了这种方法。
之后，经过查找一些实现办法发现只需要每一位对应相加，然后把仅为carry记录下来，用于下一位的相加即可。
代码如下：
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode first = new ListNode(0);
ListNode temp = first;
while(l1 != null || l2 != null){
int val1 = 0;
if(l1 != null){
val1 = l1.val;
l1 = l1.next;
}
int val2 = 0;
if(l2 != null){
val2 = l2.val;
l2 = l2.next;
}
int tmp = val1 + val2 + carry;
temp.next = new ListNode(tmp%10);
carry = tmp / 10;
temp = temp.next;
}
if(carry == 1){
temp.next = new ListNode(1);
}
return first.next;
}
}