C++ 代码(简单易懂的bfs版本)

// 使用层序遍历的方式序列化二叉树(bfs 版本)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string str;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)                                  // 空树的情况
        {
            str += "null ";
            return str;
        }

        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            auto node = q.front();
            q.pop();

            if(node == nullptr) str += "null ";
            else
            {
                str += (to_string(node->val) + ' ');
                q.push(node->left);
                q.push(node->right);
            }
        }

        return str;
    }

    int getval(string& data, int cur, int next)
    {
        int val = 0;
        if(data[cur] != '-')
            for(int i = cur; i < next; ++i) val = val * 10 + data[i] - '0';
        else
        {
            for(int i = cur + 1; i < next; ++i) val = val * 10 + data[i] - '0';
            val = -val;
        }

        return val;
    }
    // Decodes your encoded data to tree.
    // 思路：使用队列，从根节点开始，层层去构建二叉树的结点。
    TreeNode* deserialize(string data) {
        // 1. 先构建根节点
        queue<TreeNode*> q;
        auto root = new TreeNode(-1);
        int cur = 0, next = 0;
        while(next < data.size() && data[next] != ' ') next++;       // 此时 next 是第一个空格的位置
        if(data[cur] == 'n') return nullptr;
        else 
        {
            int val = getval(data, cur, next);
            root->val = val;
            q.push(root);
        }

        // 2. 使用队列逐步向下一层扩展(bfs)
        cur = next + 1;
        next = cur;
        while(q.size())
        {
            auto node = q.front();
            q.pop();
            if(node == nullptr) continue;

            // 解析左节点，解析后链接
            TreeNode* left = nullptr;
            while(next < data.size() && data[next] != ' ') next++;       
            if(data[cur] != 'n') 
            {
                int val = getval(data, cur, next);
                left = new TreeNode(val);
            }
            node->left = left;
            q.push(left);
            cur = next + 1;
            next = cur;

            // 解析右结点,解析后链接
            TreeNode* right = nullptr;
            while(next < data.size() && data[next] != ' ') next++;       
            if(data[cur] != 'n') 
            {
                int val = getval(data, cur, next);
                right = new TreeNode(val);
            }
            node->right = right;
            q.push(right);
            cur = next + 1;
            next = cur;
        }

        return root;
    }
};

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string str;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
       dfs(root);
       return str;
    }

    // 使用前序遍历序列化二叉树
    void dfs(TreeNode* root)
    {
        if(root == nullptr)            // 如果当前为空结点，那么将其序列化为 null;
        {
            str += "null ";
            return;
        }
        else                           // 当前不为空结点时，将结点中的值序列化为相应的值
            str +=  (to_string(root->val) + ' ');

        dfs(root->left);                // 递归处理左子树
        dfs(root->right);               // 递归处理右子树
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int cur = 0;
        return d_dfs(data, cur);
    }

    TreeNode* d_dfs(string data, int& cur)
    {
        if(cur >= data.size()) return nullptr;                // 字符串解析完毕，直接返回null;

        // 解析不同结点的字符串区间
        int c = cur;                                          // 根节点字符串的区间[cur, c - 1]
        while(c < data.size() && data[c] != ' ') c++;

        if(data[cur] == 'n') 
        {
            cur = c + 1;                                      // 当前为空结点，直接跳过处理下一个结点。
            return nullptr;
        }
        else
        {
            auto root = new TreeNode(-1);

            int val = 0;                                      // 处理正负数
            if(data[cur] == '-') 
            {
                for(int i = cur + 1; i < c; ++i) val = val * 10 + data[i] - '0';
                val = -val;
            }
            else
                for(int i = cur; i < c; ++i) val  = val * 10 + data[i] - '0';

            root->val = val;

            // 递归处理左子树，右子树
            cur = c + 1;
            root->left = d_dfs(data, cur);
            root->right = d_dfs(data, cur);     // 在处理右子树的时候，cur 已经被改变过了(左子树 null 那一步改变的)
            return root;
        }
    }
};
// 总结：本答案使用 "前序遍历" 序列化
// 本题难点在于对序列化后的字符串进行解析操作。对二叉树序列化的时候将空结点进行了 null 标记，这样才使得我们
// 可以利用一个序列构造出二叉树，因此，我们只需严格的按照 "根，左，右" 的方式一个值一个值(包括 null)来构建出
// 完整的二叉树。
// 实现细节: 在构建过程中由于全局只需要一个指针，利用指针严格的依次解析每一个值，因此我们对指针的传递使用引用传递。

11

C++ 代码(未使用库函数)

// 反转字符串的操作：
// 1. 先反转整个字符串。
// 2. 再逐个反转各个单词即可。
class Solution {
public:
    string reverseWords(string s) {
        if(!s.size()) return string();

        // 1. 反转整个字符串
        for(int i = 0, j = s.size() - 1; i <= j; i++, j--)
        {
            swap(s[i], s[j]);
        }

        // 2. 逐个反转各个单词
        int k = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] != ' ' && i != s.size() - 1) continue;          // 空格与字符串结尾都作为一个单词的结束。

            int j = 0;
            if(i != s.size() - 1) j = i - 1;                        // 当前为空格
            else j = i;                                             // 当前为字符串结尾   
            while(k <= j)
            {
                swap(s[k], s[j]);
                k++;
                j--;
            }

            k = i + 1;                                              // 跳到下一个单词的首位置
        }

        return s;
    }
};

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;

        // 求出两个链表的长度
        auto curA = headA, curB = headB;
        int lengthA = 0, lengthB = 0;
        while(curA) {curA = curA->next; lengthA++;}
        while(curB) {curB = curB->next; lengthB++;}

        // 较长链表先走差值步
        int n = abs(lengthA - lengthB);
        if(lengthA > lengthB) 
            while(n--) headA = headA->next;
        else 
            while(n--) headB = headB->next;

        // 两个链表一起走
        while(headA != headB)
        {
            headA = headA->next;
            headB = headB->next;
        }

        return headA;
    }
};

C++ 代码

// 快慢指针
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head) return nullptr;

        auto first = head, second = head;
        first = first->next, second = second->next->next;  // 方便进入循环
        while(first != second)
        {
            first = first->next;                           // 慢指针一次走一步
            second = second->next->next;                   // 快指针一次走两步

            if(!first || !second) return nullptr;          // 若没有环，则直接返回 nullptr
        }

        // 此时就是第一次的相遇点
        second = head;
        while(first != second)
        {
            first = first->next;
            second = second->next;
        }

        // 此时就是环入口
        return second;
    }
};

C++ 代码(简单易懂)

// 二叉树层序遍历的变形(null标记)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if(!root) return vector<vector<int>>();

        vector<vector<int>> res;
        vector<int> temp;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        int curnum = 0;                       // 统计当前二叉树的层数 
        while(q.size())
        {
            auto cur = q.front();
            q.pop();
            if(cur)
            {
                temp.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            else 
            {
                curnum++;
                if(curnum % 2 == 1) res.push_back(temp);
                else res.push_back(vector<int>(temp.rbegin(), temp.rend()));
                temp.clear();
                if(q.size())                  // 当前的null不是最后一个null继续加入，否则就不再加入null了。
                    q.push(nullptr);
            }
        }

        return res;
    }
};

C++ 代码

class Solution {
public:

    vector<int> printMatrix(vector<vector<int> > matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return vector<int>();

        vector<int> v;
        int n = matrix.size(), m = matrix[0].size();

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        vector<vector<bool>> flags(n, vector<bool>(m, false));            // 标记已经走过的位置
        int x = 0, y = 0;
        int k = 1;                                                        // 起始方向为 "右"
        for(int i = 0; i < m * n; ++i)
        {
            v.push_back(matrix[x][y]);
            flags[x][y] = true;
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || flags[nx][ny])   // 当前位置出界，改变方向
            {
                k = (k + 1) % 4;
                nx = x + dx[k], ny = y + dy[k];                           // 重新计算新坐标的位置
            }

            x = nx;                                                       // 合法坐标
            y = ny;
        }

        return v;
    }
};

(模拟法) $O(n)$

利用一个栈来模拟栈的压入与弹出操作,主要操作如下：栈初始为空，遍历push序列，依次将每个元素压入栈中，每次压入一个元素后，栈顶的元素是否与pop序列中的元素进行比较，如果相同，则弹出继续比较，如果不同则继续压栈。如果pop序列遍历完毕则正确，否则反之。

C++ 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        // 判断边界条件
        if(!pushV.size() && !popV.size()) return true;
        int n = pushV.size();
        int m = popV.size();
        if(n != m) return false;

        // 利用一个栈来模拟操作
        stack<int> stk;
        int i = 0, j = 0;
        while(j < m)
        {
            if(stk.empty() || stk.top() != popV[j])
            {
                stk.push(pushV[i]);
                ++i;
            }

            if(stk.top() == popV[j])
            {
                stk.pop();
                ++j;
            }
        }

        if(stk.empty())
            return true;
        else
            return false;
    }
};

C++ 代码

// 两栈实现一个队列(主栈，临时栈)
// 主栈：用来实现队列的基本操作
// 临时栈：当主栈操作 peek, pop 函数时，临时储存数据，操作完后再将数据拷贝到主栈中
class MyQueue {
public:
    stack<int> s, t;
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int n = s.size() - 1;           // 需要转移的个数
        while(n--)
        {
            t.push(s.top());
            s.pop();
        }

        int temp = s.top();
        s.pop();

        int m = t.size();
        while(m--)
        {
            s.push(t.top());
            t.pop();
        }

        return temp;
    }

    /** Get the front element. */
    int peek() {
        int n = s.size() - 1;           // 需要转移的个数
        while(n--)
        {
            t.push(s.top());
            s.pop();
        }

        int temp = s.top();

        int m = t.size();
        while(m--)
        {
            s.push(t.top());
            t.pop();
        }

        return temp;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

算法1

(哈希表统计次数) $O(n)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 判断边界条件
        for(auto e : nums)
        {
            if(e < 0 || e > nums.size() - 1)
                return -1;
        }

        // 哈希表统计数字个数
        int n = nums.size();
        unordered_map<int, int> hash(n);

        for(auto e : nums)
        {
            hash[e]++;
            if(hash[e] >= 2)
            {
                return e;
            }
        }

        return -1;
    }
};

算法2

(交换法) $O(n)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        // 判断边界条件
        int n = nums.size();
        for(auto e : nums)
        {
            if(e < 0 || e > n - 1)
                return -1;
        }

        // 交换法
        for(int i = 0; i < n; ++i)
        {
            while(i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if(i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];
        }

        return -1;
    }
};