最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
以中间为拓展起点 双指针向两端遍历 注意中心1个或2个
"""
class Solution {
    public String longestPalindrome(String s) {
        
        int len=s.length();
        int res=0;
        String temp="";
        for(int i=0;i<len;i++){ ////遍历回文中心点
            for(int j=0;j<=1;j++){  //回文子串长度为奇数时  中心为1个i=j   为偶数时，中心为2个 j=i+1
                 int l=i,r=i+j;
                while(l>=0&&r<len&&s.charAt(l)==s.charAt(r)) {l--;r++;}
                if(res<r-l-1){
                    res=r-l-1;
                    temp=s.substring(l+1,r);
                }
            }
        }
        return temp;
    }
}


合并链表

归并排序

1、利用快慢指针 找到链表中央节点

2、将链表一分为二进行分别排序

3、合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public ListNode sortInList (ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    return mergeSort(head);
}

public ListNode mergeSort(ListNode head) {
    if (head.next == null) {
        return head;
    }

    ListNode slow = head, fast = head, pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null;
    ListNode left = mergeSort(head);
    ListNode right = mergeSort(slow);
    return merge(left, right);
}
public ListNode merge(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (left != null && right != null) {
        if (left.val < right.val) {
            cur.next = left;
            left = left.next;
        } else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next;
    }
    if (left != null) {
        cur.next = left;
    }
    if (right != null) {
        cur.next = right;
    }
    return dummy.next;
}

前缀树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Trie {
    private boolean is_string=false;
    private Trie next[]=new Trie[26];

    public Trie(){}

    public void insert(String word){//插入单词
        Trie root=this;
        char w[]=word.toCharArray();
        for(int i=0;i<w.length;++i){
            if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();
            root=root.next[w[i]-'a'];
        }
        root.is_string=true;
    }

    public boolean search(String word){//查找单词
        Trie root=this;
        char w[]=word.toCharArray();
        for(int i=0;i<w.length;++i){
            if(root.next[w[i]-'a']==null)return false;
            root=root.next[w[i]-'a'];
        }
        return root.is_string;
    }
    
    public boolean startsWith(String prefix){//查找前缀
        Trie root=this;
        char p[]=prefix.toCharArray();
        for(int i=0;i<p.length;++i){
            if(root.next[p[i]-'a']==null)return false;
            root=root.next[p[i]-'a'];
        }
        return true;
    }
}

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//方法3：辗转相除法
        int max = a > b ? a : b;
        int min = a < b ? a : b;
        if(max % min == 0) return min;
        return gcd(max % min, min);
         
//方法4：更相减损术（避免了取模运算，用效率更高的减法运算替代）
        int max = a > b ? a : b;
        int min = a < b ? a : b;
        if(max % min == 0) return min;
        return gcd(max - min, min);
         
//方法5：更相减损术非递归实现
        while(a != b){
            if(a > b) a -= b;
            else b -= a;
        }
        return a;

立方根 牛顿迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
"""
二分法
"""
double fun(double x) {
    if (x == 0) return 0;
    double low = 0;
    double top = x;
    if (x < 0) {
        low = x;
        top = 0;
    }
    while (low<top)
    {
        double mid = (low + top) / 2;
        double tmp = mid*mid*mid;
        if (tmp > x) {
            top = mid;
        }
        else if (tmp < x) {
            low = mid;
        }
        else {
            return mid;
        }
    }
}

import java.util.*;
/**
*  牛顿迭代思想: x = (2*x + y/x/x)/3;
*/
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();
        double m = get(n);
        System.out.println(String.format("%.1f",m));
    }
    
    public static double get(double n){
        double a, b;
        a = n;
        if(n == 0){
            return 0;
        }
        // 利用迭代法进行求解 -- 牛顿迭代法
        b = (2 * a + n / a / a) / 3;
        // Math.abs(x)返回指定数字x的绝对值
        while(Math.abs(b - a) > 0.000001){
            a = b;
            b = (2 * a + n / a / a) / 3;
        }
        return b;
    }
}