/algorithm

Primary LanguageJava

基础

Code01 选择排序

Code02 冒泡排序

Code03 插入排序

二分问题

二分不一定需要有序，只有有某些排他性条件可以构造二选一情景就可以使用

Code04 在一个有序数组 找值是否存在

Code05 在一个有序数组 找》=某个数字最左侧位置

Code05 在一个有序数组 找《=某个数字最右侧位置

Code06 局部最小值问题 在一个相邻元素不相等无序序列 寻找任意一个局部最小值位置 1.边界不是局部最小值 说明两个边界必有最小值

异或运算

Code07 printOddTimesNum1 一个数组只有一个数出现奇数次，其他数出现偶数次 寻找奇数次数字 printOddTimesNum2 一个数组有二个数出现奇数次，其他数出现偶数次 寻找两个奇数次数字 (寻找一个数最右侧的1) N&(~N+1) ^ 异或运算符 相同得0 相异得1 运算满足交换律 和结合律 N ^ N = N 0 ^ N = N;

Code08
一个数组中有一种数出现K次，其他数都出现了M次， 已知M > 1，K < M，找到出现了K次的数 要求额外空间复杂度O(1)，时间复杂度O(N)

链表

Code09- 单链表

public class Node{
    private Integer val;
    private Node next;
    public Node(Integer val){
        this.val = val;
    }
}

双链表

public class DoubleNode{
    private Integer val;
    private DoubleNode next;
    private DoubleNode prev;
    public DoubleNode(Integer val){
        this.val = val;
    }
}

Code12 栈和队列的实现 1.双向链表 2.数组 实现循环队列 判断空判断满 1.少用一个数组位置 当队列为空时条件：rear == front 当队列满时条件为：（rear+1）% maxsize == front 2.使用额外变量 记录队列大小size 队列容量limit 当队列为空时条件：size == 0 当队列满时条件：size == limit Code13 实现一个特殊的栈，在基础操作基础上，在实现返回栈中最小元素 1)pop，push，getMin 操作时间复杂度O(1) 2) 设计的栈类型可以使用现成的栈结构 Code14 实现一个队列，用两个栈 PS：实现原理：两个栈 一个push栈，一个pop栈

  1. 当pop栈为空的时候才能从push栈导入
  2. 导入pop栈是不能中断

递归

Master公式 用来计算子问题规模确定的递归函数的时间复杂度。 形如

  • T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数) 的递归函数，可以直接通过Master公式来确定时间复杂度
    • 如果 log(b,a) < d，复杂度为O(N^d)
    • 如果 log(b,a) > d，复杂度为O(N^log(b,a))
    • 如果 log(b,a) == d，复杂度为O(N^d * logN)

哈希表与有序表

哈希表和有序表的使用和性能

  • 哈希表在使用层面.上可以理解为一-种集合结构
  • 如果只有key，没有伴随数据value，可以使用HashSet结构
  • 如果既有key，又有伴随数据value，可以使用HashMap结构
  • 有无伴随数据，是HashMap和HashSet唯 一的区别，实际结构是- -回事
  • 使用哈希表增(put)、删(remove)、 改(put)和查(get)的操作，可以认为时间复杂度为0(1)，但是常数时间比较大
  • 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小.
  • 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

归并排序与随机快拍

归并排序

  1. 整体是递归，左边排好序+右边排好序+merge让整体有序
  2. 让其整体有序的过程里用了排外序方法
  3. 利用master公式来求解时间复杂度
  4. 当然可以用非递归实现 Code15 在一个数组虫。一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数 组小和。求数组小和。 例子: [1,3,4,2,5]
  5. 1左边比1小的数:没有
  6. 3左边比3小的数: 1
  7. 4左边比4小的数: 1、3
  8. 2左边比2小的数: 1
  9. 5左边比5小的数: 1. 3、4、2所以数组的小和为1+1+3+1+1+3+4+2=16