Leetcode中级算法总结

数组与字符串

1三数之和 先排序再建立map进行查找，注意continue条件以防重复元素

2矩阵置零 仅用常量空间解决？将原矩阵的第一行和第一列作为记录，单独记录左上角

3字母异位词分组 将字符串排序后建立哈希表做搜索 sort(temp.begin(),temp.end());直接排序

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> answer;
        if(strs.size()==0)
            return answer;
        unordered_map<string,int> a;
        for(int i=0;i<strs.size();i++){
            string temp =  strs[i];
            sort(temp.begin(),temp.end());
            if(a.find(temp)==a.end()){
                vector<string> newvec{strs[i]};
                answer.push_back(newvec);
                a.insert(pair<string,int>(temp,answer.size()-1));
            }
            else{
                answer[a[temp]].push_back(strs[i]);
            }
        }
        return answer;
    }
};

4无重复字符的最长子串 快慢指针+建一个数组/哈希表做记录

5最长回文子串 中心扩散法/动态规划/马拉车

6递增的三元子序列 记录最小值和第二小值即可

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int l1=nums[0];int l2=INT_MAX;
        for(int i=1;i<nums.size();i++){
            if(nums[i]<=l1){
                l1=nums[i];
            }
            else if(nums[i]<=l2){
                l2=nums[i];
            }
            else
                return true;
        }
        return false;
    }
};

链表

1两数相加 建立新链表记录每位和，终止条件为某一链表到nullptr以及不进位

2奇偶链表

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==nullptr || head->next==nullptr || head->next->next==nullptr)
            return head;
        ListNode* oddHead = head;
        //奇数链表的当前节点
        ListNode* oddCur = oddHead;

        //偶数链表的头节点
        ListNode* evenHead = head->next;
        //偶数链表的当前节点
        ListNode* evenCur = evenHead;

        while (evenCur != nullptr && evenCur->next != nullptr) {
            //奇数节点串一起
            oddCur->next = oddCur->next->next;
            //偶数节点串一起
            evenCur->next = evenCur->next->next;
            //奇偶指针往后移
            oddCur = oddCur->next;
            evenCur = evenCur->next;
        }
        //最后偶数链表和奇数链表需要串在一起
        oddCur->next = evenHead;
        return oddHead;
    }
};

3相交链表 走到尾后从另一链表头开始，最终相交于交点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *l1=headA;
        ListNode *l2=headB;
        while(l1!=l2){
            if(l1->next==nullptr && l2->next==nullptr)
                return nullptr;
            if(l1->next==nullptr)
                l1=headB;
            else
                l1=l1->next;
            if(l2->next==nullptr)
                l2=headA;
            else
                l2=l2->next;
        }
        return l1;
    }
};

树和图

1二叉树的中序遍历 左中右

#递归解法
class Solution {
public:
    void order(TreeNode* currentNode,vector<int> &result){
        if (!currentNode)
            return;
        order(currentNode->left,result);
        result.push_back(currentNode->val);  
        order(currentNode->right,result);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        order(root,res);
        return res;
    }
};
#迭代解法
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return vector<int>();
        }
        vector<int> answer;
        stack<TreeNode*> stack0;
        while (root != nullptr || !stack0.empty()) {
            while (root != nullptr) {
                stack0.push(root);
                root = root->left;
            }
            if (!stack0.empty()) {
                TreeNode *node = stack0.top();
                stack0.pop();
                answer.push_back(node->val);
                root = node->right;
            }
        }
        return answer;
    }
};

2二叉树的锯齿形层次遍历

BFS解法
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> answer;
    if(root==nullptr)
        return answer;
    int index = 0;
    answer.push_back({ root->val });
    queue<TreeNode*> nodes;
    nodes.push(root);
    while (!nodes.empty()) {
        int size0 = nodes.size();
        vector<int> temp;
        stack<TreeNode*> s1;
        for (int i = 0; i < size0; i++) {
            s1.push(nodes.front());
            nodes.pop();
        }
        for (int i = 0; i < size0; i++) {
            TreeNode* temp_node=s1.top();
            s1.pop();
            if (index % 2 == 0) {
                if (temp_node->right != nullptr) {
                    temp.push_back(temp_node->right->val);
                    nodes.push(temp_node->right);
                }
                if (temp_node->left != nullptr) {
                    temp.push_back(temp_node->left->val);
                    nodes.push(temp_node->left);
                }
            }
            else {
                if (temp_node->left != nullptr)
                {
                    temp.push_back(temp_node->left->val);
                    nodes.push(temp_node->left);
                }
                if (temp_node->right != nullptr)
                {
                    temp.push_back(temp_node->right->val);
                    nodes.push(temp_node->right);
                }
            }
        }
        if(!temp.empty())
            answer.push_back(temp);
        index++;
    }
    return answer;
    }
};
DFS解法
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<deque<int>> res;
        travel(root,&res, 0);
        vector<vector<int>> res0;
        for(int i=0;i<res.size();i++){
            vector<int> temp(res[i].begin(),res[i].end());
            res0.push_back(temp);
        }
        return res0;
        }

    void travel(TreeNode* cur, vector<deque<int>>* res, int level) {
        if (cur == nullptr)
            return;
        //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
        if (res->size() <= level) {
            deque<int> newLevel;
            res->push_back(newLevel);
        }
        //遍历到第几层我们就操作第几层的数据
        deque<int> *list = &(*res)[level];
        //这里默认根节点是第0层，偶数层相当于从左往右遍历，
        // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
        // 要把数据添加到集合的开头
        if (level % 2 == 0)
            list->push_back(cur->val);
        else
            list->push_front(cur->val);
        //分别遍历左右两个子节点，到下一层了，所以层数要加1
        travel(cur->left, res, level + 1);
        travel(cur->right, res, level + 1);
    }
};

3从前序与中序遍历序列构造二叉树

解题关键：右节点永远都不可能比左节点先遍历

//四指针迭代解法
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
    TreeNode* root = new TreeNode(preorder[0]);
    if(inorder.empty())
        return root;
    btree(root, preorder, inorder, 0 , inorder.size()-1 ,0 ,inorder.size()-1);
    return root;
    }
void btree(TreeNode* root, vector<int>& preorder, vector<int>& inorder, int index1,int index2, int index3, int index4) {
    for (int i = index3;; i++) {
        if (preorder[index1] == inorder[i]) {
            if (i>index3) {
                TreeNode* left = new TreeNode(preorder[index1 + 1]);
                root->left = left;
                btree(left, preorder, inorder, index1 + 1 ,index1+i-index3 ,index3,i-1);
            }
            else {
                root->left = nullptr;
            }
            if (index4>i) {
                TreeNode* right = new TreeNode(preorder[index1+i-index3+1]);
                root->right = right;
                btree(right, preorder, inorder,index1 + i - index3 + 1, index2,i + 1 ,index4);
            }
            else {
                root->right == nullptr;
            }
            break;
        }
    }
}
};

持续更新。。。