# JAVA数据结构和算法

**Repository Path**: fengye11153/dataStructuresAndIndexes

## Basic Information

- **Project Name**: JAVA数据结构和算法
- **Description**: JAVA数据结构和算法汇总
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-09-12
- **Last Updated**: 2023-09-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 数据结构和算法

## README


* 1 基础数据结构 二分查找

如何快速的在有序数组arr内，找到目标值target
基础版
改进版
jdk自带二分查找算法实现
有重复元素的情况下如何查找目标值？

力扣  704 二分查找
//最基本的写法必须掌握
public static int binarySearch(int[] arr,int target){
    int =0,j=arr.length-1;
    while(i<=j){
        int mid =(i+j)>>>1;
        if(arr[mid]>target){
            j=mid-1;
        }else if(arr[mid]<target){
            i=i+1;
        }else {
            return mid;
        }
    }
    return -1;
}

力扣  35  搜索插入位置
public static int binarySearch(int[] arr,int target){
    int =0,j=arr.length-1;
    while(i<=j){
        int mid =(i+j)>>>1;
        if(arr[mid]>target){
            j=mid-1;
        }else if(arr[mid]<target){
            i=i+1;
        }else {
            return mid;
        }
    }
    return i;
}
力扣  34  排序数组中查找元素的第一个和最后一个位置

public int[] searchRange(int[] arr,int target){
    int left=binarySearchLeftMost(arr,target);
    if(left==-1){
        return new int[]{-1,-1};
    }else{
        return new int[]{left,binarySearchRightMost(arr,target)};
    }
}

public static int binarySearchLeftMost(int[] arr,int target){
    int =0,j=arr.length-1;
    int candidate=-1;
    while(i<=j){
        int mid =(i+j)>>>1;
        if(arr[mid]>target){
            j=mid-1;
        }else if(arr[mid]<target){
            i=i+1;
        }else {
            candidate=mid;
            j=mid-1;
        }
    }
    return candidate;
}

public static int binarySearchRightMost(int[] arr,int target){
    int =0,j=arr.length-1;
    int candidate=-1;
    while(i<=j){
        int mid =(i+j)>>>1;
        if(arr[mid]>target){
            j=mid-1;
        }else if(arr[mid]<target){
            i=i+1;
        }else {
            candidate=mid;
            i=mid+1;
        }
    }
    return candidate;
}

* 2 数组
数组 元素是连续存储的，可以通过索引位置来获取元素,索引从0开始计算；
int [] arr={1,2,3,4,5,6,7}
根据索引查找元素，时间复杂度1
增删涉及到元素的移动，效率相对较差；

简单数组：固定长度的数组 静态数组
动态数组
二维数组
int[][] array={{1,2,3},{2,3,1},{3,2,1}};
array[i][j] 其中 i j 分别代表 外层数组 内层数组的索引位置

自定义动态数组：包含基本的增删改；

* 3 链表

每个元素都指向下一个元素，与数组最大的区别是数据不连续存储
单向链表：每个元素只知道下一个元素是谁 next
双向链表：每个元素知道上一个元素和下一个元素 pre next
循环链表： head tail 
链表中的每一个元素成为节点，包含当前值value和指针 pre next

增删快，起始位置插入时间复杂度1，其他位置需要先确认插入位置，然后在执行插入；
查询相对较慢，


* 4 基础数据结构  递归
递归调用：自己调用自己，处理的范围会缩减，最终缩减到无需递归；

递归的解决方案取决于解决同一类问题的更小子集；

思路：
1 确定是否可以使用递归
2 推导出递归关系，即父问题与子问题的关系，以及递归的结束条件

single recursion 
multi recursion



* 5 基础数据结构  队列
特点 先进先出
队列
插入：只能从队列尾部插入
获取 :只能从队列头部获取

* 6 二叉树
遍历方式：  
层序遍历

* 7 栈 Stack
特点 先进后出
只能在其一段添加元素和删除元素，习惯来说，可以操作的称之为栈顶；
如同生活中的一摞书，只能从栈顶操作;