算法Tips
目录
注意点
- 子序列、子集，都不要求连续
- 【判断字符串内容相等】.equals()；leetcode 内置jdk的问题，不能使用==判断字符串是否相等
- 【判断字符相等】==
- 乘法得写乘号*
增强for循环
==与.equals()
对于引用数据类型，如：String，比较其内容时要用.equals，而不能用==；
而对于基本数据类型，如：int、char可以直接用==
如果发现测试用例是很长的字符串的时候结果错误，检查下你们用集合时候，判断Interger是否相等是不是用了==，要用equal哦
- 因为Integer是对象，==只有在128以内的数字才正确，因为128以内用的是jvm缓存里的对象，大于这个数字，即使是同个数字，地址也不相同
length和length()
打印数组与打印List类型的区别
数组(除了char[]型)，必须调用toString()，否则输出hash值
不能有重复元素
思路:1、hash，判断 contain；2、排序（T15）
判断数是否为奇数
二维数组获得行和宽
//board[][];
n = board.length;
if (n == 0) {
return;
}
m = board[0].length;
集合转数组/数组转集合
//集合转数组
String[] arr1 = new String[list.size()];
list.toArray(arr1);
数组转集合补充：
数组去重后转化为集合
HashSet去重
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
用HashMap做词频统计
- key较多时用hash，否则数组就可以
取多位数的各个位上的数
- 整数转成String型
int N;
String[] strings = (N + "").split("");//拆成字符串数组
//操作完后再转成int多位数
Integer.parseInt(String.join("",strings));
- 用char型数组存放
int n;
String s = String.valueOf(n);
char[] chars = s.toCharArray();
//操作完后再转成int多位数
Integer.parseInt(String.valueOf(chars));
- 用%和/配合
自定义比较器
按0位置元素从小到大排序（Leetcode.56）
Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
按0位置元素从大到小排序，相同时，按1位置从小到大排（Leetcode.406）
Arrays.sort(people,(a,b)->{//正则表达式
if(a[0]==b[0])return a[1]-b[1];//a[0]为h值，a[1]为K值
return b[0]-a[0];//从大到小
});
链表转化为数组
toArray(T[] a)
以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。 例子：Leetcode.406
que.toArray(new int[people.length][]);
将字符数组转化为字符串
char[] c={'a','b','c'};
String.copyValueOf(c)//"abc"
String类的copyValueOf与valueOf的区别以及valueOf与toString的区别
二维数组的长和宽
//定义一个整型数组:3行4列
int a[][] = new int[3][4];
//获取行数---3行
int lenY = a.length;
//获取列数---4列
int lenX = a[0].length;
注意base case
if(a==null || a.length==0 || a[0].length==0) return false;
求数组所有元素和
T1005
int[] nums;//未初始化
Arrays.stream(nums).sum();
将数组元素按绝对值从大到小排序
T1005随想录
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue).toArray();
反转字符串
leetcode.344（额外空间复杂度O(1)）：字符串前后两端字符交换
可用新空间接受字符时：leetcode.1047
while(!stack.isEmpty()){
str=stack.poll()+str;//stack.poll()可换成对字符串的顺序遍历，只要后+str就可以实现逆序
}
大小写字母转换
import java.util.Scanner;
public class fighting
{
public static void main(String[] args)
{
System.out.println("输入的字符串为：");
Scanner sc=new Scanner(System.in);
String str=sc.next();
String str1="";
for(int i=0;i<str.length();i++)
{
char ch=str.charAt(i);
if((ch>='a'&&ch<='z'))//读取的单个字符在'a'和'z'之间才可以转换
{
ch=(char)((int)ch-32);//先将字符ch转换为整型计算ASCII码，再转换为字符型输出字符A~Z的ASCII码为65~90，字符a~z的ASCII码为97~122，每个大小写字符的ASCII码都相差32,因此用小写字符的ASCII码 减去32即可得到该字符的大写形式
//+32
}
str1+=ch;
}
System.out.println("方法一输出的字符串为：");
System.out.println(str1);
System.out.println("方法二输出的字符串为：");
System.out.println(str.toUpperCase());//toUpperCase()将字母转换为大写
//System.out.println(str.toLowerCase());//toLowerCase()将字母转换为小写
}
}
ArrayList
对于List<List>这种形式的返回类型，可以用result.add(new ArrayList<>(path));(leetcode77)
String/ StringBuilder/ StringBuffer
对比
互相转换
判断回文方法
判断数组A是否为数组B的子数组/子序列（或者字符串问题）
- 可以动态规划（T392）
- 看原数组大小，如果比较小（1000左右），可用回溯法，找出所有子数组，每次与数组A比较是否相等
- 如果数组大小非常大，但数组/字符串中存储类型单一（如字符串）只由小写字母组成，可使用哈希方法中的数组来记录各字母出现次数，比较A、B的次数数组（或公用一个数组，一加一减）(T383)；如果类型也不单一，可用Set存储（T349）
将字符串中每个字符取出
String magazine;
for (char c : magazine.toCharArray())
负数
0-num或者-num
