文章目录
- 17.电话号码的字母组合
- 77.组合
- 46.全排列
- 74.搜索二维矩阵
- 215.数组中的第K个最大元素
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]\
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a","b","c"]
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits.length() == 0){
return result;
}
HashMap<Character,String> phoneMap = new HashMap<>(){{
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
}};
backtracking(result,phoneMap,digits,0,new StringBuffer());
return result;
}
public void backtracking(List<String> result,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination){
if(index == digits.length()){
result.add(combination.toString());
}else{
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int count = letters.length();
for(int i=0;i<count;i++){
combination.append(letters.charAt(i));
backtracking(result,phoneMap,digits,index+1,combination);
combination.deleteCharAt(index);
}
}
}
}
delete方法与deleteCharAt两个方法都是用来删除StringBuffer字符串指定索引字符的方法
77.组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
输入：n = 1, k = 1
输出：[[1]]
class Solution {
List<List<Integer>> result = new ArrayList<>(); // 存储结果的列表
LinkedList<Integer> path = new LinkedList<>(); // 存储当前路径的链表
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
// 回溯算法
public void backtracking(int n, int k, int startIndex) {
// 如果当前路径长度等于k，将路径添加到结果列表中
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// 从startIndex开始遍历，直到n + 1 - (k - path.size())
for (int i = startIndex; i <= n + 1 - (k - path.size()); i++) {
path.add(i); // 将当前数字添加到路径中
backtracking(n, k, i + 1); // 递归处理下一个数字
path.removeLast(); // 回溯，移除当前数字
}
}
}
LinkedList的removeLast()方法是指删除链表的最后一个元素
46.全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入：nums = [0,1]
输出：[[0,1],[1,0]]
输入：nums = [1]
输出：[[1]]
class Solution {
List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length]; // 记录每个元素是否已经使用过
List<Integer> track = new ArrayList<>(); // 存储当前排列的元素
backtracking(track, nums, used); // 回溯算法求解全排列
return res; // 返回结果列表
}
// 回溯算法求解全排列
public void backtracking(List<Integer> track, int[] nums, boolean[] used) {
if (track.size() == nums.length) {
res.add(new ArrayList(track)); // 将当前排列添加到结果列表中
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue; // 如果当前元素已经使用过，跳过
}
used[i] = true; // 标记当前元素为已使用
track.add(nums[i]); // 将当前元素添加到当前排列中
backtracking(track, nums, used); // 继续递归求解
used[i] = false; // 回溯，将当前元素标记为未使用
track.removeLast(); // 回溯，移除当前排列中的最后一个元素
}
}
}
74.搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果target在矩阵中，返回true；否则，返回 false 。
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // 矩阵的行数
int n = matrix[0].length; // 矩阵的列数
int low = 0; // 二分查找的起始位置
int high = m * n - 1; // 二分查找的结束位置
while (low <= high) { // 当起始位置小于等于结束位置时，继续查找
int mid = low + (high - low) / 2; // 计算中间位置
int x = matrix[mid / n][mid % n]; // 获取中间位置的元素值
if (x < target) { // 如果中间位置的元素值小于目标值，说明目标值在右侧，更新起始位置
low = mid + 1;
} else if (x > target) { // 如果中间位置的元素值大于目标值，说明目标值在左侧，更新结束位置
high = mid - 1;
} else { // 如果中间位置的元素值等于目标值，说明找到了目标值，返回true
return true;
}
}
return false; // 如果没有找到目标值，返回false
}
}
215.数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入: [3,2,1,5,6,4], k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
class Solution {
public int findKthLargest(int[] nums, int k) {
int count = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i=0;i<nums.length;i++){
// 如果队列中的元素个数小于k，直接将元素加入队列
if(queue.size() < k){
queue.offer(nums[i]);
}else if(nums[i] > queue.peek()){ // 如果当前元素大于队列中的最小元素（堆顶元素）
queue.poll(); // 移除堆顶元素
queue.offer(nums[i]); // 将当前元素加入队列
}
}
return queue.peek(); // 返回队列中的最小元素（堆顶元素），即第k大的元素
}
}
最大堆与最小堆
最大（小）堆是指在树中，存在一个结点而且该结点有儿子结点，该结点的data域值都不小于（大于）其儿子结点的data域值，并且它是一个完全二叉树（不是满二叉树）。
