【答疑】算法训练营答疑 issue

[GeekUniversity]

学习过程中，你遇到哪些问题，都可以在此条 issue 下提问，我们的助教或者其他学员看到你的问题后会帮你解答。

提问之前，建议先了解下 如何进行有效的提问？

[HongChao6]

做 “83. 删除排序链表中的重复元素” 时，
考虑 如何删除 非排序 链表重复的元素，使得每个元素只出现一次。
不知 老师有什么好的解决方法？

[HongChao6]

"441. 排列硬币"
描述：
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。

这个其实是 数学公式的 等差数列求和，那将数学公式 转换成 代码，有什么较好的思维方式么？

[tidelgl]

21. 合并两个有序链表
    问题：
    为什么不能同时将两个链表的 next 加入到结果链表里呢？

/**
 * 21. 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const dummyHead = new ListNode();
    let curr = dummyHead;
    let currL1 = l1;
    let currL2 = l2;
    
    while(currL1 != null && currL2 != null) {
        // 比较两个结点的大小，小的先加入新链表
        if (currL1.val <= currL2.val) {
            curr.next = currL1;
            curr.next.next = currL2;
        } else {
            curr.next = currL2;
            curr.next.next = currL1;
        }
        currL1 = currL1.next;
        currL2 = currL2.next;
        curr = curr.next.next;
    }
    
    // 如果 l1 还没遍历完直接加入新链表
    if (currL1 != null) {
        curr.next = currL1;
    }
    // 如果 l2 还没遍历完直接加入新链表
    if (currL2 != null) {
        curr.next = currL2;
    }
    
    return dummyHead.next;
};

[HongChao6]

1. 合并两个有序链表
   问题：
   为什么不能同时将两个链表的 next 加入到结果链表里呢？

/**
 * 21. 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const dummyHead = new ListNode();
    let curr = dummyHead;
    let currL1 = l1;
    let currL2 = l2;
    
    while(currL1 != null && currL2 != null) {
        // 比较两个结点的大小，小的先加入新链表
        if (currL1.val <= currL2.val) {
            curr.next = currL1;
            curr.next.next = currL2;
        } else {
            curr.next = currL2;
            curr.next.next = currL1;
        }
        currL1 = currL1.next;
        currL2 = currL2.next;
        curr = curr.next.next;
    }
    
    // 如果 l1 还没遍历完直接加入新链表
    if (currL1 != null) {
        curr.next = currL1;
    }
    // 如果 l2 还没遍历完直接加入新链表
    if (currL2 != null) {
        curr.next = currL2;
    }
    
    return dummyHead.next;
};

有这样两个链表
A: 1-->2-->3-->4
B: 5-->6-->7-->8
怎么 可以 同时将两个链表的 next 加入到结果链表里呢？

[sumnous]

做 “83. 删除排序链表中的重复元素” 时，
考虑 如何删除 非排序 链表重复的元素，使得每个元素只出现一次。
不知 老师有什么好的解决方法？

第一种方法是，先链表排序，再删除排序链表中的重复元素
第二种方法是，新建一个链表（或其他数据结构）用于存放原链表中的非重复元素

您可以思考下这两种方法的时间复杂度，另外还有木有更好的方案

[sumnous]

"441. 排列硬币"
描述：
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。

这个其实是 数学公式的 等差数列求和，那将数学公式 转换成 代码，有什么较好的思维方式么？

利用了等差数列的性质，可建立等式, n = (1 + x) * x / 2，用一元二次方程的求根公式可以得到行数的的求解公式, 也就是x的求解公式，x = (-1 + sqrt(8 * n + 1)) / 2，然后取整后就是能填满的行数，代码一行就可以实现

[JackZhangDF]

快速排序分区函数如下：

- (NSInteger)partition:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
    NSInteger key = left;
    NSInteger i = left;
    NSInteger j = right;
    while (i != j) {
        while (i<j && [array[key] integerValue] <= [array[j] integerValue]) {
            j--;
        }
        while (i<j && [array[key] integerValue] >= [array[i] integerValue]) {
            i++;
        }
        if (i<j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    
    //最终将基准数归位, 因为i == j, 需要将<基数所在位置的value>与<i/j相等的位置的value>互换位置
    [array exchangeObjectAtIndex:i withObjectAtIndex:left];
    return i;
}

内层while 顺序变了，为什么会出错？或者如何自然而然写出分区函数？

[sumnous]

快速排序分区函数如下：

- (NSInteger)partition:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
    NSInteger key = left;
    NSInteger i = left;
    NSInteger j = right;
    while (i != j) {
        while (i<j && [array[key] integerValue] <= [array[j] integerValue]) {
            j--;
        }
        while (i<j && [array[key] integerValue] >= [array[i] integerValue]) {
            i++;
        }
        if (i<j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    
    //最终将基准数归位, 因为i == j, 需要将<基数所在位置的value>与<i/j相等的位置的value>互换位置
    [array exchangeObjectAtIndex:i withObjectAtIndex:left];
    return i;
}

内层while 顺序变了，为什么会出错？或者如何自然而然写出分区函数？

while 套while 的方式，逻辑上容易写错的。建议这个题目可以考虑下用递归查找

[mikejicken]

求助帖
反转链表 代码
ListNode* reverseList_iteratively(ListNode* head) {
ListNode *h=NULL, *p=NULL;
while (head){
p = head->next;
head->next = h;
h = head;
head = p;
}
return h;

Q： p = head->next;
head->next = h;
h = head;
head = p;
这段代码看不太明白，能给讲讲吗

[sumnous]

求助帖
反转链表 代码
ListNode* reverseList_iteratively(ListNode* head) {
ListNode *h=NULL, *p=NULL;
while (head){
p = head->next;
head->next = h;
h = head;
head = p;
}
return h;

Q： p = head->next;
head->next = h;
h = head;
head = p;
这段代码看不太明白，能给讲讲吗

给你简单画了个图，说明了下， 关键点在于 listnode 本身值是一个指针，他的next 是另一个指针。 head = p 可以看做一个指针 指向另一个 p 的指针