算法

链表反转-迭代-递归

有序链表1->2->3->4->5
需要其输出反转==>>5->4->3->2->1

//有序链表1->2->3->4->5==>>5->4->3->2->1    链表反转
public class ReverseList {
    static class ListNode {
        //值
        int val;
        //指向下一个节点的指针
        ListNode next;

        //全参构造函数
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //1.迭代法：反转函数
    public static ListNode reversalList(ListNode head){
        ListNode next,pre=null;//当前指针指向的下一个对象next和当前指针的前一个节点pre
        ListNode current=head;//当前指针
        while(current!=null){
            //下一个节点=当前节点的下一个节点
            next=current.next;
            //当前节点的下一个节点=前一个节点
            current.next=pre;
            //前一个节点=当前节点
            pre=current;
            //当前节点=下一个节点
            current=next;
        }

        //返回翻转后的链表
        return pre;

    }

    //2.递归法：反转函数
    public static ListNode reversalList2(ListNode head){
        if(head==null||head.next==null){
            //如果链表为空或者链表只有一个节点，直接返回链表
            //或者已经到达最后一个节点
            return head;
        }
        ListNode new_head = reversalList2(head.next);
        head.next.next=head;
         head.next=null;

        return new_head;
    }

    //遍历打印
    public static void printNode(ListNode node){
        System.out.print(node.val);
        while (node.next!=null){
            node=node.next;
            System.out.print("->"+node.val);
        }
        System.out.println();
    }


    public static void main(String args[]) {

        //定义一个1->2->3->4->5的链表
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);

        //翻转前打印
        System.out.println("翻转前:");
        printNode(node1);

        //反转
        //ListNode node = reversalList(node1);
        ListNode node = reversalList2(node1);

        //打印反转后的链表
        System.out.println("翻转后:");
        printNode(node);

    }
}

统计n以内的素数个数-暴力-埃氏筛选

素数：只能被1和自身整除的自然数 0，1 除外

输入：100
输出：25

暴力算法和埃氏筛选：

package com.hnit.day02;


import java.util.Scanner;

//统计n以内的素数个数（只能被1和自身整除的自然数 0，1 除外）2是最小的素数
public class SuShu {
    public static void main(String args[]) {
        //输入
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入一个整数n: ");
        int n = scanner.nextInt();

        int result1 = bf(n);  //调用暴力算法计算素数个数
        int result2 = eratosthenes(n); //调用埃氏筛法计算素数个数
        System.out.println("暴力算法: " + n + "以内的素数个数为:" + result1 + "个");
        System.out.println("埃氏筛法: " + n + "以内的素数个数为:" + result2 + "个");
    }

    //1. 暴力算法计算素数个数
    // 暴力算法的思想是：从2开始，依次判断每个数是否为素数，直到n为止。
    public static int bf(int n) {
        int count = 0;//记录素数的个数
        for (int i = 2; i <= n; i++) { //定义外循环，循环判断n内每一个数
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    //判断是否为素数的函数
    private static boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) { //不是素数
                return false;
            }
        }
        // 循环结束，为素数
        return true;
    }


    //2. 埃氏筛法计算素数个数
    // 埃氏筛法的思想是：从2开始，将每个素数的倍数都标记为合数，直到n为止。
    // 合数一定不是素数，因为它可以被分解成两个因数。减少了判断素数的次数。
    // 2*2=4, 2*3=6, 2*4=8, 2*5=10, 2*6=12, 2*7=14, 2*8=16, 2*9=18, 2*10=20, 2*11=22, 2*12=24, 2*13=26
    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n+1];//初始化默认值都为 false，作为素数标记
        int count = 0;
        for (int i = 2; i <= n; i++) {//2是最小的素数
            if (!isPrime[i]) {
                count++;

                //for (int j = 2*i ; j < n; j+=i) //存在重复标记，优化如下的循环
                for (int j = i * i; j < n; j += i) {//j是i的倍数，合数的标记位
                    isPrime[j] = true;//标记合数，不是素数
                }
            }
        }
        return count;
    }
}

删除排序数组中的重复项-双指针

一个有序数组nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
不能使用额外的数组空间，必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
例如： 输入：[0,1,2,2,3,3,4]
输出：5

双指针算法：
思路：数组完成排序后，我们可以放置两个指针i和j，i为慢指针，j为快指针。
只要当nums[i]==nums[j],我们就增加j来跳过重复项
当nums[i]!=nums[j]时，说明重复项已经跳完，将nums[j]的值赋予nums[i+1]，然后i++。
接着重复相同的过程，直到j到达数组的末尾为止。

package com.hnit.day03;

public class SortedArrayDuplicates {

    public static void main(String[] args) {
        int [] nums=new int[]{0,1,2,2,3,3,4};
        int result=removeDuplicates(nums);
        System.out.println("数组新长度为："+result);
    }

    //双指针算法
    public static int removeDuplicates(int[] nums) {
        if(nums.length==0){//如果数组为空，直接返回0
            return 0;
        }
        //定义慢指针
        int i=0;
        //定义快指针
        for(int j=1;j<nums.length;j++){
            //如果两个指针指向的元素不相等
            if(nums[j]!=nums[i]) {
                //慢指数加1
                i++;
                //将快指针指向的元素赋值给慢指针指向的元素
                nums[i] = nums[j];
            }
        }
        //返回新数组的长度，因为i是索引，所以长度是i+1
        return i+1;
    }
}

寻找数组的中心下标

给定一个整数数组nums，请编写一个能够返回数组“中心下标”的方法，
中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心下标，返回-1。如果数组有多个中心下标，应该返回靠近左边的那一个。
注意：中心下标可能出现在数组的两端。

思路：先统计出整个数组的总和，然后从第一个元素开始叠加。总和递减当前元素，叠加递增当前元素，直到两个值相等。

package com.hnit.day04;

import java.util.Arrays;

public class ArrayCenterIndex {
    public static void main(String[] args) {
        System.out.println(pivotIndex2(new int[]{1, 7, 3, 6, 5, 6}));
    }

    //sum = 28
    //i=0 total=1 false sum=27
    //i=1 total=8 false sum=20
    //i=2 total=11 false sum=17
    //i=3 total=17 true return 3
    public static int pivotIndex(int[] nums) {
        //获取数组元素的总和
        int sum = Arrays.stream(nums).sum();
        //定义左边元素的总和
        int total = 0;
        for(int i=0;i<nums.length;i++){
            total+=nums[i];
            //当前面元素的总和与后面元素的总和相等时，返回下标
            if(total==sum){
                return i;
            }
            //将总和减去当前元素，即右边元素的总和
            sum = sum  -nums[i];
        }
        //没有中心下标，返回-1
        return -1;
    }



    //思路2：左边元素的总和*2+当前元素=总和
    //一旦满足true，返回当前下标
    //不满足则当前元素右移，如果找不到则返回-1
    public static int pivotIndex2(int[] nums) {
        //获取数组元素总和
        int sum = Arrays.stream(nums).sum();
        //定义左边元素的总和
        int total = 0;
        for(int i=0;i<nums.length;i++){
            if(total*2+nums[i]==sum){
                return i;
            }
            total+=nums[i];
        }
        //没有中心下标，返回-1
        return -1;
    }
}

X的平方根-二分查找-牛顿迭代

在不使用sqrt(x)函数的情况下，得到x的平方根整数部分
解法一：二分查找
x的平方根肯定在0,X之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，m平方值如果大于x，则往左边找，小于等于则往右边找

解法二：牛顿迭代
假设平方根是i，则i和x/i必然都是x的因子，而x/i必然等于i，推到出i+x/i=2*i,得出i=(i+x/i)/2
由此得出解法，i可以任取一个值，只要上述公式成立，i必然就是x的平方根，如果不成立，(i+x/i)/2得出的值进行递归，直至得出正确解。

package day05;

public class SqrtX {
    public static void main(String[] args) {
        System.out.println(binarySearch(10));
        System.out.println(newton(10));
    }

    //二分法
    public static int binarySearch(int x) {
        //定义左右指针,以及返回值
        int l = 0, r = x, index = -1;
        int mid;
        while (l < r) {//当左指针小于右指针时
            //定义中间值
            mid = l + (r - 1) / 2;
            //如果中间值的平方值小于等于x
            if (mid * mid <= x) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }

    //牛顿迭代法
    public static int newton(int x) {
        if(x==0) return 0;
        return (int) sqrt(x,x);
    }

    public static double sqrt(double i,int x) {
        double res = (i+x/i)/2;
        if(res==i){
            return i;
        }else{
            return sqrt(res,x);
        }
    }
}