3/19题解

1.给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
方法一：贪婪
如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 * 2，因此 ans 一直为偶数。但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。

class Solution {
public:
    int longestPalindrome(string s) {
        if(s.length()<1) return 0;
        map<char,int> m;
        int res=0;
        for(char c:s)
             ++m[c];
        for(char c='A';c<='z';c++)
        {
            res+=m[c]/2*2;
            if(m[c]%2==1&&res%2==0)//ans为奇数后就不再计算，奇数数量字符多出来的一个字符了
            {
                res+=1;
            }
        }
        return res;
    }
};

2.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：https://leetcode-cn.com/problems/add-two-numbers/
思路：按位相加，如果有进位就记录这个进位。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum=0;
        ListNode* p1=l1;
        ListNode* p2=L2;
        ListNode* Head=new ListNode(0);
        ListNode* p=Head;
        while(p1!=NULL||p2!=NULL||sum>0){
            if(p1!=NULL){
                sum+=p1->val;
                p1=p1->next;
            }
            if(p2!=NULL){
                sum+=p2->val;
                p2=p2->next;
            }
            p->val=sum%10;
            sum/=10;//进位标志
            if(p1!=NULL||p2!=NULL||sum>0){
                p->next=new ListNode(0);
                p=p->next;
            }
        }
        return Head;
    }
};