练练leetcode上的题目，顺便学学英语。
目录
数组
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
给定一个数组，写一个函数将0元素移动到数组末尾，同时保持非0元素的位置不变。
思路:
给定一个下标变量k。然后判断当前数组位置下标的值是否为0，不为0和k位置数组值交换，然后k++。为0,不动，数组下标后移，
k记录的是第一个0元素的位置。
/**
* 移动0
* @param arr
*/
public static int[] moveZero(int[] arr)
{
if (null == arr || arr.length <= 1)
{
return null;
}
//k记得是第一个0元素的位置
int k = 0;
for (int i = 0, length = arr.length; i < length; i++)
{
//如果当前不为0，那么和第一个0元素位置交换。
//如果当前为0则保持不动，导致所有的0都会紧挨着。
if (arr[i] != 0)
{
swap(arr, i, k);
//所有的0都会紧挨着,k加1代表第一个0元素的位置挪到下一位
k++;
}
}
return arr;
}
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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
思路：
一.滑动窗口，其实就是两个下标(l 和 r)控制窗口里数量大小，其中l是左下边，r是右下标。
l和r都是只能++不让--， r控制的是进入窗口的数字，l控制的是离开窗口的数字，l <= r。
二.返回滑动窗口的最大值：
1.最简单暴力的方法，当然是直接遍历窗口里的数字进行比较。
2.用一个双端队列：
a.核心思想，维护所有可能成为最大值的数组索引的优先级队列！！!
b.队列记录数组索引，存的是数组索引，但是比较的是数组里的值，队列从头部到尾部是用索引取数组对应值从大到小排序。
c.窗口下标r增加让新进来的数从队列尾部进来。新进来的数当前索引最大，所以如果比较值还是最大，那么队列里其它元素都可以弹出，
其它索引没有机会成为最大了，只保留当前索引。如果新进来的数最小，那么直接添加到队列尾部，随着l增加有机会成为最大。
如果是一个中间值，那么把比它小的值的索引从队列弹出，加入到对应位置。
d.l增加说明有元素出窗口，如果当前l的索引刚好是队列头部索引，那么队列头部元素出队列，出窗口了。
实现如下:
public static void main(String[] args)
{
int[] arr = new int[]{1, 9, 8, 3, 5, 2};
int wl = 3;
int[] windowMaxValues = getWindowMaxValues(arr, wl);
if (null != windowMaxValues)
{
for (int i = 0, length = windowMaxValues.length; i < length; i++)
{
System.out.print(windowMaxValues[i] + " ");
}
}
}
/**
* 四个要素：
* 1.举例规律会发现最多会有length - k + 1个窗口
* 2.优先级队列的维护
* 3.i - k >= 0 窗口出值，队列更新
* 4.i - k + 1 >= 0 窗口形成，需要获取当前窗口最大值
* @param nums
* @param k
* @return
*/
public static int[] getWindowMaxValues(int[] nums, int k)
{
if (null == nums || nums.length < k || k <= 0)
{
return null;
}
LinkedList<Integer> queue = new LinkedList<>();
int length = nums.length;
//举例规律会发现最多会有length - k + 1个窗口
int[] maxValues = new int[length - k + 1];
//用i和长度k来控制窗口的左下标和右下标
for (int i = 0; i < length; i++)
{
//如果当前队列不为空，并且尾元素小于当前索引元素（用索引取对应数组值）
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i])
{
queue.pollLast();
}
//添加的是索引
queue.addLast(i);
//窗口出值，需要判断是否更新队列
if (i - k >= 0 && !queue.isEmpty())
{
//如果当前出窗口的索引，刚好和队列头索引相等，出队列
if (queue.peekFirst() == i - k)
{
queue.pollFirst();
}
}
//窗口形成，需要获取当前窗口最大值
if (i - k + 1 >= 0 && !queue.isEmpty())
{
maxValues[i - k + 1] = nums[queue.peekFirst()];
}
}
return maxValues;
}
复杂度:比较平均是O(1)级别，长度N，那么时间复杂度为O（n）。
子数组中最大值与最小值差小于等于定值（滑动窗口变种）
给定一个整型数组arr和一个整数num。某个arr中的子数组sub,
如果想达标，必须满足：
sub中最大值 - sub中最小值 <= num
返回arr中达标子数组的数量
思路：
1.用滑动窗口。
2.窗口满足，那么子数组窗口一定满足，sub中最大值 - sub中最小值 <= num。
3.窗口不满足，窗口即使继续扩展那么还是不满足条件。
时间复杂读，因为窗口左下标l和右下标r只右递增，没右回退操作，所以时间复杂度和上面一题一样O（n）。
代码：
public class SubArrSatisfyTargetValue
{
public static void main(String[] args) {
int[] arr = new int[]{0, 7, 6, 4, 8, 5};
int num = getSubNumSatisfyCondition(arr, 3);
System.out.println(num);
}
public static int getSubNumSatisfyCondition(int[] arr, int targetValue)
{
if (null == arr || arr.length <= 0)
{
return 0;
}
LinkedList<Integer> maxLinked = new LinkedList<>();
LinkedList<Integer> minLinked = new LinkedList<>();
//[l, r) 约定左闭右开, r是第一个不满足的数，那么满足的子数组个数就是r - l
int l = 0;
int r = 0;
//满足条件的个数
int num = 0;
//l是开头位置，尝试每个开头
while (l < arr.length)
{
//此时窗口开头是l,r继续尝试向右扩，直到违规
//注意当l自增后，r是在原有的基础上继续尝试向右扩
while (r < arr.length)
{
//最大队列
while (!maxLinked.isEmpty() && arr[maxLinked.peekLast()] <= arr[r])
{
maxLinked.pollLast();
}
maxLinked.addLast(r);
//最小队列
while (!minLinked.isEmpty() && arr[minLinked.peekLast()] >= arr[r])
{
minLinked.pollLast();
}
minLinked.addLast(r);
//如果不满足 最大值 - 最小值 <= targetValue, 跳出while
int value = arr[maxLinked.getFirst()] - arr[minLinked.getFirst()];
if (value > targetValue)
{
break;
}
r++;
}
//返回当前以l为首元素的满足条件的子数组个数
num += r - l;
//l自增，换开头，那么队列的首元素过期
if (maxLinked.getFirst() == l)
{
maxLinked.pollFirst();
}
if (minLinked.getFirst() == l)
{
minLinked.pollFirst();
}
//换开头
l++;
}
return num;
}
}
链表
1.合并有序链表
public static void main(String[] args) {
// 创建三个有序的 LinkedList
LinkedList<Integer> l1 = new LinkedList<>();
l1.add(1);
l1.add(4);
l1.add(5);
LinkedList<Integer> l2 = new LinkedList<>();
l2.add(1);
l2.add(3);
l2.add(4);
LinkedList<Integer> l3 = new LinkedList<>();
l3.add(2);
l3.add(6);
// 合并三个链表
LinkedList<Integer> linkedList = mergeTwoLists(mergeTwoLists(l1, l2), l3);
// 输出合并后的链表
System.out.println(linkedList);
}
/**
* 遍历方式
*/
public static LinkedList<Integer> mergeTwoLists(LinkedList<Integer> l1, LinkedList<Integer> l2) {
LinkedList<Integer> mergedList = new LinkedList<>();
// l1 和 l2 本身就是有序的，所以只需要比较头节点即可
while (!l1.isEmpty() && !l2.isEmpty()) {
// 比较两个链表的头节点，将较小的节点加入到合并后的链表中
if (l1.peekFirst() <= l2.peekFirst()) {
mergedList.add(l1.pollFirst()); // 移除并返回l1的第一个元素
} else {
mergedList.add(l2.pollFirst()); // 移除并返回l2的第一个元素
}
}
// 将剩余的节点加入到合并后的链表中
while (!l1.isEmpty()) {
mergedList.add(l1.pollFirst());
}
while (!l2.isEmpty()) {
mergedList.add(l2.pollFirst());
}
return mergedList;
}
2.反转链表
/**
* 反转链表
* @author lizhibiao
* @date 2024/9/25 16:06
*/
public class ReverseLinkedList {
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
// 迭代反转链表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next; // 暂存下一个节点
current.next = prev; // 当前节点指向前一个节点
prev = current; // 移动 prev 到当前节点
current = next; // 移动 current 到下一个节点
}
return prev; // prev 成为了新的头结点
}
public static void main(String[] args) {
// 示例链表: 1 -> 2 -> 3 -> 4 -> 5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ReverseLinkedList solution = new ReverseLinkedList();
ListNode reversedHead = solution.reverseList(head);
// 输出反转后的链表
while (reversedHead != null) {
System.out.print(reversedHead.val + " ");
reversedHead = reversedHead.next;
}
}
}