二进制运算（与或非和左右移）
<<表示左移，不分正负数，低位补0；
3 << 2 //12 则是将数字3左移2位 322 = 3*(2的2次方)
数学意义：在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
数学意义：右移一位相当于除2，右移n位相当于除以2的n次方。
>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
//比如x转为16进制，思想就是分组(num & 0xf,即取出低4位 转为整数)再将每个组数转为16进制再删去那个组（num>>>4）
if(num==0) return "0";
String hex = "0123456789abcdef";
StringBuilder sb = new StringBuilder();
while(num!=0){
sb.append(hex.charAt(num&0xf));
num>>>=4; //无符号右移
}
return sb.reverse().toString();
链表中点（或者说奇数偶数长度下二分）（代数进去算一下）
//找到一半的位置（奇数就放弃最中间的数）
head = h;
for(int i = 0; i < ((length + 1 )/ 2) - 1 ;i++ ){
head = head.next;
}
//i < length/2 在回文的背景下无所谓 <= 也可以（重要的是代数算一下）
ListNode headFirst = h;
ListNode headLast = pre;
for(int i = 0 ; i < length/2 ;i++){
if(headFirst.val != headLast.val)
return false;
headFirst = headFirst.next;
headLast = headLast.next;
}
public boolean isPalindrome(ListNode h) {
int length = 0;
ListNode head = h;
while(head != null){
length++;
head = head.next;
}
head = h;
for(int i = 0; i < ((length + 1 )/ 2) - 1 ;i++ ){
head = head.next;
}
//========================
ListNode pre = head;
ListNode cur = head.next;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
// ListNode a = h;
// for(int i = 0 ; i < length/2 ;i++){
// System.out.print(a.val+" ");
// a = a.next;
// }
// System.out.println();
// ListNode aa = pre;
// for(int i = 0 ; i < length/2 ;i++){
// System.out.print(aa.val+" ");
// aa = aa.next;
// }
ListNode headFirst = h;
ListNode headLast = pre;
for(int i = 0 ; i < length/2 ;i++){
if(headFirst.val != headLast.val)
return false;
headFirst = headFirst.next;
headLast = headLast.next;
}
return true;
}
map排序
//这里将map.entrySet()转换成list
List> list = new ArrayList>(map.entrySet());
//然后通过比较器来实现排序
Collections.sort(list,new Comparator>() {
//升序排序
public int compare(Map.Entry o1,
Map.Entry o2) {
if(o1.getKey() > o2.getKey()){
return 1;
}else if(o1.getKey() < o2.getKey()){
return 0;
}else{
return o2.getValue() - o1.getValue();
}
}
});
for(Map.Entry m:list){
System.out.println(m.getKey()+":"+m.getValue());
}
return null;
//=======================分割线=======================
Map map = new TreeMap<>();
//自定义比较器
Comparator> valCmp = new Comparator>() {
@Override
public int compare(Map.Entry o1, Map.Entry o2) {
return o2.getValue()-o1.getValue();
}
};
for(int i = 0 ; i < nums.length ; i++){
if(map.containsKey(nums[i])){
map.put(map.get(nums[i]) , map.get(nums[i]+1));
}else{
map.put(nums[i] , 1);
}
}
//将map转成List，map的一组key，value对应list一个存储空间
List> list = new ArrayList>(map.entrySet()); //传入maps实体
Collections.sort(list,valCmp); // 注意此处Collections 是java.util包下面的,传入List和自定义的valCmp比较器
int[] res = new int[k];
for(int i = 0 ; i < k ; i++) {
res[i] = list.get(i).getValue();
}
return res;
数组排序
Arrays.sort(people, (int[] o1, int[] o2) ->{
if(o2[0] == o1[0]){
return o2[1] - o1[1];
}else{
return o1[0] - o2[0];
}
});
数组赋值
Arrays.fill(f,Integer.MAX_VALUE);
Map构建（不要再先判断有无值再put了）
public int findLHS(int[] nums) {
Map map = new HashMap<>();
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
int ans = 0;
for (int i : nums) {
if (map.containsKey(i - 1)) {
ans = Math.max(ans, map.get(i) + map.get(i - 1));
}
}
return ans;
}
数组排序2（由大到小）（不建议使用，但是我记得有面经问过这种流的使用）
//数组元素转换为数值流
IntStream stream = Arrays.stream(nums);
//流中元素全部装箱
Stream st = stream.boxed();
//将流转换为数组
Integer[] num = st.toArray(Integer[]::new);
Arrays.sort(num , Collections.reverseOrder());
DFS常用
List res = new ArrayList<>();
linkedList path = new linkedList<>();
public List binaryTreePaths(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null)
return ;
path.add(String.valueOf(root.val));
if(root.left == null && root.right == null) {
res.add(String.join("->", path));
}
dfs(root.left);
dfs(root.right);
path.removeLast();
}
寻找环/寻找相同元素（其实就想记录下数组模拟链表的例子）
public int findDuplicate(int[] nums) {
int a = 0;
int b = 0;
while (true){
a = nums[a];
b = nums[nums[b]];
if (a == b){
a = 0;
while (a != b){
a = nums[a];
b = nums[b];
}
return a;
}
}
}
层序遍历二叉树顺便记录每层节点数量
public int findBottomLeftValue(TreeNode root) {
TreeNode res = new TreeNode();
Queue queue = new linkedList();
queue.add(root);
int size = 0 ;
while (!queue.isEmpty()){
int num = 0;
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(i == 0)
res = node;
if(node.left != null ){
num ++;
queue.add(node.left);
}
if(node.right != null){
num ++;
queue.add(node.right);
}
}
size = num;
}
return res.val;
}
未完待补充
