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;
}
}
- 给定一个字符串 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
