IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 高龄白菜java学习第九十一天(java数据结构和算法(12)) -> 正文阅读

[数据结构与算法]高龄白菜java学习第九十一天(java数据结构和算法(12))

四、斐波那契查找(黄金分割法)

思路分析

即:数组长度不足时补足,然后用特殊mid值做递归
代码实现

package Search.fib2;

import java.util.Arrays;

public class FibonacciSearch2 {
    public static int maxSize = 20;//确定斐波那契数组的大小
    public static void main(String[] args) {
        int[] arr = {1, 3, 14, 22, 23, 100};
        System.out.println(fibSearch(arr, 100));
    }

    //非递归方法得到一个斐波那契数列
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0]=1;
        f[1]=1;
        for (int i = 2; i < maxSize; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }

    //非递归方式编写算法
    public static int fibSearch(int[] a,int key){//key:我们需要查找的关键码(值)
        int low = 0;
        int high = a.length-1;
        int k = 0;//表示斐波那契分割数值点的对应下标
        int mid =0;
        int f[]=fib();
        while (a.length>f[k]-1){//说明还没有找到
            k++;
        }
        int[] temp = Arrays.copyOf(a,f[k]-1);//不足的部分会被0填充
        for (int i = a.length; i < temp.length; i++) {
            temp[i]= a[high];
        }

        //使用while循环来找到我们的数
        while (low<=high){
            mid = low+f[k-1]-1;
            if (key<temp[mid]){//应该继续向左查找
                high=mid-1;
                //为什么是k--,因为f[k]=f[k-1]+f[k-2],分别是全部=前+后
                //k--相当于把前部分再次拆分
                k--;
            } else if (key>temp[mid]){
                low=mid+1;
                k-=2;
            } else {
                if (mid<=high){//控制超出原来数组的元素对应的下标
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;//没有找到
    }
}

第五章:哈希表

在这里插入图片描述

在这里插入图片描述
代码实现

package HashTable;

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable table = new HashTable(5);
        Emp e1 = new Emp(1, "faker");
        Emp e2 = new Emp(2, "Bengie");
        Emp e3 = new Emp(3, "Bang");
        Emp e4 = new Emp(7, "Wolf");

        table.add(e1);
        table.add(e2);
        table.add(e3);
        table.add(e4);

        table.list();
        System.out.println("==============");
        System.out.println(table.find(10));
    }

}

//哈希表
class HashTable {
    private LinkedList1[] listArray;
    private int size;//共有多少条链表

    public HashTable(int size) {
        this.size = size;
        //初始化链表
        listArray = new LinkedList1[size];//不能直接用,此时只创建了链表集,没有初始化链表,会报空指针异常
        for (int i = 0; i < size; i++) {
            listArray[i] = new LinkedList1();
        }
    }

    //编写散列函数
    public int hashFun(int id) {
        return id % size;
    }

    //真正的动作行为由HashTable调用完成
    public void add(Emp emp) {
        //根据员工id,得到该员工应当添加到哪条链表
        int listNum = hashFun(emp.id);
        listArray[listNum].add(emp);
    }

    public void list(){
        for (int i = 0; i < size; i++) {
            listArray[i].list(i);
        }
    }

    public Emp find(int id){
        int i = hashFun(id);
        return listArray[i].findEmp(id);
    }
}

//雇员节点
class Emp {
    public int id;
    public String name;
    public Emp next;

    public Emp() {
    }

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

//创建链表
class LinkedList1 {
    //没有头节点,直接指向第一个雇员节点(有效)
//    Emp head = new Emp(0,"");
    private Emp head;

    //假定当添加雇员时,id是自增的(总是从小到大)
    //因此直接加到本链表的最后即可
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个,使用辅助指针找到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                curEmp.next = emp;
                break;
            }
            curEmp = curEmp.next;//后移

        }
    }

    //遍历链表的雇员信息
    public void list(int no) {//链表编号
        if (head == null) {
            System.out.println("编号为"+no+"的链表为空");
            return;
        }
        Emp curEmp = head;
        while (curEmp != null) {
            System.out.printf(curEmp+"=>");
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    //根据id查找雇员
    public Emp findEmp(int id){
        if (head==null){
            System.out.println("链表为空,无法查询");
            return null;
        }
        Emp curEmp = head;
        while (curEmp!=null){
            if (curEmp.id==id){
                return curEmp;
            }
            curEmp=curEmp.next;
        }
        //说明遍历之后没找到
        return null;
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-12 19:50:47  更:2021-11-12 19:52:44 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 1:05:50-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码