|
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母
解题思路
数组是一种最简单的哈希表，因为两个字符串只包含小写字母所以我们可以设置一个长度为26的数组，0-25分别对应a-z出现的次数，最后再遍历一次数组如果出现了不为1的元素就表明两个字符串不是有效的字母异位词
核心代码
class Solution {
public boolean isAnagram(String s, String t) {
int[] result = new int[26];
for(int i = 0; i < s.length(); i++) {
result[s.charAt(i) - 'a']++;
}
for(int j = 0; j < t.length(); j++) {
result[t.charAt(j) - 'a']--;
}
for(int k = 0; k < 26; k++) {
if(result[k] != 0) {
return false;
}
}
return true;
}
}
时间复杂度
O(n)
空间复杂度
O(1)
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
解题思路
这道题是虚假的求交集，即只是求出元素并不要求元素的个数所以我们可以声明两个set集合，然后将两个set集合中包含的元素加入到结果数组中
也可以使用排序双指针求解这里就不做演示了
核心代码
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<>();
HashSet<Integer> set0 = new HashSet<>();
int i = 0;
for(int item : nums1) {
set.add(item);
}
for(int item : nums2) {
if(set.contains(item))
set0.add(item);
}
int[] result = new int[set0.size()];
for(int item : set0) {
result[i] = item;
i++;
}
return result;
}
}
时间复杂度
O(n)
空间复杂度
O(n)
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
- 我们可以不考虑输出结果的顺序。
解题思路
真正的求交集，和上一题一样也是两种思路，排序双指针的会简单一些
核心代码
排序双指针
class Solution { public int[] intersect(int[] nums1, int[] nums2) {
时间复杂度
O(n)
空间复杂度
O(n)
两个map模拟并集
class Solution { public int[] intersect(int[] nums1, int[] nums2) {
时间复杂度
O(n)
空间复杂度
O(n)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1
示例 2：
输入：n = 2输出：false
提示：
解题思路
将数通过%10分离个位数再通过/10移除个位数并让其他位数顺位减一，将分离完的个位数依次平方求和然后储存到set集合中，循环这个过程，如果平方和和set中的元素重复那么这个数就不是快乐数
核心代码
class Solution { public boolean isHappy(int n) {
时间复杂度
O(logn)
空间复杂度
O(logn)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6输出：[0,1]
提示：
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
解题思路
这道题求解思路很多，暴力硬A的，二分查找，也可以使用哈希表来求得
使用目标数字减去数组的值如果map中存在那么就返回这两个值如果map中不存在那么就将这个数组元素和数组下标存入map中
核心代码
class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; if(nums == null || nums.length == 0) { return result; } HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { int temp = target - nums[i]; if(map.containsKey(temp)) { result[0] = i; result[1] = map.get(temp); return result; } map.put(nums[i], i); } return result; }}
时间复杂度
O(n)
空间复杂度
O(n)
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]输出：2解释：两个元组如下：1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 02. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]输出：1
提示：
- n == nums1.length
- n == nums2.length
- n == nums3.length
- n == nums4.length
- 1 <= n <= 200
- -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
解题思路
因为题解的最后是需要得到能够构成0的个数，所以我们可以将前两个数组的元素之和求出同时统计出现的次数记录到map中，然后再统计剩余元素的和，在map中寻找后两个元素相加求和的相反数如果能找到就记录出现的次数
核心代码
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); int temp; int res = 0;
时间复杂度
O(n^2)
空间复杂度
O(n)
为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"输出：true
提示：
- 1 <= ransomNote.length, magazine.length <= 105
- ansomNote 和 magazine 由小写英文字母组成
解题思路
因为只需要magazine中的字符在ransomNote中出现的次数一致就可以了，所以我们用数组来记录赎金信中的字母及其个数，然后将杂志中的元素进行比对
核心代码
class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] result = new int[26]; for(int i = 0; i < ransomNote.length(); i++) {
时间复杂度
O(n + m)
空间复杂度
O(1)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []输出：[]
示例 3：
输入：nums = [0]输出：[]
解题思路
排序双指针，首先确认第一个元素，如果第一个元素大于0就没有后续的必要了，因为不可以包含重复的三元组所以还涉及到了去重的操作，再确认好第一个元素之后，剩下两个元素的值也很好确认可以使用双指针来分别指向末尾和第一个元素后一位的元素
核心代码
class Solution { public List<List<Integer>> threeSum(int[] nums) {
时间复杂度
O(n^2)
空间复杂度
O(n)
这道题和15题核心思路基本一致
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) {
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
解题思路
模拟题仔细就可以了
核心代码
class MyQueue {
解题思路
模拟题我是使用一个队列实现的
核心代码
class MyStack { List<Integer> list0 = null;
解题思路
栈很适合用来做匹配消除，遍历整个字符串，如果栈中元素不为空并且栈顶元素和对应的右括号匹配就弹出栈
核心代码
class Solution { public boolean isValid(String s) {
时间复杂度
O(n)
空间复杂度
O(n)
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入："abbaca"输出："ca"解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
解题思路
- 消除相邻且相同的元素第一种思路用栈来实现
- 使用Stringbuffer模拟栈
- 双指针遍历字符串，让快慢指针同速前进，如果遇到需要删除的元素就让慢指针–下次循环直接就覆盖了
核心代码
class Solution { public String removeDuplicates(String s) { LinkedList<Character> queue = new LinkedList<>(); char temp; for(int i = 0; i < s.length(); i++) { temp = s.charAt(i);
class Solution { public String removeDuplicates(String s) { StringBuffer buffer = new StringBuffer(); char temp;
class Solution {
public String removeDuplicates(String s) {
char[] c = s.toCharArray();
int slow = 0;
for(int fast = 0; fast < s.length(); fast++) {
c[slow] = c[fast];
if(slow > 0 && c[slow] == c[slow - 1]) {
slow--;
} else {
slow++;
}
}
return new String(c,0,slow);
}
}
时间复杂度
- O(n)
- O(n)
- O(n)
空间复杂度
- O(n)
- O(n)
- O(1)
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
解题思路
求解逆波兰表达式，如果是数字直接入栈，如果是操作符，从栈中取出两个元素进行操作后再压入栈
核心代码
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
int a = 0;
int b = 0;
for(int i = 0; i < tokens.length; i++) {
if ("+".equals(tokens[i])) {
a = stack.pop();
b = stack.pop();
stack.push(b + a);
} else if ("-".equals(tokens[i])) {
a = stack.pop();
b = stack.pop();
stack.push(b - a);
} else if ("*".equals(tokens[i])) {
a = stack.pop();
b = stack.pop();
stack.push(b * a);
} else if ("/".equals(tokens[i])) {
a = stack.pop();
b = stack.pop();
stack.push(b / a);
} else {
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
时间复杂度
O(n)
空间复杂度
O(n)
解题思路
需要统计前k个高频元素，既需要统计元素出现的个数而且需要按照出现的个数进行排序，我们可以使用优先级队列维护一个小根堆，按照出现次数对元素进行升序排序，如果队列长度大于k就将队头元素弹出，最后优先级队列剩余的即是前k个元素
核心代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] result = new int[k];
HashMap<Integer, Integer> map = new HashMap<>();
for(int temp : nums) {
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
Set<Map.Entry<Integer, Integer>> set = map.entrySet();
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
for(Map.Entry<Integer, Integer> entry : set) {
queue.offer(entry);
if(queue.size() > k) {
queue.poll();
}
}
for(int i = k - 1; i >= 0; i--) {
result[i] = queue.poll().getKey();
}
return result;
}
}
时间复杂度
O(nlogk)
空间复杂度
O(n)
核心代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
int j = 0;
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < nums.length; i++) {
while(!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
if(i >= k - 1) {
result[j++] = nums[deque.peek()];
}
}
return result;
}
}
|