表示范围

java int

2147483647 = 2.147483647 * 10^9
一般算法题数的范围小于10^9级
0x3f3f3f3f的十进制是1061109567，是10^9级别的，而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形， 4个 3f!
Java

输入输出和返回值
- import java.util.*
- Scanner in = new Scanner(System.in):
  - String str = in.nextLine(); or in.next();
  - 没有读字符方法，可以 char ch = in.next.charAt(0);
    返回值 int[][]
```
List<int[]> resList = new ArrayList<>();
return resList.toArray(new int[resList.size()][])
```
注意resList.toArray() 返回的是 object 数组
return resList.toArray(new int[resList.size()][]) 用了这个方法
- public T[] toArray(T[] a)
- 都可

输入零时一些返回值

if(root == null) return new ArrayList(0);
双重List时
- res.add(new ArrayList(oneRes));
- 其构造方法为：

Arrays.sort()

自定义比较器用法，注意第二种用lambda，元素类型需要是对象

  Arrays.sort(events, new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                if( o1[1]- o1[0] < o2[1]-o2[0]){
                    return -1;
                }
                if(o1[1]- o1[0] > o2[1]-o2[0]){
                    return 1;
                }
                if(o1[0]<=o2[0]){
                    return -1;
                }else{
                    return 1;
                }
            }
        });

输入输出的demo

2022.02.20

nextInt() 读取整数，next() 读取String ，它们都不会处理换行符
next()方法在读取内容时，会过滤掉有效字符前面的无效字符
next()划分每个元素的标准是：空格、制表符、或者换行符。所有元素均有这三种情况分割开来
next()方法在扫描到空白符的时候会将前面的数据读取走，但会丢下空白符“\r”在缓冲区中
nextLine()方法字面上有扫描一整行的意思，它的结束符只能是Enter键，即nextLine()方法返回的是Enter键之前没有被读取的所有字符，它是可以得到带空格的字符串的。

beforeDemo:

next()不能吸收(有效字符后面的)回车符（及空格符），nextLine()可以吸收回车符（空格符）

格式化输出 printf

使用栈和队列

双端队列Deque
stack = new LinkedList
();
- offer, poll, peek
- 既然用了Deque,就使用 offerLast() offerFirst() pollLast() pollFirst() peekLast() peekFirst()
Queue queue = new LinkedList<>();
- poll, offer, peek
  使用堆（and 比较器规则）
import java.util.PriorityQueue;
import java.util.Queue;
Queue minHeap = new PriorityQueue();
Queue
maxHeap = new PriorityQueue
((x,y)->(y-x)); （最大堆：参数2-参数1）
- 如果比较逻辑比较复杂，语法就是 (x,y)->{ … }.

sum: 默认最小堆（参数1-参数2），按数从小到大排列

以上，都还是只是利用元素的自然排序!

如果要实现‘优先队列’，or tuple（a,b），存a, 根据b 在堆内排序，需要重写比较器Comparator 的 compare 方法

PriorityQueue<Integer> stHeap = new PriorityQueue<Integer>(k,
new Comparator<Integer>(){
public int compare(Integer a , Integer b){
        return map.get(a)-map.get(b);
    }
}                                                          
                                                        );
//编译过
Queue<Integer> stHeap = new PriorityQueue<Integer>(2,
              new Comparator<Integer>(){
                  public int compare(Integer a,Integer b){
                      return map.get(a)-map.get(b);//1.堆中存放的是元素，但比较的应该是元素的频率 2 对堆来说： 参数1-参数2 是默认的 小顶堆
                  }
              }
      );//这里要显式指定k，默认是 11 ,否则 if(stHeap.size()<k){ 一直为假

横向对比：Arrays.sort 比较器

Arrays.sort(words,(first,second)->first.length()-second.length());

JAVAcompare方法比较规则

返回负数，不需要交换参数1 和参数2 的位置
返回正数，需要交换参数1 和参数2 的位置

可以简单记：（x，y）->return (x-y) 升序，（x , y）-> return (y-x) 是降序
- 所以，Queue maxHeap = new PriorityQueue((x,y)->(y-x));是大顶堆

使用Map

HashMap
xx = new HashMao();
- bestSelectSet.getOrDefault(root,0)
- setSe.put(root,root.val);
put get // 栈是push

put(key,value)
- key比较相同，会替换旧值！
- 链表或者红黑树上有多个，这些键值对的key是不同的！只不过映射的index相同而已
HashMap.containsKey(key), HashMap.containsValue(Value)
遍历HashMap有哪些方法？
- https://blog.csdn.net/w605283073/article/details/80708943
  长度
数组是 nums.length
字符串 String.length()

String

in.next() vs in.nextLine()?
split()
- 分割规则
- regex的使用

补充“12..”分割完，也只有12，不是{“12”}
另一个分割case: “a good example” 用” “分割后，是{“a”,”good”,””,””,”example”}
- boolean String.contains（String str）
- charAt(int index)
- String.trim();
- 遍历String的每个字符需要for(int i =… 不能用for each循环；字符是基本类型，可以 == 可比较内容，但注意 ch ==’s’ , 用单引号
一般用toCharArray();转成char[ ] 来遍历字符串中的字符 char[] c = str.trim().toCharArray();
- String.toCharArray()

String内置了compareTo方法，用于两个字符串的字典序比较
- public int compareTo( String anotherStr);
  - 比参数字符串小，返回值是负数
- public int compareToIgnoreCase(String anotherStr;
2022.03.15 Java String indexOf()方法
- public int indexOf(int ch) // 输入’c’，同 99，最自动转
- public int indexOf(int ch, int fromIndex)
- int indexOf(String str)
- int indexOf(String str, int fromIndex)

StringBuilder

StringBuilder.toString();
StringBuilder.appen(boolean ,char, char[], {cha[] int offset int len}, double , String,….)
int StringBuilder.indexOf(String str)
StringBuilder.delete(int start, int end) , StringBuilder.deleteCharAt(int index)
自己也有 charAt(int index) 函数

Swap(String a, String b)能否交换外面a，b的值？

知识点1: java 值传递，简单简化，外面的a b固然是不会改变其值的
- 可用反射实现
知识点2：字符串常量池，在堆中中-1.8；运行时常量池（类信息）- 原空间
String a = new String(“blabla”) 得到的是字符串常量池的 ‘简接引用’
String a = “blabla”; 得到的是字符串常量池的 ‘直接引用’

== 优先级及字符运算-小心坑

int c3 = dp[i-1][j-1] + (str1.charAt(i-1) == str2.charAt(j-1) ? 0 :1);//要加括号不然就是先+

随机数

Random random = new Random(); // import java.util.*
random.nextInt(bound);// [0,bound)

JAVA中的正则表达式
https://www.cnblogs.com/look-up-at-the-starlit-sky/p/11602401.html

一、校验数字的表达式
1 数字：^[0-9]*$
2 n位的数字：^\d{n}$
3 至少n位的数字：^\d{n,}$
4 m-n位的数字：^\d{m,n}$
5 零和非零开头的数字：^(0|[1-9][0-9]*)$
6 非零开头的最多带两位小数的数字：^([1-9][0-9]*)+(.[0-9]{1,2})?$
7 带1-2位小数的正数或负数：^(\-)?\d+(\.\d{1,2})?$
8 正数、负数、和小数：^(\-|\+)?\d+(\.\d+)?$
9 有两位小数的正实数：^[0-9]+(.[0-9]{2})?$
10 有1~3位小数的正实数：^[0-9]+(.[0-9]{1,3})?$
11 非零的正整数：^[1-9]\d*$ 或 ^([1-9][0-9]*){1,3}$ 或 ^\+?[1-9][0-9]*$
12 非零的负整数：^\-[1-9][]0-9"*$ 或 ^-[1-9]\d*$
13 非负整数：^\d+$ 或 ^[1-9]\d*|0$
14 非正整数：^-[1-9]\d*|0$ 或 ^((-\d+)|(0+))$
15 非负浮点数：^\d+(\.\d+)?$ 或 ^[1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0$
16 非正浮点数：^((-\d+(\.\d+)?)|(0+(\.0+)?))$ 或 ^(-([1-9]\d*\.\d*|0\.\d*[1-9]\d*))|0?\.0+|0$
17 正浮点数：^[1-9]\d*\.\d*|0\.\d*[1-9]\d*$ 或 ^(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*))$
18 负浮点数：^-([1-9]\d*\.\d*|0\.\d*[1-9]\d*)$ 或 ^(-(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*)))$
19 浮点数：^(-?\d+)(\.\d+)?$ 或 ^-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)$
二、校验字符的表达式
1 汉字：^[\u4e00-\u9fa5]{0,}$
2 英文和数字：^[A-Za-z0-9]+$ 或 ^[A-Za-z0-9]{4,40}$
3 长度为3-20的所有字符：^.{3,20}$
4 由26个英文字母组成的字符串：^[A-Za-z]+$
5 由26个大写英文字母组成的字符串：^[A-Z]+$
6 由26个小写英文字母组成的字符串：^[a-z]+$
7 由数字和26个英文字母组成的字符串：^[A-Za-z0-9]+$
8 由数字、26个英文字母或者下划线组成的字符串：^\w+$ 或 ^\w{3,20}$
9 中文、英文、数字包括下划线：^[\u4E00-\u9FA5A-Za-z0-9_]+$
10 中文、英文、数字但不包括下划线等符号：^[\u4E00-\u9FA5A-Za-z0-9]+$ 或 ^[\u4E00-\u9FA5A-Za-z0-9]{2,20}$
11 可以输入含有^%&',;=?$\"等字符：[^%&',;=?$\x22]+
12 禁止输入含有~的字符：[^~\x22]+
三、特殊需求表达式
1 Email地址：^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$
2 域名：[a-zA-Z0-9][-a-zA-Z0-9]{0,62}(/.[a-zA-Z0-9][-a-zA-Z0-9]{0,62})+/.?
3 InternetURL：[a-zA-z]+://[^\s]* 或 ^https://([\w-]+\.)+[\w-]+(/[\w-./?%&=]*)?$
4 手机号码：^(13[0-9]|14[5|7]|15[0|1|2|3|5|6|7|8|9]|18[0|1|2|3|5|6|7|8|9])\d{8}$
5 电话号码("XXX-XXXXXXX"、"XXXX-XXXXXXXX"、"XXX-XXXXXXX"、"XXX-XXXXXXXX"、"XXXXXXX"和"XXXXXXXX)：^(\(\d{3,4}-)|\d{3.4}-)?\d{7,8}$
6 国内电话号码(0511-4405222、021-87888822)：\d{3}-\d{8}|\d{4}-\d{7}
7 身份证号：
        15或18位身份证：^\d{15}|\d{18}$
        15位身份证：^[1-9]\d{7}((0\d)|(1[0-2]))(([0|1|2]\d)|3[0-1])\d{3}$
        18位身份证：^[1-9]\d{5}[1-9]\d{3}((0\d)|(1[0-2]))(([0|1|2]\d)|3[0-1])\d{4}$
8 短身份证号码(数字、字母x结尾)：^([0-9]){7,18}(x|X)?$ 或 ^\d{8,18}|[0-9x]{8,18}|[0-9X]{8,18}?$
9 帐号是否合法(字母开头，允许5-16字节，允许字母数字下划线)：^[a-zA-Z][a-zA-Z0-9_]{4,15}$
10 密码(以字母开头，长度在6~18之间，只能包含字母、数字和下划线)：^[a-zA-Z]\w{5,17}$
11 强密码(必须包含大小写字母和数字的组合，不能使用特殊字符，长度在8-10之间)：^(?=.*\d)(?=.*[a-z])(?=.*[A-Z]).{8,10}$
12 日期格式：^\d{4}-\d{1,2}-\d{1,2}
13 一年的12个月(01～09和1～12)：^(0?[1-9]|1[0-2])$
14 一个月的31天(01～09和1～31)：^((0?[1-9])|((1|2)[0-9])|30|31)$
15 钱的输入格式：
16 1.有四种钱的表示形式我们可以接受:"10000.00" 和 "10,000.00", 和没有 "分" 的 "10000" 和 "10,000"：^[1-9][0-9]*$
17 2.这表示任意一个不以0开头的数字,但是,这也意味着一个字符"0"不通过,所以我们采用下面的形式：^(0|[1-9][0-9]*)$
18 3.一个0或者一个不以0开头的数字.我们还可以允许开头有一个负号：^(0|-?[1-9][0-9]*)$
19 4.这表示一个0或者一个可能为负的开头不为0的数字.让用户以0开头好了.把负号的也去掉,因为钱总不能是负的吧.下面我们要加的是说明可能的小数部分：^[0-9]+(.[0-9]+)?$
20 5.必须说明的是,小数点后面至少应该有1位数,所以"10."是不通过的,但是 "10" 和 "10.2" 是通过的：^[0-9]+(.[0-9]{2})?$
21 6.这样我们规定小数点后面必须有两位,如果你认为太苛刻了,可以这样：^[0-9]+(.[0-9]{1,2})?$
22 7.这样就允许用户只写一位小数.下面我们该考虑数字中的逗号了,我们可以这样：^[0-9]{1,3}(,[0-9]{3})*(.[0-9]{1,2})?$
23 8.1到3个数字,后面跟着任意个 逗号+3个数字,逗号成为可选,而不是必须：^([0-9]+|[0-9]{1,3}(,[0-9]{3})*)(.[0-9]{1,2})?$
24 备注：这就是最终结果了,别忘了"+"可以用"*"替代如果你觉得空字符串也可以接受的话(奇怪,为什么?)最后,别忘了在用函数时去掉去掉那个反斜杠,一般的错误都在这里
25 xml文件：^([a-zA-Z]+-?)+[a-zA-Z0-9]+\\.[x|X][m|M][l|L]$
26 中文字符的正则表达式：[\u4e00-\u9fa5]
27 双字节字符：[^\x00-\xff] (包括汉字在内，可以用来计算字符串的长度(一个双字节字符长度计2，ASCII字符计1))
28 空白行的正则表达式：\n\s*\r (可以用来删除空白行)
29 HTML标记的正则表达式：<(\S*?)[^>]*>.*?|<.*? /> (网上流传的版本太糟糕，上面这个也仅仅能部分，对于复杂的嵌套标记依旧无能为力)
30 首尾空白字符的正则表达式：^\s*|\s*$或(^\s*)|(\s*$) (可以用来删除行首行尾的空白字符(包括空格、制表符、换页符等等)，非常有用的表达式)
31 腾讯QQ号：[1-9][0-9]{4,} (腾讯QQ号从10000开始)
32 中国邮政编码：[1-9]\d{5}(?!\d) (中国邮政编码为6位数字)
33 IP地址：\d+\.\d+\.\d+\.\d+ (提取IP地址时有用)

比较器

-Arrays.sort(words,(first,second)->first.length()-second.length());

ArralyList 对象有 sort方法

public void sort(Comparator<? super E> c)
alist.sort((o1,o2)->{return o1-o2;});

others
switch
- break是跳出switch,不会执行 default;
- 循环中嵌套switch, break 会跳出最近的 switch or 循环;
- 循环中嵌套switch, continue 是结束本次循环. continue 不能单独和 switch 使用

JAVA整型表示范围

int : - 2^31 ~ 2^31 - 1 ，首位用 0,1 表示正负数
正数：原码
负数：补码
向右移位，高位填充符号位

位运算 & ^ | ~，移位运算

运算优先级很低
if( n & 0x01 ==1) 错误
if( ( n & 0x01 ==0) ) 正确 // if( ( n & 0x01 ) ==0) 正确
-顺便复习了JAVA中位运算规则，移位运算规则
-为什么负数要用补码计算？补码计算的算法是怎么样的？

操作数移位运算符移动位数
a >>1 ： a 右移1位
a <<1： a 左移1位

Math

double Math.pow(底数,指数)；
- 不是power
(double) Math.sqrt(double)

碎碎念

数组题，没有号好思路，排序下再想想？
这是2维数组，zz
比较数组内容：Arrays.equals(arr1,arr2)
看题目，把题目约束都看清楚，有时候问题会简化，或者解题时不会漏掉特殊情况
复杂度，衡量的是随问题输入规模变大时的变化情况。可能解题时需要开辟一个很大的数组或者Map,Set，但开辟后，不随问题输入规模增大而增大，那么空间复杂度依旧是O（1）. e.g. 用int[ 26] 统计字符串中字符的数量。

小技巧

不能用循环和判断语句，可以用短路运算做判断和选则

class Solution {
  public int sumNums(int n) {
      boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
      return n;
  }
}

n 是整数值, !!n 转n为布尔型, 代表n大于小于0;

实战经验

打印输出顺序

0409 荣耀笔试

如果是有多组数据需要求解，封装了一个函数求解每组数据。不要在求解函数中立即打印，这样会影响后面的输入
把每一次结果当作返回值返回，最后再统一打印！

0411 webank
字符串与大整数
BigInteger bint = new BigInteger(“10000000000000000000000000000”)；
Long liint = new Long(“1000000000000000000000000000000000);

不要用float 用 double

腾讯模拟
不要用float , 用double!

如何向上取整

腾讯2018春（腾讯2018春招技术类编程题汇总- 第3题）
Math.ceil(double x) 有局限的
a0 = (int) Math.ceil(a0 / 2);

如果a0总是一个整数，当a0=1， a0/2就会变成0，ceil 后还是 0
此题正确的向上取整做法： a0 = (a0+1)/2

搜索路径-path-point

class Point {
    String x;
    String y;
    public Point(String x, String y) {
        this.x = x;
        this.y = y;
    }
    public boolean equals(Object obj) {
        Point comp = (Point) obj;
        if (this.x.equals(comp.x)  && this.y.equals(comp.y)) { //字符串比较记得不要用 ==
            return true;
        } else return false;
    }
    public int hashCode() {
        return x.hashCode() + y.hashCode();
    }
}

知识点

一般来说, 程序中有3种错误处理方式, 各有优劣

返回值. 统一, 但不能方便计算结果
全局变量. 方便使用计算结果, 用户可能忘了检查
异常处理. 推荐的方式. 可为不同出错原因定义不同的异常处理逻辑并查看,但会改变程序原来执行顺序, 降低性能.

for中的条件判断一旦为假则跳过for循环

//开始for循环 state[j]==false为假，则整个for循环就会被跳过
//错误示范
for (int j = 0; (j < n) && (state[j] == false); j++) {//整个for都不会进入
                if (t == -1 || dis[j] < dis[t]) {
                    t = j;
                }
            }
//如果要跳过某些情况应该在循环内部实现:
for (int j = 0; j < n ; j++) {//state[j]==false 实现了我们枚举U集
           if (state[j]==false &&( t == -1 || dis[j] < dis[t])) {
                    t = j;
                }
            }

算法和数据结构

# zz碎碎念

表示范围

Java

输入输出和返回值

返回值 int[][]

Arrays.sort()

输入输出的demo

格式化输出 printf

使用栈和队列

使用堆（and 比较器规则）

使用Map

长度

String

StringBuilder

== 优先级及字符运算-小心坑

随机数

比较器

others

JAVA整型表示范围

位运算 & ^ | ~，移位运算

Math

碎碎念

小技巧

实战经验

打印输出顺序

不要用float 用 double

如何向上取整

搜索路径-path-point

知识点

for中的条件判断一旦为假则跳过for循环

# zz碎碎念

表示范围

Java

输入输出 和 返回值

返回值 int[][]

Arrays.sort()

输入输出的demo

格式化输出 printf

使用栈和队列

使用堆（and 比较器规则）

使用Map

长度

String

StringBuilder

== 优先级及字符运算-小心坑

随机数

比较器

others

JAVA整型表示范围

位运算 & ^ | ~，移位运算

Math

碎碎念

小技巧

实战经验

打印输出顺序

不要用float 用 double

如何向上取整

搜索路径-path-point

知识点

for中的条件判断一旦为假则跳过for循环

输入输出和返回值