2021.11.21 559.N叉树的最大深度

题目

思路

?①深度遍历

②广度优先遍历：每次出队要把队列所有的元素拿出来。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int max_depth = 0;
    int maxDepth(Node* root) {
        dfs(root,0);
        return max_depth;
    }
    void dfs(Node* root,int height){
        if(root == NULL) return;
        height += 1;
        max_depth = max(max_depth,height);
        vector<Node*> _children = root->children;
        for(int i = 0; i < _children.size(); i++) {
            dfs(_children[i],height);
        }
    }
};

2021.11.22 384.打乱数组

题目

思路

打乱方法：初始时waiting设置为初始化的数组，循环n次，第i次时，从waiting中随机抽取一个数num，将shuffle的第i个数设置为num，然后从waiting中把num删除。

class Solution {
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
    vector<int> shuffle() {
        vector<int> shuffled = vector<int>(nums.size());
        list<int> lst(nums.begin(), nums.end());
      
        for (int i = 0; i < nums.size(); ++i) {
            int j = rand()%(lst.size());
            auto it = lst.begin();
            advance(it, j);
            shuffled[i] = *it;
            lst.erase(it);
        }
        copy(shuffled.begin(), shuffled.end(), nums.begin());
        return nums;
    }
private:
    vector<int> nums;
    vector<int> original;
};

改进

class Solution {
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
    
    vector<int> shuffle() {
        for (int i = 0; i < nums.size(); ++i) {
            int j = i + rand() % (nums.size() - i);
            swap(nums[i], nums[j]);
        }
        return nums;
    }
private:
    vector<int> nums;
    vector<int> original;
};

2021.11.23 859.亲密字符串

题目

?思路

①首先判断两个字符串是否相等，如果相等的话再判断字符串是否有某个字符出现的次数超过1。

②如果两个字符串不想等的话，用下标first和second记录字符串对应位置不相等的下标，遍历一遍字符串，只有当first!=-1&&second!=-1时，而且对应位置的字符能够交换才返回true，其余都返回false。

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.size() != goal.size()) {
            return false;
        }
        
        if (s == goal) {
            vector<int> count(26);
            for (int i = 0; i < s.size(); i++) {
                count[s[i] - 'a']++;
                if (count[s[i] - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        } else {
            int first = -1, second = -1;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] != goal[i]) {
                    if (first == -1)
                        first = i;
                    else if (second == -1)
                        second = i;
                    else
                        return false;
                }
            }

            return (second != -1 && s[first] == goal[second] && s[second] == goal[first]);
        }
    }
};