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++)
        {
            //当找到重复元素且lastRepeatedPos小于找到重复元素的下表时，更新lastRepeatedPos
            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);