首页 教程 note

# 算法

# 链表
1. 链表倒序
非递归
ArrayList 的 add方法可以指定插入位置
顺序查询ListNode.next，存入ArrayList的第一个位置，返回ArrayList
递归
首先传入待倒序链表
对链表判空
对ListNode.next调用倒序函数
把ListNode.val传给ArrayList
    
2. 链表反转——双链表
    创建新链表 ListNode newnode = null
    对反转链表head判空
    存temp = head.next
    把head.next指向newNode // 成为了新的链表
    把head给newNode
    head = temp //变回原来的链表
    
3. 合并排序列表——哨兵节点
    ListNode a = new ListNode(0);
	ListNode b = a;

4. 公共节点——历遍所有节点，有公共节点必然会同时到达公共节点
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
历遍所有节点，直到l1 = l2
    三元运算符
    
5. 链表中环的入口
    快链表和慢链表，有环会相遇，无环快链表指向null
    有环，初始化快链表，以相同的速度历遍，再次相遇的点为环入口
    
6. 倒数第K个节点
    先行一步，快链表比快链表先走K步
    
7. 删除重复节点
    Map<Integer,Integer> mp = new HashMap<>()
    使用put和get方法
    历遍，使用哈希表记录每个值出现的次数
    再次历遍，删除次数不等于1的节点
# 其他算法
字符串：
    工具：
    charAt（） 比较使用 == ''
    HashMap<Character,Integer>
    StringBuilder
    StringBuffer
    equalsIgnoreCase // 不缺分大小写
    toUpperCase() // 转大写
    toLowerCase() // 转小写
    char转换为String String.valueOf()
    cahr 通过 -32 转小写 +32 转大写
    cahr 也可通过Character 的toUpperCase() 和 toLowerCase() 妆花大小写
    String.substring(i) // 截取i及之后的字符串
    String.substring(i,j) // 截取i 到j-1间的字符串
    a.CompareTo(b) // 比较字符串大小,拼接时shi'y，>0 a > b; <0 a < b 
数组：
    工具：
# 输入输出
System.in
    Scanner in = new Scanner(System.in)
    in.next() // 读取到下一个非空字符
    in.nextLine() // 读取一整行，直到有换行符（回车），包括空格和换行符
    in.nextInt // 整数输入
    in.next(),charAt(0) // 字符的输入
    in.nextFloat() // 浮点型的输入
    in.hasNext() // 以空格
    in.hasNextLine() // 以回车作为结束标志
# 进制转换：
//10进制转换 16进制
 System.out.println(Integer.toHexString(val));
 System.out.println(String.format("%x", val));
 //10进制转换 8进制
 System.out.println(Integer.toOctalString(val));
 System.out.println(String.format("%o", val));
 //10进制转换 2进制
 System.out.println(Integer.toBinaryString(val));
 
 //16进制转换 10进制
 System.out.println(Integer.valueOf("f", 16));
 //8进制转换 10进制
 System.out.println(Integer.valueOf("11", 8));
 //2进制转换 10进制
 System.out.println(Integer.valueOf("0101", 2));
# 递归 + 回溯

递归：

把一个大型问题层层转化为一个与原问题相似的小问题

如果是线性递归，子问题直接回到父问题，不需要回溯

如果是树形递归，父问题有很多分支，需要从子问题回到父问题，进入另一个子问题，需要回溯父问题的状态，才能进入下一个子问题

1. 没有重复项数字的全排列
    全排列：对数组元素进行元素交换，时每一种排列都可能出现
    思路：每个元素都放到第一位进行历遍排序
    递归条件：
    1. 终止条件：要交换位置的下标到了数组最后一位，结束本次排序
    2. 返回值：把前面已经确认好位置的元素返回给父问题
    3. 本级任务：历遍从它开始的后续元素
    
    全排列：
    1. 当待排序数被取完时结束
    2. 对每一个数进行标记，取出作为第一个元素单独存放，inedx
    3. 执行递归，依次把剩余的数取出放到标记数后面
    4. 在删除的位置恢复被取出的数
    5. 删除上一次被标记数 index.size-1
    
有重复数，递归+回溯+hashmap  
import java.util.*;


public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<>();
        for(int n : num){
            list.add(n);
        }
        ArrayList<Integer> index = new ArrayList<>();
        recursion(list,index);
        LinkedHashMap<ArrayList<Integer>, Integer> map = new LinkedHashMap<>();
        for(int i = 0; i < ans.size(); i++){
            map.put(ans.get(i),map.getOrDefault(ans.get(i),0)+1);
        }
        
        ArrayList<ArrayList<Integer>> newans = new ArrayList<>();
        Set<Map.Entry<ArrayList<Integer>,Integer>> en = map.entrySet();
        for(Map.Entry<ArrayList<Integer>,Integer> e : en){
            newans.add(e.getKey());
        }
        return newans;
        // return ans;
    }

    public void recursion(ArrayList<Integer> list,ArrayList<Integer> index){
        if(list.isEmpty()){
            ans.add(new ArrayList<Integer>(index));
        }else{
            for(int i = 0; i < list.size(); i++){
                Integer temp = list.remove(i);
                index.add(temp);
                recursion(list,index);
                list.add(i,temp);
                index.remove(index.size()-1);
            }
        }
    }
}
# DFS 深度优先搜索算法
1. 矩阵路径
    回溯 + 递归
    1. 确认结束条件
    2. 取出当前路径节点，防止回退路径
    3. 分别查询当前路径节点的四个方向，看是否符合要求
    4. 恢复当前路径节点
    5，返回
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] words = word.toCharArray();
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(dfs(matrix,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] matrix, char[] words, int i, int j, int index){
         
        if(index == words.length - 1){
            return true;
        }
        char temp = matrix[i][j];
        matrix[i][j] = '.';
        boolean res = dfs(matrix,words,i+1,j,index+1)||dfs(matrix,words,i-1,j,index+1)||dfs(matrix,words,i,j+1,index+1)||dfs(matrix,words,i,j-1,index+1);
        matrix[i][j] = temp;
        return res;


    }
}
# 栈 Stack
# 队列 Deque
# 双向队列 ArrayDeque
1. 栈的压入弹出序列
    栈顶元素等于当前需要弹出的元素，则弹出，否则继续进栈
    第一个元素必须先进栈
    进栈次数要等于待进栈元素个数
# 动态规划
思想：
    将待求解问题分解成若干个相互关联的小问题，先求解小问题，然后从这些小问题的解得到原问题的解
    
1. 连续子数组的最大和
    如果加上后面一个元素，反而小于刚加上的元素，那么直接使用刚加上的元素作为新的子数组头
    若要输出最大和对应的子数组，则添加标记位 lift 和 right
    添加最大区间标记位
更新于 阅读次数 次