算法归类
本文最后更新于158 天前,其中的信息可能已经过时,如有错误请发送邮件到3368129372@qq.com

基本用法

基础篇:https://www.flandre.ltd/java/
数据结构篇幅: https://www.flandre.ltd/数据结构/

排序

算法

  • 可以先向栈中存入"-1",这样可以做到每次操作时先弹出并且判断一个元素。

快速幂

注意递归出口为n=0,因为幂可能为负数

二分法

  • 可解决旋转排序数组问题,最后一个值很关键,比它大则在第一个递增区间,比它小则在第二个递增区间。
    1. 对于旋转数组,二分之后有一边必定有序,可进行分类讨论写题
    2. 索引为n-1的位置一定为最小值或者在最小值的右边
  • 取中点可使用 mid=left+(right-left)/2 防止数据溢出。
  • 最好不要在中间return结果,在最后出循环之后再return,每次循环的时候可以对ans进行更新。

回溯法

  • 个人建议定义为void,使用return;直接回到上一层。
  • 可使用iter遍历,stringBuilder的deleteCharAt(sb.length()-1)可快速删除最后一个字符)
  • 可在递归出口相同的地方进行枝剪
  • 传入的list为地址,可直接被修改,建议传入StringBuilder来进行答案的增减
  • dfs时,可把回溯结果设为boolean,方便从点看起
    如下所示

    private boolean dfs(TreeNode node, TreeNode target, List<TreeNode> path) {
        if (node == null) {
            return false;
        }
    
        path.add(node);
    
        if (node.val == target.val) {
            return true;
        }
    
        if (dfs(node.left, target, path) || dfs(node.right, target, path)) {
            return true;
        }
    
        path.remove(path.size() - 1);
        return false;
    }

动态规划

  • 先定义好dp[]到底代表着什么,数组之间有什么关系,数组与答案有什么关系。

位运算

  • 寻找最低位的1
    s = 101100
    ~s = 010011
    (~s)+1 = 010100 // 根据补码的定义,这就是 -s   最低 1 左侧取反,右侧不变
    s & -s = 000100 // lowbit
  • 巧用异或解决成对含单的问题

技巧

  • for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) 可以对i与j一起进行遍历
  • 需要对值与下表同时排序时,可以定义一个二维数组A[n][2],然后自定义Arrays.sort(A,(a,b)->a[0]==b[0]?a[0]-b[0]:a[1]-b[1]),实现升序
  • 遇到多个区间的问题,可以对首元素进行排序,用堆存储末元素,这样遍历两次只需要根据首尾的状态就能够运算,而不用遍历这个区间的所有元素
  • dfs递归时,把dfs放在操作的上面可以先遍历到底再一步一步挽回,放操作的下面则相反
  • 树形dp,可把边存储为
    List<Integer>[] g = new ArrayList[n];
    for(int i=0;i<n;i++){
    g[i] = new ArrayList<>();
    }
    g[0].add(-1);
    for(int[] edge : edges){
    g[edge[0]].add(edge[1]);
    g[edge[1]].add(edge[0]);
    }

    注意不能用Arrays.fill填充g!!!不然填充的是同一个对象!!!
    但是可以用:Arrays.setAll(g, e -> new ArrayList<>());

  • 递归时设置begin与end,初始值为1-n

特别

字典排序

  • 从右到左找到第一个右侧大于左侧的数
  • 右侧的右侧找到最小大于原左侧的数,交换
  • 将交换后右边排序
感谢您的收看~
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇