算法test012_牛客博客

1、给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

参考代码一：

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode tail = head;
    for (int i = 0; i < k; i++) {
        //剩余数量小于k的话，则不需要反转。
        if (tail == null) {
            return head;
        }
        tail = tail.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(head, tail);
    //下一轮的开始的地方就是tail
    head.next = reverseKGroup(tail, k);

    return newHead;
}

/*
左闭又开区间
 */
private ListNode reverse(ListNode head, ListNode tail) {
    ListNode pre = null;
    ListNode next = null;
    while (head != tail) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;

}

参考代码二：

解题思路：
K个一组翻转链表，具体到每一段，其实就是一个简单的翻转链表的问题
所以我们只需要将每一个段翻转的头结点返回，拼接到前一段的翻转后的尾结点即可

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null) return null;
ListNode cur = head;
int i = k;
// 先遍历找到下一段的开头
while(i>0&&cur!=null){
cur = cur.next;
i--;
}
// 如果没有到k个，那么原顺序返回
if(i>0) return head;
// 关键在于这个位置，返回值拼接到当前段翻转后的尾结点即可
// 而尾结点就是原链表在当前段的头
ListNode pre = reverseKGroup(cur,k);
cur = head;
i = k;
while(i>0){
ListNode tmp = cur.next;
cur.next= pre;
pre = cur;
cur = tmp;
i--;
}
return pre;

}

2、给定一个单词列表和两个单词 word1 和 word2，返回列表中这两个单词之间的最短距离。

示例:
假设 words = ["practice", "makes", "perfect", "coding", "makes"]

输入: word1 = “coding”, word2 = “practice”
输出: 3
输入: word1 = "makes", word2 = "coding"
输出: 1
注意:
你可以假设 word1 不等于 word2, 并且 word1 和 word2 都在列表里。

方法 1：暴力算法

一个比较简单的方法是遍历整个数组直到找到第一个单词。每次我们找到跟第一个单词一样的词时，我们就遍历整个数组去找跟第二个单词一样的词，并求解最近距离。

public int shortestDistance(String[] words, String word1, String word2) {
int minDistance = words.length;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
for (int j = 0; j < words.length; j++) {
if (words[j].equals(word2)) {
minDistance = Math.min(minDistance, Math.abs(i - j));
}
}
}
}
return minDistance;
}
时间复杂度：O(n^2)
) ，这是因为每次找到一个 word1 ，我们都需要遍历一遍整个数组去找 word2 出现的位置。

空间复杂度：O(1)。没有使用额外的空间。

方法 2：遍历一次

我们可以记录两个下标 i1 和 i2 来显著提高暴力的时间复杂度，我们保存 word1 和 word2 的最近出现位置。每次我们发现一个新的单词出现位置，我们不需要遍历整个数组去找到另一个单词，因为我们已经记录了最近出现位置的下标。

public int shortestDistance(String[] words, String word1, String word2) {
int i1 = -1, i2 = -1;
int minDistance = words.length;
int currentDistance;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
i1 = i;
} else if (words[i].equals(word2)) {
i2 = i;
}

    if (i1 != -1 && i2 != -1) {
        minDistance = Math.min(minDistance, Math.abs(i1 - i2));
    }
}
return minDistance;

}
复杂度分析

时间复杂度：O(n)。这个问题的解法是线性的，我们无法比 O(n)O(n) 更快是因为我们至少要遍历每个元素一次。
空间复杂度：O(1) 。没有使用额外空间。

转载链接：https://leetcode-cn.com/problems/shortest-word-distance/solution/zui-duan-dan-ci-ju-chi-by-leetcode/

算法test012