leetcode2&3

leetcode2:Add Two Numbers

I:(2->4->3)+(5->6->4)
O:(7->0->8)
原则:有进位往后增加,无则扩展

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/<!--more-->
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* p = &dummy;
int cn=0;
while(l1||l2){
int val = cn+(l1?l1->val:0)+(l2?l2->val:0);
cn = val/10;
val = val%10;
p->next = new ListNode(val);
p = p->next;
if(l1)
l1 = l1->next;
if(l2)
l2 = l2->next;
}
if(cn!=0){
p->next = new ListNode(cn);
p = p->next;
}
return dummy.next;
}
};

leetcode3:Longest Substring Without Repeating Characters

问题:寻找最大不重复字母的子串长度
解法:1.从每个元素找起始无重复字符串,时间复杂度为O(n^3)
2.将没出现的字母放入set,当重复字母出现时,把已有之前的set的字母移除,并记录最长的子串长度
3.用数组不用Map,直接定义一个变量来保存无重复字符串的第一个字符的下标,碰到重复的就更新下标

int lengthOfLongestSubstring(string s) {
int tables[256];
fill(tables,tables+256,-1);
int result=0,lastRepeatedPos=-1;
for(int i=0;i<s.size();i++)
{

if(tables[s[i]]!=-1&&lastRepeatedPos<tables[s[i]])
lastRepeatedPos=tables[s[i]];

//更新最大值
result=max(result,i-lastRepeatedPos);
//元素插入表中
tables[s[i]]=i;
}
return result;
}

总结:对于一个字符串,如果未出现重复,则该值放入数组中,由于ASCII最多有256种符号,则放入一个大小为256的数组里;如果出现重复的字母,即不为默认的-1,且第一个字符下标比这个重复字母下标小,则更新下标以及最长长度,并将该长度放入对应符号的数组值里。

std::fill用法

void fill(first,last,val);
fill(array,array+n,element);

memset(array,array+n,element);