数据结构和算法

将所有的类装载到一个集合中

通过反射获取该类

所有的类实现统一接口，有统一方法

执行测试

public static void main(String[] args) {
   Random random = new Random();
   int max = Integer.MIN_VALUE;
   int min = Integer.MAX_VALUE;
   for (int i = 0; i < 100000; i++) {
      int j = random.nextInt();
      if(j < min){
         min = j;
      }
      if(j > max){
         max = j;
      }
   }
   System.out.println("max:"+max+"===="+"min"+min);
}

bound = Math.min(start + intervald, arrayNum);

for (int i = 0; i < length; i++) {
  for (int j = 0; j < i; j++) {
    if((intarray[j] < intarray[i])&&((longest[j] + 1) > longest[i])){
      longest[i] = longest[j] + 1;
     }
    }
    if(longest[i] > best){
    best = longest[i];
    point = i;
  }
}

从最大值处依次往后找，
找出值

只考虑第一个元素，则最大子段和为其本身 DP[0] = nums[0]
考虑前两个元素，最大子段和为 nums[0],num[1]以及 nums[0] + num[1] 中最大值 设为DP[1]
考虑前三个元素，如何求其最大子段和？还是分为两种情况讨论，第三个元素在最后的字串内吗？
若第三个元素也包含在最后的字串内，则DP[2] = Max(DP[1]+nums[2] , nums[2])

dp[0] = nums[0]
dp[1] = max( dp[0] + nums[1] ,  nums[1] )
dp[i] = max( dp[i - 1] + nums[ i ] ,nums[ i ] )

站在自身角度考虑，如果前面的值加起来还没有自身大，那么就刷新数组，前面舍去不要

左边的最大值

右边的最大值

中间的最大值

问题描述

解决思路

问题描述

解决思路

问题描述

解决思路

maxMultiarray[i] = Math.max(maxMultiarray[i], (i - j) * Math.max(j, maxMultiarray[j])); 

求出某个点为 1，以此为起点，向下/右求解最大变长

getMaxSideLength()

状态转换公式

循环体内，确定最大值

状态矩阵是 [n+1][n+1]

将动态规划的二维矩阵降为一维矩阵，空间复杂度降低

状态值

注意

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多

首先随即选取array[0]作为选定元素，通过循环，依次取当前值进行对比，
相等则count++，不等则count--,
count为0，则重新选择当前值为选定元素，继续循环

上述循环只为过滤出选定值，推出循环后，
进入下一个循环，判断该值是否为超过半数的值

多于数组一半则输出，否则输出 -1

对数组进行排序，如果存在多余一半的数，则不然出现在数组中间

记录下数组一半的那个特殊值，通过循环查找该值出现的次数

多于数组一半则输出，否则输出 -1

通过循环，将数组数据放入map中

循环的过程中，查找出现次数最多的那个值

多于数组一半则输出，否则输出 -1

防止到一个map中，
返回首先出现的大于三次的字母

设计思路

注意事项

设计思路

优化

注意事项

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

冒泡排序优化

设计思路

注意事项

设计思路

注意事项

设计思路

注意事项

不建议使用，维护堆的成本较高，

时间复杂度O(lengthlogh),
如果k相对length很小，时间复杂度为O(nlogn)
n为length

将 [k] 维护成一个最大堆,
klogk

对比和交换 ： O(hlogk)

适合内部排序

if(k == low || k == low - 1){
return ;
}

判空

判满

判空

判满

判断条件

赋值条件

链队列在第一次入队时

不可以用

必须用

负载因子，超过某负载因子，进行扩容，数组整体复制

加锁

负载因子，超过某负载因子，进行扩容，数组整体复制

加锁

判空

判满

判空

判满

注意

左右两个指针，不断做比较，往最大值靠拢，相当于排序
每次比较的最大值保存起来，跟下次的最大值比较，
相同，说明存在相同值，
不想同，计数值++

存在三个值：x,y,z;
1)若 y>x ; y>z;  => 2*y > x+z;
2)2*y > x+z; 不能 => y>x ; y>z;

不能用该方法证明最值

首先找出是否为均值单调

判断开始趋势

三层循环

materix_b.length=materix_a[0].length != materix_c的任何值

数组的相似

数独初始化

循环判断

输出

顺时针螺旋打印矩阵：将矩阵
[{1,2,3},
{8,9,4},
{7,6,5}]
打印输出为：1，2，3，4，5，6，7，8，9

设计思路

设计思路

头插法
insertHead

尾插法
insertTail

元素存在并删除成功，返回true

元素不存在或删除失败，返回false

元素存在并删除成功，返回true

元素不存在或删除失败，返回false

查找成功，返回位置 index

查找失败，返回 -1

查找成功，返回该位置的值

查找失败，返回 Integer.MIN_VALUE

构造较交叉链表

判断两个链表是否相交

找出两个链表的交点

尾插法构造有环单链表

判断单聊表是否有环

找出带环单链表的入口

头插法
insertHead

尾插法
insertTail

元素存在并删除成功，返回true

元素不存在或删除失败，返回false

元素存在并删除成功，返回true

元素不存在或删除失败，返回false

查找成功，返回位置 index

查找失败，返回 -1

查找成功，返回该位置的值

查找失败，返回 -1

将一个字符串转换成一个128位链表数组；
数组中的位数表示是否存在某个字符；
数组中某位对应的哪个链表表示字符串中该数组出现的位置

根据当前目标串的值去源串的list中查找；
返回源串中该值出现的 list中的 最左边 的位置

void generateGS(char *b, int m, int *suffix, bool *prefix)
//预处理模式串，填充suffix，prefix
{
int i, j, k;
for(i = 0; i < m; ++i)//两个数组初始化
{
suffix[i] = -1;
prefix[i] = false;
}
for(i = 0; i < m-1; ++i)//b[0,i]
{
j = i;
k = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较)
while(j >= 0 && b[j] == b[m-1-k])//与b[0,m-1]求公共后缀子串
{
--j;
++k;
suffix[k] = j+1;
//相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
// (如果有多个相同长度的子串，被赋值覆盖，存较大的)
}
if(j == -1)//查找到模式串的头部了
prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
}
}

代表在模式串P中，当前下标对应的字符之前的字符串中，有多大长度的相同前缀后缀。
例如如果next [j] = k，代表在模式串P中，下标为j的字符之前的字符串中有最大长度为k 的相同前缀后缀

next[0] = -1

如果已知next[j] = k,如何求出next[j+1]呢

1*10^2 + 2*10^1 + 3*10^0 = 123

4*10^2 + 0*10^1 + 4*10^0 = 404

(a-'a')*26^2 + (b-'a')*26^1 + (c-'a')*26^0 = 28

初始值

通项

计算

然而引入求余又会引发新的问题，tsts ≡≡ p (mod q), 并不意味着就一定有 tsts = p.
但相反，tsts ! ≡≡ p (mod q),那么一定有 tsts ！= p. 由此，一旦tsts ≡≡ p (mod q) 满足，
我们还需要把T[s+1, … , s+m] 和 P[1…m] 这两个字符串逐个字符比较，每个字符都一样，才能最终断定T[s+1,…,s+m] = P[1…m]. 

如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1

否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1

判断数组值相等的错误写法：

设计思路

注意事项

缺点

优化方案

排序

回溯法

list赋值：
list = listtemp,赋值是错误的，容易导致list跟随listtemp，而不是副本

正确：
list = new ArrayList<Integer>(listtemp);

回溯法

sumTemp += binaryTree.value;
if(sumTemp > sum){
sum = sumTemp;
}
if判断要在加和之后，不要再加和之前，不然无法记录值

add()增加函数

insertFixup()颜色调整

rotateRight()左旋

rotateLeft()右旋

步骤一：常规插入：树的二分查找，然后对插入点进行颜色调整。

步骤二：调整方式见下图。

步骤三：部分结点需要进行左旋和右旋。

1）步步为营，必须弄清楚所以指针去向。

2）因为Java语言的原因，栈内的指针不保存，因此需要每次返回root。

3）左旋右旋发生后，当前结点发生变化，需要更改当前结点。

4）严格按照上图思考，先判断叔叔是祖父节点的左孩子还是右孩子？
再对当前结点是左孩子还是右孩子进行判断。

当要插入的节点的父节点
是黑色的时候

初始化：
当插入的节点是根节点时

父节点是祖父节点的左支

父节点是祖父节点的右支

红叔问题：
叔叔节点为红

黑叔问题

参考博客

共两种

说明：其他情况要么不存在要么可以转化

查找 x 的父节点

查找 x 的父节点

排序，可以使用各种排序算法

遍历边，且判断回路

实践

输入：一个 邻接矩阵 或者 邻接表 所代表的图，
          这个图的路径权值必须全部为正，
          指定某个起点。

输出：一个散列表，
          数组代表这个起点到其他所有点的最短距离，
          列表部分表示，起点到当前点的路径。

反射对象的某些方法

参数

通过类获取实现的所有接口，组装代理

Object[] arrLocal;

synchronized (this)

非更改

更改