type
status
date
slug
summary
tags
category
icon
password

idea快捷方法

mac系统
option+commnd+v 自动生成对象
control+return 进入generate模式,需要全选的时候点击第一个然后按住shift,一直按到最后一个可以实现全点
 

方法介绍

一些使用的比较多的方法在这里介绍
  • ToCharArray( )的用法,将字符串对象中的字符转换为一个字符数组。
  • 对于for(类型名  类型 : 需要遍历的数组)
    • 这时候就是先创建了对象或者变量,然后遍历数组,一个一个赋值给类型
      类型:可以是变量,对象
      类型名:比如String,int,自己建的User对象,不能遍历字符串对象
  • Math.max(value1,value2……)函数返回一组数中的最大值。
  • 在Java中,当你使用nextInt()方法读取一个整数后,光标会停留在该行的末尾,但实际上并没有读取该行的换行符。而nextLine()方法会读取光标所在行的剩余内容,包括可能的换行符,直到换行符为止,然后返回剩余内容(不包括换行符)。如果没有这一行,接下来的循环可能会受到之前的换行符的影响,导致输出结果前面有一个空行。
  • Stringbuilder可变字符串
 

编码失误

  • 特别是在数组中,计算机是从0开始计数的
  • 不要将if,for,swich循环在不清楚的情况下大量的混合使用!
  • 使用Scanner时要注意import java.util.Scanner这句话应该在方法的外面,如果没有该语句,会显示找不到变量,显示没有标识符,需要符号,一般是括号或者标点出错
  • int x=in.nextInt(),该语句的I要大写
  • case(1 || 2)这样写是错的!,数字只能用case穿透
  • System.out.println的开头字母S大写!
  • 显示与Scanner有关的找不到,一般是没有“import java.util.Scanner”这句话导致的。显示找不到某些表达式,很有可能是没有定义,或者超出方法,或者字母拼写错误
  • 字符串与字符串相比,应该先转化为同类型,不然永远是错的,然后使用equals方法
  • 进行字符串比较需要equals,进行char比较用== 单引号表示char,双引号表示String!!!!
  • 数组中的循环设置,变量均小于最大值,没有等于
  • 使用charAt()方法时要注意对应变量为char类型,使用其他类型变量不会报错,但是错的!
  • 使用二分法时要防止溢出
 
究竟什么时候用库函数,什么时候要自己实现
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数
如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,那么直接用库函数。
使用库函数最大的忌讳就是不知道这个库函数怎么实现的,也不知道其时间复杂度,上来就用,这样写出来的算法,时间复杂度自己都掌握不好的。
 

排序算法

堆排序

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为0(nlogn),它也是不稳定排序。
  1. 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
  1. 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
  1. 一般升序采用大顶堆,降序采用小顶堆
    1. notion image
      notion image
 

快速排序

快速排序是一种基于分而治之的排序算法,其中:
  1. 通过从数组中选择一个中心元素将数组划分成两个子数组,在划分数组时,将比中心元素小的元素放在左子数组,将比中心元素大的元素放在右子数组。
  1. 左子数组和右子数组也使用相同的方法进行划分,这个过程一直持续到每个子数组都包含一个元素为止。
  1. 最后,将元素组合在一起以形成排序的数组。
 

选择排序

 

冒泡排序

 

插入排序

 

希尔排序

希尔排序(Shell Sort)基本思想:
将整个序列切按照一定的间隔取值划分为若干个子序列,每个子序列分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子序列和插入排序。直至最后一轮排序间隔为 1,对整个序列进行插入排序。
notion image
notion image
notion image
 

归并排序

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
  1. 设定两个指针,最初位置分别为两个已经排序序列的起始位置。
  1. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
  1. 重复步骤3直到某一指针达到序列尾。
  1. 将另一序列剩下的所有元素直接复制到合并序列尾。
 

位运算

  • 任何一个整数在底层一定有32位信息
  • 左移/右移n位即乘/除2^n
  • 一个int整数的32位信息从0开始,依次向左,分别对应2的0至31次方,即int整数的数据范围为 0~2^32-1(无符号) -2^31~2^31-1(有符号)
  • 三十二位中的第一位是符号位,负数的符号位是1,正数的符号位是0,将符号位去除后,剩下的31位取反加1即为该负数的值
  • >>为带符号右移,>>>为不带符号右移动,最小整数(负数)为例,右移即整体向右移动数位
  • 负号和补码结果一致,补码等于反码加一
  • 最小数和0取反都是本身
  • n的二进制表示中第k位是几
    • 先把第k位移到最后
    • 看个位是几
  • lowbit(x) 返回x的最后一位1
 

二叉树

二叉树顺序存储通常只考虑完全二叉树
第n个元素的左子结点为第2n+1个元素 第n个元素的右子结点为第2n+2个元素
第n个元素的父节点为第(n-1)/2个元素
先序遍历:头节点,左子树,右子树
中序遍历:左子树,头节点,右子树
后序遍历:左子树,右子树,头节点
后继节点指二叉树的中序遍历中一个数的下一个节点
前驱节点指二叉树的中序遍历中一个数的前一个节点

递归实现

递归序

notion image
1 -> 3 -> 5 -> null(以5为节点,左子树为空) -> 5 -> null(以5为节点,右子树为空) -> 5 -> 3 -> 6 -> null -> 6 -> null -> 6 -> 3 -> 1 -> 2 -> null -> 2 -> null -> 2 -> 1 -> 4 -> null -> 4 -> null -> 4 -> 1
先,中,后序实际上就是第一次出现时输出,第二次出现时输出,第三次出现时输出

非递归实现(栈)

基本逻辑,以先序为例
  • 弹出节点就打印
  • 先压右子树,再压左子树
后序为先序的逆向输出
中序
  • 整条左边界依次入栈
  • 弹出节点并打印
 

链表

  • 复制链表
  • 对ArrayList进行升序排序需要Collections.sort();对数组排序用Arrays.sort();

notion image
  • peek()方法调用的是最顶端的数据!!!

二维数组

根据指定比较器引发的顺序对指定的对象数组进行排序
sort(T[] a, Comparator<? super T> c)

Trie

字典树(Trie)也被称为”单词查找树“或”数字树“,有时候也被称为基数树或前缀树(因为可以通过前缀的方式进行索引)。—— 它是一种搜索树,一种已排序的数据结构,通常用于存储动态集或键为字符串的关联数组。
键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
字典树字母的存放有26个,也就是说在实现的过程中,每一个节点的分支都有26个槽位用来存放可能出现的字母组合。同理如果是数字树的话就是10个数字的组合,每个字典树上的节点对应的分支则有10个操作存放可能出现组合的数字。

集合

对集合的遍历
当题目有要求与某些单词对应,进行相关操作时,可以使用HashSet集合存储特殊数值

字符串

在 Java 中,charAt() 方法返回指定索引处的字符,但该字符是不可修改的,字符串是不可变的(immutable)。因此,你不能直接s.charAt(left) = s.charAt(right)进行赋值操作。想要修改字符串中的某个字符,你可以先将字符串转换为字符数组,进行修改,然后再将字符数组转换回字符串。
对字符串前缀的比较,适用于比较字符串前缀,或者截取某一段字符串
需要输出特定格式时可以使用StringJoiner
java字符串转数字的方法:
1、转化为整型数字 Integer.parseInt(String s)
图的遍历
深度优先遍历(DFS)
DFS遍历适用递归
广度优先遍历(BFS)
BFS遍历使用队列
根据下图的数字顺序可判断两者的遍历顺序
notion image

移动窗口

滑动窗口是计算机语言中重要的算法之一,主要用于处理连续的数组数据或者字符串数据,常用来提取数据中的子数组或者子串。适合连续和/积问题,不适合有负值的问题,因为不知窗口往哪滑
用一个for循环进行操作,for循环中的指针为滑动窗口的终止指针!
力扣209:移动窗口例题

离散化

  • 值域大,个数少,让不同数值的数据分别对应数组的顺位下标
  • 数组中可能有重复元素,需要去重,如何算出数组离散化后的值

前缀和

不适合数值过大的问题,因为前缀和/积数字可能超出数字表示范围

动态规划(DP)

适合子数组最大/最小问题,不适合和为k问题,因为要记录上一步的和/积,来更新当前步的和/积,但当前和/积难以确定来自前一步还是自身
 

回溯

  • 如果解决一个问题有多个步骤,每一个步骤有多种方法,题目又要我们找出所有的方法,可以使用回溯算法;
  • 回溯算法是在一棵树上的深度优先遍历(因为要找所有的解,所以需要遍历);
  • 组合问题,相对于排列问题而言,不计较一个组合内元素的顺序性(即[1,2,3]与[1,3,2]是同一个组合),因此很多时候需要按某种顺序展开搜索,这样才能做到不重不漏。
  • 学习心得:其实和套for循环是类似的,只是之前的题目中套的for循环次数有限且较少,如果题目要求的for循环次数不定,那就可以使用回溯,基本结构类似于for循环中嵌套递归,让每一层for循环的时候去向下递归,本质就是遍历出每一个组合的所有可能。
  • 一次for循环结束,i递增,字符串继续拼接,符合条件的就添加,当最里面那层for循环结束后就退出到外层,外层i再递增,实际上和几层for循环类似,然后依照上面的步骤,直到最外层for循环也结束,再继续遍历下一个数字。
notion image
 
文章摘抄搭建博客经验分享
bhddgt
bhddgt
一个普通的干饭人🍚
公告
type
status
date
slug
summary
tags
category
icon
password
🎉NotionNext 4.0即将到来🎉
-- 感谢您的支持 ---
👏欢迎更新体验👏