LeetCode(2) || Add Two Numbers && Longest Substring Without Repeating Characters
题记
刷LeetCode第二天，今天做了两道题，速度比我想的要慢，看样子两个月的目标有点难，尽力吧。今天主要做了Add Two Numbers和Longest Substring Without Repeating Characters 两道题，下面就来看下这两道题吧。
题一:Add Two Numbers
题目内容
You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
解题思路
- LeetCode给的函数。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { }
}
- 题目的意思大致是：给出两个链表，这两个链表其实表示的一个倒置的非负整数，每一个节点表示非负整数的某一位上的数。比如链表2 -> 4 -> 3，其实表示的整数342。那么现在要做的是就是有这样的两个整数相加，最后返回同样规则的链表.比如 2->4->3 + 5 -> 6 ->4 = 7 -> 0 -> 8 即 342+465 = 807.
- 这道题难度不是很大，我能想到有两种思路，第一种将每一个链表转换成十进制整数，然后整数相加，再将相加后的整数转换成链表输出，计算复杂度在2*O(n)，而另一种就是直接链表相加，处理好进位就OK了，计算复杂度在O(n)。说实话，本来我以为第二种的运算时间是要小于第一种的，但是没想到结果差不多。其实当时我还想了另外一种方法，就是在进行链表转换成十进制整数以及十进制整数转换成链表时候，用16进制代替，这样就可以用移位代替除法操作，但是奈何16进制的加法一时没辙。
解题结果
方法一：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
long num1 = 0;
long num2 = 0;
ListNode pl1 = l1;
ListNode pl2 = l2;
long index1 = 1;
long index2 = 1;
if ( l1 == null || l2 == null ){
return null;
}
while(true){
if ( pl1 != null ){
num1 += pl1.val*index1;
pl1 = pl1.next;
index1*=10;
}
if ( pl2 != null ){
num2 += pl2.val*index2;
pl2 = pl2.next;
index2*=10;
}
if( pl2 == null && pl1 == null ){
break;
}
}
long sum = num1 + num2;
ListNode head = new ListNode((int) (sum % 10));
head.next = null;
sum = sum / 10;
ListNode lsPoint = head;
while( sum > 0 ){
ListNode lnSum = new ListNode((int) (sum % 10));
lsPoint.next = lnSum;
sum = sum / 10;
lsPoint = lnSum;
}
return head;
}
方法二：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pl1 = l1;
ListNode pl2 = l2;
ListNode pHead = new ListNode(0);
ListNode pTravel = pHead;
int sum;
int carry = 0;
if ( l1 == null || l2 == null ){
return null;
}
while( pl1 != null || pl2 != null ){
int val1 = 0;
int val2 = 0;
if ( pl1 != null){
val1 = pl1.val;
pl1 = pl1.next;
}
if ( pl2 != null){
val2 = pl2.val;
pl2 = pl2.next;
}
sum = val1 + val2 + carry;
ListNode newNode = new ListNode(sum % 10);
pTravel.next = newNode;
pTravel = newNode;
carry = sum / 10;
}
if( carry == 1 ){
ListNode newNode = new ListNode(carry);
pTravel.next = newNode;
pTravel = newNode;
}
return pHead.next;
}
两种方法的运行时间差不多，但是最短时间大概是在350ms，不知道是怎么弄出来的。
题二:Longest Substring Without Repeating Characters
题目内容
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
解题思路
- LeetCode给出的函数
public class Solution {
public int lengthOfLongestSubstring(String s) {
}
}
- 题目的意思大致是：找寻字符串S里面字符不重复的最长的子串长度。
- 一般情况下，用两个for循环能获取最长的子串长度，计算复杂度是o(n2)，想都不用想肯定通不过。因为O(n2)在遍历的时候会进行重复的遍历。
看一个例子：
S="abbdeca"。
t1="abbdeca"，t1[1]==t1[2]。
t2="bbdeca"，t2[0]==t2[1]。
t3="bdeca"，一直扫描到最后。
t4="deca"、t5、t6、t7都同上。
我们在处理t1的时候已经扫描到了s[2]，然后处理t3的时候扫描了s[2]到s[6]，这两个子串已经扫描完了整个母串。
换言之，能使得子串停止扫描的位置只有两处：1.s[2]；2.s[6](结尾)。
对于另一个例子S="aaab"，能使子串停止扫描的位置分别是：s[1],s[2],s[3](结尾)。
- 由此可见，之所以出现重复遍历，是因为在母串中扫描每一个字符都需要知道该字符是否在子串中出现过，如果使用遍历子串的方式那么肯定就费时了。那么有啥法子可以不遍历就知道重不重复呢，Hash表就可以实现，复杂度也变为了o(n)。同样我采用了两种方法，一种是使用Java自带的HashMap结构，另一种是自己定义数组来实现Hash。
- 但是实际做的时候发现单单使用Hash还是不行的，需要有个指针来表示子串的起始的位置。比如字符串s="akicklac"，当我扫描到第二个k，也就是s[4]是，Hash表里面存放的是a，k，i，c，s[4]已经替换了s[1]的那个k了，这是子串起始位置需要从s[0]变为s[2],否则s[6]会因为s[0]的存在而少算。
解题结果
方法一
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> hash = new HashMap<Character,Integer>();
int num = 0;
int max = 0;
int start = 0;
for(int i = 0 ; i < s.length() ; i++ ){
Character cha = s.charAt(i);
if( hash.containsKey(cha)){
int val = hash.get(cha);
if ( val >= start) {
start = val + 1;
num = i - val - 1;
}
}
hash.put(cha, i);
num++;
max = max < num ? num : max;
}
return max;
}
方法二
public int lengthOfLongestSubstring(String s) {
int max = 0;
int[] local = new int[256];
int start = 0;
int num = 0;
for( int i = 0 ; i < s.length(); i++ ){
Character ch = s.charAt(i);
int localValue = local[ch] ;
if ( localValue-- > start ){
start = localValue + 1;
num = i - localValue - 1;
}
local[ch] = i + 1;
num++;
max = max < num ? num : max;
}
return max;
}