leetcode

1 原题
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

题目大意

有两个单链表，代表两个非负数，每一个节点代表一个数位，数字是反向存储的，即第一个结点表示最低位，最后一个结点表示最高位。求两个数的相加和，并且以链表形式返回。

解题思路

对两个链表都从第一个开始处理，进行相加，结果再除以10求商，作为下一位相加的进位，同时记录余数，作为本位的结果，一直处理，直到所有的结点都处理完

public class AddTwoNumbersByLinkedlist {
    public static void main(String[] args) {
        Node one = new Node(2);
        one.next = new Node(4);
        one.next.next = new Node(3);
        Node two = new Node(5);
        two.next = new Node(6);
        two.next.next = new Node(4);
        add(one, two);
    }

    @Data
    public static class Node {
        public Node(int value) {
            this.value = value;
        }
        public Node() {
        }
        private int value;
        Node next;
    }

    private static Node add(Node one, Node two) {
        Node curr = one;
        Node root = one;
        int carry = 0;
        while (one != null && two != null) {
            int sum = one.value + two.value + carry;
            one.setValue(sum % 10);
            carry = sum / 10;
            curr = one;
            one = one.next;
            two = two.next;
        }
        if (one != null) {
            curr.next = one.next;
        }
        if (two != null) {
            curr.next = two;
        }
        if (carry == 1) {
            while (curr.next != null && carry == 1) {
                curr = curr.next;
                int sum = curr.getValue() + carry;
                curr.setValue(sum % 10);
                carry = sum / 10;
            }
            if (carry == 1) {
                curr.next = new Node(1);
            }
        }
        return root;
    }
}

2. 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
   方法四：中心扩展算法
   参考自：【https://leetcode-cn.com/problems/longest-palindromic-substring/solution/】
   事实上，只需使用恒定的空间，我们就可以在 O(n^2) 的时间内解决这个问题。
   我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。
   你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如“abba” 的中心在两个'bb'之间）。

代码示例：
public class Solution {
    public static void main(String[] args) {
        String str="aabaa";
        System.out.println(longestPalindrome(str));
    }

    private static String longestPalindrome(String str) {
        int start=0,end=0,len;
        for (int i=0;i<str.length();i++){
            int len1=centerAround(str,i,i);
            int len2=centerAround(str,i,i+1);
            len=Math.max(len1,len2);
            if (len>end-start){
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        return str.substring(start,end+1);
    }
    public static  int centerAround(String str,int start,int end){
        int L=start;
        int R=end;
        while (L>=0&&R<str.length()&&str.charAt(L)==str.charAt(R)){
            L--;
            R++;
        }
        return R-L+1-2;
    }
}

3.字典树

public class TrieTree {

    public void insert(TrieNode node, String word) {
        for (int i = 0; i < word.length(); i++) {
            Character c = new Character(word.charAt(i));
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node.children.get(c).ncount++;
            node=node.children.get(c);
        }
    }

    public int search(TrieNode node, String word) {
        for (int i = 0; i < word.length(); i++) {
            Character c = new Character(word.charAt(i));
            if (!node.children.containsKey(c)) {
                return 0;
            }
            node = node.children.get(c);
        }
        return node.ncount;
    }

    static class TrieNode {
        int ncount;
        Map<Character, TrieNode> children;

        public TrieNode() {
            ncount = 0;
            children = Maps.newHashMap();
        }
    }
}

测试：
public class Test {
    public static void main(String[] args) {
/**
 * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
 * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
 */
        String[] strs = {"banana", "band", "bee", "absolute", "acm"};
        String[] prefix = {"ba", "b", "band", "abc"};
        TrieTree tree = new TrieTree();
        TrieTree.TrieNode node = new TrieTree.TrieNode();
        for (String s : strs) {
            tree.insert(node, s);
        }
// tree.printAllWords();
        for (String pre : prefix) {
            int num = tree.search(node, pre);
            System.out.println(pre + " " + num);
        }
    }
}

【参考文章】
https://blog.csdn.net/derrantcm/article/details/46905087