算法 专题

11月16日

链表反转

https://www.nowcoder.com/share/jump/5820267981700126436945

#include <cassert>
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *vh=new ListNode(-1);
        vh->next=head;
        ListNode *pre_m_ptr, *m_ptr ;//,*pre_n_ptr, *n_ptr
        ListNode *it=head,*pre_it=vh;
        int i=1;
        while(it!=nullptr){
            if(i==m){
                m_ptr=it;
                pre_m_ptr=pre_it;
            }
            if(i>m && i<=n){
                auto tmp=it->next;
                it->next=pre_it;// <-

                i++;
                pre_it=it;
                it=tmp;
                if(i==n+1){
                    pre_m_ptr->next=pre_it;
                    m_ptr->next=it;
                    break;
                }
                continue;

            }
            i++;
            pre_it=it;
            it=it->next;
        }
        return vh->next;
    }
};

链表中的节点每k个一组翻转_牛客题霸_牛客网 (nowcoder.com)

class Solution {
public:

    ListNode* reverseKGroup(ListNode* head, int k) {
        auto tail=head;
        int i=k;
        while (i--) {
            if(tail==nullptr){// 不满足k不要反转
                return head;
            }
            tail=tail->next;
        }

        // tail 事实际上是第k+1给元素
        ListNode *pre=nullptr,*cur=head;
        while (cur!=tail) {
            auto tmp=cur->next;
            
            cur->next=pre;

            pre=cur;
            cur=tmp;
        }
        head->next=reverseKGroup(tail,  k);
        return pre;


    }
};

11月17日

二分查找

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

• 边界问题？ [) 还是【】

• 结束条件是 l<r 还是 l<=r

• 刷题的心态！！！

动态规划