//*****************************************************************************************************************************************************// // 21:两个升序链表合并成一个升序链表
//力扣 21 题：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ****
// 核心：“伪头结点”dum,cur从dum 开始：找目标，指向目标，目标转移，自己转移到敌人为止 （顺序不能乱！！）
//做法：搞一个伪头结点 dum，从这儿开始，谁小，cur 就指向谁。那个人挪下一个为止。 //方法一：搞一个伪头结点 dum，从这儿开始，谁小，cur 就指向谁。那个人挪下一个为止。
// cur 指向dum 开始 ,cur 移动！
//结果 ： dum->1->2->····
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dum = new ListNode(0); //dum 作用：充当头结点，一直不动 “伪头结点”
//cur 就像工人一样，一直在找小的，指向小的，等小的移动到下一个，cur就移动到对方位置
//cur 就是一直在连接
//最后输出的是后，只需要输出 dum 后面的就行！！
//要是没有 dum 呢? cur 链接到最后，怎么输出链表？
//可以从处在最后的cur 开始，往前遍历输出。但就是麻烦！还不如直接 dum头结点输出方便
ListNode* cur = dum; //cur 从“伪头结点”dum 开始连接
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) { //L1的值小的话
cur->next = list1; // cur 的next 指向L1
list1 = list1->next; //L1挪到下一个位置（从第一个元素移到第二个元素）（L1刚开始指第一个元素）
}
else {
cur->next = list2; //和上面一样··
list2 = list2->next;
}
cur = cur->next; //cur 移到next （这里的next就是更小的L1 /L2)
//这里有两个细节：指向（next) 移动 （本身） 有区别的
// 核心逻辑：cur 指向dum 开始
// L1和L2比较，找到最小的
// cur 指向L1/L2（找到目标）
//目标转移到下个位置
//cur 转移（移动）到敌人为止
// 一直循环
// 核心：找到目标，指向目标，目标转移，自己转移到敌人为止 （顺序不能乱！！）
//现实生活中：你找最弱的敌人->准备进攻->敌人发现跑到下一个位置->进攻敌人为止（敌人已经跑了）->继续找弱小敌人->持续···
}
cur->next = list1 != nullptr ? list1 : list2;
//cur->next = list1 != nullptr 如果 list1 不空的话，cur ->next 指向list1 。如果list1空了,那就指向list2
//核心：谁不空，我就指向谁
return dum->next; //dum->1->2->···· 只需要返回 dun->next 就行！
}
};
链接：https ://leetcode.cn/problems/merge-two-sorted-lists/submissions/
来源：力扣（LeetCode）
//****************************** //递归来做这题 太TM经典了！！ //方法二：递归
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { //比赛入口····
if (l1 == NULL) { //L1和L2，谁小，谁就移动到下一个位置。如果哪一方移动到了NULL，直接输出另一个的所有元素
return l2;
}
if (l2 == NULL) { //L2空了，就返回L1所有元素
return l1;
}
if (l1->val <= l2->val) { //如果L1小 ，那么弱小方找到了。
l1->next = mergeTwoLists(l1->next, l2); //L1可以退出“找小”环节，让L1->next 和 L2 加入比赛
// L1 指向= L1->next 和 L2最小的一方 //mergeTwoLists(l1->next, l2) ---> L1->next和 L2参加比赛
return l1; //返回L1 因为L1也参加了比赛。返回，肯定是返回所有参赛人员
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};
//链接：https ://leetcode.cn/problems/merge-two-sorted-lists/
//动画做得挺好的，但是那个nest 动画，应该是水平的哈，被被误导了。
//*****************************************************************************************************************************************************// // 83.给定一个已排序的链表的头 head ， 删除所有重复的元素（两个挨着的），使每个元素只出现一次 。返回已排序的链表 。
//给定一个已排序的链表的头 head ， 删除所有重复77777777777777777777777777777的元素，使每个元素只出现一次 。返回已排序的链表 。 ****
//这道题给的还是有点简单。因为，这里的“重复”是指两个元素挨着的。 比如：1->2->2->3->4 编程 1->2->3->4 所以，你只需要通过 cur.val == cur.next.val 判断就行 //方法一：常规做法
//加大难度 ：1->2->3->2->1 删除后：1->2->3 这时候，cur.val == cur.next.val 可就不好使了！
// 有两种方法：1->可以搞一个数组，每次访问“下一个”结点时，就把“下一个”结点的值放入数组。下次访问结点的时候，先在数组里访问一下有没有这个值。如果有，那就删除（跳过）这个结点。这里访问数组，可以二叉说着别的搜索。
// 2->每次访问结点，先从头访问一遍所有结点的值，看一下有没有相同的值。如果有，那就删除（跳过）这个节点。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) { // cur->val==cur->next->val
//··2··free(q) 问题，昨天整理链表的时候说过，你用 cur.next = cur.next.next; 时，无法free(cur)
//我们可以在这儿插入一个： ListNode p = cur->next ; p指向cur后面重复的结点
cur.next = cur.next.next; //我更喜欢 cur->next=cur->next->next 跳过这个节点
//小细节：你跳过了这个节点，但是没有删除这个节点。怎么删除这个节点呢？··1··
//··3··free( p->next ); 虽然这时候cur->next已经跳过去了，但是 p 一直指着原来的cur
}
else {
cur = cur.next;
}
}
return head;
}
}
//链接：https ://leetcode.cn/problems/remove-duplicates-from-sorted-list/
//************ free (重复的结点) //方法二：free (重复的结点)版本
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) { //输入的头结点不能是空，下一个结点不能是空
if (cur.val == cur.next.val) { // cur->val==cur->next->val
ListNode p = cur->next ; // 刚刚我在这里翻了个错误： ListNode p = cur ; 这么做不对！没啥用。因为p=cur ，没有开。到最后肯定不行
cur.next = cur.next.next; // 上面这个操作，我们在弄“伪结点”时候用过。所以小心细节！ 记住，free(p);
free( p ); // free( p->next ) 如果这么做，因为p=cur，相当于 free(cur->next->next) 肯定错误！
} //free (重复的结点)
else {
cur = cur.next;
}
}
return head;
}
}
//*****************************************************************************************************************************************// // 141.你一个链表的头节点 head ，判断链表中是否有环。
//你一个链表的头节点 head ，判断链表中是否有环。 ****
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
// 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环 ，则返回 true 。 否则，返回 false 。
//其实这道题在上面拓展的时候，说过，就是删除重复元素：1->2->3->2->1 删除后：1->2->3 这个时候，为了确认有没有重复元素的时候，我们也需要遍历。
// 和这个环是一样的，也就是“环-->找到重复元素”+“删除元素”=“删除重复元素
//核心：找重复元素 //找链表中找重复元素（这题核心）
//**************** python 实现 // 方法一：python 哈希数组
class Solution :
def hasCycle(self, head: ListNode) -> bool : //建立一个哈希表数组，返回 bool
seen = set() //建立哈希表
while head : //while (head != NULL) （head==head[0])
if head in seen : //直接判断有没有
return True //有的话，那说明之前存过
seen.add(head) //存入哈希表
head = head.next //指向下一个
return False //最后，一直没有重复出现过，return false
//链接：https ://leetcode.cn/problems/linked-list-cycle/description/
//*************** c++用哈希表 （指针哈希表） //方法二：c++用哈希表 （指针哈希表）
class Solution {
public:
bool hasCycle(ListNode* head) {
unordered_set<ListNode*> seen; // unordered_set<T> 容器提供了和 unordered_map<T> 相似的能力
//指针哈希表 // 但 unordered_set<T> 可以用保存的元素作为它们自己的键。
// 这种容器不能存放重复的元素.
while (head != nullptr) { //head 不是空指针
if (seen.count(head)) { //cout函数 在 seen 里面找 head
return true; //如果有的话，说明“有环”
}
seen.insert(head); //在seen 里面存储 head
head = head->next;
}
return false;
} ·····等你无聊了，可以通过指针哈希表，把上面的删除，搞一下，很简单的
};
//链接：https ://leetcode.cn/problems/linked-list-cycle/description/
//*************** 快慢指针 //方法三：快慢指针 （慢指针=快指针 --> 环）
// https://www.bilibili.com/video/BV1KG4y1G7cu/?vd_source=8441eb6ac2f8a66cec75da682ee861
bool hasCycle(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return false;
}
struct ListNode* slow = head; //慢指针
struct ListNode* fast = head->next; //快指针 快指针比慢指针多走一步
while (slow != fast) { //快慢指针不相遇的时候
if (fast == NULL || fast->next == NULL) { // 这个判定，结合图形理解！
// ·(p)->·->NULL(p) 相当于fast==NULL
// ·(p)-> NULL -> NULL(p) 相当于fast->next==NULL 这种情况肯定不允许，所以提前判断。
// 空指针跳着走，但是，不能跳过空指针。所以保证跳的那个不能是空指针
return false; //fast==NULL 或者 fast->next==NULL ，说明快指针到达尾部了.
}
slow = slow->next;
fast = fast->next->next; // 右边的： fast->next 不能是 NULL !!
} //所以提前判断，fast->next ==NULL 的话,return false
return true; // 当slow==fast 时退出 while 循环，说明相遇，说明有闭环
//如果是线性：慢指针永远追不上快指针 （这个简单）
//如果有环，快指针先进入环，进行循环。随后慢指针也会进入循环。这时候，相对速度看，快指针比慢指针多走一步。
// ···-> 慢指针->······->快指针····->····
// · ·
// ····························
//只要速度不相等，一个环里肯定能相遇！基本常识。 只是时间问题而已
}
//链接：https ://leetcode.cn/problems/linked-list-cycle/description/
//***************** 骚操作 //方法四：骚操作 （循环10001次）
bool hasCycle(struct ListNode* head)
{
int n = 0;
while (head) // while ( head !=NULL)
{
head = head->next; //一直循环
n++;
if (n > 10000) //n=100001 也行
return true; //链表最长：10000 你走了100001步，肯定是有循环。不然你不会多走的
}
return false; //你都没走完10000步，肯定没有循环。提前遇到 NULL （截止）了
}
//***************************************************************************************************************************************// // 160. 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null ****
// 经典算法：两个人干活，前面分开干，后面有部分一起。给你两个人干活情况，判断两个人有没有一起干过？ // 方法一：A:aaaa cccc NULL bbb / B :bbb cccc NULL aaaa -->相遇->一起干 cccc NULL 提前相遇 返回：c
// A -> a , B -> b,假设两个人一起干了 c 天
//
//指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
//如果 pA 到了末尾，则 pA = headB 继续遍历 A干完活，干B的活
//如果 pB 到了末尾，则 pB = headA 继续遍历 B干完活，干A的活
//两个人把自己和对方的活干完了，会相遇的，一起干共同部分活
//A :aaaa cccc NULL bbb
// 相遇->一起干 cccc NULL 提前相遇 返回：c
//B :bbb cccc NULL aaaa
//A :aaaa NULL bbb NULL 最后NULL才相遇
//B :bbb NULL aaaa NULL
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
if (headA == NULL || headB == NULL) { //输入判断
return NULL;
}
struct ListNode* pA = headA, * pB = headB;
while (pA != pB) {
pA = pA == NULL ? headB : pA->next; //pA==NULL pA干完了，把pB的活干一遍 所以：pA=handB
//pA!=NULL pA没干完，接着干 pA=pA->next
pB = pB == NULL ? headA : pB->next; //pB==NULL pB干完了，把pA的活干一遍 所以：pB=handA
//pB!=NULL pB没干完，接着干 pB=pB->next
}
return pA; //pA==pB 相交的交点
}
//链接：https ://leetcode.cn/problems/intersection-of-two-linked-lists/
//
//************* 倒着遍历
//A :aaaa cccc NULL bbb cccc NULL
// 如果这样的话，倒着遍历 （p=p->prior)，同时判断他俩值相不相等。返回最后一个相等的值
//B :bbb cccc NULL aaaa cccc NULL
///这么做，没问题。当然可以。但是，得自己定义 prior双链结构，有点麻烦。题目就给了 next结构，自己定义 prior 结构
//可以用两次递归，两次回溯中搞定 prior结构
//************** 哈希表 //方法二：指针哈希表
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
unordered_set<ListNode*> visited; //建立“指针”哈希表 visited
ListNode* temp = headA; ///temp移动指针
while (temp != nullptr) {
visited.insert(temp); //temp访问的非空指针存入哈希表
temp = temp->next; //继续找下一个指针
} //目的：把A的所有值存入哈希表
temp = headB; //重新遍历 B
while (temp != nullptr) {
if (visited.count(temp)) { //查看temp的值在不在哈希表里 如果有，if(1)，相当于if(true)
return temp; //如果有的话，返回。这个就是第一个重复的结点
}
temp = temp->next; //如果没有，继续找
}
return nullptr; //while(temp==nullptr) 退出循环 ，返回nullptr
}
};
//链接：https ://leetcode.cn/problems/intersection-of-two-linked-lists/description/
//***************** 常规做法 //方法三：长的部分剪掉，记录短的部分长度len，再同时剪掉len个长度。剩余就是共同部分( NULL or C )
//一开始两边同时遍历，判断值相不相等。这么做不行因为长度不相等。问题来了，我把唱的部分剪掉，然后遍历值相不相等不就行了
//核心思想就出来了：先遍历两个链表，统计两个链表的长度。然后谁小，我就先指定len 的谁。然后把长的剪掉，这时候长度相等。
// 再同时剪短的，剪多长呢？剪短的长度为止。这时候，剩下的如果是NULL，那就是没有共同部分。入伙不是，那就是共同部分的第一个结点
//长的部分剪掉，记录短的部分长度len，再同时剪掉len个长度。剩余就是共同部分( NULL or C )
class Solution {
public:
int getLength(ListNode* head) { // 接受ListNode* 的函数
int ans = 0;
for (; head; head = head->next) ++ans; //第一head 我咋看不懂？。我知道这是访问所有节点，统计长度。
// ListNode* temp = head;
// while (temp != NULL) {
// temp = temp->next;
// ans++;
}
return ans; //ans 就是链表长度
}
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
int lenA = getLength(headA); //找到 A 和 B 的长度
int lenB = getLength(headB);
int len = 0;
if (lenA > lenB) {
len = lenB; //谁小，我就从谁开始
while (lenA-- > lenB) //后自减 lenA>lenB ;lenA=lenA-1; 直到长度相等
headA = headA->next;
}
else {
len = lenA;
while (lenB-- > lenA)
headB = headB->next;
}
//此刻，A和B的长度相等
//aaaaaaacccc
// bbbbbbbcccc
while (len--) { //同时减长度
if (headA == headB) //等他俩相等的时候，返回C （第一个相等的C）
return headA;
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
};
//***************************************************************************************************************************************// // 203. 删除指定链表结点 *****
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 //方法一：常规做法 （head 删除 和内部删除）
//java 版本
class Solution {
public ListNode removeElements(ListNode head, int val) {
//删除值相同的头结点后，可能新的头结点也值相等，用循环解决
while (head != null && head.val == val) { //先判断头结点是不是要删除的结点 ，如果是，只需要 head=head->next
head = head.next;
}
if (head == null) //头结点是空的，世界返回head 或者 NULL 都行
return head;
ListNode prev = head; //这时候，头结点不是删除的结点，那就构造移动结点 prev
while (prev.next != null) { //确保当前结点后还有结点
if (prev.next.val == val) { //prev 后面的值是删除的结点
prev.next = prev.next.next; //那么久跳过这个节点
}
else {
prev = prev.next; //如果后面不是，那就继续遍历，直到 后面没有节点 （prev->next==NULL )
}
}
return head; //如果遍历到最后，还是 prev->next==NULL ,“那说明没有删除的结点”XXX说错了。那就返回原始的head
//不是“那说明没有删除的结点”，而是prev 走到头了，走完了，活结束了。返回head就完事
//忍不住再说一句：head 从始至终，除非删除 head，那么had=head->next，不然head一直没动过。一直在prev再动
// head 不动，prev 从head出发，进行遍历，判断，删除的活。最后活干完了 ，返回head就行
//核心思想就是：先判断head 要不要删除（进行判断），然后prev从head出发，进行遍历，判断，删除的活。干完了，返回head
//超简单！！！
}
}
//链接：https ://leetcode.cn/problems/remove-linked-list-elements/description/
//
//***************** 方法和上面一样+“哨兵” //方法二：方法和上面一样+“哨兵” （ 都转化成“内部结点 ）
//上面的判断中，进行了两种删除：head 删除和内部节点删除。其中，head 删除：head=head->next 就行。
// 但是别的节点：先判断后面有节点（判断prev还没走到头），然后 prev=prev->next->next 就行
//两种删除不太一样。能不能合并呢？ 当然可以。把“头结点”变成“内部节点”就行--->加“哨兵”
class Solution {
public ListNode removeElements(ListNode head, int val) {
//创建一个虚拟头结点
ListNode dummyNode = new ListNode(val - 1); //加一个“哨兵”
//细节：为啥要 val-1呢？ 是为了防止“哨兵”和“删除的结点”一样
//如果“哨兵”和“头结点”一样了，那不就和上面的一样了吗？是不是也要删除“哨兵”呢？
//不用！因为，你是从 prev.next.val == val 开始的。也就是 dummyNode.next.val == val，也就是head.val=val
//跳过了dummyNode.val 。所以管你相不相等，我根本就不访问。
// 但是，以防万一，还是不要让相等。也许这个“哨兵”不访问，但别的“哨兵”万一访问到了，同时“哨兵”的值还影响到了程序，那就麻烦了。很难发现
//提出了新的细节：“哨兵”的值要注意。不能让“哨兵的值”和“特殊值”相等。
//所以，“哨兵”的值一定要初始化！！以防万一
dummyNode.next = head; //哨兵后面是head
ListNode prev = dummyNode; //从“哨兵”开始遍历，这时候“头结点”变成了“内部节点”
while (prev.next != null) { //确保当前结点后还有结点（判断还没有走到尾）
if (prev.next.val == val) {
prev.next = prev.next.next; //你看，只有一种删除，哪怕你是头结点
}
else {
prev = prev.next;
}
}
return dummyNode.next; // 相当于 head 为啥不直接 return head 呢？不行！万一这和head 要删除呢？
// 只要有了“哨兵”，head 就不在是head 。head 和“内部节点”一样，一视同仁！！
// 有了“哨兵”，“哨兵”就是新的“head”
}
}
链接：https ://leetcode.cn/problems/remove-linked-list-elements/description/
//***************** //方法三：递归 （回溯中判断要不要返回这个结点）
//突然，明白递归，应该从后往前想！
//比如这道题，你从 return null 开始往后想
//A -> B -> C-> D -> E -> NULL
//A 的下一个节点是 B 你确定？？万一B是删除的，目标呢？ 同理，你都不能确定后面的节点是不是真正的后面结点（不能确定会不会删除）
// 但是，如果后面是NULL，百分百就是你后面结点。，突破口来了： E-> NULL 百分百确定！D ->E ? 判断一下E是不是和目标值相同（会不会被删除）
// 所有情况你都得到倒着来 倒着：如果真的是你后面（不用删除），那就返回 如果要删除，那就返回下一个值
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null)
return null;
head.next = removeElements(head.next, val); //下一个？扔进函数 只要不是空，你问我下一个，我就把你扔进函数里
//直到下一个是空的，返回空 ：head.next = NULL 记住：最后一个元素后面的是空的
//
// 开始进入下面部分 ：把你扔出来 （扔出来阶段）
if (head.val == val) { //如果你的值和目标值相同，那就扔你后面的（跳过你） 刚开始，head 是最后一个元素，
return head.next;
}
else {
return head; //如果不是，那就把你扔出来
}
//上面这种递归：没有释放删除的节点。只是跳过了。可以改进：396/397 用下面代替：
/*if ( head.val==val){
struct ListNode* P1, * P2;
P1 = head;
P2 = head.next;
free(p1);
return P2;*/
} //***** 核心：388-3-390 ：扔进去阶段 下面是：扔出来阶段 牛逼！！！他喵的
}
//链接：https ://leetcode.cn/problems/remove-linked-list-elements/description/
//***************************************************************************************************************************************// // 206. 反转链表 ****
//反转链表
// 1->2->3->4->NULL 变成 4->3->2->1->NULL
//迭代（双指针） 类似双指针 // 方法一：迭代（双指针） 类似双指针
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head,
ListNode* pre = nullptr;
while (cur != nullptr) { //cur :1-2-3-4-NULL
ListNode* tmp = cur->next; // 暂存后继节点 //先走到2（找到下一个点）
cur->next = pre; // 修改 next 引用指向 //（temp 找到下一个点后，立刻找pre （NULL））
pre = cur; // pre 暂存 cur //per 赶紧走到cur 位置，为了迎接下一个 cur->next
//下一步开始，per 就成了cur 的前结点，temp成了后结点 (per 名字的来源）
cur = tmp; // cur 访问下一节点 //开始真正移动到下一点(temp)
//核心：cur 先让temp 找到下一家，然后自己指向尾部（pre / NULL)，pre移动到cur（此时的cur是下一个cur头结点---尾部充当头结点），最后cur移动到下一点
}
return pre; //cur ==NULL 说明cur已经走完了整个元素
}
};
//链接：https ://leetcode.cn/problems/reverse-linked-list/description/
//
//***************** 递归 //方法二：递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
return recur(head, nullptr); // 调用递归并返回 //最后返回的就是头结点
}
private: // 1->2->3->4->5->NULL
ListNode* recur(ListNode* cur, ListNode* pre) { // res = recur (下一个结点，这个结点）
if (cur == nullptr) return pre; // 终止条件 //判断 下一个结点是否为空。 直到下一个结点位空，返回 这个结点（最后一个结点）(5)
ListNode* res = recur(cur->next, cur); // 递归后继节点 // res = recur (下一个结点，这个结点）扔进函数 递归最后：5 然后往下走
cur->next = pre; // 修改节点引用指向 // 下一个结点 -> 这个结点 （反转）
return res; // 返回反转链表的头节点 // 返回最后一个结点 （5），然后继续“递归后继节点”------回溯状态
//(下一个结点 <- 这个结点）
// （1 <- NULL ) （1 -> NULL ) 返回5 ---> 返回5 : 5->4->3->2->1->NULL
// ( 2 <- 1 ) ( 2 -> 1 ) 返回5
// ( 3 <- 2 ) ( 3 -> 2 ) 返回5 //回溯状态，不可能进入死循环。回溯到最后：return recur(head, nullptr);
// ( 4 <- 3 ) ( 4 -> 3 ) 返回5
// ( 5 <- 4 ) ( 5 -> 4 ) 返回5
//(NULL <- 5 ) 回溯 ( 5 -> NULL) 返回5
}
};
//链接：https ://leetcode.cn/problems/reverse-linked-list/
//方法三：栈 //栈
//链表只能 从前至后 访问每个节点，而题目要求 倒序输出 各节点值，这种 先入后出 的需求可以借助 栈 来实现。
class Solution {
public:
vector<int> reverseBookList(ListNode* head) {
stack<int> stk;
while (head != nullptr) {
stk.push(head->val);
head = head->next;
}
vector<int> res;
while (!stk.empty()) {
res.push_back(stk.top());
stk.pop();
}
return res;
}
};
//链接：https ://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/
//***************************************************************************************************************************************// // 234.回文链表 ****
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//输入：head = [1,2,2,1] 输出：true
bool isPalindrome(struct ListNode* head) { //方法一：链表值存入链表，前后遍历数组
int vals[50001], vals_num = 0;
while (head != NULL) { //把链表的值都存入数组里
vals[vals_num++] = head->val; // vals[vals_num] = head->val ; vals_num++;
head = head->next;
} // vals_num 链表的长度
for (int i = 0, j = vals_num - 1; i < j; ++i, --j) { // i 从第0个（最左边/头部），j 从 vals_num-1 （最右边/尾部）开始遍历
//这部分可以用“双链表”来做
// i < j 说明只要 i 在左边， j 在右边
if (vals[i] != vals[j]) { //只要左边的值和右边的值不相等，那就不是对称的，不是“回文链表”
return false;
}
}
return true;
}
//这道题引入了数组：为啥呢？ 利用数组搜索数字，是O(1)的复杂度。
//链接：https ://leetcode.cn/problems/palindrome-linked-list/
//************************ 经典递归 回溯 （双指针法） 用单指针，玩出了双指针******* //方法二：递归 回溯，前后遍历数组 （类双指针法）
class Solution {
public:
int ans = true;
ListNode* front;
void dfs(ListNode* tail)
{
if (!tail)return; //if (NULL)不会执行 // if (! NULL ) 执行 return (直接返回）
//相当于： if ( tail==NULL ) return ;
/**/ dfs(tail->next); //一直找最后一个结点 当 tail==NULL 的时候，return ；这时候，tail指向最后一个元素，开始往下执行
//回溯
if (ans) // if ( true ) // 有时候：if (ans ! = NULL)
{
if (tail->val != front->val) //最后一个元素的值 ？ 最前面元素的值 比较
ans = false; //如果不相等，那就不是回文链表，直接返回 false,结束
else front = front->next; // front 指向下一个 （手动指向下一个）
} //而 tail 利用回溯的特性，自动指向前面的结点 回溯作用： tail=tail->prior
} //我很好奇，这里为啥没用 return ? 直接自动到回溯点，继续回溯 ·············
bool isPalindrome(ListNode* head)
{
ListNode* front = head; // front 指向头结点 如果不用front ,head 早就跑到后面了。 目的就是，记住“头结点”，方便遍历。
dfs(head);
return ans;
}
};
//链接：https ://leetcode.cn/problems/palindrome-linked-list/description/
//***************************************************************************************************************************************// // 876.链表的中间结点 ****
// 链表的中间结点
//head = [1, 2, 3, 4, 5] 输出：3 head = [1, 2, 4, 5] 输出：4 （第二个中间结点）
//方法一：数组 （指针数组） //方法一：数组 （指针数组）
class Solution {
public:
ListNode* middleNode(ListNode* head) {
vector<ListNode*> A = { head };
while (A.back()->next != NULL)
A.push_back(A.back()->next);
return A[A.size() / 2];
}
};
//链接：https ://leetcode.cn/problems/middle-of-the-linked-list/
//************** 方法二：单指针法 （先遍历整个链表，统计长度； 第二次遍历到中间位置 ） //方法二：单指针法 （先遍历整个链表，统计长度； 第二次遍历到中间位置 ）
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int n = 0;
ListNode* cur = head;
while (cur != nullptr) {
++n;
cur = cur->next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur->next;
}
return cur;
}
};
//链接：https ://leetcode.cn/problems/middle-of-the-linked-list/
//************** 方法三：快慢指针 （当快指针走到末尾时，慢指针就是中间结点） //方法三：快慢指针 （当快指针走到末尾时，慢指针就是中间结点）
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
//链接：https ://leetcode.cn/problems/middle-of-the-linked-list/
//***************************************************************************************************************************************// // 1290. 二进制链表转十进制整数 ****
//二进制链表转十进制整数
// head = [1,0,1] 输出：5
class Solution {
public:
int getDecimalValue(ListNode* head) {
ListNode* cur = head;
int ans = 0;
while (cur != nullptr) {
ans = ans * 2 + cur->val;
cur = cur->next;
}
return ans;
}
};
//核心：这就相当于，比如说计算十进制的数：526，你先读取到52，如果发现后面还有一个6，那直接把52乘10加6就可以了
// //从左往右看！ 5-> 0101应该是 (((0*2 + 0)*2 + 1)*2 + 0)*2 + 1
//链接：https ://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/
//
//***************************************************************************************************************************************//
//********** 2023.11.1结束 今天就做了四五道题，受不了了！！明天干25道题。一起来，就把所有代码就先输进去，然后花一天时间进行编译！！解释 ************//
//***************************************************************************************************************************************//
//***************************************************************************************************************************************//
//移除未排序链表中的重复节点。保留最开始出现的节点。 输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3] //删除重复结点（不挨着，升级版）
//方法一：哈希表
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
if (head == nullptr) {
return head;
}
unordered_set<int> occurred = { head->val };
ListNode* pos = head;
// 枚举前驱节点
while (pos->next != nullptr) {
// 当前待删除节点
ListNode* cur = pos->next;
if (!occurred.count(cur->val)) {
occurred.insert(cur->val);
pos = pos->next;
}
else {
pos->next = pos->next->next;
}
}
pos->next = nullptr;
return head;
}
};
链接：https ://leetcode.cn/problems/remove-duplicate-node-lcci/solutions/303505/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/
//******方法二 ：枚举（两个循环） //方法二 ：枚举（两个循环）
struct ListNode* removeDuplicateNodes(struct ListNode* head) {
struct ListNode* ob = head; // 1->2->2->3->4
while (ob != NULL) { //这题早上，一眼就看出来了。妈的现在2023-11-2 16:30:56想半天我丢
struct ListNode* oc = ob; //（每次oc 从ob 开始） //刚开始： ob->1 oc从1开始遍历，看谁和ob相等。如果一样。那就跳过去 内部while 结束后，退出
while (oc->next != NULL) { //ob=ob->next 现在ob->2 oc开始指向ob oc 从2开始遍历，看谁和ob(2)一样。以此类推
if (oc->next->val == ob->val) { //双循环！之前见的都是很明显的两个 for嵌套，而这个是两个 while 嵌套。都一样
oc->next = oc->next->next;
}
else {
oc = oc->next;
}
}
ob = ob->next;
}
return head;
}
作者：力扣官方题解
链接：https ://leetcode.cn/problems/remove-duplicate-node-lcci/solutions/303505/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/
//***********************************************************************************************************************
//删除重复所有结点，只留下不同的结点
//方法一：递归
class Solution { //递归考虑了：1->1->1->2 这种情况 （头结点也考虑了）
public:
ListNode* deleteDuplicates(ListNode* head) { //发现3后面没有数字，那就直接返回3 返回到1后面（2已经删没了） 递归结束
if (!head || !head->next) { //head == NULL or head->next==NULL --->return head;
return head; //代码角度，很直接。 cog这个问题角度出发：如果head->next 是空的，那就返回空(head==NULL)
//或者你后面的后面是空，那就返回你自己head 所以，无论如何，合并返回head
}
if (head->val != head->next->val) { // head 和 head->net 的值不相等 ,
head->next = deleteDuplicates(head->next); //那就把后面的值带进递归判断一下，这个玩意儿有没有重复的。
}
else { // head 和 head->net 的值相等
ListNode* move = head->next; //可能后面有好几个重复的 // 1->2->2·->2··->3 move指向2·
while (move && head->val == move->val) { // 2·==2 //再判断，发现还一样 //这时候不一样了，退出while
move = move->next; //move->2·· //还一样，那就move->3
}
return deleteDuplicates(move); //但不确定3后面有没有重复的（不确定是否删除3） //比如： 1->3->3->3
} //那就只好把3带进递归，判断一下
return head;
}
};
//链接：https ://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
//方法二：一次遍历
//一边遍历、一边统计相邻节点的值是否相等，如果值相等就继续后移找到值不等的位置，然后删除值相等的这个区间。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head; //上面一样 逆时空的，或者后面没有，那就返回你自己
ListNode* preHead = new ListNode(0); //搞了个数组 ·····？？
preHead->next = head; //prehead 是“哑结点”
ListNode* pre = preHead; // pre 指向哑结点
ListNode* cur = head; // cur 指向头结点
while (cur) {
// cur-> nxt !=NULL
while (cur->next && cur->val == cur->next->val) { //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
cur = cur->next; //细节：先指向最后一个元素；你看倒数第二行： cur=cur->next ，会逃过最后一个元素。
} //因为本题要求：删除所有重复结点
if (pre->next == cur) {
pre = pre->next; //pre和cur之间没有重复节点，pre后移
}
else {
//pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
//但是pre不移动，仍然指向已经遍历的链表结尾
pre->next = cur->next;
}
cur = cur->next;
}
return preHead->next;
}
};
//妈的！！！！！！！！！！！！！！！！！！这道题想了半个多小时，终于想明白了！！
// pre cur pre负责铺路； cur用来筛选 cur 判断有没有重复：如果有重复，那他就走到最后一个重复地方，pre直接跳到cur后面（直接跳过了所有重复部分）
// 如果没有重复部分（ pre->next == cur ），那么就正常 pre=pre->next 。
// 核心：最后只需要返回 preHead->next 就行。返回的就是pre 铺好的路
//方法三：利用计数，两次遍历 *****下面这个代码没看懂。还没学习C++知识 ：unordered_map
//class Solution {
//public:
// ListNode* deleteDuplicates(ListNode* head) {
// unordered_map<int, int> m;
// ListNode dummy(0);
// ListNode* dummy_move = &dummy;
// ListNode* move = head;
// while (move) {
// m[move->val]++;
// move = move->next;
// }
// move = head;
// while (move) {
// if (m[move->val] == 1) {
// dummy_move->next = move;
// dummy_move = dummy_move->next;
// }
// move = move->next;
// }
// dummy_move->next = nullptr;
// return dummy.next;
// }
//};
//链接：https ://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
//*****************************************************************************************
//给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。 //返回倒数第cnt的结点
//输入：head = [2, 4, 7, 8], cnt = 1 输出：8
//方法一：两个指针”一个向前走cnt步，然后一起同步走。前面的指针到末尾时，后面的就是倒数第cnt个结点，返回就行
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* former = head, * latter = head;
for (int i = 0; i < cnt; i++) {
if (former == nullptr) return nullptr;
former = former->next;
}
while (former != nullptr) {
former = former->next;
latter = latter->next;
}
return latter;
}
};
//链接：https ://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
//方法二：先遍历长度，然后走 len-cnt长度就行 //方法二：先遍历长度，然后走 len-cnt长度就行
class Solution {
public:
ListNode* trainningPlan(ListNode* head, int cnt) {
int n = 0;
ListNode* node = nullptr;
for (node = head; node; node = node->next) {
n++;
}
for (node = head; n > cnt; n--) {
node = node->next;
}
return node;
}
};
//链接：https ://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
//方法三：官方解答：和方法一一样 //快慢指针，快指针先走k 步
//重复一边：这题要求链表的倒数第k个节点，最简单的方式就是使用两个指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。
class Solution {
public:
ListNode* trainningPlan(ListNode* head, int cnt) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && cnt > 0) {
fast = fast->next;
cnt--;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
//链接：https ://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
//*****************************************************************************************
//方法四；栈 //栈
//把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可
public int kthToLast(ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();
//链表节点压栈
while (head != null) {
stack.push(head);
head = head.next;
}
//在出栈串成新的链表
ListNode firstNode = stack.pop();
while (--k > 0) {
ListNode temp = stack.pop();
temp.next = firstNode;
firstNode = temp;
}
return firstNode.val;
}
//链接：https ://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
//方法五：递归 //递归
int size;
public int kthToLast(ListNode head, int k) {
if (head == null)
return 0;
int value = kthToLast(head.next, k);
if (++size == k)
return head.val;
return value;
}
//链接：https ://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
//***********************************************************************
//删除结点 （最简单版本） //删除指定结点（最简单）
class Solution {
public:
void deleteNode(ListNode* node) {
// 复制 node.next 到 node
node->val = node->next->val;
// 从链表中删除 node.next
node->next = node->next->next;
}
};
//https ://leetcode.cn/problems/delete-middle-node-lcci/
//***********************************************************************
//两个链表相加 //两个链表相加（十进制）
//我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
// 具体而言，如果当前两个链表处相应位置的数字为 n1, n2 ，答案链表处相应位置的数字为(n1 + n2 + carry)?mod?10
//如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 000 。
//此外，如果链表遍历结束后，有 carry > 0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
//小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点 head。
//使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while (l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
if (carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
}
//链接：https ://leetcode.cn/problems/add-two-numbers/
//删除倒数第n个结点 //删除倒数第n个结点
//栈 //栈
//弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
stack<ListNode*> stk;
ListNode* cur = dummy;
while (cur) {
stk.push(cur);
cur = cur->next;
}
for (int i = 0; i < n; ++i) {
stk.pop();
}
ListNode* prev = stk.top();
prev->next = prev->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
//链接：https ://leetcode.cn/problems/remove-nth-node-from-end-of-list/
//方法二：开始对链表进行一次遍历，得到链表的长度 L。再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1个节点时，就是删除的节点。 //先遍历长度，再次遍历到len-n+1个结点
class Solution {
public:
int getLength(ListNode* head) {
int length = 0;
while (head) {
++length;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
int length = getLength(head);
ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
//链接：https ://leetcode.cn/problems/remove-nth-node-from-end-of-list/
//*************************************************************************************************
//给定一个链表，两两交换 输入：head = [1,2,3,4] 输出：[2, 1, 4, 3] //链表，两两交换
//递归 //递归
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}
//链接：https ://leetcode.cn/problems/swap-nodes-in-pairs/
//“哨兵” 常规做法 //“哨兵” 常规做法
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode dummyHead;
dummyHead.next = head;
struct ListNode* temp = &dummyHead;
while (temp->next != NULL && temp->next->next != NULL) {
struct ListNode* node1 = temp->next;
struct ListNode* node2 = temp->next->next;
temp->next = node2;
node1->next = node2->next;
node2->next = node1;
temp = node1;
}
return dummyHead.next;
//ListNode* ans = dummyHead->next;
//free(dummyHead);
//return ans;
}
//链接：https ://leetcode.cn/problems/swap-nodes-in-pairs/solutions/
//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 //给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
//下面是我写的代码，但是出了问题。以后再看看吧~~
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (k == 0 || head == nullptr || head->next == nullptr) {
return head;
}
int len = 0;
ListNode* pir = head;
ListNode* pr = head;
ListNode* p = head;
while (pir->next != NULL) {
pir = pir->next;
len++;
}
int kk = len - k % len;
int j = 0;
for (j = 0; j < len; j++) {
if (j == kk - 1) {
p = pr;
}
pr = pr->next;
}
pr->next = head;
p = NULL;
return pr;
}
};
//常规做法：每个结点向右平移2个结点--->把最后两个结点拼接在头结点位置 //常规做法：每个结点向右平移2个结点--->把最后两个结点拼接在头结点位置
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (k == 0 || head == nullptr || head->next == nullptr) {
return head;
}
int n = 1;
ListNode* iter = head;
while (iter->next != nullptr) {
iter = iter->next;
n++;
}
int add = n - k % n; // 链表长度：3 向右平移5个结点=3+2 （3相当于没有移动）所以，5-->2
if (add == n) { //计算完后，如果向右移动的长度和链表长度相同，也是相当于没有移动
return head; //这个算法等同于 k % n == 0 (也就是 k 是 n 的倍数）
}
iter->next = head; // iter 是“哨兵”头结点 XXXX 不是！你单纯看这个，你感觉iter 就是个“哨兵”，但是别忘了这个之前，iter通过循环，到了最后一个结点
//最后一个结点->head ,就把这个链表变成了“环”。现在任务就是，找到那个结点，“断掉”就行
// “链表”-->“环” 的方法：从头结点开始访问链表的最后一个结点（p->next==NULL)，然后 p->next=head 就行，此时链表变成了“环”
//head = [1,2,3,4,5], k = 2
while (add--) { //while (add-- !=0)
iter = iter->next;
} //此时：inter 在3上面
ListNode* ret = iter->next; //ret 在4
iter->next = nullptr; //把3后面断掉
return ret; //返回4就行
}
};
//链接：https ://leetcode.cn/problems/rotate-list/
//*******************************************************************************************************
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 //分割链表
//你应当 保留 两个分区中每个节点的初始相对位置
//输入：head = [1, 4, 3, 2, 5, 2], x = 3 输出：[1, 2, 2, 4, 3, 5]
//小的找出来，大于等于找出来，小的接在大的前面
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* small = new ListNode(0);
ListNode* smallHead = small; //smallHead 一直不动，为最后 return smallHead->next; 做准备
ListNode* large = new ListNode(0);
ListNode* largeHead = large; //largeHead 一直不动，为最后 mall->next = largeHead->next; 做准备
while (head != nullptr) {
if (head->val < x) {
small->next = head; //先指向小的
small = small->next; //然后移过去
}
else {
large->next = head;
large = large->next;
}
head = head->next; //自己走向下一个 你看，head 亲自出场了！！为啥呢？因为这个head用不上了。做一遍之后，分解成大小两部分了
}
// 小：smallHead -> 1-> 1-> 2-> 2 small 在2
// 大：largeHead -> 3-> 4-> 5-> 6 large 在 6
large->next = nullptr; //大的在后半部分 此时，large 在大的里面最后！！ //largeHead -> 3-> 4-> 5-> 6->nullptr
small->next = largeHead->next; //此时，small 在小的里面最后！！ 所以后面直接拼接 largeHead 就行
//smallHead -> 1-> 1-> 2-> 2 -> 3-> 4-> 5-> 6->nullptr //跳过了largeHead
return smallHead->next; //1-> 1-> 2-> 2 -> 3-> 4-> 5-> 6->nullptr
} //满满的细节！！
};
//链接：https ://leetcode.cn/problems/partition-list/
//重现搞一个链表，遍历那个链表，先把小的接在新链表后面，再把大的接在后面
//···········又是错的。。。没找出来原因
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* n;
ListNode* pri;
pri->next = n;
ListNode* pp;
pp->next = head;
while (head ！= NULL && head->next ！= NULL) {
if (head->val < x) {
n->next = head;
}
}
while (pp->next ！= NULL && pp->next->next ！= NULL) {
if (pp->next->val >= x) {
n->next = pp->next;
}
pp = pp->next;
}
return pri->next;
}
};
//**************************************************************************************************
//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
// 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
//输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1, 4, 3, 2, 5]
//我自己用递归试了一下，不行。理论来讲，可以的。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
struct ListNode* he;
he->next = head;
struct ListNode* a;
int i;
for (i = 0; i <= left; i++) {
if (i == left - 2)
head->next = recur(head, head->next);
head = head->next;
}
return he->next;
}
public:
ListNode* recur(ListNode* cur, ListNode* pre) {
int j;
if (cur == nullptr) return pre;
struct ListNode* res = recur(cur->next, cur);
if (j == right - left) //只递归 right - left 次
return res
cur->next = pre;
j++;
return res;
}
}
class Solution {
public int storeWater(int[] bucket, int[] vat) {
int len = bucket.length;
int h = 0;
int g = 0;
int arr[][] = new int[len][2];
for (int j = 0; j < len; j++) {
if (bucket[j] == 0) {
if (vat[j] == 0)
continue;
h = 2;
bucket[j] = bucket[j] + 1;
for (int i = 0; i < len; i++) {
if (vat[i] == 0) {
arr[i][0] = 0;
continue;
}
int mx = 0;
mx = Math.max(mx, vat[i] / bucket[i]);
return mx + 1;
}
}
}
if (h == 0) {
for (int i = 0; i < len; i++) {
if (vat[i] == 0) {
arr[i][0] = 0;
g++;
continue;
}
arr[i][0] = vat[i] / bucket[i];
arr[i][1] = i;
}
Arrays.sort(arr, (a, b)->b[0] - a[0]);
int k = arr[0][1];
bucket[k] = bucket[k] + 1;
}
int mx = 0;
int u = 0;
for (int w = 0; w < len; w++) {
int f=0;
mx = Math.max(mx, vat[w] / bucket[w]= vat[w] % bucket[w]==0 ? vat[w] / bucket[w]: vat[w] / bucket[w]+1);
int y=vat[w] / bucket[w] = vat[w] % bucket[w] == 0 ? vat[w] / bucket[w] : vat[w] / bucket[w] + 1
if(mx==y )
}
if (g == len)
return 0;
return mx + 1;
}
}
class Solution {
public int storeWater(int[] bucket, int[] vat) {
int len = bucket.length;
int h = 0;
int g = 0;
int arr[][] = new int[len][2];
for (int j = 0; j < len; j++) {
if (bucket[j] == 0) {
if (vat[j] == 0)
continue;
h = 2;
bucket[j] = bucket[j] + 1;
for (int i = 0; i < len; i++) {
if (vat[i] == 0) {
arr[i][0] = 0;
continue;
}
int mx = 0;
mx = Math.max(mx, vat[i] / bucket[i]);
return mx + 1;
}
}
}
if (h == 0) {
for (int i = 0; i < len; i++) {
if (vat[i] == 0) {
arr[i][0] = 0;
g++;
continue;
}
int j = vat[i] / bucket[i];
if (vat[i] % bucket[i] != 0)
j++;
arr[i][0] = j;
arr[i][1] = i;
}
Arrays.sort(arr, (a, b)->b[0] - a[0]);
int k = arr[0][1];
int e = 0;
int u = bucket[k];
int f = (vat[k] % u == 0) ? vat[k] / u : vat[k] / u + 1;;
int p = vat[k] / u;
if (vat[k] % u == 0)
p++;
int r = p;
int w = 0;
for (int q = 0; q < 100000; q++) {
w = (vat[k] % u == 0) ? vat[k] / u : vat[k] / u + 1;
u++;
r = (vat[k] % u == 0) ? vat[k] / u : vat[k] / u + 1;
int sum = r + e;
if (sum > f)
break;
f = sum;
e++;
}
}
if (g == len)
return 0;
return e + w;
}
}
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- ryyc.cn 版权所有 湘ICP备2023022495号-3
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务