2.28 链表、字符串中等 328 3

328. Odd Even Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //时间复杂度n 空间复杂度1 
        if(!head || !head->next) 
            return head;
        ListNode* second = new ListNode(0);
        ListNode* ptr = head;
        ListNode* se = second;
        
        while(ptr){
            ListNode* temp = ptr->next;
            if(temp == nullptr)break;
            if(temp->next != nullptr){
                ptr->next = ptr->next->next;//跳过偶数位
                temp->next = nullptr;//防止环                
            }else{
                ptr->next = nullptr;//第一个链表终止
            }
            se->next = temp;//second链表
            se = se->next;
            if(ptr->next == nullptr){
                break;
            }else{
                ptr = ptr->next;
            }
        }
        //拼接
        ptr->next = second->next;
        return head;
    }
};

3. Longest Substring Without Repeating Characters

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //最长无重复字符字串 字符串中的字母独一无二
        //找到字符串 查找是否存在于letter中
        //ch 有字母 数字 符号 空格四种类型
        
        unordered_set<char> sub; // 用 unordered_set 存储已经出现过的字符
        int max = 0;
        for(char ch : s){
            if(sub.find(ch) != sub.end()){
                //找到了 之前找到的substr就是一种结果 要将sub清空 然后再重新找
                if(sub.size() > max){
                    max = sub.size();
                }
                sub.clear();
            }
            sub.insert(ch);
        }
        if(sub.size() > max){
            max = sub.size();
        }
        return max;
    }
};

"dvdf"这个示例不通过 说明上述算法有缺点，下方使用的是长度变动的滑动窗口：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //最长无重复字符字串 字符串中的字母独一无二
        //找到字符串 查找是否存在于letter中
        //ch 有字母 数字 符号 空格四种类型
        
        unordered_set<char> sub; // 用 unordered_set 存储已经出现过的字符
        int max = 0;
        //滑动窗口
        int left = 0;
        for(int right = 0 ; right < s.size() ; right++){
            while(sub.find(s[right]) != sub.end()){
                //当右边界在substr中， 则左边界收缩
                sub.erase(s[left]);
                left++;
            }
            //如果不在 ，则插入当前字符
            sub.insert(s[right]);

            if(max < right - left + 1){
                max = right - left + 1;
            }
        }
        
        return max;
    }
};