【算法】——力扣hot100常用算法技巧

一：HashMap

1：实例化

实例化：Map<参数一，参数二> hash = new HashMap<参数一，参数二>  //键值对形式

2：put方法

hash.put(key,value)         以键-值对的形式进行put

3：计算长度

hash.size()                         返回表的长度，记得size后有()

4：获取key对应的value

hash.get(key)                   

返回键值key所对应的value//如果key不存在，那么返回null（boolean类型），一般还是getOrDefault()用的多

5：获取key，若无返回自定义值

hash.getOrDefault（key2，自定义值） 

在表里查找是否存在key2这个关键字，若存在返回key2所对应的value，不存在返回自定义的值

注：不能尾追++，一般采用hash.getOrDefault(key2，0)+1

6：移除关键字

hash.remove(key)              移出关键字key（key和value都没啦）

7：是否包含Key

hash.containsKey()          若查询的k在hash表中存在则返回true，否则false

没有hash.contains()这个方法

8：遍历hashMap

 for(Map.Entry<Integer , Integer> entry : map.entrySet()){}  遍历Map

map.entrySet() 这里要注意！！！

9：Map.Entry<> entry  用法

Map.Entry 对象有两个方法：getKey() 和 getValue()，分别用于获取键和值。

二：有关数组的用法

1：hash数组

①经典用法：把字符串中字符出现的次数以数组的形式存储（关联ASCII码值）

char[] array = 字符串名字.toCharArray();

for（char s : array）hash[ s - 'a']++;

2：遍历数组

（1）String[] array = {"first" , "second" , "third"}                 for(String x : array){}  //For-Each循环，注字符串数组可以用foreach循环进行遍历，但是字符数组不可以

（2）字符数组不可以用foreach循环进行遍历，要用正常的fori循环（重点）

3：打印数组元素

Arrays.toString()                           //传入要打印的数组即可。

4：返回一个空数组

用长度作为判断依据

5：复制数组

Arrays.copyOf(数组名，复制长度);

6：字符数组

char[] str = new char[a.length()+b.length()];

数组的初始化：当你使用 new char[a.length() + b.length()] 初始化一个 char[] 数组时，数组中的每个元素会被默认初始化为 '\u0000'，即空字符。在进行四则运算的时候很容易出现问题

三：字符串相关

1：字符串转数组

String a = “abcdefg”      char[] a1= a.toCharArray()           

 //将字符串数组转换为字符数组（常用）

.charAt(下标0~length()-1)       

 //返回下标对应的字符。字符串长度是length()  数组没有括号

2：子字符串

（1）.substring()

截取字符串中介于两个指定下标之间的字符，第一个字符下标为0

注意：(就是小写)两个参数：截取的结果,不包括结束位置的字符。一个参数：从起始位置至字符串末尾的字符串

（2）要想截取到末尾的话

.substring(start)；一直到末尾

（3）用子字符串的长度来表示

.substring(begin,begin+len);

举例0,1,2,3,4  要2，3的话就.substring(2,2+2) ——>(2,4)不包含4很巧妙

也就是说，endIndex的数值不大于字符串长度就可以

3：数组转字符串

字符串转字符数组 char[] ch = s.toCharArray();

字符数组转为字符串  String str = String.valueOf(数组名称);

int类型的数字通过String.valueOf() 方法也可以很方便地转换为字符串。

数字转字符，用+'0'这种形式（不要强转！！！）

(len % 10) + '0' 会把取模结果转换为对应的数字字符的 Unicode 码点，再通过强制类型转换得到对应的数字字符。所以，最终输出的就是字符 '3'。

4：字符串拼接方式

方式一：

String ret = " ";

ret += num[i];

方式二：

5：返回字符串指定下标的字符

字符串的名字.charAt(下标);

6：StringBuilder/StringBuffer用法

  (1)   StringBuilder性能更好，StringBuffer线程更安全，两者方法一样

（2）append追加字符，字符拼接，

（3）计算长度 .length()

（4）删除指定位置的元素 .deleteCharAt()

（5）转化为字符串  .toString()

（6）反转字符  .reverse();返回类型是StringBuffer或StringBuilder

StringBuilder下的toString方法，把拼接的内容以字符串的形式输出。

7：Integer类型转换为String类型

Integer.toString(num1 - num2);

8：Java中字符串的大小写转换

• String.toUpperCase()：将字符串中的所有字母转换为大写。
• String.toLowerCase()：将字符串中的所有字母转换为小写。

9：Java中字符的大小写转换（leetcode支持有这个标准库）

• Character.toUpperCase(char c)：将字符转换为大写
• Character.toLowerCase(char c)：将字符转换为小写

10：indexOf

String str = "hello world";
System.out.println(str.indexOf('o'));//返回第一个o在字符串中出现的位置的下标，4
System.out.println(str.indexOf("wor"));//返回wor这个字符串，首字母w的位置

int o = str.indexOf('o');
int second = str.indexOf('o', o + 1);//第一个参数是找哪个字符，第二个参数是从哪个下标开始找
System.out.println(second);

四：涉及比较

Integer.MAX_VALUE

Math.min()

Math.max()

五：编程易错点

1：^在java中是异或的意思

举例：a=1  ；int result = a^2; 结果result = 3

2：在数组中尽量不要出现减法，容易越界

举例：num[mid+1] > num[mid]  不要写成nums[mid] > nums[mid-1]

六：涉及运算

1：除法运算

对于异号的两个整数，C++/Java语言的原则是使商尽可能大（涉及正负统一修正）

负数j % 正数k  =  m 余 负数f    <=====>    (j %k + k) %k  此时余数为正数

2：三目运算符

buffer.append(ret % 2 == 1 ? '1' : '0'); //还可以这样写，女少。

3：平方运算

Math.pow() 函数返回基数（base）的指数（exponent）次幂，即 base^exponent。

七：for循环

1：for(int x : nums)  修改x的值并不能修改数组中的值

2：遍历字符a~z

for(char ch = 'a' ; ch <= 'z' ; ch++){}

八：涉及随机数

1：Random.nextInt()方法

是生成一个随机的int值，该值介于[0,n)的区间，也就是0到n之间的随机int值，包含0而不包含n。

九：有关排序

1：冒泡排序

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for(int j = n-1 ; j > 0 ; j--){
            for(int i = 0 ; i < j ;){
                if(nums[i] > nums[i+1]){
                    swap(nums , i , i+1);
                    i++;
                }else{
                    i++;
                }
            }
        }
        return nums;
    }

    public void swap(int nums[] , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

}

2：快排（分三个区间）

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums , int l , int r){
        if(l >= r){
            return;
        }
        // Random random = new Random();
        // int index = random.nextInt(r - l + 1) + l;//随机下标
        // int key = nums[index];//随机数

        int key = nums[new Random().nextInt( r - l + 1) + l];
        int left = l-1 , right = r+1 , i = l;
        while(i < right){
            if(nums[i] < key){
                swap(nums,i++,++left);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,i,--right);
                //i++;不能++换过来的数还是一个没有被排序的数
            }
        }
        quickSort(nums,l,left);
        quickSort(nums,right,r);
    }

    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }
}

3：编译器自带排序Arrays.sort()

Arrays.sort()传入参数数组，可以是字符数组，整型数组。时间复杂度为：nlogn

十：有关数据类型

1：BigDecimal

实例化的时候需要传入一个对象

2：自动装箱/拆箱

Integer.parseInt("0")   输出结果为 int类型的0

十一：栈

1：栈里要存放字符串的话，把泛型设置为StringBuffer类型

十二：集合

1：new一个集合

List<> list = new ArrayList<>();

2：添加元素

list.add();

3：Pair<>类型

Pair用法很简单，直接构造Pair<K,V>对象，它只提供获取K和V的方法，没有更改的方法，因此是固定的键值对。

Pair<String, Integer> pair = new Pair<>("pair", 1);

System.out.println(pair.getKey());

System.out.println(pair.getValue());

4：集合转数组（遍历集合的方式）

5：集合反转

Collections.reverse() 是 Java 中 Collections 类提供的一个静态方法，用于反转列表（List）中的元素顺序。该方法没有返回值，直接对传入的 list 进行修改。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        // 创建一个与 list 同大小的 int 数组
        int[] array = new int[list.size()];
        // 使用 for 循环手动赋值
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);  // 获取 List 中的 Integer 对象并赋值给数组
        }

十三：队列

1：new 一个队列

Queue<> queue = new LinkedList<>();

2：入队

queue.add();

3：出队

queue.poll();

4：队列的大小

queue.size();常用于for循环，用foreach循环也能达到目的

5：用集合可以模拟一个队列

十四：优先级队列

1：创建优先级队列的方法

PriorityQueue<> heap = new PriorityQueue<>((a,b) -> a-b); 小根堆  差为负数a放前面

PriorityQueue<> heap = new PriorityQueue<>((a,b) -> b-a); 大根堆

2：添加元素

offer()和add()都可以

在容量有限的 PriorityQueue 中，offer() 更安全，因为它会在队列已满时返回 false，而 add() 会抛出 IllegalStateException 异常。

3：弹出元素

.poll()

4：获取堆顶元素

.peek()

十五：字符相关

1：判断是否为字母

Character.isLetter();

十六：数学公式

1：平方运算

Math.pow(double a, double b)用于计算 a 的 b 次幂，返回值类型是 double。

2：开方运算

开任意次方：通过 Math.pow() 方法实现开任意次方的运算。将待开方的数作为底数，1 除以开方次数作为指数，即可得到开方结果。

使用开方Math.sqrt()，“square root” 翻译为中文是 “平方根”。

返回值类型是 double

3：绝对值

Math.abs()