头像

星火燎原_6




离线:13小时前


最近来访(23)
用户头像
微雨双飞燕
用户头像
Accepter
用户头像
yxc的小迷妹
用户头像
我要出去乱说
用户头像
cbatea
用户头像
AAAL
用户头像
Life_0
用户头像
dhxdl6666
用户头像
晨钟
用户头像
多多_0
用户头像
tuffynibbles
用户头像
雨耀
用户头像
年华_1
用户头像
向前看丶
用户头像
joker-zz
用户头像
追梦人..
用户头像
DinBong-hhh
用户头像
ζ肃ζ苑
用户头像
.yxc.
用户头像
wby0124


/*
    在最坏的情况下,那个出现次数超过数组一半的数,就算其余全部的数都来抵消它,也没有关系,它也还是会有剩余
    因为它已经超过数组的一半了,再怎么抵消都会有剩余的
    所以最后的那个数,就是出现次数最多的那个数

    总体思路就是:取一个数val,cnt=1,然后判断下一个数是否与其相同,相同就cnt加1,然后继续下去,如果一直相同就一直加,
    当然如果不小心碰到了不同的,那么就减1,减到为0的时候,val就要重新换新的值,并把cnt重新置为1
*/
class Solution {
public:
    unordered_map<int, int> m;
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0, val = -1;
        for(auto x : nums) {
            if(!cnt)    val = x, cnt = 1;   // 如果减到为0,val就重新取一个数,并把cnt重置为1
            else {
                if(x == val)    cnt++;
                else cnt --;
            }
        }
        return val;
    }
};

截屏2022-12-05 11.47.32.png



活动打卡代码 LeetCode 14. 最长公共前缀

/*
    第一重循环就是枚举一下当前有多少个字符,第二重循环就是枚举一下有多少个字符串,看一下所以字符串的这个字符是不是一样的
    前缀的子串一定要连续
    不连续的话就成了一个dp问题了,非常复杂
*/
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if(strs.empty())    return res;

        for(int i = 0; ; i++) {
            if(i >= strs[0].size()) return res;
            char c = strs[0][i];    //获取第一个字符串的第i个字符
            for(auto& str: strs)  // 枚举一下后面的字符串
                if(str[i] != c || str.size() <= i )  // 判断后面i和字符串大小的关系,判断每个字符串第i个字符和第一个字符串第i个字符是否不等,如果不等就直接返回
                    return res;
            res += c;   // 否则的话就表示满足条件,将此前缀元素添加到字符串中
        }
        return res;
    }
};


活动打卡代码 AcWing 51. 数字排列

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> nums;
    vector<bool> st;

    vector<vector<int>> permutation(vector<int>& _nums) {
        nums = _nums;
        st = vector<bool> (nums.size(), false);     
        sort(nums.begin(),nums.end());  //由于要去重,故得先排序
        dfs(0);
        return res;
    }

    void dfs(int u)
    {
        if(u == nums.size())
        {
            res.push_back(path);
            return;
        }

        for(int i=0; i< nums.size(); ++i)
        {
            if(!st[i])
            {
                if(i>0 && nums[i] == nums[i-1] && !st[i-1])     // 去重
                    continue;
                st[i]=true;
                path.push_back(nums[i]);
                dfs(u+1);
                path.pop_back();
                st[i]=false;
            }
        }
    }
};

WechatIMG2720.jpeg
截屏2022-11-28 15.34.35.png



活动打卡代码 AcWing 50. 序列化二叉树

 [二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解](https://blog.csdn.net/u013834525/article/details/80421684) 

序列化是指,将二叉树的输出转成字符串形式
反序列化是指,将字符串形式的输出转成二叉树的形式输出

截屏2022-11-28 10.31.12.png

/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;     // 把序列化的答案放到res中去
        dfs_s(root, res);
        return res;
    }

    // 前序遍历
    void dfs_s(TreeNode *root, string &res)
    {
        if (!root) {    // 如果说根节点是空的,那么就在结果res中加入“null ”
            res += "null ";     
            return;     // 然后返回
        }
        res += to_string(root->val) + ' ';  // 根节点,用空格隔开
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;  // 从第0个位置开始
        return dfs_d(data, u);
    }

    // 反序列就比较麻烦,因为它需要将字符转成整数
    TreeNode* dfs_d(string data, int &u)    // 所有递归的时候,u都是同一个u,牵一发而动全身
    {
        if (u == data.size()) return NULL;  // 序列完后,到最后一个点以后,说明没有了已经,就返回空就行了
        // 否则就把下一个元素取出来
        int k = u;
        while(data[k] != ' ') k++; //k记录当前数字的位数如134是个三位数的数字,56是个两位数的数字,退出的时候,k指向了字符后面的空格,所以回到下个字符的首部需要加1.
        // k指向了字符后面的空格,这句话要重点注意

        if(data[u] == 'n') {    //如果当前字符串是“null”
            u = k+1;    //回到下一个数字的首部,注意是u = k+1, 不是u = u+1;
           // cout << "k = " << k <<endl;
            return NULL;    //表示这次构造的是一个null节点,并没有孩子节点,所以跳过后面的递归
        }
        // 否则的话,当前节点就是一个数字,我们需要把这个数字给算出来
        int val = 0, sign = 1;  
        if (data[u] == '-') sign = -1, u ++ ;   // 如果为负数
        for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
        // 将字符串转成整数
        // 也就是把整体往前面移动一下,把个位空出来,让个位能够填充数字
        val *= sign;
        u = k + 1;  // 把u放到下一个字符的首部位置上去
        // 因为是按前序遍历“加密”的,所以这里也按前序遍历“解密”,这样取的顺序就跟原来的一样了
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);
        return root;
    }
};

截屏2022-11-28 13.33.49.png

问题1、在反序列化函数里面,为什么while(data[k] != ‘ ‘) k++的时候,难道不会担心k跳出去吗?越界了怎么办?
答:其实在后面if(data[u] == ‘n’)的时候,就是面对最后一个字符“null”,最后一个一定是“null”,会直接return出来,所以不会再进行递归下去,这样的话,k的指向也就停留在“null”前面的一个空格上,也就不会为了寻找空格而越界了。

一般来说,这里加上个k < data.size()这个判断条件会更好。

2、TreeNode* dfs_d(string data, int &u) 为什么参数u要取&引用
截屏2022-11-28 14.10.28.png
截屏2022-11-28 14.10.55.png




力扣题解

/**
 * 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:
    TreeNode *head, *pre; // 创建两个指针,只会指向已有节点
    TreeNode* convert(TreeNode* root) {
        if (root == NULL) return root;

        dfs(root);
        return head;        
    }

    void dfs(TreeNode* cur) {
        // 中序遍历
        if (cur == NULL) return;
        // 左子树:可认为左半边已经处理好(最左点是head,最右点是pre)
        dfs(cur->left);

        // 根节点:将当前的cur加入到左半边
        if (head == NULL && pre == NULL) { // 递归到最左边的特殊情况 // 如果你们两个指针什么都没有,就来指向我吧,起码你们有个去处
            head = cur;     // 这里应该也就是一开始进入到这个函数来的时候,head和pre都是空,让head指向cur,也就是指向头节点
            pre = cur;
        } else {  // 将当前的cur加入到左半边    // 这里的pre是表示前面指针的意思,这里的pre已经是有指向了的,不是空的
            pre->right = cur;
            cur->left = pre;
            pre = cur;
        }

        // 右子树
        dfs(cur->right);
    }
};

截屏2022-11-27 15.42.42.png
截屏2022-11-27 16.14.56.png



活动打卡代码 LeetCode 51. N 皇后

WechatIMG2706.jpeg

class Solution {
public:
    int n;
    vector<bool> col, dg, udg;
    vector<vector<string>> ans;
    vector<string> path;

    void dfs(int u) {
        if(u == n) {    // 如果说搜到了最后一行的后面一行,那么就说明找到一个解,就在答案里面加入一个解
            ans.push_back(path);
            return ;
        }

        for(int i = 0; i < n; ++i) {    // 枚举每一列
            if(!col[i] && !dg[u - i + n] && !udg[u + i]) {  //如果这一列没有皇后,且对角线上也没有皇后
                col[i] = dg[u - i + n] = udg[u + i] = true;
                path[u][i] = 'Q';   // 把u行i列这个方案记录一下
                dfs(u + 1);     // 搜索下一行
                path[u][i] = '.';   // 搜索完之后记得恢复一下现场
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
    }



    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        // 对数组进行初始化
        col = vector<bool>(n);  
        dg = udg = vector<bool>(n*2);       // 正对角线是2*n-1条,负对角线也是2*n-1条
        path = vector<string> (n, string(n, '.'));      // 初始化为点

        dfs(0); // 从第0行开始搜
        return ans; // 搜完之后就返回答案
    }
};

截屏2022-11-27 13.08.18.png
截屏2022-11-27 15.16.32.png




截屏2022-11-27 11.07.32.png

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        // 新创建一个节点与第一个节点相同,插入在第一个节点和第二个节点之间,后面依次类推
        for (auto p = head; p;)
        {
            auto np = new ListNode(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        for (auto p = head; p; p = p->next->next)
        {
            if (p->random)
                p->next->random = p->random->next;      // 让复制产生的节点的随机指针跟原来节点的随机指针指向同样的东西,只是这个东西是复制产生的
        }

        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next)     // 这里的p = p->next是说让p这个指针指到某个节点上,注意要与p的next指针区分开来哦!!
        {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;    // 恢复原链表
        }

        return dummy->next;
    }
};



vector中的函数pop_back

/**
 * 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>> ans;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root, sum);     // 这里不采取加的方法,采用减,能够少写一个变量
        return ans;
    }

    void dfs(TreeNode* root, int sum) {
        if(!root)   return;
        path.push_back(root->val);
        sum -= root->val;
        if(!root->left && !root->right && !sum) ans.push_back(path);
        // 遍历到叶节点的时候,就判断一下当前路径是不是满足,如果满足,就把当前路径记录下来
        // 也就是说找到了一条合法的路径,就把它添加到ans答案中去
        if(root->left) dfs(root->left, sum);    // 所有的路径都包含根节点,所以传入的sum不用恢复原来的值
        if(root->right) dfs(root->right, sum);
        path.pop_back();    // 不光会遍历一个分支,还会去遍历其它分支,所以在遍历完当前子树之后,一定要把path清空一下
        // pop_back主要是除去本次添加的这个节点
        // 在回溯过程中,会不断pop_back把path里面的节点给删除掉,因为path在清除之前已经添加到了ans中去,所以不用担心path被清除却没有添加到ans的情况
    }
};

截屏2022-11-27 10.10.16.png
截屏2022-11-27 10.15.12.png