2020-05-27

LeetCode数组

1160.拼写单词(统计出现次数)

题目

分析

1. 主要思想就是：通过计算参考表和单词表每个单词出现次数对比(参照表出现次数一定要比找的多 才可能拼出来)
2. 具体步骤：
    2.1 分别设计一个jishu数组统计参考表每个单词出现次数 || 一个temp数组统计要查的每个单词的出现次数(用完就要清0)
    2.2 然后每个单词位都需要对比，然后对比成功+1之后达到26就说明能凑出来这个单词，输出长度。

代码

public class PingXieDanCi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        String[] words=new String[n];   //输入要判断的words表
        for(int i=0;i<words.length;i++){
                words[i]=input.next();
        }
        String chars=input.next();  //输入chars字符串
		//可以试试每一次统计是否正确
        /*int[] b=countCharacters(words,chars);
        for(int i=0;i<26;i++){
            if(b[i]!=0) {
                System.out.println((char) (i + 97) + "有" + b[i] + "个");
            }
        }*/
        System.out.println(countCharacters(words,chars));
    }

    public static int countCharacters(String[] words, String chars) {
        int sum=0;  //记录总长度
        char[] a=chars.toCharArray();  //chars字符串转字符数组
        int[] jishu=new int[26];
        int[] temp=new int[26];

        for(int i=0;i<chars.length();i++){
            jishu[chars.charAt(i)-97]++;  //计算chars字符串中各单词个数
        }

        for(int i=0;i<words.length;i++){
            int chang=words[i].length();  //计算每一个要判断的词汇的长度

            for(int j=0;j<words[i].length();j++){
                temp[words[i].charAt(j)-97]++;  //计算chars字符串中各单词个数
            }

            //对比两个数组
            int flag=0; //每位判断是否满足条件
            for(int z=0;z<26;z++){
                if(jishu[z]>=temp[z]){
                    flag+=1;  //满足要凑的比我有的少 就+1
                }
                if(jishu[z]<temp[z]){
                    break;  //有参考表没有的单词 一定凑不出来!
                }
            }

            if(flag==26){
                sum+=chang;  //每一位都满足 就可以拼凑出来
            }

            //用完之后将temp数组清0
            for(int w=0;w<26;w++){
                temp[w]=0;  //计算chars字符串中各单词个数
            }

        }
        return sum;
    }

}

结果

88.合并两个有序整数数组(ArrayList集合)

题目

分析

1. 主要通过有序的ArrayList集合存放两个数组元素
2. 通过Collections.sort()方法进行排序然后返回

代码

public class HeBinShuZu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();  //数组1的长度
        int n=input.nextInt();  //数组2的长度
        int[] a=new int[m];  //定义数组1
        int[] b=new int[n];  //定义数组2
        for(int i=0;i<m;i++){
            a[i]=input.nextInt();  //按序输入数组1的值
        }
        for(int j=0;j<n;j++){
            b[j]=input.nextInt();  //按序输入数组2的值
        }

        System.out.println("调函数之后的list"+merge(a,m,b,n).toString());  //list集合转字符串
    }

    public static ArrayList<Integer> merge(int[] nums1, int m, int[] nums2, int n) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            list.add(nums1[i]);
        }
        System.out.println("第一次添加之后的list:"+list.toString());
        System.out.println("第一次的长度"+list.size());
        System.out.println("----------------------");
        for(int j=0;j<n;j++){
            list.add(nums2[j]);
        }
        System.out.println("第二次添加之后的list:"+list.toString());
        System.out.println("第二次的长度"+list.size());
        System.out.println("----------------------");
        Collections.sort(list);
        System.out.println("排序后的list:"+list.toString());
        System.out.println("排序后的长度"+list.size());
        System.out.println("----------------------");
        return list;
    }

}

结果

53. 0-n-1中缺失的数字(双指针二分查找)

题目

分析

1. 数组下标计数：新建数组然后利用数组下标记录每个数组出现次数，如果出现次数为0就是缺失的数字。
2. 双指针：使用二分法进行分左右两部分对比，只要是顺序不缺少的话肯定是下标和当前值一定一样。
    2.1 左边没缺   左指针挪到中间指针的右边
    2.2 左边缺失   右指针挪到中间指针的左边

代码

public class QueShiShuZi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();  //数组1的长度
        int[] a=new int[m];  //定义数组1
        for(int i=0;i<m;i++){
            a[i]=input.nextInt();  //按序输入数组1的值
        }
        System.out.println("挨个遍历"+missingNumber(a));
        System.out.println("双指针"+missingNumber2(a));
    }

	//挨个遍历存到计数数组中
    public static int missingNumber(int[] a) {
        int que=0;
        int[] b=new int[a.length+1];
        for(int i=0;i<a.length;i++){
            b[a[i]]++;
        }
        for(int i=0;i<b.length;i++){
            if(b[i]==0){
                que=i;   //下标计数的数组里面没出现肯定就是缺失了
            }
        }
        return que;
    }

	//双指针二分法查询
    public static int missingNumber2(int[] a) {
        int que=0;  //缺失的结果
        int left=0;  //左指针
        int right=a.length-1;  //右指针
        while(left<=right){
            int zhong=(left+right)/2;  //中间指针
            if(a[zhong]==zhong){
                left=zhong+1; //左边的下标和数值没有断就肯定是相等 所以缺失的在右边 左指针放在中间指针右边
            }
            else{
                right=zhong-1; //左边肯定缺失了 右指针放到中间指针的左边
            }
        }
        return left;  //最后一定是三个指向同一个位置
    }

}

实现

118.杨辉三角形(动态递归)

题目

分析

1. 动态递归：遍历迭代之后进行增加
2. list集合：使用Arraylist集合

代码

public class YangHuiSanJiao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();   //输入杨辉三角形的行数
        long[][] b=yanghui(n);  //接住调用方法的结果
        System.out.println("动态递归解法:");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.printf(b[i][j]+" ");
            }
            System.out.println();
        }
    }

    //动态递归
    public static long[][] yanghui(int n){
        if(n==0){
            return null;  //0行就返回null
        }
        long[][] a=new long[n][n];
        a[0][0]=1; //第一行第一列赋值1 方便后面的加
        for(int i=1;i<n;i++){  //从第二行开始
            for(int j=0;j<n;j++) {
                if(j==0){
                    a[i][j]+=a[i-1][j];  //第一列的只能加上面的
                }else{
                    a[i][j]=a[i-1][j]+a[i-1][j-1];  //上面的和上面的左边之和
                }
            }
        }
        return a;
    }

}

实现

26.删除排序数组中的重复项(HashSet集合)

题目

分析

1. 不重复就需要使用set集合：我们使用HashSet集合
2. 循环将每个数组元素往set插入(刚好不能插入重复的)
3. 输出set.size()就是最后要的长度

代码

public class ShanChuChongFu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(removeDuplicates(a));
    }

    public static int removeDuplicates(int[] nums) {
        HashSet<Integer> set=new HashSet<Integer>();  //建立hashset集合
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);  //遍历添加元素
        }
        System.out.println(set.toString());  //输出set集合元素
        return set.size(); //输出set集合的长度
    }
}

结果

1051.高度检查器(桶排序)

题目

分析

1. 非递减就是说必须是递增/相等
2. 利用桶排序数组下标记录每个桶的数量，然后进行对比，一旦桶里面的数量和下标不相等那么就是要移动的点，所有计数器加一

代码

public class GaoDuJianChaQi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(heightChecker(a));  //调用结果返回
    }

    //桶排序
    public static  int heightChecker(int[] heights) {
        int count=0; //用于记录最少需要几次
    //建立1,2,3,4,5...100一共101个桶
        int[] arr=new int[101];
    //遍历数组 -- 计算每个桶中有多少元素
        for(int i:heights){
            arr[i]++;
        }
    	
		for(int i=1,j=0;i<arr.length;i++){
        	while(arr[i]-->0){  //一直到结束(桶用完)
            	if(heights[j++]!=i){
                	count++;  //非递减就是说必须下标和当前桶数量相等
            	}
        	}
    	}
        return count;  //返回次数
    }

}

实现

674.最长连续递增序列(动态递归)

题目

分析

1. 主要是一个ans和count两个计数(ans一直是当前位置最长的序列长度)
2. 每一次判断如果是递增就+1 如果不符合就直接为1 这样保证每次最长的给了ans
3. 最后输出的时候看ans大还是count大就输出(有可能count一直++最后一次的时候count比ans还大一个)

代码

public class ZuiChangXuLie {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findLengthOfLCIS(a));
    }

    public static int findLengthOfLCIS(int[] nums) {
        if(nums.length<=1){
            return nums.length;  //长度0/1就是1
        }
        int ans=1;  //存当前的最大的长度
        int count=1;
        for(int i=0;i<nums.length-1;i++){  //因为i+1 所以i只能到最长-1
            if(nums[i]<nums[i+1]){
                count++;  //递增+1
            }else{
                count=1;  //断了就从1开始
            }
            ans=count>ans?count:ans; //返回最大的值
        }
        return ans;
    }

}

实现

35.搜索插入位置(双指针二分法)

题目

分析

1. 找到：就是二分法直到某一次中间指针和要找的一样
2. 没找到：就和之前的找缺少的数字一样不断地二分法

代码

public class SouSuoChaRuWeiZhi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(searchInsert(a,m));  //调用方法返回结果
    }

    public static int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int zhong=(left+right)/2;
            if(nums[zhong]==target){ //如果找到了就返回
                return zhong;
            }else   //如果找不到就找缺的位置(和之前的找缺少点一样)
                if(nums[zhong]<target){  //在右边
                   left=zhong+1; 
            }else{   //在左边
                right=zhong-1;
            }
        }
        return left;
    }

}

结果

1299.将每个元素替换成右侧最大元素(反序遍历)

题目

分析

1. 这个题反序遍历会很好做！！！
2. 思路：
    2.1 设置max存放右边最大的值(对比一次就更新一次)
    2.2 设置temp存当前的值(用于更新对比)
    2.3 存放最大值max给当前值 然后进行max更新

代码

public class TiHuanYouCeZuiDa {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int[] b=replaceElements(a);  //新数组接结果
        for(int i=0;i<n;i++){
            System.out.print(b[i]+" ");
        }
    }
    //反序遍历
    public static int[] replaceElements(int[] arr) {
        int max=-1;  //一开始从最后一个开始赋-1
        for(int i=arr.length-1;i>=0;i--){
            int temp=arr[i];
            arr[i]=max;  //当前值赋给右边最大值
            max=temp>max?temp:max; //max更新为右边最大值
        }
        return arr;
    }

}

结果

167.两数之和II -输入有序数组(双指针)

题目

分析

1. 使用双指针思路： 左右指针相加计算
2. 计算思路(return new int[]{left+1,right+1})：
    2.1 左右指针之和 == target  就直接新建数组返回两个下标
    2.2 左右指针之和 < target 左边太小 左指针右移
    2.3 左右指针之和 > target 右边太大 右指针左移

代码

public class LiangShuHe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        int[] c=twoSum(a,m);  //接结果数组
        for(int i=0;i<2;i++){
            System.out.print(c[i]+" ");
        }

    }

    public static int[] twoSum(int[] numbers, int target) {
        if(numbers==null){
            return null;
        }
        int left=0;  //左指针
        int right=numbers.length-1;  //右指针
        while(left<right){
            int sum=numbers[left]+numbers[right];  //两个指针所在数组的值
            if(sum==target){
               return new int[]{left+1,right+1};  //直接返回一个新建数组 值就是两个下标
            }else
            if(sum<target){  //左边的太小  左指针右移
                left++;
            }
            else{   //右边的太大 右指针左移
                right--;
            }
        }
        return null;
    }

}

结果

1266.访问所有点的最小时间(切比雪夫距离)

题目

分析

其实就是dx和dy的最大值之和

代码

public int minTimeToVisitAllPoints(int[][] points) {
    int res=0; //最后的距离
    for(int i=1;i<points.length;++i){
        int xMinus=Math.abs(points[i][0]-points[i-1][0]);
        int yMinus=Math.abs(points[i][1]-points[i-1][1]);
        res+=(xMinus>yMinus?xMinus:yMinus); //加两坐标差最大值
    }
    return res;
}

结果

1010.总持续时间可被60整除的歌曲(排列组合)

题目

分析

1. 思路：主要是卡在了如何配对 因为假如20和40配对了但是20还可以和后面的100配对所以没办法取消
        因此借鉴了大佬的将所有数组%60取余数进行分类讨论
2. 具体实现：
        2.1 余数是0的两两配对选择   n*(n-1)/2
        2.2 余数是30的两两配对也是  n*(n-1)/2
        2.3 其他余数就是 n*m

代码

public class LiuShiZhengChuGeQu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(numPairsDivisibleBy60(a));  //调用方法返回结果
    }

    public static int numPairsDivisibleBy60(int[] time) {
        int[] yu=new int[60];
        for(int i=0;i<time.length;i++) {
            yu[time[i]%60]++;  //每个数字的余数放在yu数组对应下标
        }
        //记录总数的count
        int count=0;
        //1. 余数是0的情况两两选择 ls*(ls-1)/2
        	int ls=yu[0];
        	count=ls*(ls-1)/2;
        //2. 余数是30的情况两两选择 ss*(ss-1)/2
        	int ss=yu[30];
        	count+=ss*(ss-1)/2;
		//3.其余的1对59 2对58就用双指针进行移动添加  n*m
        	int i=1;  //左指针
        	int j=59;//右指针
        	while(i<j){
            	count+=yu[i++]*yu[j--];  //1对59 2对58 3对57等等
        	}
        return count;  //返回成功的对数
    }

}

结果

1351.统计有序矩阵中的负数

题目

分析

1. 类似于剑指offer内的统计正数的个数
2. 我们考虑用两个指针识别
    2.1 如果当前值>0 说明左边的这行都不符合 直接行指针下移一行
    2.2 如果当前值<0 说明下边的这列都符合   直接列指针左移一列 然后将这列的其他元素计数++

代码

public class TongJiFuShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[][] a=new int[m][n];
        for(int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                a[i][j]=input.nextInt();  //输入二维数组
            }
        }
        System.out.println("最终负数的个数是:"+countNegatives(a));
    }

    public static int countNegatives(int[][] grid) {
        int count=0;
        int hang=0;  //初始从第一行
        int lie=grid[0].length-1;  //初始从最后一列开始
        for(;hang<grid.length&&lie>=0;){
          //1. 当前位置是正数 因为是递减所以它前面的不符合 直接换下一行
            if(grid[hang][lie]>=0){
                hang++;  //换下一行
            }
          //2. 当前位置是负数  因为是递减所以它下面的都符合 直接换前面一列
            else{
                int temp=hang;  //找个中间值替换行 不然while会改变hang影响count计数
                while(temp<grid.length) {
                    System.out.print(grid[temp++][lie]+" "); //输出这列所有负数
                }
                count+=grid.length-hang; //这一列有几个数字符合 (行长度-当前行)
                lie--;  //换前一列
            }
        }
        return count;
    }

}

结果

1089.复写零(ArrayList集合)

题目

分析

这种题目主要是在0后面加0如果用数组比较麻烦，因此选择list集合

代码

public class FuXieLin {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        ArrayList<Integer> lister=duplicateZeros(a);
        for(int i=0;i<a.length;i++){
            System.out.print(lister.get(i));
        }

    }

    public static ArrayList<Integer> duplicateZeros(int[] arr) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0){
                list.add(arr[i]);
            }
            if (arr[i]==0) {
                list.add(arr[i]);
                list.add(arr[i]);
            }
        }
        return list;
    }

}

结果

605.种花问题(贪心)

题目

分析

1. 最左侧： 00...  考虑一侧是不是为0
2. 最右侧： ...00  考虑一侧是不是为0
3. 中间位置：...000...  考虑两侧是不是为0

代码

public class ZhongHua {public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(canPlaceFlowers(a,m));
    }

    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(n==0) {
            return true; //不种花 返回成功
        }
        int count=0; //记录可以种的个数
        int i=0; //记录下标
        while (i < flowerbed.length) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;  //种花 +1 
                count++;  //记录种了多少次
            }
            i++;
        }
            return count>=n;  //返回是否可以
    }

}

结果

1346.检查整数及其两倍数是否存在(哈希表HashMap)

题目

分析

1. 思路：使用hashMap进行存放数组的所有元素
2. 步骤：
    2.1 先新建hashmap将数组依次放入
    2.2 然后判断0的情况 如果有两个0以上就符合条件
    2.3 然后判断非0的情况 如果2倍的在map里面有的话就说明符合条件

代码

public boolean checkIfExist(int[] arr) {
    Map map=new HashMap();
    int zeroCount=0;// 对0进行特殊处理
    for (int i = 0; i < arr.length; i++) {
        if(arr[i]==0){// 计算0的个数
            zeroCount++;
        }
        map.put(arr[i],0);  
    }
    if(zeroCount>=2){// 如果存在两个以上的0，就符合
        return true;
    }else {
        for (int i : arr) {
            if (i!=0&&map.containsKey(i * 2)) {  //如果map里面有2倍的i存在
                return true;
            }
        }
    }
    return false;
}

结果

53.最大子序和(动态递归)

题目

分析

1. 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
2. sum>0，则说明sum有增益效果，则sum保留并加上当前遍历数字
3. sum<=0则说明sum需要舍弃，则sum直接为当前遍历数字
4. 每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果

代码

public class ZuiDaZiXuHe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        System.out.println(maxSubArray(a));
    }

    public static int maxSubArray(int[] nums) {
        int ans=nums[0]; //当前最大就是第一个数
        int sum=0;
        for(int i=0;i<nums.length;i++){
          if(sum>0){
             sum+=nums[i];  //sum>0就说明对结果有好处
          }else{
              sum=nums[i];  //sum<0就说明需要扔掉 sum直接成为当前数字
          }
          ans=Math.max(ans,sum);  //每次将当前最大值和 一轮之后的sum比较
        }
        return ans;
    }

}

结果

643.子数组最大平均数(滑动窗口)

题目

分析

1. 思路：我们需要初始化前k个的值,设置ans存最好的结果，he是目前的结果。
2. 滑动窗口：he+=nums[i]-nums[i-k];  //加后面的一个就必须要减去前面一个

代码

public class ZuiDaPingJunShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        int k=input.nextInt();
        System.out.println(findMaxAverage(a,k));  //调用方法
    }

    public static double findMaxAverage(int[] nums, int k) {
        double he=0;
        for(int i=0;i<k;i++) {
            he += nums[i];   //加上前面的k个当做初始和
        }
        double ans=he;  //目前结果为初始和
        for(int i=k;i<nums.length;i++){  //从前k个和之后遍历
             he+=nums[i]-nums[i-k];  //加后面的一个就必须要减去前面一个
             ans=Math.max(he,ans);  //每次选最大的更新
        }
        return ans/k;  //he/k就是最终平均值
    }

}

结果

1122.循环遍历矩阵(四个指针)

题目

分析

1. 如果数组为空 --返回为null
2. 如果数组不为空
     2.1 建立ArrayList集合
     2.2 建立四个坐标用于标识数组变化
     2.3 从左往右(行：top            列：left到right)
     2.4 从上到下(行：top+1到bottom  列：right) 
     2.5 从右到左(行：bottom         列：right-1到left)  --注意可能最后是一行就不进行这一步
     2.6 从下到上(行：bottom-1到top  列：left)    --注意可能最后是一列就不进行这一步

代码

public class XiangDuiPaiXu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();
            }
        }
        System.out.println(spiralOrder(a).toString()); //接结果按字符串返回
    }

    public static ArrayList<Integer> spiralOrder(int[][] a) {
        if(a==null){
            return null;  //如果数组为空 就输出null
        }
        ArrayList<Integer> list=new ArrayList<Integer>();  //新建list集合存结果
        int row=a.length;     //行
        int col=a[0].length;  //列
        int left=0;   //二维数组上面行的最左边
        int right=col-1; //二维数组上面行的最右边
        int top=0;   //二维数组左边的最上边
        int bottom=row-1;  //二维数组左边的最下边
		/*
			假设以4*4举例：
				1  2   3  4
				5  6   7  8
				9  10 11 12
				13 14 15 16
		*/
        while(left<=right&&top<=bottom){
            //1.左到右
                for(int i=left;i<=right;i++){  //输出1 2 3 4(一直到right)
                    list.add(a[top][i]);
                }
            //2.上到下
                for(int i=top+1;i<=bottom;i++){  //输出 8 12 16(从top+1到bottom)
                    list.add(a[i][right]);
                }
            //3.右到左
                if(top!=bottom) {
                    for (int i = right-1; i >=left; i--) {  //输出15 14 13(从right-1到left)
                        list.add(a[bottom][i]);
                    }
                }
            //4.下到上
                if(left!=right) {
                    for (int i = bottom-1; i > top; i--) {  //输出 9 5 1(从bottom到top-1)
                       list.add(a[i][left]);
                    }
                }
            //5.一轮结束之后更改四个坐标
                left++;
                right--;
                top++;
                bottom--;
        }
        return list;  //返回集合
    }

}

结果

53.在排列数组中查找出现次数(二分法)

题目

分析

1. 使用两次二分法确定左边和右边界限
2. 最终次数就是出现的长度 (right-right-1)

代码


public class ChaZhaoShuZi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
           a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(search(a,m));
    }

    public static int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
    //1. 找右边界
        while(left<=right){
            int middle=(left+right)/2;
            if (nums[middle]<=target){   //一直找最右边的数字！！！！！！
                left=middle+1;   //在右边
            }else{
                right=middle-1;  //在左边
            }
        }
        int righter=left;

    //初始化左右指针
       left=0;
       right=nums.length-1;

    //2. 找左边界
        while(left<=right){
            int middle=(left+right)/2; 
            if (nums[middle]>=target){   //一直找最左边的数字！！！！！！！
                right=middle-1;   //在右边
            }else{
                left=middle+1;    //在左边
            }
        }
        int lefter=right;
        
        return righter-lefter-1;  //返回出现区间的大小
    }

}

结果

面试4.二维数组中查找(两个指针移动)

题目

分析

1. 制定hang和lie两个指针
2. 二维数组遍历
    /*
        1 4 7 11 15
        2 5 8 12 19
        3 6 9 16 22      假设目标是13
        10 13 14 17 24
        18 21 23 26 30
    */
    2.1 只要当前的比target大(16>13) 说明这一列下面都不符合    换前一列lie--；
    2.2 只要当前的比target小(7<13)  说明这一行左边的都不符合  换下一行hang++；
    2.3 直到遇到的话输出true，没有的话就是false

代码

public class ErWeiShuZuChaZhao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();
            }
        }
        int target=input.nextInt();
        System.out.println(findNumberIn2DArray(a,target));
    }

    public static boolean findNumberIn2DArray(int[][] a, int target) {
        int hang=0;
        int lie=a.length-1;
        for(int i=0;i<a.length;i++){   //二维数组循环
            for(int j=0;j<a[i].length;j++){
                if(a[i][j]>target){  //这列下面的都比当前的大 只能换前一列找
                    lie--;
                }
                if(a[i][j]<=target){  //这行没看的了 换下一行
                    hang++;
                }
                if(a[i][j]==target){  //找到了就返回true
                    return true;
                }
            }
        }
        return false;
    }

}

结果

面试3.数组中重复的数字(数组下标存储)

题目

分析

1. 遍历数组使用Arrays.sort()方法排序之后通过数组下标存到另外一个数组B。
2. 遍历数组如果里面的值>1就直接break就行，题目只需要输出一个。

代码

public class ShuZuChongFuShu {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findRepeatNumber(a));
    }

    public static int findRepeatNumber(int[] nums){
        int flag=0;
        Arrays.sort(nums);
        int[] b=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            b[nums[i]]++;
        }
        for(int i=0;i<nums.length;i++){
            if(b[i]>1){
                flag=i;
                break;
            }
        }
        return flag;
    }

}

结果

面试17.主要元素(投票)

题目

分析

1. 思路：我们可以sort排序之后查看中间位置的数字就是主要元素。

代码

public class ZhuYaoYuanSu {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(majorityElement(a));
    }

    public static int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;    //如果没有数组/数组为空  --> 返回-1
        }
        Arrays.sort(nums);  //排序
        int result = nums[nums.length/2];  //下标在中间的数一定是要找的数
        return result;
    }
}

结果

面试17.22.单词转换(DFS/BFS)

题目

分析

代码

1
2

结果

面试17.4消失的数字(双指针二分法)

题目

分析

找缺失数字系列题目
1. 排序(保证按照顺序啦)
2. while循环双指针二分法
    2.1 中间数==下标(前面的没缺少) 左指针到中间的右边一个数字
    2.2 中间数!=下标(前面有缺少)     右指针到中间的左边一个数字

代码

public class DanCiZhuanHuan {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(missingNumber(a));
    }

    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);  //排序
        int left=0; //左指针
        int right=nums.length-1;  //右指针
            while (left <= right) {
                int zhong = (left + right) / 2;
                if(nums[zhong]==zhong){
                    left=zhong+1; //左边的下标和数值没有断就肯定是相等 所以缺失的在右边 左指针放在中间指针右边
                }
                else{
                    right=zhong-1; //左边肯定缺失了 右指针放到中间指针的左边
                }
            }
        return left;
    }

}

结果

面试16.17.连续数列(动态递归)

题目

分析

1. 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
2. sum>0，则说明sum有增益效果，则sum保留并加上当前遍历数字
3. sum<=0则说明sum需要舍弃，则sum直接为当前遍历数字
4. 每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果

代码

public class LianXuShuLie {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(maxSubArray(a));
    }

    public static int maxSubArray(int[] nums) {
        int ans=nums[0]; //当前最大就是第一个数
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];  //sum>0就说明对结果有好处
            }else{
                sum=nums[i];  //sum<0就说明需要扔掉 sum直接成为当前数字
            }
            ans=Math.max(ans,sum);  //每次将当前最大值和 一轮之后的sum比较
        }
        return ans;
    }

}

结果

面试16.15珠玑妙算(HashMap集合)

题目

分析

1. 伪猜中=real-fake
2. 使用HashMap集合：一个存储字母一个是次数
3. 遍历solution字符串，保存每个字母对应的次数
4. 遍历guess字符串，两个字符串 抵消掉猜对的数字其他的就是伪猜中的次数(计算最大匹配成功数)
5. 遍历两个字符串得到真正匹配成功数
6. 最后新建数组弹出real和real-fake即可

代码

public class ZhuJi {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        String a=input.next();
        String b=input.next(); 
        int[] ans=masterMind(a,b);
        for(int i=0;i<ans.length;i++){
            System.out.print(ans[i]+" ");
        }
    }

    public static int[] masterMind(String solution, String guess) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();

        for(char c:solution.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);  //往map里面存solution里面每个字母的个数
        }

        int fake=0,real=0;  //fake伪没猜中  //real为猜中

        for(char c:guess.toCharArray()){
            if(map.containsKey(c)&&map.get(c)>0){  //抵消掉猜对的数字其他的就是伪猜中的次数
                fake++;
                map.put(c,map.get(c)-1);  //减少出现的次数(最后计算最大的匹配成功数)
            }
        }

        for(int i=0;i<4;i++){
            if(solution.charAt(i)==guess.charAt(i)){real++;}  //如果每一位相等说明猜中了+1
        }

        int[] ans={real,fake-real};  //伪猜中包含猜中次数
        return ans;
    }

}

结果

面试08.03魔术索引(双指针二分法)

题目

分析

1. 和找缺失的数组的下标题一样
2. 双指针二分法判断

代码

public class MoShuSuoYin {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findMagicIndex(a));
    }

    public static int findMagicIndex(int[] nums) {
        int left = 0, right = nums.length;  //左右指针
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] != mid)  //左边有缺少的数字
			{
                if (nums[mid] >= 0) 
				{  
                    right = mid;
                } 
				else 
				{
                    left = mid + 1;  //在右边
                }
            } 
			else
			 {
                left = mid + 1;  //右边有缺少的数字
            }
        }
        return left -1;
    }

}

结果

面试01.02判断是否互为字符重排

题目

分析

1. 统计每个出现次数如果出现次数一样就肯定可以重排
2. 步骤
    2.1 如果长度不同肯定false
    2.2 将s1的每个单词的ascii码存进去一个int数组
    2.3 将s2的每个单词的ascii码从int数组删除掉
    2.4 如果数组还是一直全是0就成功true

代码

public class ZiFuChongPai {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s1=input.next();
        String s2=input.next();
        System.out.println(CheckPermutation(s1,s2));
    }

    public static boolean CheckPermutation(String s1, String s2) {
        int l1=s1.length();
        int l2=s2.length();
        if(l1!=l2){     //如果两个长度不一样直接返回false
            return false;
        }
        int[] index=new int[128];  //char存的是里面的ascii码
        for(int i=0;i<l1;i++){
            index[s1.charAt(i)]++;  //将s1里面的字符的ascii码添加到数组
            index[s2.charAt(i)]--;  //将s2里面的字符的ascii码从数组删除
        }
        for(int i=0;i<index.length;i++){
            if(index[i]!=0){  //如果存的那个数组里面全空 那就是能重排
                return false;
            }
        }
        return true;
    }

}

结果

面试01.01判断字符是否唯一(首次和最后一次出现位置不同)

题目

分析

1. 使用indexof和lastindexof方法
2. 只要首次和末次出现位置不同就说明至少出现两次以上！！！！

代码

public class PanDuanWeiYi {  public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s1=input.next();
        System.out.println(isUnique(s1));
    }
    public static boolean isUnique(String s1) {
        for(char ch:s1.toCharArray()){  ///增强for循环 s1的每个字符
        //第一次和最后一次出现位置不同(一定至少两个)
            if(s1.indexOf(ch)!=s1.lastIndexOf(ch)){
                return false;
            }
        }
        return true;
    }

}

结果

面试01.07旋转矩阵(二次旋转)

题目

分析

代码

public static void rotate(int[][] matrix) {
        int n=matrix.length;  //获取数组长度
        //1. 以对角线(左上-右下)为轴反转
            for(int i=0;i<n-1;i++){  //假如n=3 只取0 1这两行(我们只看右上角)
                for(int j=i+1;j<n;j++){  //假如n=3  依次取01 02 12(右上角三个数字) 
                    int tmp=matrix[i][j];  
                    matrix[i][j] = matrix[j][i];  //对角线的两边的两个数互换
                    matrix[j][i] = tmp;
                }
            }

        //2. 每一行以中点进行翻转
            int mid=n>>1;  //就是取一半(>>二进制向右挪一位)
			/*
				3(0011) -> 1(0001)  所以三列中间的是第二列(下标是1)
				5(0101) -> 2(0010)  所以五列中间的是第三列(下标为2)		
			*/
        for (int i = 0; i < n; i++) {    //所有行都循环
            for (int j = 0; j < mid; j++) {  //列只找到左边一半
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];   //中点行两边的互换 
                matrix[i][n - 1 - j] = tmp;
            }
        }

    }

结果

面试01.08零矩阵(一维数组定行列)

题目

分析

1. 思路：
    1.1 新建两个一维数组存放需要清0的行和列 
2. 步骤：
    2.1 先遍历获取出来要清0的行和列的下标
    2.2 然后遍历查找需要清0的行然后清0
    2.3 然后遍历查找需要清0的列然后清0

代码

public class LingJuZheng {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        int[][] a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a[i][j] = input.nextInt();
            }
        }
        setZeroes(a); //调用方法进行清0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                System.out.print(a[i][j]+" ");  //输出数组
            }
            System.out.println();
        }

    }

    public static void setZeroes(int[][] matrix) {
        boolean[] line = new boolean[matrix.length];   //设置两个存放行和列的布尔数组
        boolean[] column = new boolean[matrix[0].length];
        //1.找出要清零的行列
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    line[i] = true;   //存放要清0的行
                    column[j] = true; //存放要清0的列
                }
            }
        }

        //2.开始对行清零
        for (int i = 0; i < matrix.length; i++) {
            if (line[i]) {  //行存在
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;   //所在列清0
                }
            }
        }

        //3.开始对列清零
        for (int i = 0; i < matrix[0].length; i++) {
            if (column[i]) { //列存在
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;  //所在行清0
                }
            }
        }

    }

}

结果

面试05.08绘制直线(位运算)

题目

分析

代码

class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {  
        int[] ans=new int[length];
        int low=(y*w+x1)/32;
        int high=(y*w+x2)/32;
        for(int i=low;i<=high;i++){
            ans[i]=-1;
        }
        ans[low]=ans[low]>>>x1%32;
        ans[high]=ans[high]&Integer.MIN_VALUE>> x2 % 32;
        return ans;

    }
}

结果

面试08.04幂集(回溯法)

题目

分析

代码

public class MiDeng {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(subsets(a));
    }

    public static List<List<Integer>> subsets(int[] nums) {
        //结果集合
            List<List<Integer>> list = new ArrayList();
        //回溯方法
            backtrack(list,new ArrayList<>(),nums,0);
        //返回list集合
            return list;
    }

    public static void backtrack(List<List<Integer>>list,List<Integer>tempList,int []nums,int start){
        List<Integer> templist=new ArrayList<>();  //里面临时集合templist
        list.add(tempList); //新建名为tempList集合
        for(int i=start;i<nums.length;i++){
            tempList.add(nums[i]);  //把start之后的元素添加进去
            backtrack(list,tempList,nums,i+1);  //进行下次回溯
            tempList.remove(tempList.size()-1); //移除最后一个
        }
    }

}

结果

所有奇数长度子数组的和

题目

分析

1. 难点就在于怎么确定截取的位置，怎么找到所有奇数位置
2. 考虑从第一位开始找每一位符合的奇数，所以i从0到len
3. 然后就是考虑j的变化，因为每次i变化之后j只能从i后面取，所以j从等于i开始遍历
4. 符合条件: 如果j-i是0 2 4这种的话就是符合条件(i和j都是第二位的话，就算是奇数位，所以是0 2 4)
5. 就可以单独写一个方法计算i到j的和，每次if符合调用返回结果。

代码


import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] arr=new int[]{1,4,2,5,3};
        System.out.println(sumOddLengthSubarrays(arr));
    }
 
    public static int sumOddLengthSubarrays(int[] arr) {
        int res=0;
        int len=arr.length; //获取数组长度
        for(int i=0;i<len;i++){
           for(int j=i;j<len;j++){
               if((j-i)%2==0){  //奇数距离
                   res+=find(i,j,arr);
                   System.out.println("这次是从第"+(i+1)+"到第"+(j+1)+"个位置求和，和为:"+res);
               }
           }
        }
        return res;
    }

    public static int find(int i,int j,int[] arr){
        int sum=0;
        for(int z=i;z<=j;z++){
            sum+=arr[z];
        }
        return sum;
    }

}

结果

根据数字二进制下1的数目排序(Integer.bitCount()方法)

题目

分析

1. 遍历所有数组求1的个数
2. 将每个数中1的个数*10000+原数
3. Arrays.sort()排序之后在%10000就可以得到排序

代码


public int[] sortByBits(int[] arr) {
    int[] map = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        map[i] = Integer.bitCount(arr[i]) * 10000000 + arr[i];  //1的个数*100000000+原数
    }
    Arrays.sort(map);  //排序
    for (int i = 0; i < map.length; i++) {
        map[i] = map[i] % 10000000;  //取余
    }
    return map;  //返回数组
}

结果

分糖果(一半和不同糖果数对比)

题目

分析

1. 妹妹和弟弟手里都是a.length/2个糖果
2. 具体妹妹拿多少就要看set去重和平均值得大小对比

代码


public int distributeCandies(int[] candies) {
       HashSet < Integer > set = new HashSet < > ();
       for (int candy: candies) {
           set.add(candy);  //记录不同糖果的个数
       }
       return Math.min(set.size(), candies.length / 2);  //对比两者
   }

结果

数组序号转换(map集合存<数字,序号>)

题目

分析

1. 因为有重复的数字 所以直接输出不太好弄
2. 使用map集合存储每个数字和数字出现的位置(排序sort之后就好弄)
3. for循环a数组，这样可以顺序填进去

代码


public static int[] arrayRankTransform(int[] a) {
       int n=a.length;  //数组长度
       int[] temp=a.clone();  //赋值a数组生成新的temp数组
       Arrays.sort(temp);  //sort排序
       int count=1;
       Map<Integer,Integer> map=new HashMap<>();  //生成map集合
       for(int i=0;i<n;i++){
           if(!map.containsKey(temp[i])){
               map.put(temp[i],count++);  //只将不重复的数字  存入数字和序号
           }
       }
       for(int i=0;i<n;i++){
           a[i]=map.get(a[i]);  //遍历a数组 将序号放入
       }
       return a;  //输出原数组
   }

结果

最长和谐子序列(枚举)

题目

分析

1. 从第一位开始遍历 找到跟他一样大而且比他大1的数字就count计数器+1
2. 注意就是一定要有比他大1的数，用一个布尔值确定有没有。!!!!!

代码


public int findLHS(int[] nums) {
       int res = 0;   //接住最后结果
       for (int i = 0; i < nums.length; i++) {   //遍历所有元素
           int count = 0;  //记录每个元素的个数
           boolean flag = false;
           for (int j = 0; j < nums.length; j++) {
               if (nums[j] == nums[i])  //找到和当前值一样的值可以当做序列值
                   count++;
               else if (nums[j] + 1 == nums[i]) {  //找到比当前值大1的值也可以当序列值
                   count++;
                   flag = true; //标志改为true  说明满足有最大最小值
               }
           }
           if (flag)
               res = Math.max(count, res);  //如果有的话 就找最大值
       }
       return res;  //返回res结果
   }

结果

2020-05-11

剑指offer

数组

二维数组的查找

面试三题目

题目分析

1. 使用暴力二重循环遍历
2. 使用题目中横竖都递增的原理：
    2.1 如果相等输出true
    2.2 目标n>a[i][j] 说明我们要找的比现在位置的要大 (这一行都比目标的小)所以下移一行 i++
    2.3 目标n<a[i][j] 说明我们要找的比现在位置的要小 (这一列都比目标的大)所以左移一列 j--

代码实现

public class erweishuzuchazhao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
          System.out.println("输入要查找的元素的值：");
2020/5/18 10:14:36           System.out.println("输入二维数组的行：");
            int h=input.nextInt();  //输入二维数组的行
          System.out.println("输入二维数组的列：");
            int l=input.nextInt();  //输入二维数组的列
            int[][] a =new int[h][l];
          System.out.println("输入二维数组内容：");
            //输入二维数组的值
                for(int i=0;i<h;i++){
                   for(int j=0;j<l;j++){
                    a[i][j]=input.nextInt();
                   }
                }
            //调用函数得到结果
               if(chazhao(a,n)==1){
                   System.out.println("要查询的"+n+"存在");
               }else{
                   System.out.println("要查询的值不存在");
               }
    }

  //1. 二维数组循环遍历(不推荐)
    public static int chazhao(int[][] a,int n){
        int f=0;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a[i].length;j++){
                if(a[i][j]==n)
                {
                    f=1;  //存在就赋值为11
                }
            }
        }
        return f;
    }

 //2. 布尔值判断
 public boolean Find(int n, int [][] a) {
        //判断数组空
        if((a==null||a.length==0)||(a.length==1&&a[0].length==0)){
            return false;
        }
        int i=0; //左上角
        int j=a[0].length-1;  //右上角
        while(i<=a[0].length-1&&j>=0){
            if(n==a[i][j]) {return true;}   //找到了
            if(n<a[i][j]) {j--;}   //这一列都比n大 (往左移动)
            else{ i++;}   //这一行都比n小(往下移动)
        }
        return false;
    }

}

实现结果

字符串

替换空格

面试四题目

请实现一个函数，把字符串中的每个空格替换成”%20”.例如输入“We are happy.”，则输出为”We%20are%20happy.”

题目分析

1. 这类题解决网络编程中由于URL参数中含有特殊字符导致服务器端无法获取正确的参数值。
    1.1 解决规则：通过在'%'后跟上ASCII码的两位十六进制的表示。
    1.2 解决举例：空格的ASCII码是32(16进制的0x20)，因此空格被替换为"%20"
2. 空格替换的实现方式：
    2.1 将原来的字符串中的空格字符 --> '%' '2' '0' 这三个字符(覆盖修改字符串后面的内存)
    2.2 新建StringBuilder字符串在此上面替换(可以自己分配足够多的内存) 
    2.3 新建数组实现

代码实现

public class zifutihuan {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.nextLine();
        System.out.println(replaceSpace(s));
 System.out.println(replaceSpace(s));
    }

    //1.新建数组实现
    public static char[] replaceSpace(String s){
 		if(s==null){
            return null;  //字符串为空就输出null
        }
        char[] a=new char[s.length()*3];
        int size=0;
        //循环新字符数组然后进行更替操作
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);  //获取s字符串的对应字符
            if(c==' '){
                a[size++]='%';
                a[size++]='2';
                a[size++]='0';
            }else{
                a[size++]=c;  //把原来的字符放进去
            }
        }

      return a;
    }

    //2.新建StringBuilder类实现
    public String replaceSpace(StringBuffer str) {
    	if(str==null){
            return null;  //字符串为空就输出null
        }
        StringBuilder s=new StringBuilder();
        for(int i=0;i<str.length();i++){
            char c=str.charAt(i);
            if(c==' '){
                s.append('%');
                s.append('2');
                s.append('0');
            }else{
                 s.append(c);
            }
        }
        return s.toString();
    }

}

实现结果

字符串的排列

面试题二十八题目

题目分析

代码实现

public class ZiFuPaiLie {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.nextLine();
        System.out.println("要排列的字符串:"+s);
        System.out.println("排列之后的结果"+Permutation(s));
    }

    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> ans=new ArrayList<String>();
        char[] a=str.toCharArray();  //字符串转数组
        
        return ans;
    }

}

实现结果

链表

从尾到头打印链表

面试五题目

输入一个链表的头结点，从尾到头反过来打印每个结点的值。

题目分析

1. 很明显这需要用栈实现，将链表的每个元素压入栈然后弹出

代码实现

ListNode类：

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

mianshisan类：

public class mianshisan {
    public static void main(String[] args) {
        ListNode head1=new ListNode(1);
        ListNode head2=new ListNode(3);
        ListNode head3=new ListNode(2);
        head1.next=head2;  //生成链表：1 --> 2 --> 3
        head2.next=head3;
        head3.next=null;
       //调用方法
        reversePrint(head1);
    }

    //自定义反转打印的方法
    public static void reversePrint(ListNode head){
        //压栈
        Stack<ListNode> stk=new Stack<>();
        ListNode temp=head;
        while(temp!=null){  //直到指向最后一个位置
            stk.push(temp);
            temp=temp.next; //不断更替
        }
        //循环输出
        while(!stk.isEmpty()){
            System.out.println(stk.pop().val);  // 挨个出栈
        }
    }

}

实现结果

树

重建二叉树

面试六题目

题目分析

此题就是

代码实现

1
2

实现结果

递归和循环

斐波那契数列

面试九题目

题目分析

1.递归：
    1.1 如果n=1/n=0就返回n
    1.2 其他情况下递归调用n-1和n-2

2.动态规划：    
    不断循环递进求最后一个数的原理
     c=a+b;  //第三个数
     a=b;   //原来的b成为下一轮的a
     b=c;   //原来的c成为下一轮的b

代码实现

public class FeiBo {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        //System.out.println("递归:"+digui(n));     //递归
        System.out.println("动态规划:"+dongtai(n));   //动态代理
    }

    //递归
    public static int digui(int n){
        if(n<=0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return digui(n-1)+digui(n-2);  //从第二项开始依次递增
    }

    //动态规划
    public static long  dongtai(int n){
		if(n<=0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        long a=1;
        long b=1;
        long c=2;
        for(int i=2;i<n;i++){  //依次往后挪动
            c=a+b;  //第三个数
            a=b;   //原来的b成为下一轮的a
            b=c;   //原来的c成为下一轮的b
        }
        return c;
    }

}

实现结果

1.测试小数字时候递归还可以：

2.测试大的数字之后递归暴露了自己的缺点：

青蛙跳台阶(普通)

面试九题目

题目分析

1.递归
    1.1 前三项和n一样
    1.2 第四项之后开始就是前两项之和(斐波那契数列)
2.动态规划
    不断循环递进求最后一个数的原理
     c=a+b;  //第三个数
     a=b;   //原来的b成为下一轮的a
     b=c;   //原来的c成为下一轮的b

代码实现

import java.util.Scanner;
public class FeiBo {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println("递归:"+digui(n));     //递归
        System.out.println("动态规划:"+dongtai(n));   //动态代理
    }

    //递归
    public static int digui(int n){
        if(n<=3){
            return n;  //前三个就是 1 2 3 (5 8...)
        }
        return digui(n-1)+digui(n-2);  //其余就是前两者之和
    }

    //动态规划
    public static long dongtai(int n) {
        if(n<=3){
            return n;  //前三个就是 1 2 3 (5 8...)
        }
        long sum=0;
        long a=1;
        long b=2;
        for(int i=2;i<n;i++){
            sum=a+b;  //后面的是前面的两次
            a=b;      //现在的第二个是下一轮的第一个
            b=sum;    //现在的总和是下一轮的第二个
        }
        return sum;
    }

}

实现结果

青蛙跳台阶(变态)

面试九题目

题目分析

 1.推理可得到f(n)=2f(n-1)

f(1) = 1;
f(2) = f(1)+1 = f(1)+f(1) = 2*f(1) = 2;
f(3) = f(2)+f(1)+1 = f(2)+f(1)+f(1)= f(2)+2*f(1) = f(2)+f(2)=2*f(2) = 2*2;
f(k) = f(k-1) + f(k-2) + …+ f(2)+ f(1) + 1= f(k-1) + f(k-2) + …+ f(3)+f(2)+f(1) + f(1)
     = 2*f(k-1)

代码实现

public class QingWa {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println("递归:"+tiao(n));       //递归
        System.out.println("动态规划:"+tiaoer(n)); //动态规划
    }

    //递归实现
    public static int tiao(int n) {
        if(n<=1){
            return 1;   // f(n)=1
        }
        return 2*tiao(n-1);  // f(n)=2*f(n-1)
    }

    //动态规划
     public static int tiaoer(int n) {
        if(n<=0){
            return 0;   // f(0)=0
        }
        if(n==1){
            return 1;   // f(1)=1
        }
        int a=1;
        int b=1;
        for(int i=1;i<n;i++){
            b=a*2;  //当前的值是上一个的二倍
            a=b;   //计算出来的值当做下一轮的数
        }
        return b;
    }

}

实现结果

位运算

二进制中1的个数

面试十题目

题目分析

1.关于求解1的个数(负数容易死循环--它要整体n/2右移保证还是一个负数所以前面一直补1--不可能将n/2为0)
    1.1 循环(只解决正数)：从个位不断取出来n(n%10)的数字判断是否为1然后n/n缩小范围最后输出个数
    1.2 位运算(n与n-1):会把最右边的1变为0 能进行多少次就相当于有多少个1
    1.3 使用Integer.toBinaryString(n)将n的二进制转为字符串，遍历1的个数

2.关于输出每位数字
    2.1 字符串拼接：(字符串+数字=数字拼一起)
    2.2 数组存放：(每一位放数组内反序输出)

代码实现(只能处理正数)

public class QiuYi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println("一共有:"+qiu(n));  //1的个数
        System.out.println(qiuer(n));  //每一位的值
    }

    //求出有多少个1
    private static long qiu(int n) {
        long sum=0;  //计数器
        int m=1;  //每一位的值
        while(n!=0){
            m=n%2;
            if(m==1){
                sum++;  //如果是1就计数器加1
            }
            n=n/2;
        }
        return sum;
    }

    //输出每一位的值
    private static String qiuer(int n) {
        int[] a=new int[100];  //定义数组存放每一位元素
        String target="";
        int i=0;  //获取每一位的数字
        while(n!=0){
            i=n%2;
            target=i+target;  //字符串+数字=数字附加(将每次i放前面加  因为从个位取出来是反序的)
            n=n/2;
        }
        return target;
    }

}

代码实现(位运算)

1100为例，减去1就是1011，两者相与就是1000(相当于第二位的1没了)

private static int qiusan(int n) {
        int sum=0;
        while(n!=0){
            n=n&(n-1);  // (原整数-1)与(原整数) == (最右边1变为0)
            sum++;  //变一次就相当于记录一个1变化
        }
        return sum;
    }

代码实现(Integer.toBinaryString()然后遍历)

//Integer.toBinaryString()
    private static int qiusi(int n) {
        int sum=0;
        String s=Integer.toBinaryString(n);  //n的二进制转为字符串
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);  //取出每一个位置的字符
            if(c=='1'){
                sum++;  //字符如果为1计数器就加一
            }
        }
        return sum;
    }

实现结果

普通算法(只能解决正数负数不能/2)

位运算(正负数均可)

易错面试题

数值的整数次方

面试十一题目

题目分析

1. 底为0   指数无论  --> 0
2. 底不为0 指数为0   --> 1
3. 底不为0 指数小于0 --> 按照循环求解之后答案取倒数
4. 底不为0 指数大于等于1 --> 正常流程

代码实现

public class CIFang {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        double n=input.nextDouble();
        int m=input.nextInt();
        System.out.println(n+"的"+m+"次方是"+cifang(n,m));
    }

    public static double cifang(double base,int exponent){
        double c=1;
        //底为0
        if(base==0){
            return 0;
        }
        if(exponent==0){  //任何数的0次方都是1
            return 1;
        }
        //底不为0  指数是负数
        if(exponent<0){
            exponent=-exponent;
            while (exponent--!=0) {  //有多少m就乘多少次n
                c*=base;  //c=c*n 在前面的基础上乘n
            }
            c=1.0/c;  //取倒数
        }
        //底不为o  指数大于等于1
        if(exponent>=1) {
            while (exponent--!=0) {  //有多少m就乘多少次n
                c*=base;  //c=c*n 在前面的基础上乘n
            }
        }
        return c;
    }

}

实现结果

打印1到最大的n位数

面试十二题目

题目分析

1. 暴力法(无法解决大数问题)：先算出最大值，然后按序输出
2. 数组/字符串：
3. 全排列：

代码实现

//1.暴力法(找到最大数然后按序输出)
   public static String printNumbers(int n){  //传入一个n
       int max=0;  //输出的最大的值
       //1.先求出最大数(方便定义数组下标大小)
       for(int i=0;i<n;i++){
           max=max*10+9;    //从9 99 999 9999...
       }
       //2.通过最大值创建数组
       int[] a=new int[max];
       for(int i=1;i<=max;i++){
               a[i]=i;
       }
       return Arrays.toString(a);  //使用Arrays的方法将数组转为字符串
   }

实现结果

数组中只出现一次的数字

题目

题目分析

1. 使用数组下标的好处：新建数组记录下标计数
2. 使用set集合(不能重复)：然后将1次以上的直接弹出，其他的添加到set集合

代码实现

public class YiCi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=input.nextInt();  //输入要判断的数组元素
        }
        System.out.println(Find(a));
    }

    public static Set<Integer> Find(int[] a) {
        Set<Integer> s1=new HashSet<>();
        for(int i=0;i<a.length;i++){
            if(!s1.add(a[i])){  //如果重复了(2次以上)
                s1.remove(a[i]);  //移除set集合 里面剩下的就都是只出现一次的值
            }
        }
        return s1;
    }

}

实现结果

调整数组顺序(奇数在偶数前面)

面试十四题目

题目分析

思路：使用两个指针交换奇偶数(快排的感觉)
    1. 左右指针赋初始值
    2. 分下面三种情况
        2.1 左指针不超过右指针 + 左边值是奇数(不需要交换) --> 左指针右移
        2.2 左指针不超过右指针 + 右边值是偶数(不需要交换) --> 右指针左移
        2.3 其他情况下直接交换左右指针对应数组的值

代码实现

public class ShunXu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();  //输入二维数组的行和列
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();  //输入要判断的数组元素
            }
        }


    }

    public static ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list=new ArrayList<Integer>();  //定义arraylist集合 底层是数组
        int row=matrix.length;     //行
        int col=matrix[0].length;  //列
        int left=0;
        int right=col-1;
        int top=0;
        int bottom=row-1;
        return list;
    }

}

实现结果

顺时针打印矩阵

面试二十题目

题目分析

1. 如果数组为空 --返回为null
2. 如果数组不为空
     2.1 建立ArrayList集合
     2.2 建立四个坐标用于标识数组变化
     2.3 从左往右(行：top    列：left到right)
     2.4 从上到下(行：top+1到bottom  列：right) 
     2.5 从右到左(行：bottom  列：right-1到left)  --但要注意可能最后是一行就不需要进行这一步
     2.6 从下到上(行：bottom-1到top  列：left)    --但要注意可能最后是一列就不需要进行这一步

关于left/right/bottom/top的分析：

代码实现

public class ShunXu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();  //输入二维数组的行和列
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();  //输入要判断的数组元素
            }
        }

        System.out.println(printMatrix(a));  //打印调用方法结果
    }

    public static ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix==null){
            return null;  //如果数组为空 就输出null
        }
        ArrayList<Integer> list=new ArrayList<Integer>();  //定义arraylist集合 底层是数组
        int row=matrix.length;     //行
        int col=matrix[0].length;  //列
        int left=0;   //二维数组上面行的最左边
        int right=col-1; //二维数组上面行的最右边
        int top=0;   //二维数组左边的最上边
        int bottom=row-1;  //二维数组左边的最下边
        while(left<=right&&top<=bottom){
            //从左到右
            for(int i=left;i<=right;i++){
                list.add(matrix[top][i]);
            }
            //从上到下(从下一行开始向下走)
            for(int i=top+1;i<=bottom;i++){
                list.add(matrix[i][right]);
            }
            //从右到左(从左边一列开始向左走)
            if(top!=bottom) {   //如果是一行的话就不需要返回去(已经左到右)
                for (int i = right - 1; i >= left; i--) {
                    list.add(matrix[bottom][i]);
                }
            }
            //从下到上(从上一行开始向上走)
            if(left!=right) {  //如果是一列的话就不需要返回去(已经上到下)
                for (int i = bottom - 1; i > top; i--) {
                    list.add(matrix[i][left]);
                }
            }
            //下一个正方形矩阵(往里缩小 -- 变换四个下标)
            top++;
            right--;
            left++;
            bottom--;
        }
        return list;
    }

}

实现结果

2020-05-02

图

图的概念：

https://www.cnblogs.com/songgj/p/9107797.html

图的展示方式

1. 邻接表
2. 邻接矩阵(相通为1，不通为0)

邻接矩阵实现

Graph类(和顶点数组有关)

//顶点数组
public class Graph {
    private Vertex[] vertex;  //存放顶点的矩阵
    private int currentSize;  //下标
    int[][] adjMat;   //二维矩阵存放顶点之间的关系


    public Graph(int size){
        vertex=new Vertex[size];  //设置顶点数组大小
        adjMat=new int[size][size]; //二维数组默认为0
    }

    //向图中添加顶点
    public  void  addVertex(Vertex v){
        vertex[currentSize++]=v;
    }

	//向图中添加边
    public void addEdge(String v1,String v2){
        int index1=0;
        int index2=0;
        for(int i=0;i<vertex.length;i++){
            if(vertex[i].getValue().equals(v1)){  //如果要添加的和v1是相等的 就把下标给index1
                index1=i;
                break;
            }
        }
        for(int i=0;i<vertex.length;i++){
            if (vertex[i].getValue().equals(v2)) {  //如果要添加的和v2是相等的 就把下表给index2
                index2=i;
                break;
            }
        }
        //相通给1
        adjMat[index1][index2]=1;  //把对应的位置变1
        adjMat[index2][index1]=1;

    }

}

Vertex类(顶点类)

//顶点类
public class Vertex {
     private String value;

    public Vertex(String value) {
        super();
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }

}

TestGraph类(测试类)

public class TestGraph {
    public static void main(String[] args) {
     //创建五个顶点
        Vertex v1=new Vertex("A");
        Vertex v2=new Vertex("B");
        Vertex v3=new Vertex("C");
        Vertex v4=new Vertex("D");
        Vertex v5=new Vertex("E");
        Graph g=new Graph(5);
     //增加节点
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);
     //增加边
        g.addEdge("A","C");
        g.addEdge("B","C");
        g.addEdge("A","B");
        g.addEdge("B","D");
        g.addEdge("B","E");
     //打印二维矩阵
        for(int[] a:g.adjMat){
            System.out.println(Arrays.toString(a));
        }

    }
}

结果分析

结果展示

图的遍历

1. 深度优先搜索算法(用栈的方式思考)
2. 广度优先搜索算法(用队列的方式思考)

两种遍历讲解

举例图：

深度优先搜索算法(DFS)

走迷宫一样，当前顶点走到死路就返回一步看能不能再走，把死路位置的顶点弹出去

1. 栈先放入A顶点 (栈内：A)
2. 搜索邻接矩阵中第一行A顶点可以到达哪个顶点
3. 栈再放入B顶点 (栈内：B A)
4. 搜索邻接矩阵中第二行B顶点可以到达哪个顶点
5. 栈再放入C顶点 (栈内：C B A)
6. 搜索邻接矩阵中第三行C顶点可以到达哪个顶点
7. 没有可以到达的顶点因此C顶点从栈弹出 (栈内：B A)  --已经搜索到的C弹出(C)
8. 返回到栈顶B顶点查看还可以到达哪个顶点
9. 栈再放入D顶点 (栈内: D B A)
10. 搜索邻接矩阵中第四行D顶点可以到达哪个顶点
11. 没有可以到达的顶点因此D顶点从栈弹出 (栈内：B A) --已经搜索到的D弹出(C D)
12. 返回到栈顶B顶点查看还可以到达哪个顶点
13. 栈再放入E顶点 (栈内：E B A)
14. 搜索邻接矩阵中第五行E顶点可以到达哪个顶点
15. 没有可以到达的顶点因此E顶点从栈弹出 (栈内：B A) --已经搜索到的E弹出(C D E)
16. 五个顶点都被遍历过后弹出栈内元素(先出B后出A)
17. 最终遍历顺序是： A B E D C

广度优先搜索算法(BFS)

从当前顶点一条路走到死，走死顶点就出队。让屁股后面的顶点继续走到死

1. 队列先放入A顶点 (队列内：A)
2. 搜索邻接矩阵中第一行A顶点可以到达哪个顶点
3. 队列再放入B顶点 (队列内：B A)
4. 搜索邻接矩阵中第一行A顶点还可以到达哪个顶点 
5. 队列再放入C顶点 (队列内：C B A)
6. 现在A没有可以到达的顶点因此A顶点出队(队列内：C B) --已经搜索到的A出队(A)
7. 现在搜索B还可以到达哪些顶点
8. 队列再放入D顶点 (队列内：D C B)
9. 在搜索B还可以到达哪些顶点
10. 队列再放入E顶点 (队列内：E D C B)
11. 五个顶点都被遍历过后弹出栈顶元素(先出B后出C然后D最后E)
12. 最终遍历顺序是： A B C D E

代码实现

1
2

2020-05-01

哈希表

通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数(映射函数)

满足计算简单和分布均匀的两大原则

五大方法

1. 直接定址法:(像利用数组下标对照着定位放)  -- 计算简单但是分布可能不均匀
2. 数字分析法:(事先知道数据分布)  -- 比如电话号码/身份证号码只需要考虑后几位存放问题
3. 平方取中法:(将所存的数字平方之后取最中间的位)  -- 比如17*17=289 放到数组下标为8的位置(会冲突)
4. 取余法:(将所存的数字取余数)  -- 比如17%10=7放到数组下标为7的位置(会冲突)
5. 随机数法:(将所存的数字random()方法随便放)  --不建议使用(随便放进去的不好取出来)

散列冲突的解决方案

两大方法

1. 开放地址法
    1.1 线性探测法  -- 有冲突的就 依次向后找空位放
    1.2 二次探测法  -- 有冲突的就 按照1的平方 2的平方 ..找空位放
    1.3 再哈希法    -- 使用两个散列函数存放 
2. 链地址法(HashMap底层)
    数组+链表的形式:(在数组下标对应的数组相当于建立一个链表，把符合相应条件的按照顺序指向)

2020-04-22

哈弗曼树

哈弗曼树(最优二叉树)

带权路径长度最小(WPL)的树(权值越大的节点离根节点越近)

WPL(带权路径长度)

WPL(带权路径长度):树中所有叶子节点的带权路径长度之和

WPL计算举例(X的系数就是从这个节点到根节点的有几个节点)

流程分析

步骤:

1. 排序
2. 挑选最小的两个 生成新的节点
3. 两个步骤不停的交替执行(排序之后就选最小的两个生成新的然后把新的节点放到以前的序列排序)

手写流程:

哈弗曼树代码实现(List范型)

步骤分析

//先使用数组中所有元素创建若干个二叉树(只有一个节点)
//排序
//取出来权值最小的两个二叉树
//创建一颗新的二叉树
//将取出来权值最小的两个二叉树移除    
//放入原来的二叉树集合中

Node类

public class Node implements Comparable<Node>{  //要使用排序要实现Comparable类
    int value;
    Node left;
    Node right;

    public Node(int value){
        this.value=value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value-o.value);  //自己设置输出node节点的值
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + '}';
    }

}

Test类

public class Test {
    public static void main(String[] args) {
        int[] arr=new int[]{3,7,8,29,5,11,23,14};
        System.out.println("原来的数组: "+Arrays.toString(arr));  //输出原来的数组
        Node node=createHuffmanTree(arr);  //调用方法
    }

    public static Node createHuffmanTree(int[] arr){
    //先使用数组中所有元素创建若干个二叉树(只有一个节点)
        List<Node> nodes=new ArrayList<>();
            for(int value:arr){
                nodes.add(new Node(value));
            }
        //循环处理
        while(nodes.size()>1){
          //排序
             Collections.sort(nodes);
            System.out.println("每一次剩下的数: "+nodes);
          //取出来权值最小的两个二叉树
            Node left=nodes.get(nodes.size()-1);
            Node right=nodes.get(nodes.size()-2);
          //创建一颗新的二叉树
            Node parent=new Node(left.value+right.value);
          //将取出来权值最小的两个二叉树移除
            nodes.remove(left);
            nodes.remove(right);
          //将新的放入原来的二叉树集合中
            nodes.add(parent);
        }
        System.out.println(nodes);
        return null;
    }

}

总结

1. 使用list<Node>范型去存储数组元素
2. 使用for循环add方法添加数组元素为节点
3. 使用Collections类的sort方法对范型对象排序
4. 获取范型对象的最后两个二叉树
5. 创建新的二叉树(值为第四步两个二叉树的值)
6. 通过remove方法移除
7. 通过add添加第五步新创建的二叉树
8. 可以直接输出nodes(最后只剩下结果的那个二叉树)

执行过程分析:

哈弗曼编码原理分析

通讯领域信息处理的三种方式

1. 定长编码(将对应的数字用ASCII码替换)
2. 不定长编码(将字母的出现频率计算出来 然后给固定的数字代表)
    容易出现分不清到底是代替哪个字母 
3. 哈夫曼编码(将字母出现频率计算出来 然后排序 选出最小两个生成新的 排序)
    然后左边的路权值给0 / 右边的给1

三种方式举例

定长编码

将对应的字母的翻译成ASCII码 – ASCII码翻译对应二进制

不定长编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制)

哈夫曼编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制) – 编写哈弗曼树(左路径给0/右路径给1) – 不同路径找到不同单词的值

哈弗曼编码代码实现

步骤分析

1. 统计字符数并且排序
2. 创建哈夫曼树
3. 创建哈夫曼树编码表
4. 编码

Node类

public class Node implements Comparable<Node>{
    Byte data;  //n:11 c:1 这种形式
    int weight;  //权值
    Node left;
    Node right;
    public Node(Byte data,int weight){
        this.data=data;
        this.weight=weight;
    }

    //实现接口方法 (获取值)
    @Override
    public int compareTo(Node o) {
        return o.weight-this.weight;
    }

    //输出node信息
    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", weight=" + weight + ", left=" + left + ", right=" + right + '}';
    }

}

TestHuffmantreeCoDE类

public class TestHuffmantreeCoDE {

    public static void main(String[] args) {
     //输入一个叫msg的字符串  让他使用哈夫曼编码
        String msg="can you can a can as a can canner can a can.";
            byte[] bytes=msg.getBytes();
        //进行哈夫曼编码压缩
         byte[] b=huffmanZip(bytes);
            System.out.println("压缩前"+bytes.length);
            System.out.println("压缩后"+b.length);
    }

    //进行哈夫曼编码(主)
    private static byte[] huffmanZip(byte[] bytes) {
        //1. 先统计每一个byte出现的个数  放入一个集合
            List<Node> nodes=getNodes(bytes);  //调用方法
        //2. 创建哈弗曼树
            Node tree=createHuffmanTree(nodes);  //创建一个叫tree的哈弗曼树
        //3. 创建哈夫曼编码表
            Map<Byte,String> huffCodes=getCodes(tree);
        //4. 编码(将每个byte替换成map里面的string)
            byte[] b=zip(bytes,huffCodes);

        return b;
    }

    //4. 将每个byte替换成Map集合里面的string即可
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
        StringBuilder sb=new StringBuilder();
        //把需要压缩的byte数组处理成一个二进制的字符串
        for(byte i:bytes){
            sb.append(huffCodes.get(i));  //获取到键
        }
        //定义长度
        int len;
        if(sb.length()%8==0){
            len=sb.length()/8;
        }else{
            len=sb.length()/8+1;  //%8之后的余数还可以凑成一个
        }

        //用于存储压缩后的byte
            byte[] by=new byte[len];
        //记录新byte的位置
            int index=0;

        for(int i=0;i<sb.length();i+=8){
            String strByte;
            if(i+8>sb.length()){
                strByte = sb.substring(i); // 不截取 只显示当前的
            }else{
                strByte = sb.substring(i, i + 8); // 截取8位为一个单元
            }
            byte byt=(byte)Integer.parseInt(strByte,2); //将2进制其转成10进制
          //将截取出来的8位的单元转成10进制最后存到之前创建的by数组
            by[index++]=byt;
        }

        return by;
    }

    //在第三步中用于存储路径
    static  StringBuilder sb=new StringBuilder();
    //在第三步中用于存储哈弗曼编码
    static Map<Byte,String> huffCodes=new HashMap<>();

    //3. 创建哈弗曼树编码表
    private static Map<Byte, String> getCodes(Node tree) {
        if(tree==null){
            return null;
        }
        getCodes(tree.left,"0",sb);   //左边赋0
        getCodes(tree.right,"1",sb);  //右边赋1
        return huffCodes;
    }

    //3.1 给左右节点递归传递下面的值
    private static void getCodes(Node node, String code, StringBuilder sb) {
      //新建stringbuilder的sb2对象
        StringBuilder sb2=new StringBuilder(sb);
      //新的stringbuilder对象添加进去 0 / 1
        sb2.append(code);
      //
        if(node.data==null){  //不是节点
            getCodes(node.left,"0",sb2);
            getCodes(node.right,"1",sb2);
        }
        else{  //直到最后一个叶子节点(底部)
            huffCodes.put(node.data,sb2.toString()); //将输出 n:00 a:01 c:02这种形式
        }
    }

    //2. 创建哈夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        //
        while(nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //取出两个权值最小的二叉树
                Node left=nodes.get(nodes.size()-1);
                Node right=nodes.get(nodes.size()-2);
            //创建新的二叉树
                Node parent=new Node(null,left.weight+right.weight);  //新创建的没有值 权值是下面两个相加
            //把之前的两棵二叉树设置为新创建的二叉树的子树
                parent.left=left;
                parent.right=right;
            //把之前的两棵二叉树从之前的删除
                nodes.remove(left);
                nodes.remove(right);
            //把新创建的二叉树放入集合中
                nodes.add(parent);
        }
        return nodes.get(0); //返回第0个(最大的那个)
    }

    //1. 把byte数组转化为node集合
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes=new ArrayList<>();
        //使用map数组存储每一个byte出现了多少次
            Map<Byte,Integer> counts=new HashMap<>();  //map对象叫counts   c:11 a:12 d:123 这种形式
        //s统计每一个byte出现次数
            for(byte i:bytes){
                Integer count = counts.get(i);  //统计对应每个byete出现的次数为count
                if(count==null){
                    counts.put(i,1);  //如果第一次出现  出现次数为1
                }
                else{
                    counts.put(i,count+1);  //不是第一次出现 直接出现次数+1
                }
            }
        //把每一个键值对转为一个node对象
            for(Map.Entry<Byte,Integer> i:counts.entrySet()){      //map集合遍历的一种方式
                nodes.add(new Node(i.getKey(),i.getValue()));
            }
         return null;
    }

}

哈夫曼编码解码

实现思路

1. 把byte数组转为一个二进制的字符串(使用异或补齐八位)
2. 将字符串按照指定的赫夫曼编码进行解码
    2.1 使用map将赫夫曼树编码的键值交换(现在是反向通过value查找)
    2.2 创建集合存储解码之后的数字
    2.3 处理字符串(按照0 01 11这种形式转换为 99 95这种数字)
    2.4 将存储解码的集合转为数组

解码的类

  //解码
   private static byte[] decode(Map<Byte, String> huffCodes2, byte[] bytes) {
       StringBuilder sb=new StringBuilder();
       //1. 把byte数组转为一个二进制的字符串
           for(int i=0;i<bytes.length;i++){
               byte b=bytes[i];
               boolean flag=(i==bytes.length-1);
               sb.append(byteToBitstr(!flag,b));  //不断地添加对应的二进制字符串
           }
       //2. 将字符串按照指定的赫夫曼编码进行解码
           //把赫夫曼编码的键值对进行交换(反向)
               Map<String,Byte> map=new HashMap<>();
               for(Map.Entry<Byte,String> entry:huffCodes.entrySet()){
                   map.put(entry.getValue(),entry.getKey());
               }
       //创建一个集合 用于存byte
           List<Byte> list=new ArrayList<>();

       //处理字符串(前缀编码不重复)
           for(int i=0;i<sb.length();){
               int count=1;
               boolean flag=true; //确定几位是一个判断的 (1 11 111这种)
            //截取一个byte
                 while(flag){
                   String key=sb.substring(i,i+count);  //用key去map找对应的
                   Byte b=map.get(key);
                   if(b==null){
                       count++;  //没截取到 就往下放一位找
                   }else{
                       flag=false; //截取到 就不让截取
                   }
               }
           }

        //把集合转为数组
           byte[] b=new byte[list.size()];   //[96,98,98,...]  转为数组{96,98,98,...}
           for(int i=0;i<b.length;i++){
               b[i]=list.get(i);
           }

       return b;
   }

//需要将所需要的8位截取出来
   public static String byteToBitstr(boolean flag,byte b) {
       int temp = b;
       if (flag) {
           temp |= 256; //异或
       }
       String str = Integer.toBinaryString(temp);
       if (flag) {
           return str.substring(str.length() - 8);  //取出来后八位
       }else{
           return str;  //只取出来自己的东西
       }
       
   }

哈夫曼编码压缩文件

实现原理

1. 创建一个输入流
2. 创建一个和输入流指向的文件大小一样的byte数组
3. 读取文件内容;
4. 读取结束后关闭输入流
5. 进行哈夫曼编码进行编码
6. 创建输出流
  6.1 将压缩后的byte数组写入文件
  6.2 将哈夫曼编码表写入文件
  6.3 关闭输出流

具体方法

main方法:

//进行哈夫曼压缩文件
      String src="1.bmp";  //压缩前的文件
      String dst="2.zip";  //压缩后的文件
          zipFile(src,dst);  //调用压缩方法

压缩的方法:

public static  void zipFile(String src,String dst)throws IOException {
     //1. 创建一个输入流
         InputStream is=new FileInputStream(src);  //使用输入流获取文件内容
     //2. 创建一个和输入流指向的文件大小一样的byte数组
         byte[] b=new byte[is.available()];
     //3. 读取文件内容
         is.read(b);
     //4. 读取结束后关闭
         is.close();
     //5. 进行哈夫曼编码进行编码
         byte[] bytezip=huffmanZip(b);  //调用方法
     //6. 创建输出流
         OutputStream os=new FileOutputStream(dst);
         ObjectOutputStream oos=new ObjectOutputStream(os);
       //6.1 将压缩后的byte数组写入文件
           oos.writeObject(bytezip);
       //6.2 将哈夫曼编码表写入文件
           oos.writeObject(huffCodes);
       //6.3 关闭流
           os.close();
           oos.close();

   }

哈夫曼编码解压文件

实现原理

1. 创建一个输入流
2. 读取byte数组     (解压给byte数组的)
3. 读取哈夫曼编码表  (解压给byte数组的)
4. 关闭流
5. 调用解码方法
6. 创建一个输出流
7. 写出数据
8. 关闭输出流

具体方法

//解压
   public static void unZip(String src,String dst) throws IOException, ClassNotFoundException {
       //1. 创建一个输入流
           InputStream is=new FileInputStream("2.zip");  //使用输入流获取文件内容
           ObjectInputStream ois =new ObjectInputStream(is);
       //2. 读取byte数组
           byte[] b= (byte[]) ois.readObject();
       //3. 读取哈夫曼编码表
           Map<Byte,String> codes=(Map<Byte, String>) ois.readObject();
       //4. 关闭流
           ois.close();
           is.close();
       //5. 解码
           byte[] bytes = decode(codes, b);
       //6. 创建一个输出流
            OutputStream os=new FileOutputStream(dst);
       //7. 写出数据
            os.write(bytes);
       //8. 关闭输出流
            os.close();
   }

哈夫曼编码完整代码(Node不展示)

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class TestHuffmanCode {

	public static void main(String[] args) {
//		String msg="can you can a can as a can canner can a can.";
//		byte[] bytes = msg.getBytes();
//		//进行赫夫曼编码压缩
//		byte[] b = huffmanZip(bytes);
//		//使用赫夫曼编码进行解码
//		byte[] newBytes = decode(huffCodes,b);
//		System.out.println(new String(newBytes));
		String src="1.bmp";
		String dst="2.zip";
//		try {
//			zipFile(src, dst);
//		} catch (IOException e) {
//			e.printStackTrace();
//		}
		try {
			unZip("2.zip", "3.bmp");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * 文件的解压
	 * @param src
	 * @param dst
	 * @throws Exception 
	 */
	public static void unZip(String src,String dst) throws Exception {
		//创建一个输入流
		InputStream is  = new FileInputStream("2.zip");
		ObjectInputStream ois = new ObjectInputStream(is);
		//读取byte数组
		byte[] b = (byte[]) ois.readObject();
		//读取赫夫曼编码表
		Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
		ois.close();
		is.close();
		//解码
		byte[] bytes = decode(codes, b);
		//创建一个输出流
		OutputStream os  = new FileOutputStream(dst);
		//写出数据
		os.write(bytes);
		os.close();
	}
	
	/**
	 * 压缩文件
	 * @param src
	 * @param dst
	 * @throws IOException
	 */
	public static void zipFile(String src,String dst) throws IOException {
		//创建一个输入流
		InputStream is = new FileInputStream(src);
		//创建一个和输入流指向的文件大小一样的byte数组
		byte[] b = new byte[is.available()];
		//读取文件内容
		is.read(b);
		is.close();
		//使用赫夫曼编码进行编码
		byte[] byteZip = huffmanZip(b);
		//输出流
		OutputStream os = new FileOutputStream(dst);
		ObjectOutputStream oos = new ObjectOutputStream(os);
		//把压缩后的byte数组写入文件
		oos.writeObject(byteZip);
		//把赫夫曼编码表写入文件
		oos.writeObject(huffCodes);
		oos.close();
		os.close();
	}
	
	/**
	 * 使用指定的赫夫曼编码表进行解码
	 * @param huffCodes2
	 * @param b
	 * @return
	 */
	private static byte[] decode(Map<Byte, String> huffCodes, byte[] bytes) {
		StringBuilder sb = new StringBuilder();
		//把byte数组转为一个二进制的字符串
		for(int i=0;i<bytes.length;i++) {
			byte b = bytes[i];
			//是否是最后一个。
			boolean flag = (i==bytes.length-1);
			sb.append(byteToBitStr(!flag,b));
		}
		//把字符串按照指定的赫夫曼编码进行解码
		//把赫夫曼编码的键值对进行调换
		Map<String, Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> entry:huffCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		//创建一个集合，用于存byte
		List<Byte> list = new ArrayList<>();
		//处理字符串
		for(int i=0;i<sb.length();) {
			int count=1;
			boolean flag = true;
			Byte b=null;
			//截取出一个byte
			while(flag) {
				String key = sb.substring(i, i+count);
				b = map.get(key);
				if(b==null) {
					count++;
				}else {
					flag=false;
				}
			}
			list.add(b);
			i+=count;
		}
		//把集合转为数组
		byte[] b = new byte[list.size()];
		for(int i=0;i<b.length;i++) {
			b[i]=list.get(i);
		}
		return b;
	}
	
	private static String byteToBitStr(boolean flag,byte b) {
		int temp=b;
		if(flag) {
			temp|=256;
		}
		String str = Integer.toBinaryString(temp);
		if(flag) {
			return str.substring(str.length()-8);
		}else {
			return str;
		}
	}

	/**
	 * 进行赫夫曼编码压缩的方法
	 * @param bytes
	 * @return
	 */
	private static byte[] huffmanZip(byte[] bytes) {
		//先统计每一个byte出现的次数，并放入一个集合中
		List<Node> nodes = getNodes(bytes);
		//创建一颗赫夫曼树
		Node tree = createHuffmanTree(nodes);
		//创建一个赫夫曼编码表
		Map<Byte, String> huffCodes = getCodes(tree);
		//编码
		byte[] b = zip(bytes,huffCodes);
		return b;
	}
	
	/**
	 * 进行赫夫曼编码
	 * @param bytes
	 * @param huffCodes2
	 * @return
	 */
	private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
		StringBuilder sb = new StringBuilder();
		//把需要压缩的byte数组处理成一个二进制的字符串
		for(byte b:bytes) {
			sb.append(huffCodes.get(b));
		}
		//定义长度
		int len;
		if(sb.length()%8==0) {
			len=sb.length()/8;
		}else {
			len=sb.length()/8+1;
		}
		//用于存储压缩后的byte
		byte[] by = new byte[len];
		//记录新byte的位置
		int index = 0;
		for(int i=0;i<sb.length();i+=8) {
			String strByte;
			if(i+8>sb.length()) {
				strByte = sb.substring(i);
			}else {
				strByte = sb.substring(i, i+8);
			}
			byte byt = (byte)Integer.parseInt(strByte, 2);
			by[index]=byt;
			index++;
		}
		return by;
	}

	//用于临时存储路径
	static StringBuilder sb = new StringBuilder();
	//用于存储赫夫曼编码
	static Map<Byte, String> huffCodes = new HashMap<>();
	/**
	 * 根据赫夫曼树获取赫夫曼编码
	 * @param tree
	 * @return
	 */
	private static Map<Byte, String> getCodes(Node tree) {
		if(tree==null) {
			return null;
		}
		getCodes(tree.left,"0",sb);
		getCodes(tree.right,"1",sb);
		return huffCodes;
	}

	private static void getCodes(Node node, String code, StringBuilder sb) {
		StringBuilder sb2 = new StringBuilder(sb);
		sb2.append(code);
		if(node.data==null) {
			getCodes(node.left, "0", sb2);
			getCodes(node.right, "1", sb2);
		}else {
			huffCodes.put(node.data, sb2.toString());
		}
	}

	/**
	 * 创建赫夫曼树
	 * @param nodes
	 * @return
	 */
	private static Node createHuffmanTree(List<Node> nodes) {
		while(nodes.size()>1) {
			//排序
			Collections.sort(nodes);
			//取出两个权值最低的二叉树
			Node left = nodes.get(nodes.size()-1);
			Node right = nodes.get(nodes.size()-2);
			//创建一颗新的二叉树
			Node parent = new Node(null, left.weight+right.weight);
			//把之前取出来的两颗二叉树设置为新创建的二叉树的子树
			parent.left=left;
			parent.right=right;
			//把前面取出来的两颗二叉树删除
			nodes.remove(left);
			nodes.remove(right);
			//把新创建的二叉树放入集合中
			nodes.add(parent);
		}
		return nodes.get(0);
	}

	/**
	 * 把byte数组转为node集合
	 * @param bytes
	 * @return
	 */
	private static List<Node> getNodes(byte[] bytes) {
		List<Node> nodes = new ArrayList<>();
		//存储每一个byte出现了多少次。
		Map<Byte, Integer> counts = new HashMap<>();
		//统计每一个byte出现的次数
		for(byte b:bytes) {
			Integer count = counts.get(b);
			if(count==null) {
				counts.put(b, 1);
			}else {
				counts.put(b, count+1);
			}
		}
		//把每一个键值对转为一个node对象
		for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}

}

2020-04-18

二叉树

二叉树(任何子节点数<=2)

1. 最大度为2
2. 可以为空
3. 有序树(左右节点不同)

存储方式

1. 链式存储
2. 顺序存储

满二叉树(很完美)

最层都是最饱满的样子

完全二叉树(编号没有间断)

编号连续的满二叉树的子集

二叉树链式存储

实现功能

1. 前/中/后序遍历
2. 前/中/后序查找 (当前满足/左节点满足/右节点满足)
3. 删除子树【递归】 (当前节点可删/左节点/右节点)

三种遍历方法解析

不断递归自己的方法遍历

// 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

查找节点

判断节点的value值和查找的i是否相等

//前序查找
   public TreeNode frontSerach(int i){
       TreeNode target=null;
       if(this.value==i) {
           return this;   //当前节点的值就是要查找的值
       }else{
           if(leftNode!=null){
               target=leftNode.frontSerach(i); //左边的值查到的话给target
           }
           if(target!=null){
               return target;  //如果查到了就不为空 返回target
           }
           if(rightNode!=null){
               target=rightNode.frontSerach(i);  //右边的值可以查到
           }
       }
           return target;
   }

删除子树

如果是根节点直接为null/其他的话就不断递归判断左右节点

//删除子树
    public void delete(int i) {
        TreeNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;  ///这个节点置空
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;  //这个节点置空
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);  
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

完整代码

1. BinaryTree类 :创建树(set/get方法) 所需要的方法定义(调用TreeNode方法)
2. TreeNode类 : 描述节点权和左右儿子(方法具体实现)
3. TestBinaryTree类 ：创建树添加节点

BinaryTree类

public class BinaryTree {
    TreeNode root;

    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }
    //获取根节点
    public TreeNode getRoot() {
        return root;
    }

    //前序遍历
    public void frontShow(){
        if(root!=null){
            root.frontShow();   //其实就是去TreeNode里面实现
        }
    }
    //中序遍历
    public void midShow(){
        if(root!=null) {
            root.midShow();   //其实就是去TreeNode里面实现
        }
    }
    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();   //其实就是去TreeNode里面实现
        }
    }

    //前序查找
    public TreeNode frontSearch(int i){
        return root.frontSerach(i);
    }

    //删除子树
    public void delete(int i) {
        if(root.value==i){
            root=null; //当前的节点值刚好是要删除的 直接为null
        }else{
            root.delete(i); //删除节点
        }
    }

}

TreeNode类

public class TreeNode {
   //节点的权
        int value;
   //左儿子
        TreeNode leftNode;
   //右儿子
         TreeNode rightNode;

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public TreeNode(int value){
        this.value=value;
    }

    // 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

    //前序查找
    public TreeNode frontSerach(int i){
        TreeNode target=null;
        if(this.value==i) {
            return this;   //当前节点的值就是要查找的值
        }else{
            if(leftNode!=null){
                target=leftNode.frontSerach(i); //左边的值查到的话给target
            }
            if(target!=null){
                return target;  //如果查到了就不为空 返回target
            }
            if(rightNode!=null){
                target=rightNode.frontSerach(i);  //右边的值可以查到
            }
        }
            return target;
    }

    //删除子树
    public void delete(int i) {
        TreeNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

}

TestBinaryTree类

public class TestBinaryTree {
    public static void main(String[] args) {
      //创建一棵树
        BinaryTree binTree=new BinaryTree();
      //创建一个根节点
        TreeNode root=new TreeNode(1);
      //根节点赋给树
        binTree.setRoot(root);  //根节点赋给树

      //创建两个节点
        TreeNode rootL=new TreeNode(2);  //创建第二层的2
        TreeNode rootR=new TreeNode(3);  //创建第二层的3
      //新节点设置为根的两个节点
        root.setLeftNode(rootL);
        root.setRightNode(rootR);

      //给根的左节点2创建两个节点
         rootL.setLeftNode(new TreeNode(4));
         rootL.setRightNode(new TreeNode(5));
      //给根的右节点3创建两个节点
         rootR.setLeftNode(new TreeNode(6));
         rootR.setRightNode(new TreeNode(7));

      //前序遍历
        System.out.print("前序遍历:");
        binTree.frontShow();
        System.out.println();
      //中序遍历
        System.out.print("中序遍历:");
        binTree.midShow();
        System.out.println();
      //后序遍历
        System.out.print("后序遍历:");
        binTree.afterShow();
        System.out.println();

      //前序查找
        TreeNode result=binTree.frontSearch(3);
        System.out.println("前序查找结果:"+result);

     //删除子树(切点上层节点和它的关系)
        binTree.delete(2);
        binTree.frontShow();

    }
}

执行结果:

二叉树顺序存储

只考虑完全二叉树(编号连续)

顺序存储的性质

1. 第n个元素的左子节点 : 2*n+1
2. 第n个元素的右子节点 : 2*n+2
3. 任何一个节点的父节点 : (n-1)/2

具体类(三种遍历)

public class ArrayBinaryTree {

    int[] data;  //定义一个数组用于后面方法实现

    public ArrayBinaryTree(int[] data){   //构造方法传入数组
        this.data=data;
    }

    public void frontShow(){
        frontShow(0);
    }

    //前序遍历
    public void frontShow(int i){
        if(data==null||data.length==0){
            return;  //如果数组为空或者长度为0就输出0
        }
        System.out.println(data[i]);  //  输出当前的节点 (根)
        if(2*i+1<data.length){
            frontShow(2*i+1);  //递归  找左节点(2n+1)
        }
        if(2*i+2<data.length){
            frontShow(2*i+2);  //递归  找右节点(2n+2)
        }

    }

}

测试类

public class Shunxu {
    public static void main(String[] args) {
        int[] data=new int[]{1,2,3,4,5,6,7};  //定义一个链表存储的在数组内
        ArrayBinaryTree tree=new ArrayBinaryTree(data);  //传入数组
        tree.frontShow();  //前序遍历

    }
}

结果:

线索二叉树(双向链表)

线索二叉树概念：

1. 一个节点的前一个节点 --> 前驱节点(左边标记为lflag)
2. 一个节点的后一个节点 --> 后继节点(右边标记为rflag)

具体实现(可知前后节点信息)

中序线索化二叉树(关键点)

//中序线索化二叉树
       //用于临时存储前驱结点
           ThreadedNode pre=null;

   public void threadNodes(){
       threadNodes(root); //通过root不停的递归
   }

   public void threadNodes(ThreadedNode node){
       //1. 当前节点如果为null 直接返回
       if(node==null){
           return;
       }
       //2. 处理左子树
           threadNodes(node.leftNode);
         //2.1 如果当前节点没有了 我们处理它的前驱节点
             if (node.leftNode == null) {
                 node.leftNode=pre;    //当前节点的左指针 指向 前驱节点
                 node.leftType=1;  // 当前节点的左指针类型从0 -> 1
              }
         //2.2 前驱结点的右指针 如果是null(没有指向右下子树)
              if(pre!=null&&pre.rightNode==null){
                   pre.rightNode=node;
                   pre.rightType=1;
              }
         //2.3 每次处理一个节点，当前节点就是下一个节点的前驱节点(依次往下走 下一个的上面就是上一个)
              pre=node;

       //3. 处理右子树
           threadNodes(node.rightNode);
   }

遍历

public void threadIterate(){
    ThreadedNode node=root;
    while(node!=null){
        //循环找到最开始的节点
        while(node.leftType==0){
            node=node.leftNode;
        }
        System.out.println(node.value);  //打印当前节点的值
        //如果当前节点的右节点是后继节点，有可能后继节点还有后继节点
        while(node.rightType==1){
            node=node.rightNode;
            System.out.println(node.value);
        }
        node=node.rightNode;  //替换遍历的节点
    }
}

完整代码如下(三个类)

ThreadedBinaryTree类(二叉树的基础上添加中序线索树和遍历的方法)

public class ThreadedBinaryTree {
    
	ThreadedNode root;

    //设置根节点
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }
    //获取根节点
    public ThreadedNode getRoot() {
        return root;
    }

    //中序线索化二叉树
        //用于临时存储前驱结点
            ThreadedNode pre=null;

    public void threadNodes(){
        threadNodes(root); //通过root不停的递归
    }

    public void threadNodes(ThreadedNode node){
        //1. 当前节点如果为null 直接返回
        if(node==null){
            return;
        }
        //2. 处理左子树
            threadNodes(node.leftNode);
          //2.1 如果当前节点没有了 我们处理它的前驱节点
              if (node.leftNode == null) {
                  node.leftNode=pre;    //当前节点的左指针 指向 前驱节点
                  node.leftType=1;  // 当前节点的左指针类型从0 -> 1
               }
          //2.2 前驱结点的右指针 如果是null(没有指向右下子树)
               if(pre!=null&&pre.rightNode==null){
                    pre.rightNode=node;
                    pre.rightType=1;
               }
          //2.3 每次处理一个节点，当前节点就是下一个节点的前驱节点(依次往下走 下一个的上面就是上一个)
               pre=node;

        //3. 处理右子树
            threadNodes(node.rightNode);
    }

    //遍历线索二叉树
    public void threadIterate(){
        ThreadedNode node=root;
        while(node!=null){
            //循环找到最开始的节点
            while(node.leftType==0){
                node=node.leftNode;
            }
            System.out.println(node.value);  //打印当前节点的值
            //如果当前节点的右节点是后继节点，有可能后继节点还有后继节点
            while(node.rightType==1){
                node=node.rightNode;
                System.out.println(node.value);
            }
            node=node.rightNode;  //替换遍历的节点
        }
    }

    //前序遍历
    public void frontShow(){
        if(root!=null){
            root.frontShow();   //其实就是去TreeNode里面实现
        }
    }
    //中序遍历
    public void midShow(){
        if(root!=null) {
            root.midShow();   //其实就是去TreeNode里面实现
        }
    }
    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();   //其实就是去TreeNode里面实现
        }
    }

    //前序查找
    public ThreadedNode frontSearch(int i){
        return root.frontSerach(i);
    }

    //删除子树
    public void delete(int i) {
        if(root.value==i){
            root=null; //当前的节点值刚好是要删除的 直接为null
        }else{
            root.delete(i); //删除节点
        }
    }

}

TestThreadedBinaryTree测试类

public class TestThreadedBinaryTree {
    public static void main(String[] args) {
        //创建一棵树
        ThreadedBinaryTree binTree=new ThreadedBinaryTree();
        //创建一个根节点
        ThreadedNode root=new ThreadedNode(1);
        //根节点赋给树
        binTree.setRoot(root);  //根节点赋给树

        //创建两个节点
        ThreadedNode rootL=new ThreadedNode(2);  //创建第二层的2
        ThreadedNode rootR=new ThreadedNode(3);  //创建第二层的3
        //新节点设置为根的两个节点
        root.setLeftNode(rootL);
        root.setRightNode(rootR);

        //给根的左节点2创建两个节点
        rootL.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode=new ThreadedNode(5);
        rootL.setRightNode(fiveNode);
        //给根的右节点3创建两个节点
        rootR.setLeftNode(new ThreadedNode(6));
        rootR.setRightNode(new ThreadedNode(7));

        //中序遍历
        System.out.print("中序遍历:");
        binTree.midShow();
        System.out.println();
        System.out.println("---------------");

        //中序线索二叉树
        System.out.print("5后面的节点:");
        binTree.threadNodes();
        //查看5的后继节点
           ThreadedNode after=fiveNode.rightNode;
            System.out.println(after.value);
            binTree.threadIterate();  //测试遍历

    }
}

ThreadedNode节点类(只需要添加左右指针类型)

public class ThreadedNode {
    //节点的权
    int value;
    //左儿子
    ThreadedNode leftNode;
    //右儿子
    ThreadedNode rightNode;

    //用于标识指针类型
        int leftType;
        int rightType;

    public void setLeftNode(ThreadedNode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(ThreadedNode rightNode) {
        this.rightNode = rightNode;
    }

    public ThreadedNode(int value){
        this.value=value;
    }

    // 前序遍历(根左右)
    public void frontShow() {
        System.out.print(value+" "); //先输出当前节点内容
        if (leftNode != null) {
            leftNode.frontShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.frontShow();  //右节点
        }
    }

    // 中序遍历(左根右)
    public void midShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        System.out.print(value+" "); //先输出当前节点内容
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
    }

    //后序遍历(左右根)
    public void afterShow() {
        if (leftNode != null) {
            leftNode.midShow(); //左节点
        }
        if (rightNode != null) {
            rightNode.midShow();  //右节点
        }
        System.out.print(value+" "); //先输出当前节点内容
    }

    //前序查找
    public ThreadedNode frontSerach(int i){
        ThreadedNode target=null;
        if(this.value==i) {
            return this;   //当前节点的值就是要查找的值
        }else{
            if(leftNode!=null){
                target=leftNode.frontSerach(i); //左边的值查到的话给target
            }
            if(target!=null){
                return target;  //如果查到了就不为空 返回target
            }
            if(rightNode!=null){
                target=rightNode.frontSerach(i);  //右边的值可以查到
            }
        }
        return target;
    }

    //删除子树
    public void delete(int i) {
        ThreadedNode parent=this;  //把上一层节点存起来
        if(parent.leftNode!=null&&parent.leftNode.value==i){  //左节点是这个值
            parent.leftNode=null;
            return;
        }
        if(parent.rightNode!=null&&parent.rightNode.value==i){  //右节点是这个值
            parent.rightNode=null;
            return;
        }
        parent=leftNode;  //左边节点给上一层节点  递归
        if(parent!=null){
            parent.delete(i);
        }
        parent=rightNode;  //右边节点给上一层节点 递归
        if(parent!=null){
            parent.delete(i);
        }
    }

}

结果:

二叉排序树BST(二叉查找树/二叉搜索树)

任何一个非叶子节点 : 左子节点<当前节点<右子节点

具体实现的代码框架

1. BinarySortTree类 : 一个root根节点 然后围绕写方法
2. Node节点类 : 具体方法实现
3. TestBinarySortTree测试类 : 测试结果

创建二叉排序树(添加节点)

实现思路

1. 空树 -- 直接让要添加的节点成为root根节点
2. 不为空树 -- 调用Node实现方法
   2.1 要添加的节点为空 -- 直接返回
   2.2 要添加的节点的值 < 当前节点的值
        2.2.1 当前节点有左节点 -- 继续递归找
        2.2.2 当前节点下面空 -- 直接添加到左节点的位置
   2.2 要添加的节点的值 > 当前节点的值
        2.2.1 当前节点有右节点 -- 继续递归找
        2.2.2 当前节点下面空 -- 直接添加到右节点的位置

BinarySortTree类写方法


//向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

Node类具体实现

//向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
    }

查找节点

实现思路

1. 空树 -- 返回null
2. 不为空树 -- 调用Node实现方法
    2.1 传入的值 == 当前节点值   -- 返回当前节点
    2.2 传入的值 < 当前节点值    -- 找左边
         2.2.1 如果左边为空   -- 返回null
         2.2.2 如果左边不为空 -- 把左节点当做判断的当前节点(递归)  
    2.3 传入的值 > 当前节点值    -- 找右边
         2.3.1 如果右边为空   -- 返回null
         2.3.2 如果右边不为空 -- 把右节点当做判断的当前节点(递归)

BinarySortTree类写方法

//查找
   public Node search(int value){
     //1. 如果空树 -- 返回null
       if(root==null){
           return null;
       }
     //2. 如果不为空
       else{
           return root.search(value);
       }
   }

Node类具体实现

//查找节点
   public Node search(int value) {
     //1. 传入的值 == 当前节点值
       if(this.value==value){
           return this;  //返回当前节点
       }
     //2. 传入的值 < 当前节点值  -- 找左边
       else if(value<this.value){
           if(left==null){return null;}  //为空返回null
           return this.left.search(value);
       }
     //3. 传入的值 > 当前节点值  -- 找右边
       else{
           if(right==null){return null;}  //为空返回null
           return this.right.search(value);
       }
   }

测试添加节点和查询功能

public class TestBinarySortTree {

    public static void main(String[] args) {
        int[] arr=new int[]{7,3,10,12,5,1,9};
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }
        //3. 中序遍历
            bst.midShow();
                 System.out.println("----------------------");
        //4. 查找数中的值
            Node node = bst.search(10);
                System.out.println("查找值为10的节点的值 : "+node.value);
            Node node2 = bst.search(20);
                System.out.println("查找值为20的节点是不是为空 : "+node2);
                System.out.println("查找值为20的节点的值 : "+node2.value);

    }

}

测试结果:

删除节点

三种情况概述

1. 删除叶子节点(两种情况): 让父节点不指向它(左边/右边)
2. 删除有一颗子树的节点(四种情况): 让它的子树代替它的位置(它在左/右边 子树在左/右边)
3. 删除有两颗子树的节点(两种情况): 
    1. 找到右边最小的替换掉删除的点(它没有叶子节点)
    2. 找到右边最小的替换掉删除的点+右节点替换掉最小的点的位置 (它有右节点(左节点的话就是第一种情况))

删除叶子节点(2种情况)

实现思路

1. 删除的叶子节点是左节点  -- 让父节点的左节点为空
2. 删除的叶子节点是右节点  -- 让父节点的右节点为空

图示解释

BinarySortTree类写方法


if(target.left==null&&target.right==null)
               {
                   //2.1.1 要删除的节点是父节点的左节点
                   if (parent.left.value == value)
                   {
                       parent.left = null;  //直接让父节点把它为null
                   }
                   //2.1.2 要删除的节点是父节点的右节点
                   else
                   {
                       parent.right = null; //直接让父节点把它为null
                   }
               }

Node类具体实现

//查找父节点
public Node searchParent(int value) {
    if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
        return this;
    }else {
        if(this.value>value&&this.left!=null){
            return this.left.searchParent(value);
        }else
            if(this.value<value&&this.right!=null){
            return this.right.searchParent(value);
        }
    }
    return null;
}

删除有一颗子树的节点(4种情况)

实现思路

1. 删除的节点是父节点的左/右节点？ 删除的节点的子节点是左/右节点？
    1.1 要删除的节点有的是左子节点
        1.1.1 要删除的节点是父节点的左节点(左左)   -- 将删除节点的左节点赋给父节点的左节点
        1.1.2 要删除的节点是父节点的右节点(右左)   -- 将删除节点的左节点赋给父节点的右节点
    1.2 要删除的节点有的是右子节点 
        1.2.1 要删除的节点是父节点的左节点(左右)   -- 将删除节点的右节点赋给父节点的左节点
        1.2.2 要删除的节点是父节点的右节点(右右)   -- 将删除节点的右节点赋给父节点的右节点

图示解释

BinarySortTree类写方法


//2.3.1 左子节点
     if(target.left!=null)
        {
            //2.3.1.1 要删除的节点是父节点的左节点
             if(parent.left.value==value)
             {
                  parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
             }
             //2.3.1.2 要删除的节点是父节点的右节点
             else
             {
                  parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
             }
         }
 //2.3.2 右子节点
      else
      {
            //2.3.2.1 要删除的节点是父节点的左节点
             if(parent.left.value==value)
             {
                  parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
             }
            //2.3.2.2 要删除的节点是父节点的右节点
             else
             {
                  parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
             }
     }

删除有两颗子树的节点(2种情况)

1. 右边最小值有没有子节点？
    1.1 右边最小值没有子节点 -- 直接将最小值的节点值赋给要删除的节点的值
    1.1 右边最小值有子节点(只有右节点) -- 直接将最小值的节点值赋给要删除的节点的值 +子节点的值赋给最小值的节点值

实现思路

BinarySortTree类写方法

if(target.left!=null&&target.right!=null)
  {
        //2.2.1 删除右子树最小的节点并且获取到该节点的值
               int min=deleteMin(target.right);  
        //2.2.2 替换目标节点中的值
               target.value=min;  //最小的值赋给要删除的节点的值
  }

完整代码

BinarySortTree类写方法

package com.company.erchapaixushu;
public class BinarySortTree {

    //root根节点
        Node root;

    //向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(){
        if(root!=null){
            root.midShow(root);  //查找这个根节点开始的中序遍历
        }
    }

    //查找节点
    public Node search(int value){
      //1. 如果空树 -- 返回null
        if(root==null){
            return null;
        }
      //2. 如果不为空
        else{
            return root.search(value);
        }
    }

    //删除节点
    public void delete(int value){
        if(root==null)
        {
            return; //空树直接返回
        }
        else
        {
            //1. 找到这个节点
                Node target = search(value);
                if(target==null)
                {
                    return;
                }
            //2. 找到它的父节点
                Node parent=searchParent(value);
                //2.1 要删除的是叶子节点
                if(target.left==null&&target.right==null)
                {
                    //2.1.1 要删除的节点是父节点的左节点
                    if (parent.left.value == value)
                    {
                        parent.left = null;  //直接让父节点把它为null
                    }
                    //2.1.2 要删除的节点是父节点的右节点
                    else
                    {
                        parent.right = null; //直接让父节点把它为null
                    }
                }

                //2.2 要删除的节点有两个子节点
                else
                    if(target.left!=null&&target.right!=null)
                    {
                        //2.2.1 删除右子树最小的节点并且获取到该节点的值
                            int min=deleteMin(target.right);
                        //2.2.2 替换目标节点中的值
                            target.value=min;
                    }

                //2.3 要删除的节点是有一个子节点
                    else
                    {
                        //2.3.1 左子节点
                        if(target.left!=null)
                        {
                            //2.3.1.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
                            }
                            //2.3.1.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                        }
                        //2.3.2 右子节点
                        else
                        {
                            //2.3.2.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                            //2.3.2.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
                            }
                        }
                    }
                }
        }

    //删除右边最小的节点并且获取该节点的值
    private int deleteMin(Node node) {
        Node target=node;
        //递归一直找最左边
        while(target.left!=null){  //右边的子树里面的左节点一直可以找下去  就一定是最小的
            target=target.left;
        }
        //最小的值有右子节点
        delete(target.value);  //那么剩下了一个叶子节点肯定会通过delete方法补上去
        return target.value;  //直接返回结果
    }

    //查找父节点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

}

Node类写具体实现

package com.company.erchapaixushu;
public class Node {
    int value;  //此节点的值
    Node left;  //左节点
    Node right; //右节点

    public Node(int value){
        this.value=value;  //构造方法获取值
    }

    //向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(Node node) {
        if(node==null){
            return;  //为空就结束
        }
        midShow(node.left);  //左子树继续递归查
        System.out.println(node.value); //打印当前节点的值
        midShow(node.right);  //右子树继续递归查
    }

    //查找节点
    public Node search(int value) {
      //1. 传入的值 == 当前节点值
        if(this.value==value){
            return this;  //返回当前节点
        }
      //2. 传入的值 < 当前节点值  -- 找左边
        else if(value<this.value){
            if(left==null){return null;}  //为空返回null
            return this.left.search(value);
        }
      //3. 传入的值 > 当前节点值  -- 找右边
        else{
            if(right==null){return null;}  //为空返回null
            return this.right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;   //它的左子节点或者右子节点符合条件
        }else {
            if(this.value>value&&this.left!=null){
                return this.left.searchParent(value);  //左边
            }else
                if(this.value<value&&this.right!=null){
                return this.right.searchParent(value);  //右边
            }
        }
        return null;  //都不满足 返回空
    }

}

TestBinarySortTree类

package com.company.erchapaixushu;
public class TestBinarySortTree {
    public static void main(String[] args) {
        int[] arr=new int[]{7,3,10,12,5,1,9};
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }

        //3. 中序遍历
            bst.midShow();
                 System.out.println("----------------------");

        //4. 查找数中的值
            Node node = bst.search(10);
                System.out.println("查找值为10的节点的值 : "+node.value);
            Node node2 = bst.search(20);
                System.out.println("查找值为20的节点是不是为空 : "+node2);
                System.out.println("----------------------");

        //5. 查看父节点
            Node p1=bst.searchParent(10);
                System.out.println("输入的值的父节点是: "+p1.value);
                System.out.println("----------------------");

        //6. 删除叶子节点
            bst.delete(5); //删除叶子节点
            bst.midShow(); //删除之后查看
                System.out.println("----------------------");

        //7. 删除有一个节点的节点
            bst.delete(3); //有一个1的左节点
            bst.midShow();
                System.out.println("----------------------");

        //8. 删除有两个子节点
            bst.delete(7);  //根节点
            bst.midShow();
                System.out.println("----------------------");

    }

}

结果展示

叶子节点和有一个节点的值:

有两个节点的值:

平衡二叉树(AVL树)

平衡二叉树概念

前提: 必须是一个二叉排序树
条件: 任何一个非叶子节点满足: |左子树高度-右子树高度|<1
存在意义: 提高一般的二叉排序树的查找效率

准备获高度方法和add方法添加判断平衡

之前的add方法内部需要判断是不是平衡!!!!!!!
  //3. 查询是否平衡
          //3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2)    //左边太多 向右转(原来根的左节点作为新的根节点)
			{  
                rightRotate();  //调用具体实现内写的方法
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2)    //右边太多 向左转(原来根的右节点作为新的根节点)
			{
                leftRotate(); //调用具体实现内写的方法
            }

-------------------------------

//当前节点的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;  //当前节点高度=左右子树最大的+1
    }

//左子树的高度 (避免为空)
    public int leftHight(){
        if(left==null){  //有可能为空
            return 0;
        }
        return left.height();
    }

//右子树的高度 (避免为空)
    public int rightHight(){
        if(right==null){  //有可能为空
            return 0;
        }
        return right.height();
    }

构造平衡二叉树(单旋转)

左左情况(右旋转)

左左情况怎么变换：

左左情况代码实现:

Node类实现：

//左左情况 -- 右旋转
  private void rightRotate() {
      //1. 创建新节点(值==当前节点的值)
          Node newRight=new Node(this.value);
      //2. 当前节点的右节点 --> 新节点的右节点   (原来的根节点和它右边子树已经挪走了)
          newRight.right=this.right;
      //3. 当前节点的左节点的右节点 --> 新节点的左节点  (原来的根节点的左节点的右子树成为新节点的左节点)
          newRight.left=this.left.right;
      //4. 当前节点值 --> 当前节点的左节点的值 (左边节点被替换掉)
          this.value=this.left.value;
      //5. 当前节点的左节点的左节点 --> 当前节点的左节点 (相当于直接把当前节点的左节点被扔出去)
          this.left=this.left.left;
      //6. 新节点 --> 当前节点的右节点
          this.right=newRight;
  }

右右情况(左旋转)

右右情况怎么变换：

右右情况代码实现:

Node类实现：

//右右情况 -- 左旋转
  private void leftRotate() {
      //1. 创建新节点(值==当前节点的值)
          Node newLeft=new Node(this.value);
      //2. 当前节点的左节点 --> 新节点的左节点   (原来的根节点和它左边子树已经挪走了)
          newLeft.left=this.left;
      //3. 当前节点的右节点的左节点 --> 新节点的右节点  (原来的根节点的右节点的左子树成为新节点的右节点)
          newLeft.right=this.right.left;
      //4. 当前节点值 --> 当前节点的右节点的值 (右边节点被替换掉)
          this.value=this.right.value;
      //5. 当前节点的右节点的右节点 --> 当前节点的右节点 (相当于直接把当前节点的右节点被扔出去)
          this.right=this.right.right;
      //6. 新节点 --> 当前节点的左节点
          this.left=newLeft;
  }

完整代码

Node类(二叉排序树的基础上添加查询高度的方法 + 左/右旋转的方法 + add方法判断是否平衡)

public class Node {
    int value;  //此节点的值
    Node left;  //左节点
    Node right; //右节点

    public Node(int value){
        this.value=value;  //构造方法获取值
    }

    //向子树中添加节点
    public void add(Node node) {
        //1.传入的节点为空
        if(node==null){
            return;  //直接结束
        }
        //2.传入的节点的值和当前子树的根节点大小关系
          //2.1 传入节点值 < 子树的根节点的值
          if(node.value<this.value) {
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.left==null){
                  this.left=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.left.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
          //2.2 传入节点值 > 子树的根节点的值
          else{
             //2.1.1 当前子树的根节点下面没有左子树   --  直接添加
              if(this.right==null){
                  this.right=node;  //直接添加到左节点
             //2.1.2 当前子树的根节点下面有左子树    --  需要递归去找到
              }else{
                  this.right.add(node);  // 在当前子树的根节点下面的左节点下面去添加 (递归)
              }
          }
        //3. 查询是否平衡
          //3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2){   //左边太多 向右转(原来根的左节点作为新的根节点)
                rightRotate();
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2) {
                leftRotate();
            }

    }

    //右右情况 -- 左旋转
    private void leftRotate() {
        //1. 创建新节点(值==当前节点的值)
            Node newLeft=new Node(this.value);
        //2. 当前节点的左节点 --> 新节点的左节点   (原来的根节点和它左边子树已经挪走了)
            newLeft.left=this.left;
        //3. 当前节点的右节点的左节点 --> 新节点的右节点  (原来的根节点的右节点的左子树成为新节点的右节点)
            newLeft.right=this.right.left;
        //4. 当前节点值 --> 当前节点的右节点的值 (右边节点被替换掉)
            this.value=this.right.value;
        //5. 当前节点的右节点的右节点 --> 当前节点的右节点 (相当于直接把当前节点的右节点被扔出去)
            this.right=this.right.right;
        //6. 新节点 --> 当前节点的左节点
            this.left=newLeft;
    }


    //左左情况 -- 右旋转
    private void rightRotate() {
        //1. 创建新节点(值==当前节点的值)
            Node newRight=new Node(this.value);
        //2. 当前节点的右节点 --> 新节点的右节点   (原来的根节点和它右边子树已经挪走了)
            newRight.right=this.right;
        //3. 当前节点的左节点的右节点 --> 新节点的左节点  (原来的根节点的左节点的右子树成为新节点的左节点)
            newRight.left=this.left.right;
        //4. 当前节点值 --> 当前节点的左节点的值 (左边节点被替换掉)
            this.value=this.left.value;
        //5. 当前节点的左节点的左节点 --> 当前节点的左节点 (相当于直接把当前节点的左节点被扔出去)
            this.left=this.left.left;
        //6. 新节点 --> 当前节点的右节点
            this.right=newRight;
    }

    //当前节点的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;  //当前节点高度=左右子树最大的+1
    }

    //左子树的高度 (避免为空)
    public int leftHight(){
        if(left==null){  //有可能为空
            return 0;
        }
        return left.height();
    }

    //右子树的高度 (避免为空)
    public int rightHight(){
        if(right==null){  //有可能为空
            return 0;
        }
        return right.height();
    }


    //中序遍历(刚好是从小到大)
    public void midShow(Node node) {
        if(node==null){
            return;  //为空就结束
        }
        midShow(node.left);  //左子树继续递归查
        System.out.println(node.value); //打印当前节点的值
        midShow(node.right);  //右子树继续递归查
    }

    //查找节点
    public Node search(int value) {
      //1. 传入的值 == 当前节点值
        if(this.value==value){
            return this;  //返回当前节点
        }
      //2. 传入的值 < 当前节点值  -- 找左边
        else if(value<this.value){
            if(left==null){return null;}  //为空返回null
            return this.left.search(value);
        }
      //3. 传入的值 > 当前节点值  -- 找右边
        else{
            if(right==null){return null;}  //为空返回null
            return this.right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;
        }else {
            if(this.value>value&&this.left!=null){
                return this.left.searchParent(value);
            }else
                if(this.value<value&&this.right!=null){
                return this.right.searchParent(value);
            }
        }
        return null;
    }

}

** TestBinarySortTree类(尝试输出)**

public class TestBinarySortTree {
    public static void main(String[] args) {
        int[] arr=new int[]{8,9,6,7,5,4};    //用于改变左边不平衡
      //int[] arr=new int[]{2,1,4,3,5,6};    //用于改变右边不平衡
        //1. 创建一颗二叉排序树
            BinarySortTree bst=new BinarySortTree();
        //2. 循环添加
            for(int i:arr){
                bst.add(new Node(i));
            }
        //3.查看高度
            System.out.println("左左情况变为平衡二叉树之后树的高度:"+bst.root.height());
        //4.查看根节点的值(更新后的)
            System.out.println("左左情况变为平衡二叉树之后根的值"+bst.root.value);
        //5.中序遍历
            System.out.println("中序遍历左左情况之后:");
            bst.midShow();
    }
}

BinarySortTree类(和之前的二叉排序树没有变化)

public class BinarySortTree {

    //root根节点
        Node root;

    //向二叉排序树中添加节点
    public void add(Node node){
        //1. 如果是空树
            if(root==null){
                root=node;  //这个节点添加为根节点
            }
        //2. 不是空树
            else{
                root.add(node); //调用Node类的方法添加
            }
    }

    //中序遍历(刚好是从小到大)
    public void midShow(){
        if(root!=null){
            root.midShow(root);  //查找这个根节点开始的中序遍历
        }
    }

    //查找节点
    public Node search(int value){
      //1. 如果空树 -- 返回null
        if(root==null){
            return null;
        }
      //2. 如果不为空
        else{
            return root.search(value);
        }
    }

    //删除节点
    public void delete(int value){
        if(root==null)
        {
            return; //空树直接返回
        }
        else
        {
            //1. 找到这个节点
                Node target = search(value);
                if(target==null)
                {
                    return;
                }
            //2. 找到它的父节点
                Node parent=searchParent(value);
                //2.1 要删除的是叶子节点
                if(target.left==null&&target.right==null)
                {
                    //2.1.1 要删除的节点是父节点的左节点
                    if (parent.left.value == value)
                    {
                        parent.left = null;  //直接让父节点把它为null
                    }
                    //2.1.2 要删除的节点是父节点的右节点
                    else
                    {
                        parent.right = null; //直接让父节点把它为null
                    }
                }

                //2.2 要删除的节点有两个子节点
                else
                    if(target.left!=null&&target.right!=null)
                    {
                        //2.2.1 删除右子树最小的节点并且获取到该节点的值
                            int min=deleteMin(target.right);
                        //2.2.2 替换目标节点中的值
                            target.value=min;
                    }

                //2.3 要删除的节点是有一个子节点
                    else
                    {
                        //2.3.1 左子节点
                        if(target.left!=null)
                        {
                            //2.3.1.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.left;     //要删除的是父节点的左节点 然后它有的是左节点
                            }
                            //2.3.1.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.left;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                        }
                        //2.3.2 右子节点
                        else
                        {
                            //2.3.2.1 要删除的节点是父节点的左节点
                            if(parent.left.value==value)
                            {
                                parent.left=target.right;     //要删除的是父节点的右节点 然后它有的是左节点
                            }
                            //2.3.2.2 要删除的节点是父节点的右节点
                            else
                            {
                                parent.right=target.right;     //要删除的是父节点的右节点 然后它有的是右节点
                            }
                        }
                    }
                }
        }

    //删除右边最小的节点并且获取该节点的值
    private int deleteMin(Node node) {
        Node target=node;
        //递归一直找最左边
        while(target.left!=null){  //右边的子树里面的左节点一直可以找下去  就一定是最小的
            target=target.left;
        }
        //最小的值有右子节点
        delete(target.value);  //那么剩下了一个叶子节点肯定会通过delete方法补上去
        return target.value;  //直接返回结果
    }

    //查找父节点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

}

测试左左情况结果:

测试右右情况结果:

构造平衡二叉树(双旋转)

二叉排序树经过一次旋转之后还是不平衡的所以还需要第二次旋转

双旋转条件

1. 根的左节点的左高度 < 右高度(左少右多)  -- 1.1 根的左节点先左旋转 1.2 整体再右旋转
2. 根的右节点的右高度 < 左高度(左多右少)  -- 2.1 根的右节点先右旋转 2.2 整体再左旋转

举例：

Node类更新(单循环添加特定条件)

//3.1 左左情况(向右转)
            if(leftHight()-rightHight()>=2){   //左边太多 向右转(原来根的左节点作为新的根节点)
                //3.1.1 双旋转
                if(left!=null&&left.leftHight()<left.rightHight()){  //根的左节点的左高度<右高度
                    left.leftRotate();  //左节点先左旋转
                    rightRotate();  //整体再右旋转
                }
                //3.1.2 单旋转
                else{
                    rightRotate();
                }
            }
          //3.2 右右情况(向左转)
            if(leftHight()-rightHight()<=-2) {
                //3.2.1 双旋转
                if(right!=null&&right.rightHight()<right.leftHight()){  //根的右节点的右高度<左高度
                    right.rightRotate();  //右节点先右旋转
                    leftRotate();  //整体再左旋转
                }
                //3.2.2 单旋转
                else {
                    leftRotate();
                }

双旋转结果：

多路查找树

多路查找树分类：

1. 2-3树(B树的特例)
2. 2-3-4树(B树的特例)
3. B树和B+树

数据存储原理

B树提高普通二叉树的效率:

2-3树原理

满足条件：

1. B树中所有的叶子节点都在同一层
2. 有两个子节点的节点 --> 二节点  (二节点要么有两个节点，要么没有子节点)
3. 有三个子节点的节点 --> 三节点  (三节点要么有三个节点，要么没有子节点)
4. 有四个子节点的节点 --> 四节点  (四节点要么有四个节点，要么没有子节点)

B树和B+树原理

很多的二/三/四节点组成的二叉树

B树和B+树的区别

1. B+树的叶子节点存放内容(有序的链式结构)

2020-04-18

树

树概念

特殊树

二叉树

1. 满二叉树 : (最后一层是满的 很完美)   
2. 完全二叉树 : (编号之后中间序号没有断)
3. 二叉排序树/二叉查找树/二叉搜索树 : (左子树结点的关键字均<右子树的节点繁荣关键字)
4. 平衡二叉树 : (树的任意一个节点的左右子树的深度差不超过1)

线索二叉树

通过给节点给前后值能够知道这个节点前后节点是哪个

赫夫曼树

主要用于数据压缩(通过两个最小的值不断生成新节点)

平衡二叉树

一种二叉排序树 + |左子树高度-右子树高度|<1

多路查找树

主要学的是B和B+树

2020-04-15

排序

排序算法(8个)

排序算法概述：

性能对比：

冒泡排序

原理

1.比较两个相邻的元素，将值大的元素交换到右边(直到比较最后两个数)
2.然后开始下一轮，直至倒数第二个数交换成功

动态图：

具体实现

public class BubbleSort {
    public static void main(String[] args){
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr)); //先输出之前的数组
        maopao(arr) ;
        System.out.println(Arrays.toString(arr)); //输出排序之后的数组
    }

    //冒泡排序
    public static void maopao(int[] arr){
        //控制共比较多少轮(除过最后一个数都需要去排序)
        for(int i=0;i<arr.length-1;i++){
            //控制比较次数(每次排序时之前拍好的数字就不需要比较)
            for(int j=0;j<arr.length-1-i;j++){
                    if(arr[j]>arr[j+1]){
                        int temp=arr[j];  //三个数交换的方法
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
            }
        }
    }

}

结果：

快速排序

原理

1. 选择一个标准数(随机数/第一个) --> 一列数字分为左小右大
2. 确定左右两个指针low和high(low<high的情况下去将判断的数字区分成两类数)
3. 确定start和end两个数为数组的一开始和一结束(start<end的情况下快速排序还没有结束)
4. 判断指针左移和数字交换 (假设标准数为2)
    4.1 判断最右边开始的数字
            4.1.1 如果标准数比最右边的数小 2<=9  high指针左移 2 9
            4.1.2 如果标准数比最右边的数大 2>=1  用1把2替换掉 1 2  (一旦换数字就判断左边的去)
    4.2 接下来判断最左边开始的数字
            4.2.1 如果最左边的数比标准数小 1<=2  low指针右移  1 2
            4.2.2 如果最左边的数比标准数大 3>=2  用2把3替换掉 2 3  (一旦换数字就判断右边的去)
    4.3 不断地判断右边的只要换数字了就判断左边的只要换数字就继续交替执行!!!!!!!!!!!

5. 因为low和high碰在 要把重复的值用标准值去替换掉(low和high指向的同一个位置的那个数字要么替换了右边的要么被右边替换过来的所以肯定是两个重复的数字需要用标准值替换)
6. 接下来就是递归调用方法(不断地让两边去快排)
    6.1 处理左边的数字
         kuaisu(arr,start,low) //从start到low指针
    6.2 处理右边的数字
         kuaisu(arr,low+1,end) //从low+1的位置到end

动态图：

分析图示：

具体实现

public class QuickSort {
    public static void main(String[] args) {
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr));  //输出之前的数组
        kuaisu(arr,0,arr.length-1); //开头和结尾相当于指针
        System.out.println(Arrays.toString(arr));  //输出排序之后的数组
    }

    public static void kuaisu(int[] arr,int start,int end){  //传入数组和前后两个参数
        if(start<end){  //如果左边和右边冲突就是快速排序的结束条件
            //将第一个数作为标准数
           		 int biao=arr[start];
            //需要排序的下标
                 int low=start;
                 int high=end;

       //找比标准大的数字和比标准小的数字
           while(low<high){
            	while(low<high&&biao<=arr[high]){  // 假设标准数是2 <= 右边现在数是9
            	        high--; //右边的指针左移(符合条件)
            	    }
            //使用右边的数字替换左边的数字 (标准数是2 >= 右边是1  )
                arr[low]=arr[high];  //用1把2替换掉(做到小数左移)

             //如果左边的数字比标准数小
                while(low<high&&arr[low]<=biao){
                    	low++;  //左边指针右移(符合条件)
                	}
             //使用左边的数字替换右边的数字 ( 左边的8 >= 标准数是2) 
                arr[high]=arr[low];  //将8替换2

          }

          //标准数替换掉重复的数字(low/high都可以)
          	  arr[low]=biao;  
          //处理所有小的数字
          	  kuaisu(arr,start,low);
          //处理所有大的数字
          	  kuaisu(arr,low+1,end);
        }
    }

}

结果：

插入排序(直接插入排序)

原理

1. 最大的特点就是：我在排当前数的时候前面的数必须是有序的
2. 从第二个数开始
    2.1 遍历所有前面的数字 如果当前数(2) < 前面的数字(3 4) : 说明我还可以左移 (前面的数字给后面的数字)
    2.2 如果当前数(2) > / = 前面的数(1 2 3) : 说明已经不用挪动了就可以2替换3的位置 (3已经在上面的条件里面挪到后面了)

动态图：

具体实现


public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //int n=input.nextInt();
        int[] a=new int[]{1,5,3,6,9,4,11,87,23};
        find(a);  //调用方法返回结果
        System.out.println(Arrays.toString(a));
    }

    public static void find(int[] a){
      for(int i=1;i<a.length;i++){  //从第二位开始遍历
          int temp=a[i];  //将要插入的数字存放到temp里面
          int flag; //定义flag下标 因为for循环外面还要用
          for(flag=i-1;flag>=0&&a[flag]>temp;flag--){  //找0到i-1位置遍历
              a[flag+1]=a[flag];  //只有满足前面比要插入的数字大 才让他往后挪动
          } 
          a[flag+1]=temp;  //最后flag通过for会给一个值 然后将要插入的数字插入位置
      }
    }

}

结果：

插入排序(希尔排序)

原理

1. 根据(总数/2)的方法不断去组队排序 
  假如是9个数字 ：     
    1.1 第一轮是9/2=4(按照4的间隔对应的数字排序 0和4和8位置的排序对比 1和5的对比 2和6的对比 3和7的对比)
    1.2 第二轮是4/2=2(按照2的间隔对应的数字进行排序对比 ) 
    1.3 直到/2为1的时候结束
2. 通过这个方法比直接插入排序效率高(万一最后一个数字是最小的话就可以很快速的放到前面去)

动态图：

具体实现

public class ShellSort {
    public static void main(String[] args) {
        int []arr=new int[]{5,7,2,9,4,1,0,5,7};
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr){
        //遍历所有的步长
            for(int d=arr.length/2;d>0;d/=2){
                //遍历所有的元素
                    for(int i=d;i<arr.length;i++){ 
                      //遍历一个组的所有元素
                        for(int j=i-d;j>=0;j-=d){  //j是从
                            if(arr[j]>arr[j+d]){  //前大于后  3 2
                                int temp=arr[j];  //两个数交换
                                arr[j]=arr[j+d];
                                arr[j+d]=temp;
                            }
                        }
                    }
            }
    }

}

结果：

选择排序(简单选择排序)

原理

1. 我们就是每次都判断之后的所有的数字。每次把最小的数字换到判断的这个点上。
2. 如果后面有比现在的位置小的数字就把下标记下来最后让之前的最小的数字的下标和现在的数字更换位置。

具体实现


public class XuanZ {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,5,7,1,2,0,3,6,8};
        System.out.println(Arrays.toString(arr));  //输出未排序的顺序
        	xuanze(arr);
        System.out.println(Arrays.toString(arr));  //排序之后的顺序
    }

    public static void xuanze(int[] arr) {
        //遍历所有的数
            for(int i=0;i<arr.length;i++){
                int minIndex=i;
            //把当前遍历的数和后面所有的数依次进行比较
                //记录最小的数的下标
                for(int j=i+1;j<arr.length;j++){ //从第二个开始
                    if(arr[minIndex]>arr[j]){  //后面有数字更小 就把它记录下
                        minIndex=j;
                    }
                }
                //最小的数和当前遍历的下标不一致  后面有数字替换了当前的数字
                    if(i!=minIndex){
                        int temp=arr[i];
                        arr[i]=arr[minIndex];
                        arr[minIndex]=temp;
                    }

            }
    }

}

结果：

归并排序(递归)

原理

1. 将其划分为两部分一直到不能分解(递归)
2. 两部分开始归并 
3. 最终返回回来就是一个排序好的数组

递归思路：

动态图：

具体实现


public class GuiB {
    public static void main(String[] args) {
        int[] arr=new int[]{1,3,5,2,4,6,8,10};
        System.out.println(Arrays.toString(arr)); //排序前
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));  //排序后
    }

    public static void mergeSort(int[] arr,int low,int high){
        int middle=(high+low)/2;  //取中间位置
        if(low<high)
        {
            mergeSort(arr,low,middle);  //处理左边
            mergeSort(arr,middle+1,high);  //处理右边
            merge(arr,low,middle,high);  //归并
        }
    }

    public static void merge(int[]arr,int low,int middle,int high){
       //用于存储归并后的临时数组
        int[] temp=new int[high-low+1];
       //记录第一个数组中需要遍历的下标
        int i=low;
       //记录第二个数组中需要遍历的下表
        int j=middle+1;
       //记录临时变量存放下标
        int index=0;
      //遍历两个数组 取出小的数字放如临时数组中
        while (i<=middle&&j<=high){
            if(arr[i]<=arr[j]){   //左边数组的小  放入之后下标++
                temp[index]=arr[i];
                i++;
                index++;
            }
            else{   //右边数组的小 放入之后下标++
                temp[index]=arr[j];
                j++;
                index++;
            }
        }
    //处理多余数据
        while(j<=high){   //右边数组多了
            temp[index]=arr[j];
            j++;
            index++;
        }
        while(i<=middle){  //左边数组多了
            temp[index]=arr[i];
            i++;
            index++;
        }

     //临时数组重新存入
        for(int k=0;k<temp.length;k++){
            arr[k+low]=temp[k];
        }

    }

}

结果：

基数排序(适用多位数)

原理

1. 大概思路就是每次对排序的数字进行取余(个位到十位一直到最大数字的最高位停止)
2. 每次取余之后把数字放在余数和0..9对应的二维数组内 (第一次是99 取余之后是9就放在二维数组第一个属性是9的位置里面)
3. 然后按照0..9的顺序从二维数组取出来放入原来的数组 然后又取余数按照余数放进二维数组
4. 一直到最后一次取出来就肯定是按顺序

动态图：

具体实现

public class RadixSort {
    public static void main(String[] args) {
     int[] arr=new int[]{23,6,9,189,45,6,8,123549,56};  //需要排序的数字
        	jishu(arr);
        System.out.println(Arrays.toString(arr)); //排序之后
    }

    public static void jishu(int[] arr){
        //存储数组中最大的数字  --确定排几次
            int max=Integer.MIN_VALUE;
            for(int i=0;i<arr.length;i++){
                if(arr[i]>max){
                    max=arr[i];  //取出来最大的数字 后面会求出几位数控制循环范围
                }
            }

        //求最大数字是几位数
            int maxLength=(max+"").length(); //数字+""就会成为字符串

        //第一个下标就是表示余数的十个可能 第二个就是每个对应下标存放多少个数字
            int[][] temp=new int[10][arr.length];  //0..9的二维数组存放对应余数的数字
        //记录相应数组中数个数
            int[] counts=new int[10];  //记录0..9的二维数组里面存了几个数字

            for(int i=0,n=1;i<maxLength;i++,n*=10){
                for(int j=0;j<arr.length;j++){  //每个数字每次计算余数
                    int ys=arr[j]/n%10;  //获取余数
                    temp[ys][counts[ys]]=arr[j];  //counts[ys]是0..9对应下标存放了几个(方便二维数组存放顺序)
                    counts[ys]++;  //存放的数字+1
                }

              //循环取数
                int index=0;
                for(int k=0;k<counts.length;k++){
                    if(counts[k]!=0){  //记录存了几个数字的数组不为空(二维数组里面有数)
                        for(int l=0;l<counts[k];l++){  //遍历二维数组中存的排序的数字
                                  arr[index++]=temp[k][l];  //数字再放到原来数组
                        }              
                    }
                }

			//让记录二维数组存数的数组全部清空 (下一次取余计数好用!!!)
				for(int z=0;z<counts.length;z++){
	                    counts[z]=0;
	                }
	
	       }

    }
}

结果：

基数排序(队列)

现在使用队列进行存放(队列添加)和每一次存放之后返回(出队) – 减少了二维数组和计数数组的麻烦

队列

public class MyQueue {

    int[] elements;

    public MyQueue() {
        elements=new int[0];
    }

    //入队
    public void add(int element) {
        // 创建一个新的数组
        int[] newArr = new int[elements.length + 1];
        // 把原数组中的元素复制到新数组中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        // 把添加的元素放入新数组中
        newArr[elements.length] = element;
        // 使用新数组替换旧数组
        elements = newArr;
    }

    //出队
    public int poll() {
        //把数组中的第0个元素取出来
        int element = elements[0];
        //创建一个新的数组
        int[] newArr = new int[elements.length-1];
        //复制原数组中的元素到新数组中
        for(int i=0;i<newArr.length;i++) {
            newArr[i]=elements[i+1];
        }
        //替换数组
        elements=newArr;
        return element;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return elements.length==0;
    }

}

主要实现类

public class RqdixQueueSort {
    public static void main(String[] args) {
        int[] arr=new int[]{23,6,9,189,45,6,8,123549,56};
            jishu(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void jishu(int[] arr){
        //存储数组中最大的数字  --确定排几次
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        //求最大数字是几位数
        int maxLength=(max+"").length(); //数字+""就会成为字符串

        //临时存放数字的队列(先进先出)
            MyQueue[] temp=new MyQueue[10];
            for(int i=0;i<temp.length;i++){
                temp[i]=new MyQueue();
            }

        for(int i=0,n=1;i<maxLength;i++,n*=10){
            for(int j=0;j<arr.length;j++){  //每个数字每次计算余数
                int ys=arr[j]/n%10;  //获取余数
                temp[ys].add(arr[j]); //队列添加
            }

            //数字取出来
            int index=0;
            for(int k=0;k<temp.length;k++){
               while(!temp[k].isEmpty()){  //记录存了几个数字的数组不为空
                    arr[index++]=temp[k].poll();  //队列出队
                }
            }

        }

    }
}

堆排序(堆)

原理

1. 升序 : 小顶堆
2. 降序 : 大顶堆

动态图：

具体实现

2020-04-15

时间复杂度和空间复杂度分析

衡量算法的优劣

1. 事后统计的方法
2. 事前分析估算的方法

时间复杂度

T(n)=O(f(n))

T(n)：是指算法中基本操作语句的重复执行次数是问题规模n的某个函数
O(f(n)):是算法的渐进时间复杂度

常见时间复杂度

	常数阶O(1)
	对数阶O(log2n)
	线性阶O(n)
	线性对数阶O(nlog2n)
	平方阶O(n2)
	立方阶O(n3)
	k次方阶O(nk)
	指数阶O(2n)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

T(n)不同但是时间复杂度可能相同

例如：

T(n)=n²+5n+6 与 T(n)=3n²+3n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。

时间复杂度求法

1. 用1 代理运行实践中所有的加法常数
2. 只保留最高阶项
3. 去除最高阶项系数

2020-04-14

递归

递归(效率低)

不断调用自己

斐波那契数列

第三个数开始是前两个数之和

汉诺塔(递归)

所有问题都考虑成一个盘子和两个盘子的情况!!!!!!

public class TestHanoi {
    public static void main(String[] args) {
        han(3,'A','B','C');  //3个盘子
    }

    //n个盘子 从A通过B传到C
    public static void han(int n,char A,char B,char C){
        
		if(n==1) {
            System.out.println("第一个盘子从"+A+"移到"+C);
        }

        else {
          //移动上面所有的盘子到中间位置(最后一个它自己走上面的方法从A->C)
            han(n-1,A,C,B);
            System.out.println("第"+n+"个盘子从"+A+"移到"+C);
          //把上面的所有盘子从中间位置移到目标位置
            han(n-1,B,A,C);   //把B上面的盘子通过A全部放到C去
        }

    }

}

以三个盘子为例：