Leetcode经典中等题集
2022-09-03 本文已影响0人
奔跑吧李博
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 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
题解：
class Solution {
/**
* 思路：
* 从nums数组中取出前k个数，存入队列中
* 获取队列的最大值存储到集合中
* 然后队列移除头部，在尾部添加第k+1个数，获取队列中最大值存储到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果数组为空，则返回空数组
return new int[0];
}
int[] result = new int[nums.length-k+1]; //总共需要输出的数组
Queue<Integer> queue = new LinkedList<>();
//首次添加前k个数到队列中作为初始队列
for (int j=0;j<k;j++) {
queue.add(nums[j]);
}
//遍历队列获取最大值
int maxNum = queue.peek();
for (Integer num : queue) {
if (num > maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i<nums.length-k;i++) {
queue.poll(); //移除队列头部
queue.add(nums[i+k]); //添加数组下一个值到队列尾部
//遍历队列获取最大值
int max = queue.peek();
for (Integer num : queue) {
if (num > max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
题解：
class Solution {
/**
* 思路:
* @param height
* @return
*/
public int trap(int[] height) {
if (height == null || height.length == 1) {
return 0;
}
int water = 0; //累计能接的雨水
int leftMax = height[0];
int rightMax = height[height.length-1];
int p1 = 1, p2 = height.length-2; //第一个和最后一个柱子接雨水无效
while(p1<=p2) {
if (leftMax <= rightMax) {
water += Math.max(0, leftMax-height[p1]); //判断左边最大值和当前值的差，如果当前值大于左边最大值
//那么当前柱子无法存水
leftMax = Math.max(leftMax, height[p1]);
p1++;
} else {
water += Math.max(0, rightMax-height[p2]); //判断左边最大值和当前值的差，如果当前值大于左边最大值
//那么当前柱子无法存水
rightMax = Math.max(rightMax, height[p2]);
p2--;
}
}
return water;
}
}
7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
题解：
class Solution {
public int reverse(int x) {
//思路：如果是负数，先变正数，循环取该数的最低位倒序，最后负数加上负号
int restNum = x < 0 ? -x : x;
int newNum = 0;
while (restNum > 0) {
if (newNum > Integer.MAX_VALUE / 10 || (newNum == Integer.MAX_VALUE / 10 && restNum%10 > 7))
return 0;
if (newNum < Integer.MIN_VALUE / 10 || (newNum == Integer.MIN_VALUE / 10 && restNum%10 < -8))
return 0;
newNum = newNum * 10 + restNum % 10;
restNum = restNum / 10;
}
//倒序完成
return x < 0 ? -newNum : newNum;
}
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
题解：
class Solution {
/**
* 要解前n间房能偷的最大金额，那就尝试先从前1、2、3间能偷的最大金额找规律
Sn表示前n间房能偷的最大金额 Hn表示第n间房的金额
示例： [1,2,3,1]
前1间房能偷的最大金额 S1 = H1 = 1
前2间房能偷的最大金额 S2 = max(S1,H1) = 2
从第三间房开始，就有2种偷法了，就是偷第n间房和不偷第n间房
偷第n间房，那就不能偷n-1间房，能偷n-2间房 那么最大金额不一样的取决于最近这三间房怎么偷，因为前Sn-2都一样
前3间房能偷的最大金额 S3 = max(S2, H3+S1) = 4
前n间房能偷的最大金额 Sn = max(Sn-1, Hn+Sn-2)
*/
public int rob(int[] nums) {
int length = nums.length;
if(length <= 1) {
return nums[0];
}
int[] dp = new int[length]; //dp[i]表示前i间房能偷的最大金额
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2;i<length;i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[length-1]; //这里需要得到前n间房的最大值，所以是返回dp[length-1]
}
}
122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例：
输入：prices = [7,1,5,3,6,4]
输出：7
题解:
class Solution {
public int maxProfit(int[] prices) {
//思路：该题将数值画成折线图，就知道股票涨跌的区间，那么我们就需要在上涨的最低值买入，在上涨的最高处卖出，就可以了
//遍历数组，得到上涨区间，获取最小值，上涨区间结束获取最大值，累加这个区间差价
int profit = 0;
int min = 0, max = 0;
int pos = 0;
while(pos < prices.length-1) {
//循环条件是倒数第二个结束，内层循环必须加上外层循环的限制，否则pos移动位置可以超出数组长度
while(pos < prices.length-1 && prices[pos] >= prices[pos+1]) {
//在下跌的底部获取最小值
pos++;
}
//下一个比当前值大，下跌区间结束，得到上涨区间最小值
min = prices[pos];
while(pos < prices.length-1 && prices[pos] <= prices[pos+1]) {
//在上涨的顶部获取最大值
pos++;
}
//下一个数比上一个小了，说明上涨区间到头了，得到上涨区间最大值
max = prices[pos];
profit += max - min;
}
return profit;
}
}
316. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
题解：
class Solution {
/**
* 解题思路：
* 1.第一个条件：去重字母
* 2.第二个条件：保证字典序从小到大
* 3.第三个条件：保证字母存在至少一个
* @param s
* @return
*/
public String removeDuplicateLetters(String s) {
//第三个条件：保证字母存在至少一个
//做法：给每一种字母维护一个计数器，先遍历获取其数量，如果数量为1，则在第二个条件中不要弹出栈，否则可以弹出栈
int[] charCount = new int[256];
for (int i=0;i<s.length();i++) {
charCount[s.charAt(i)]++;
}
Stack<Character> stk = new Stack<>();
boolean[] inStack = new boolean[256]; //用于存储这个字符是否已经记录过
// 第一个条件：去重字母
for(char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
charCount[c]--;
if (inStack[c]) {
continue;
}
//第二个条件：保证字典序从小到大，在插入字母之前，判断与前一个字母的字典序，
// 如果比前一个小，则循环将字符弹出栈顶，清除在栈中的记录
while(!stk.empty() && stk.peek() > c) {
if (charCount[stk.peek()] == 0) {
break;
}
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
}
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例一：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
题解：
class Solution {
/**
* 思路：滑动窗口解法
* 设定：需要找到3个数，a+b+c=0, 这里 a b c三个数的下标从左到右
* 定义a的下标为i，b的下标为left，c的下标为right
* 首先，对数组进行排序
* 则需要找nums[i]+nums[left]+nums[right] = 0，找到则放入集合中
* 如果nums[i]+nums[left]+nums[right] > 0，则需right--
* 如果nums[i]+nums[left]+nums[right] < 0，则需left++
* 其次，a b c三个数都要去重
* @param nums
* @return
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums); //排序
int left = 0, right = 0;
for (int i=0;i<nums.length;i++) {
if (nums[i] > 0) {
//当前最小数大于0，则找不到符合条件的组
return list;
}
if (i>0 && nums[i] == nums[i-1]) {
//对i去重: 如果当前组的a和上一组的a相等，则视为重复组
continue;
}
left = i+1;
right = nums.length-1;
while(left<right) {
int temp = nums[i] + nums[left] + nums[right];
if (temp > 0) {
right--;
} else if (temp < 0) {
left++;
} else {
//找到符合条件组
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
//将b c相同元素跳过，即去重
while(left < right && nums[left+1] == nums[left]) {
//将b去重
left++;
}
while(left < right && nums[right-1] == nums[right]) {
//将c去重
right--;
}
left++;
right--;
}
}
}
return list;
}
}
16.环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
解题思路：
题解：
public ListNode detectCycle(ListNode head) {
//题解：这个题的目标，是找到环的入环点，
// 根据上图，首先根据公式推导出 a = (n-1)(b+c) + c，通过这个公式，
// 再用两个指针相同速度走，相遇点就是要返回的入环节点
//那么第一步：定义一个快指针和慢指针，快指针每步走2个，慢指针每步走一个，在有环的情况下快指针一定会追上慢指针相遇
//得到相交点，构成这幅图的形式
ListNode slow = head, fast = head;
while(fast != null) {
//让慢指针每次走1步，快指针每次走2步
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (slow == fast) {
//再构造两个慢指针走到入环节点
ListNode cur = head;
while(cur != slow) {
cur = cur.next;
slow = slow.next;
}
return cur;
}
}
return null;
}
17.反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
解题思路：
/**
* 根据上图思路：
* 1.需要快进到反转区间左位置
* 2.使用变量记住区间前一个位置和第一个位置节点
* 3.使用经典四步反转left到right区间的节点
* 4.将反转后的链表与原链表进行拼接
*/
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode pre = null, cur = head;
//cur在pre的前一个位置
for (int i=0;i<left-1;i++) {
pre = cur;
cur = cur.next;
}
//使用变量记住区间前一个位置和第一个位置节点
ListNode pre2 = pre;
ListNode cur2 = cur;
for (int i=left;i<=right;i++) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
//将反转后的链表与原链表进行拼接
//有一种情况，从第一个位置就开始反转，那么pre开始为null,pre2也是为null的，需要判空一下，头就指向pre，即反转区间的头节点
if (pre2 != null) {
pre2.next = pre;
} else {
head = pre;
}
cur2.next = cur;
return head;
}
