注册

寒冬，拒绝薪资倒挂

写在前面


今天翻看小 🍠 的时候，无意发现两组有趣数据：


一个是，互联网大厂月薪分布：


月薪分布


另一个是，国内互联网大厂历年校招薪资与福利汇总：


研发


算法


中概互联网的在金融市场的拐点。


是在 2021 年，老美出台《外国公司问责法案》开始的。


那时候，所有在美上市的中概股面临摘牌退市，滴滴上市也被叫停。



拐点从资本市场反映到劳动招聘市场，是有滞后性的，如果没有 ChatGPT 的崛起，可能寒冬还会来得更凛冽些 ...


时代洪流的走向，我们无法左右，能够把握的，只有做好自己。


如何在寒冬来之不易的机会中，谈好待遇，拒绝薪资倒挂 🙅🏻‍♀️🙅


一方面：减少信息差，在谈判的中后期，多到职场类社区论坛（牛客/小红书/脉脉/offershow）中，了解情况。


另一方面：增加自身竞争力，所有技巧在绝对实力面前，都不堪一击，如果能在笔面阶段，和其他候选人拉开足够差距，或许在后续博弈中，需要知道的套路就会越少。


增强自身竞争力，尤其是走校招路线的小伙伴，建议从「算法」方面进行入手。


下面给大家分享一道常年在「字节跳动」题库中霸榜的经典题。


题目描述


平台：LeetCode


题号：25


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


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


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


示例 1：


输入：head = [1,2,3,4,5], k = 2


输出：[2,1,4,3,5]

示例 2：
img


输入：head = [1,2,3,4,5], k = 3


输出：[3,2,1,4,5]

提示：



  • 列表中节点的数量在范围 sz 内
  • 1<=sz<=50001 <= sz <= 50001<=sz<=5000
  • 0<=Node.val<=10000 <= Node.val <= 10000<=Node.val<=1000
  • 1<=k<=sz1 <= k <= sz1<=k<=sz

进阶：



  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

迭代（哨兵技巧）


哨兵技巧我们在前面的多道链表题讲过，让三叶来帮你回忆一下：


做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。


链表和树的题目天然适合使用递归来做。


但这次我们先将简单的「递归版本」放一放，先搞清楚迭代版本该如何实现。


我们可以设计一个翻转函数 reverse ：


传入节点 root 作为参数，函数的作用是将以 root 为起点的 kkk 个节点进行翻转。


当以 root 为起点的长度为 kkk 的一段翻转完成后，再将下一个起始节点传入，直到整条链表都被处理完成。


当然，在 reverse 函数真正执行翻转前，需要先确保节点 root 后面至少有 kkk 个节点。


我们可以结合图解再来体会一下这个过程：


假设当前样例为 1->2->3->4->5->6->7 和 k = 3 ：
640.png


然后我们调用 reverse(cur, k)，在 reverse() 方法内部，几个指针的指向如图所示，会通过先判断 cur 是否为空，从而确定是否有足够的节点进行翻转：


然后先通过 while 循环，将中间的数量为 k - 1 的 next 指针进行翻转：


最后再处理一下局部的头结点和尾结点，这样一次 reverse(cur, k) 执行就结束了：


回到主方法，将 cur 往前移动 k 步，再调用 reverse(cur, k) 实现 k 个一组翻转：


Java 代码：


class Solution {
public ListNode reverseKGr0up(ListNode head, int k) {
ListNode dummy = new ListNode(-1);

        dummy.next = head;
ListNode cur = dummy;
while (cur != null) {

            reverse(cur, k);
int u = k;    
while (u-- > 0 && cur != null) cur = cur.next;

        }
return dummy.next;

    }
// reverse 的作用是将 root 后面的 k 个节点进行翻转
void reverse(ListNode root, int k) {
// 检查 root 后面是否有 k 个节点
int u = k;
ListNode cur = root;
while (u-- > 0 && cur != null) cur = cur.next;
if (cur == null) return;
// 进行翻转
ListNode tail = cur.next;
ListNode a = root.next, b = a.next;
// 当需要翻转 k 个节点时，中间有 k - 1 个 next 指针需要翻转
while (k-- > 1) {
ListNode c = b.next;

            b.next = a;

            a = b;

            b = c;

        }

        root.next.next = tail;

        root.next = a;

    }

}

C++ 代码：


class Solution {
public:
ListNode* reverseKGr0up(ListNode* head, int k) {

        ListNode* dummy = new ListNode(-1);

        dummy->next = head;

        ListNode* cur = dummy;
while (cur != NULL) {
reverse(cur, k);
int u = k;
while (u-- > 0 && cur != NULL) cur = cur->next;

        }
return dummy->next;

    }
// reverse 的作用是将 root 后面的 k 个节点进行翻转
void reverse(ListNode* root, int k) {
// 检查 root 后面是否有 k 个节点
int u = k;

        ListNode* cur = root;
while (u-- > 0 && cur != NULL) cur = cur->next;
if (cur == NULL) return;
// 进行翻转

        ListNode* tail = cur->next;

        ListNode* a = root->next, *b = a->next;
// 当需要翻转 k 个节点时，中间有 k - 1 个 next 指针需要翻转
while (k-- > 1) {

            ListNode* c = b->next;

            b->next = a;

            a = b;

            b = c;

        }

        root->next->next = tail;

        root->next = a;

    }

};

Python 代码：


class Solution:
def reverseKGr0up(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# reverse 的作用是将 root 后面的 k 个节点进行翻转
def reverse(root, k):
# 检查 root 后面是否有 k 个节点

            u, cur = k, root
while u > 0 and cur:

                cur = cur.next

                u -= 1
if not cur: return
# 进行翻转

            tail = cur.next

            a, b = root.next, root.next.next
# 当需要翻转 k 个节点时，中间有 k - 1 个 next 指针需要翻转
while k > 1:

                c, b.next = b.next, a

                a, b = b, c

                k -= 1

            root.next.next = tail

            root.next = a


        dummy = ListNode(-1)

        dummy.next = head

        cur = dummy
while cur:

            reverse(cur, k)

            u = k
while u > 0 and cur:

                cur = cur.next

                u -= 1
return dummy.next

TypeScript 代码：


function reverseKGr0up(head: ListNode | null, k: number): ListNode | null {
// reverse 的作用是将 root 后面的 k 个节点进行翻转
const reverse = function(root: ListNode | null, k: number): void {
// 检查 root 后面是否有 k 个节点
let u = k, cur = root;
while (u-- > 0 && cur != null) cur = cur.next;
if (cur == null) return;
// 进行翻转
let tail = cur.next, a = root.next, b = a.next;
// 当需要翻转 k 个节点时，中间有 k - 1 个 next 指针需要翻转
while (k-- > 1) {
let c = b.next;

            b.next = a;

            a = b;

            b = c;

        }

        root.next.next = tail;

        root.next = a;

    };
let dummy = new ListNode(-1);

    dummy.next = head;
let cur = dummy;
while (cur != null) {
reverse(cur, k);
let u = k;
while (u-- > 0 && cur != null) cur = cur.next;

    }
return dummy.next;

};


  • 时间复杂度：会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
  • 空间复杂度：O(1)O(1)O(1)

递归


搞懂了较难的「迭代哨兵」版本之后，常规的「递归无哨兵」版本写起来应该更加容易了。


需要注意的是，当我们不使用「哨兵」时，检查是否足够 kkk 位，只需要检查是否有 k−1k - 1k−1 个 nextnextnext 指针即可。


代码：


class Solution {
public ListNode reverseKGr0up(ListNode head, int k) {
int u = k;
ListNode p = head;
while (p != null && u-- > 1) p = p.next;
if (p == null) return head;
ListNode tail = head;
ListNode prev = head, cur = prev.next;

        u = k;
while (u-- > 1) {
ListNode tmp = cur.next;

            cur.next = prev;

            prev = cur;

            cur = tmp;

        }

        tail.next = reverseKGr0up(cur, k);
return prev;

    }

}

C++ 代码：


class Solution {
public:
ListNode* reverseKGr0up(ListNode* head, int k) {
int u = k;

        ListNode* p = head;
while (p != NULL && u-- > 1) p = p->next;
if (p == NULL) return head;

        ListNode* tail = head;

        ListNode* prev = head, *cur = prev->next;

        u = k;
while (u-- > 1) {

            ListNode* tmp = cur->next;

            cur->next = prev;

            prev = cur;

            cur = tmp;

        }

        tail->next = reverseKGr0up(cur, k);
return prev;

    }

};

Python 代码：


class Solution:
def reverseKGr0up(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        u = k

        p = head
while p and u > 1:

            p = p.next

            u -= 1
if not p: return head


        tail = prev = head

        cur = prev.next

        u = k
while u > 1:

            tmp = cur.next

            cur.next = prev

            prev, cur = cur, tmp

            u -= 1

        tail.next = self.reverseKGr0up(cur, k)
return prev

TypeScript 代码：


function reverseKGr0up(head: ListNode | null, k: number): ListNode | null {
let u = k;
let p = head;
while (p != null && u-- > 1) p = p.next;
if (p == null) return head;
let tail = head, prev = head, cur = prev.next;

    u = k;
while (u-- > 1) {
let tmp = cur.next;

        cur.next = prev;

        prev = cur;

        cur = tmp;

    }

    tail.next = reverseKGr0up(cur, k);
return prev;

};


  • 时间复杂度：会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
  • 空间复杂度：只有忽略递归带来的空间开销才是 O(1)O(1)O(1)

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉


作者：宫水三叶的刷题日记
来源：juejin.cn/post/7314263159116628009
0
分享
2023-12-21

0 个评论

要回复文章请先登录或注册

一个开放、互助、协作、创意的社区

关于imGeek
关于专职工程师值守
社区财富榜
赞助商
友情链接
热门标签
京ICP备2023000793号