关注算法,题目来源于LeetCode。涵盖:数组、链表、栈、堆、二叉树、BST树等数据结构,算法有搜索、排序、去重、找出现次数最多等问题。
- 使用Java8来实现
- 迭代法
因为从链表往下个节点变换时,依次是个位、十位、百位 从链表头向下依次遍历叠加 时间复杂度:O(n) 空间复杂度:O(1)
- 从大到小迭代法
将字符串转成字符数组,从字符串最大的长度依次递减;并判断是否为回文字串;如果不是则整体向后移动; 如果当前循环没有找到最大回文字串,则将遍历的回文字串长度--,继续循环 时间复杂度:O(n^3) 空间复杂度:O(1)
- 方法:每次获取剩余整数的个位数,可以一次构建反转整数的一位数字。在这样做的时候,我们可以预先检查向原整数附加另一位数字是否会导致溢出。
- 思路:这个问题其实没有考察算法的知识,模拟的是日常开发中对于原始数据的处理(例如「参数校验」等场景)
- 方法一:字符串法,并检查字符串是否为回文。但是,这需要额外的非常量空间来创建问题描述中所不允许的字符串。
- 方法二:数字本身反转,但直接操作的话可能越界,考虑只反转int 数字的一半?毕竟,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。
-
暴力解法
使用两次for循环,两两相乘可得 时间复杂度:O(n^2) 空间复杂度:O(1) -
双指针法
面积受限于最短边【代表高度】、距离【宽度】; 每次固定最长的那条边,移动最矮的那条边,然后向中间移动,看看能不能找到面积更大的点 时间复杂度:O(n) 空间复杂度:O(1)
- 思路:横向扫描,依次遍历每个字符串,更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。
15. 三数之和。给你一个包含 n 个整数的数组nums,判断nums中是否存在三个元素 a,b,c ,使得a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。
- 双指针法
先对数组排序,固定一数num[i],然后使用双指针指向剩余部分的首尾,计算三数之和是否等于0。满足则添加到集合中 如果num[i] 大于0,则三数之和无法等于0,退出循环 如果num[i] == num[i-1],则说明该数字重复,会导致重复结果,所以应该跳过 当sum == 0时,num[start] == num[start+1],则会导致重复结果,start++ 当sum == 0时,num[end] == num[end-1],则会导致重复结果,end--;
- 思路:迭代法,我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。
- 迭代法
时间复杂度:O(n) 空间复杂度:O(1)
- 思路:双指针法,数组完成排序后,我们可以放置两个指针 i 和 j,其中 i 是慢指针,而 j 是快指针。i指针表示不重复的新的位置,j表示遍历进度下标
- 思路:双指针法,我们可以放置两个指针 i 和 j,其中 i 是慢指针,而 j 是快指针。i指针表示可以存放的新的位置,j表示遍历进度下标。如果遇到不需要移除的值则两个指针同时移动
- 思路:
- 思路:二分查找
- 迭代法
从1开始,逐步向后取得对应的整数序列 时间复杂度:O(n^2) 空间复杂度:O(n)
- 贪心算法:若当前指针所指元素之前的和小于0,则丢弃当前元素之前序列
- 尾部遍历法
查找最后一个单词长度,从尾部遍历,如果找到有效单词返回即可 时间复杂度:O(n) 空间复杂度:O(1)
- 数组后续向前遍历法
数组后续遍历,如果当前下标值为9,则进位,该位置为0;如果当前下标值小于9,直接原地++,直接返回 最后需要考虑99、999这种特殊情况,则数组长度扩长1位,首位置1即可 时间复杂度:O(n) 空间复杂度:O(1)
- 迭代法
时间复杂度:O(n) 空间复杂度:O(n)
- 二分查找法
时间复杂度:O(logN) 空间复杂度:O(1) - 从小遍历法
- 使用库函数法,估记会被怼
- 动态规划法:从1阶开始计算
- 递归法:使用递归很容易解决此问题,但适用于n较小的情况下,n 较大则方法嵌套过深
- 归并法,因为两个都是有序数组,使用两个指针pos1 和 pos2分别记录两个有序数组完成的进度,并判断nums1[pos1] , nums2[pos2] 大小,使用新数据进行存储
-
递归法
中序遍历:先左、再中、再右 时间复杂度:O(n) 空间复杂度:O(n) -
栈
方法一的递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来 时间复杂度:O(n) 空间复杂度:O(n)
- 非递归中序遍历
采用中序遍历能将二叉搜索树转换为从小到大的顺序访问;可以前后两两比较 时间复杂度:O(n) 空间复杂度:O(n) - 中序遍历
中序遍历输出为一个链表,并对链表顺序访问大小 时间复杂度:O(2n) 空间复杂度:O(n)
- 遍历法
采用前序遍历,逐一比较当前元素是否相同 时间复杂度:O(n) 空间复杂度:O(1)
- 查询左子节点最大深度,再查询左子节点最大深度,然后取左、右字节点最大深度 + 1
- 广度优先搜索
时间复杂度:O(n) 空间复杂度:O(n)
- 递归法
时间复杂度:O(N) 空间复杂度:O(logN)
- 我们可以采用深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径。
- 层序遍历【广度优先算法】
- 核心思想:向前探寻下一次最低价格,如果最低价格后面的收益更大,则更新收益
- 双指针法
时间复杂度:O(n) 空间复杂度:O(1)
- 方法一:哈希表
- 方法二:异或(XOR) 1.如果我们对 0和二进制位做XOR运算,得到的仍然是这个二进制位 2.如果我们对相同的二进制位做XOR运算,返回的结果是0 3.XOR满足交换律和结合律
- 方式一:HashSet存储遍历过的链表节点,如果遍历过程中发现有之前的链表节点则存在有环
- 方法二:快慢指针,使用快指针每次向前走2步,慢指针每次向前走1步,如果链表有环则快慢指针一定会相遇
- 使用双链表辅助法
时间复杂度:O(n) 空间复杂度:O(n)
- 思路:设计一个MyNode节点类,存储节点信息(值val,当前栈最小值min,下一个节点next),每次插入向头节点插入、弹出也是头节点弹出、返回最小值只需要返回当前头的最小值即可
- 方式一:双指针分别走两个单链表,如果能相遇则存在相交的起始节点
- 方法二:HashMap法,将第一个单链表存入HashMap中,然后遍历第二个单链表,如果在第二个单链表中发现与hashMap相同的节点则存在相交的起始节点
- 方法一:哈希表 我们知道出现次数最多的元素大于n/2次,所以可以用哈希表来快速统计每个元素出现的次数
- 方法二:排序 如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序,那么下标为 n/2 的元素(下标从 0 开始)一定是众数。
- 使用双向链表作为额外空间辅助,遍历单向链表时不断向双向链表添加;然后通过双向链表从尾部遍历获取反向单向链表 时间复杂度:O(n) 空间复杂度:O(n)
- 使用栈作为辅助结构,根据栈先进后出的特性满足单向链表反向 时间复杂度:O(n) 空间复杂度:O(n)
- 迭代法:使用前驱、后驱节点进行遍历,将单向链表指针反向 时间复杂度:O(n) 空间复杂度:O(1)
- 排序法 先排序,再遍历。如果存在相同元素,则前驱元素必定会与当前遍历元素相同 时间复杂度:O(nlogn) 空间复杂度:O(1)
- HashMap法 遍历数组元素,并向hashMap中判断之前是否存在;如果存在则存在重复元素、不存在的话则向hashMap中插入元数 时间复杂度:O(n) 空间复杂度:O(n)
- 异或法: 排序后,再对数组相邻元素两两异或。如果异或为0,则代表存在一样的元素; 时间复杂度:O(nlogn) 空间复杂度:O(1)
- 递归法
从根节点左、右子节点翻转,然后再翻转左节子点树、再翻转右子节点树 时间复杂度:O(n) 空间复杂度:O(1)
- 递归法: 递归法:如果n为奇数(除1外)都不是2的幂次;如果n为偶数则继续判断它的一半是否为2的幂次 时间复杂度:O(logN) 空间复杂度:O(1)
- 位运算法:
若 n = 2^x 且 x为自然数(即 nn 为 22 的幂),则一定满足以下条件:
1、恒有 n & (n - 1) == 0,这是因为:
n 二进制最高位为 1,其余所有位为 00; n−1 二进制最高位为 0,其余所有位为 1;
2、一定满足 n > 0。
时间复杂度:O(1) 空间复杂度:O(1)
先中、再左、再右探寻法(递归、非递归实现) 先判断当前root是否与p、q相等,如果相等则返回root; 否则判断p、q是否都在左侧,是则继续递归左侧; 否则判断p、q是否都在右侧,是则继续递归右侧; 时间复杂度:O(logN) 空间复杂度:O(1)
- 原地删除法 将下一个节点的值赋值到当前节点的val,然后当前节点指针指向【当前节点的下一个、下一个节点】即可 时间复杂度:O(1) 空间复杂度:O(1)
- 计数法
因为都是小写字母,所以使用数组对字符串字符数量进行计数 时间复杂度:O(n) 空间复杂度:O(1)
- 如果堆中石头的数量 nn 不能被 44 整除,那么你总是可以赢得 Nim 游戏的胜利。 时间复杂度:O(1) 空间复杂度:O(1)
- 首尾同时向中间逼近法 使用首、尾指针分别指向数组的首、尾两端,并进行首尾元素的交换; 然后首指针++、尾指针--。当首尾指针相遇时,说明已经完成数据的交换了 时间复杂度:O(n) 空间复杂度:O(1)
- 双链表法,一个链表用来存储其中一个数组无素,另一个则用来存储交集元素
- 从小开始遍历法,不断地从最小子串判断
- 中序遍历【非递归实现】
时间复杂度:O(n) 空间复杂度:O(n)
- 原地反转法
将字符串转换成数组,然后识别出新的单词,使用双指针原地进行反转 时间复杂度:O(n) 空间复杂度:O(1)
- 根据 val 与 root.val 的大小关系,就可以确定要将 val 插入到哪个子树中。如果该子树不为空,则问题转化成了将 val 插入到对应子树上。否则,在此处新建一个以 val 为值的节点,并链接到其父节点root 上
- 借助栈Stack 数据结构完成即可
- 使用新数组直接复制
--- 计数法
--- hashMap法
- Semaphore 模拟共享竞争资源
- Semaphore 模拟共享竞争资源
- 使用前驱字符、后驱字符记录当前字符前、后字符信息,遇到 '?',从可用字符中排除前驱字符、后驱字符即可完成