java算法（三十六）

1、101-200素数的个数

方法一

public static void main(String[] args) {
    boolean flag = false;
    int num = 0;
    for(int i=101; i<200; i++){
        for (int j=2; j<i; j++){
            if(i%j == 0){
                flag = false;
                break;
            }else{
                flag = true;
            }
        }
        if(flag){
            System.out.println(i);
            num++;
        }
    }
    System.out.println("101-200之间的素数的个数为："+ num);
}

方法二

public static void main(String[] args) {
    boolean flag = false;
    int num = 0;
    for(int i=101; i<200; i++){
        for (int j=2; j<=Math.sqrt(i); j++){
            if(i%j == 0){
                flag = false;
                break;
            }else{
                flag = true;
            }
        }
        if(flag){
            System.out.println(i);
            num++;
        }
    }
    System.out.println("101-200之间的素数的个数为："+ num);
}

2、 链表排序

//class ListNode{
//    ListNode next = null;
//    int val;
//    public ListNode(int x){
//        val = x;
//    }
//}

public static void main(String[] args) {
    int[] a = new int[]{3,2,1,4};
    int i=0;
    ListNode head = new ListNode(0);
    ListNode p = head;
    while (i<a.length){
        ListNode newNode = new ListNode(a[i]);
        p.next = newNode;
        p = p.next;
        i++;
    }

    ListNode p1 = head.next;
    System.out.print("排序前的链表为: ");
    while (p1 != null){
        System.out.print(p1.val+" ");
        p1 = p1.next;
    }

    ListNode res = fun(head);
    ListNode p2 = res.next;
    System.out.println();
    System.out.print("排序后的链表为: ");
    while (p2 !=null){
        System.out.print(p2.val+" ");
        p2 = p2.next;
    }
}

private static ListNode fun(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode fast = head.next;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode temp = slow.next;
    slow.next = null;

    ListNode left = fun(head);
    ListNode right = fun(temp);

    ListNode h = new ListNode(0);
    ListNode res = h;
    while (left !=null && right !=null){
        if (left.val < right.val){
            h.next = left;
            left = left.next;
        }else {
            h.next = right;
            right = right.next;
        }
        h = h.next;
    }
    h.next = left != null?left:right;
    return res.next;
}