GreenHatHGのBlog

接口初始化规则 接口初始化规则当java虚拟机初始化一个类时，要求它的所有父类都已经初始化，但是这条规则不适用于接口 在初始化一个类时，并不会先初始化它所实现的接口 在初始化一个接口时，并不会先初始化它的父接口 因此，一个父接口并不会因为它的子接口或者实现类的初始化而初始化，只有当程序首次使用特定接口的静态变量时，才会导致该接口的初始化 样例1123456789101112131415161718192021public class Main{ public static void main(String[] args) { new C(); new C(); }}class C{ { System.out.println("CC"); //每次创建对象时都会输出 } public C(){ System.out.println("c()"); }}/ ...

区间最值查询 参考：https://blog.csdn.net/qq_41311604/article/details/79900893 RMQRMQ（Range Minimum/Maximum Query），即区间最值查询，这是一种在线算法，所谓在线算法，是指用户每次输入一个查询，便马上处理一个查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O(1)的时间内处理每次查询。 求dp现假设有一数组arr={1,3,6,7,4,2,5}； 设dp[i][j]表示从第i位开始连续2^j个数中的最小值。 例如dp[2][1]表示从第二位开始连续两个数的最小值（也就是从第二位数到第三位数的最小值），即3，6中的最小值，所以dp[2][1] = 3; 那么怎么求dp[2][1]呢？ 当i=2，j=3时，求dp[2][3] 因为2^3=8，代表从2开始有8个数，所以范围为[2,9]然后我们可以将其按照类似二分的思想将其拆分为两部分所以中间mid=(2+9)/2=5 左区间[2,5]：有4个数，其对应dp[2][2] 右区间[6,9]：有4个数，其对应dp[ ...

编译期常量与运行期常量的区别及数组创建本质分析 样例11234567891011121314151617181920import java.util.UUID;public class Main{ public static void main(String[] args){ System.out.println(MyParent3.str); }}class MyParent3{ public static final String str = UUID.randomUUID().toString(); static{ System.out.println("MyParent3 code block"); }}/*output:MyParent3 code block0e7ed916-96de-4805-865d-1b2e703482ec*/ 当一个常量的值并非编译期间可以确定的，那么其值就不会被放到调 ...

线段树入门 数据结构—线段树（segment tree）引入给定一个数组，数组长度可能非常大。现在我们需要对数组里面的数据反反复复进行两个操作 求出某一个区间里面所有元素之和，(query操作) 修改某个元素的值，(update操作) 暴力解决和前缀和对区间[L,R]（长度为n）取和，并且更新一个元素i的值，采用暴力解决方法 可得 query(L,R)时间复杂度为O(n) update(i)时间复杂度为O(1) 如果区间范围很大，再加上多次操作，暴力取和明显会超时，可以采用前缀和方式优化查询sum_arr[0]=arr[0]sum_arr[1]=arr[0]+arr[1]sum_arr[2]=arr[0]+arr[1]+arr[2]这样，假如我们想得到区间[2,4]的和，我们可以用sum_arr[4]-sum_arr[1]计算到 query(L,R)时间复杂度减小为O(1) 因为改变一个值后，要同时更新后面的sum_arr数组，所以update(i)时间复杂度增大为O(n) 如果用线段树的话，我们可以将查询和更新的的时间复杂度都变为O(logn) 方法 query ...

常量的本质含义以及反编译出现的部分助记符 样例112345678910111213141516171819public class Main{ public static void main(String[] args){ System.out.println(Mychild1.str); }}class MyParent1{ public static String str = "hello world"; static{ out.println("Myparent1 static block"); }}class Mychild1 extends MyParent1{ public static String str2 = "welcome"; static{ System.out.println("Mychild1 static ...

HDU6512 —Triangle && HDU6518—Clumsy Keke HDU6518—Clumsy Keke 解析题目大意： 给出一个三维图形的x，y，z轴的长度，然后分别给出正视图，侧视图，俯视图，视图的表示方法是在一个大方格里面，用0代表空白，用1代表阴影，这样就可以表示一个图形了，然后求出这个三维图形是由多少小正方体组成的。 我们可以运用逆向思维，首先构建一个完整的图形，然后减去没有出现的，最终剩下来的就是拥有的，然后再统计下有几个就是我们要求的答案了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/*2019-04-20 00:21:25 46MS 2184K*/#include <cstdio>#include <cstring>using namespace std;const int MAXN = 1e2;bool Map[MAXN] ...

一些STL知识填坑 参考：https://oi-wiki.org nth_element作用是找到选定区间内第 大的数，并将所有比它小的数与比它大的数分别置于两侧，返回它的地址。原理是未完成的快速排序，时间复杂度：期望 O(n) 123456789101112131415161718#include<iostream>#include<algorithm>using namespace std;int main(){ int a[]={3,1,5,4,2,6,8,7,9}; nth_element(a, a+5, a+9); for(int i=0;i<9;i++) cout << a[i] << " "; cout<<endl<<"输出第五大的数： "<<a[4]<<endl; //注意下标是从0开始计数的 return 0;}/*output:2 1 4 3 5 6 8 7 9输出第五大的 ...

EXBSGS $a^{x} \equiv b(\bmod p)$ BSGS只能求解p为素数的情况，EXBSGS可以完美解决这个问题，其基本思路就是通过转换，然后可以运用BSGS算法来求解，最终还是基于BSGS基础 EXBSGS参考：https://www.cnblogs.com/TheRoadToTheGold/p/8478697.html https://blog.csdn.net/a_bright_ch/article/details/83513731 https://www.cnblogs.com/lajioj/p/9529255.html 求解$a^{x} \equiv b(\bmod p)$（P不一定是质数）的最小非负正整数解 先放三个同余定理 定理1： 定理2： 定理3： 求解 如果b==1，那么x=0，算法结束 若gcd(a, p) != 1，令d=gcd(a, p)，若d不能整除b，则无解，算法结束，否则继续 12例如当x=1，a=4，p=8，b=3时，代入公式有4 mod 8和3 mod 8，此时d = gcd(a, p) = 4，说明a与p有 ...

BSGS BSGS(baby-step gaint-step)该算法是指类似于$a^{x} \equiv b(\bmod p$)的方程，已知a，b，p，求x的算法 原始的BSGS只能解决p为质数的情况 由费马小定理$a^{p-1} \equiv 1(\bmod p)$（a，p互质） 同时拆开上面两式得 $a^{p-1} (\bmod p)= 1(\bmod p)$ $a^{x} (\bmod p)= b(\bmod p)$ b最小取值1，而当$x=p-1$时正好为$b=1$，所以当b增大时，x须小于p-1，才能让b大于1，综合得 解x满足$0 \leq x<p$ 求解过程设$m=\lceil\sqrt{p}\rceil$（根号p向上取整），$x=Am-B(0 \leq A,B < m)$ 则由$a^{x} \equiv b(\bmod p)$有$a^{Am- B} \equiv b(\bmod p)$ 即$\frac{a^{Am}}{a^{B}}\equiv b(\bmod p)$ 即$a^{Am } \equiv b a^{B}(\bmod p)$ 我们已知的是a，b ...

学习自周志明老师的《深入理解Java虚拟机》第二版 同时参考：http://www.cnblogs.com/plxx/p/4528688.html 类的加载虚拟机把描述类的数据从Class文件加载到内存，并对数据进行校验,转换解析和初始化，最终形成可以被虚拟机直接使用的Java类型，这就是虚拟机的类加载机制 与那些在编译时需要进行连接工作的语言不同，在Java语言里面，类型的加载、连接和初始化过程都是在程序运行期间完成的，这种策略虽然会令类加载时稍微增加一些性能开销，但是会为Java应用程序提供高度的灵活性 Java里天生可以扩展的语言特性就是依赖运行期动态加载和动态连接这个特点实现的，比如 编写一个面向接口的应用程序，可以等到运行时再指定其实际的实现类 用户可以通过Java预定义的和自定义类加载器，让 一个本地的应用程序可以在运行时从网络或其他地方加载一个二进制流作为程序代码的一部 分，这种组装应用程序的方式目前已广泛应用于Java程序之中。从最基础的Applet、JSP到相 对复杂的OSGi技术 OSGi(Open Service Gateway Initiative)技 ...