242. 有效的字母异位词
难度简单336
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
class Solution {public boolean isAnagram(String s, String t) {Map<Character,Integer> map = new HashMap<Character,Integer>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);map.put(c,map.getOrDefault(c,0) + 1);}for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);map.put(c,map.getOrDefault(c,0) - 1);if(map.get(c) < 0){return false;}else if(map.get(c) == 0){map.remove(c);}}return map.isEmpty();}}
49. 字母异位词分组
难度中等650
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key,new ArrayList<String>());
list.add(str);
map.put(key,list);
}
return new ArrayList<>(map.values());
1. 两数之和
难度简单10229
给定一个整数数组 nums 和一个整数目标值 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 <= 10-10 <= nums[i] <= 10-10 <= target <= 10- 只会存在一个有效答案
**
//给定一个整数数组 nums 和一个整数目标值 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 <= 103
// -109 <= nums[i] <= 109
// -109 <= target <= 109
// 只会存在一个有效答案
//
// Related Topics 数组 哈希表
// 👍 10235 👎 0
import java.util.HashMap;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])){
result[0]=i;
result[1]=map.get(target - nums[i]);
return result;
}
map.put(nums[i],i);
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
剑指 Offer 40. 最小的k个数
难度简单189
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
//优先级队列
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
for (int i = 0; i < arr.length; i++){
heap.add(arr[i]);
}
int[] results = new int[k];
for (int i = 0; i < k; i++) {
results[i] = heap.poll();
}
return results;
}
}
239. 滑动窗口最大值
难度困难824
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 101 <= k <= nums.length
//给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
//
// 示例:
//
// 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
//输出: [3,3,5,5,6,7]
//解释:
//
// 滑动窗口的位置 最大值
//--------------- -----
//[1 3 -1] -3 5 3 6 7 3
// 1 [3 -1 -3] 5 3 6 7 3
// 1 3 [-1 -3 5] 3 6 7 5
// 1 3 -1 [-3 5 3] 6 7 5
// 1 3 -1 -3 [5 3 6] 7 6
// 1 3 -1 -3 5 [3 6 7] 7
//
//
//
// 提示：
//
// 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
//
// 注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/
// Related Topics 队列 Sliding Window
// 👍 181 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length == 0){
return new int[]{};
}
int n = nums.length;
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[ n - k +1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k){
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
剑指 Offer 49. 丑数
难度中等111
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
347. 前 K 个高频元素
难度中等628
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
若有收获，就点个赞吧
0 人点赞
