Daily_Algorithm
本文最后更新于：2 年前
每日刷题
leetcode每日刷题，先定个小目标300
高级算法分析与设计课程作业
作业一
两数之和（力扣第1题）
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
- 思路一：暴力，二重循环搜索答案，肯定超时
- 思路二：使用hash表，将遍历过的数据放入hash表中，<key , value> 为<nums[i], i>结构
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return null;
}最大子序和（力扣53题）
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
来源：力扣（LeetCode）
思路：动态规划
创建dp数组，dp[i]表示遍历到i时，第 i个数结尾的 连续子数组的最大和
动态转移方程
dp[i] = max(dp[i - 1] + nums[i], nums[i]);初始化dp
dp[0] = nums[0]遍历顺序为从前向后
public int maxSubArray(int[] nums) {
// int sum = nums[0];
// int[] dp = new int[nums.length];
// dp[0] = nums[0];
// for (int i = 1; i < nums.length; i++) {
// dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
// if(dp[i] > sum){
// sum = dp[i];
// }
// }
// return sum;
// 可以不使用dp数组，节省空间
int sum = nums[0];
int result = sum;
for (int i = 1; i < nums.length; i++) {
sum = Math.max(sum + nums[i], nums[i]);
if(sum > result){
result = sum;
}
}
return result;
}多数元素（力扣169题）
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
来源：力扣（LeetCode）
- 思路一：使用hash表，遍历数组并计数即可
- 思路二：排序，题中说了总是存在多数元素，那么排序后的弟⌊ n/2 ⌋即为所求答案
- 思路三：从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个
// 思路一
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
}
Set<Map.Entry<Integer, Integer>> entries = count.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
if(entry.getValue() > nums.length / 2){
return entry.getKey();
}
}
return -1;
}
// 思路二
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
// 思路三
public int majorityElement(int[] nums) {
int res = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if(nums[i] == res){
count ++;
}else {
count --;
if(count == 0){
res = nums[i + 1];
}
}
}
return res;
}二分查找（力扣704题）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
来源：力扣（LeetCode）
无需多言
public int search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0;
int right = nums.length - 1;
int mid = left + (right - left) / 2;
while (left <= right){
if(target > nums[mid]){
left = mid + 1;
}else if(target < nums[mid]){
right = mid -1;
}else {
return mid;
}
mid = left + (right - left) / 2;
}
return -1;
}数组中第k个最大元素（力扣215题）
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
思路一：优先队列，维护一个容量为k的优先队列（最小堆），其队首元素为最小值，当遍历完整个数组后，队首元素即为第k大的数
思路二：基于快速排序的快速选择算法
// 优先队列
public int findKthLargest(int[] nums, int k) {
// 第 1 大的数，下标是 len - 1;
// 第 2 大的数，下标是 len - 2;
// ...
// 第 k 大的数，下标是 len - k;
// 创建优先队列
// 创建一个容量为k的小根堆，那么遍历整个数组的过程中维护这个小根堆，那么其根元素就是数组中第k大的数
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, Comparator.comparingInt(a -> a));
for (int i = 0; i < k; i++) {
priorityQueue.offer(nums[i]);
}
for (int i = k; i < nums.length; i++) {
Integer peek = priori
tyQueue.peek();
if(nums[i] > peek){
priorityQueue.poll();
priorityQueue.offer(nums[i]);
}
}
return priorityQueue.peek();
}
// 快速选择
public int findKthLargest(int[] nums, int k) {
// 第 1 大的数，下标是 len - 1;
// 第 2 大的数，下标是 len - 2;
// ...
// 第 k 大的数，下标是 len - k;
int len = nums.length;
int target = len - k;
int left = 0;
int right = len - 1;
while (true) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
// pivotIndex > target
right = pivotIndex - 1;
}
}
}
private int partition(int[] nums, int left, int right) {
int randomIndex = left + random.nextInt(right - left + 1);
swap(nums, left, randomIndex);
// all in nums[left + 1..le) <= pivot;
// all in nums(ge..right] >= pivot;
int pivot = nums[left];
int le = left + 1;
int ge = right;
while (true) {
while (le <= ge && nums[le] < pivot) {
le++;
}
while (le <= ge && nums[ge] > pivot) {
ge--;
}
if (le >= ge) {
break;
}
swap(nums, le, ge);
le++;
ge--;
}
swap(nums, left, ge);
return ge;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}搜索二维矩阵（力扣240题）
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
来源：力扣（LeetCode）
思路一：题中说的很清楚是有序的矩阵，可以模仿二分搜索解决该题
思路二：
// 思路一
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] nums : matrix) {
if(search(nums, target)){
return true;
}
}
return false;
}
public boolean search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return false;
}
int left = 0;
int right = nums.length - 1;
int mid = left + (right - left) / 2;
while (left <= right){
if(target > nums[mid]){
left = mid + 1;
}else if(target < nums[mid]){
right = mid -1;
}else {
return true;
}
mid = left + (right - left) / 2;
}
return false;
}
// 思路二
public boolean searchMatrix(int[][] matrix, int target) {
// 从矩阵的右上角搜索 (0, matrix[0].length)
int m = matrix[0].length;
int n = matrix.length;
int x = 0;
int y = m - 1;
while (x < n && y >= 0){
if(target == matrix[x][y]){
return true;
} else if (target < matrix[x][y]) {
y --;
}else {
x ++;
}
}
return false;
}本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
