头像

我要出去乱说

凯里学院 => 贵州大学




离线:7小时前


最近来访(491)
用户头像
等雨停
用户头像
thunderclouds
用户头像
空银子
用户头像
chen_
用户头像
蓬蒿人
用户头像
张顺飞
用户头像
Stella-W
用户头像
Tilbur
用户头像
fengwei2002
用户头像
秋寒
用户头像
zhangjh024
用户头像
艾西韵
用户头像
努力ing
用户头像
sunny_cx
用户头像
liuxiaocs
用户头像
Syseg
用户头像
诺亚方舟.
用户头像
lcf_ac
用户头像
枫玥
用户头像
AKIMIZU_

新鲜事 原文

这两天我老是去麻烦硬件部的两位同事,请他们帮忙升级设备。下午我去取设备的时候顺便买了两杯奶茶送过去,结果他俩一看到我拿东西来,非常惶恐,疯狂摆手说使不得使不得,不用不用都是我们应该做的,你收起来吧我正在工作,反正说什么都不肯收。场面变得非常尴尬,弄得我像行贿的人一样。。最后没办法,我只能把奶茶收起来灰溜溜地走了。



首先要明确一点:只有一种情况会导致小行星发生碰撞,那就是当前小行星往左飞行,而上一个小行星往右飞行时。
思路:

  1. 遍历小行星数组,遇到往右飞行的小行星直接入栈,因为假设速度相同,往右飞的行星都不会发生碰撞;

  2. 当遇到往左飞的小行星时,表示可能会发生碰撞,这时循环判断栈顶小行星是否大于当前小行星,比当前小行星小的全都原地爆炸,直到遇到比当前小行星大的把当前小行星撞碎为止,或者栈空为止;

  3. 这里还需要额外判断两颗相撞小行星大小相等的情况,会同时爆炸;

  4. 最后栈中剩余的小行星就是永远不会发生碰撞的小行星。

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> res;                //我们用数组模拟栈

        for (int &item : asteroids)     //遍历小行星
        {
            //栈不为空,栈顶小行星向右飞行,当前小行星向左飞行且栈顶小行星较小的情况,栈顶小行星爆炸
            while (!res.empty() && res.back() > 0 && res.back() < -item)
            {
                res.pop_back();
            }

            //栈不为空,当前小行星向左飞行,且俩行星大小相同的情况,同时爆炸
            if (!res.empty() && item < 0 && res.back() == -item)
            {
                res.pop_back();
            }

            //1、若当前小行星向右飞行,不用管栈顶小行星的飞行方向,它肯定不会与栈顶小行星相撞;
            //2、栈为空时,当前小行星入栈;
            //3、若栈顶小行星向左飞行,不用管当前小行星的飞行方向,它肯定不会与栈顶小行星相撞;
            else if (item > 0 || res.empty() || res.back() < 0)
            {
                res.push_back(item);
            }
        }

        return res;
    }
};


新鲜事 原文

最近经理看我好像不太顺眼,我部门14个人就我一个实习生,平时就打打杂帮领导写写文档,在公司已经很久没写代码了。可能是记忆力或理解能力不太好,每次经理对我巴拉巴拉说一堆任务,我总记不住,事后又反复找他确认,结果把他惹毛了。今天中午经理突然又让我改文档,不太耐烦地说了一堆怎么改,当时我非常紧张,感觉已经有PTSD了,心想这次一定要做好,但是实在太紧张了,虽然有的地方不太确定,但也不敢问,怕问了又会被喷。交代完任务经理又吐槽说我肯定记不住,让我再复述一遍任务,我磕磕巴巴地重复了一遍,还在手机上打字速记了一下,才算混过去。但是真的改起文档来,还是有很多不确定的东西,可我不敢问啊,心想完了完了这次又要被骂了。果然经理过来一看,我这改的什么玩意儿,直接在工位上就开喷了,原话是:“跟你交代点事儿怎么就那么费劲呢?你到底听没听懂啊?”我又赶紧解释,继续询问改动细节,及时补救,最后终于改好了,但感觉领导已经对我失去信心,不再相信我能好好完成工作了。。哎。 想问下有工作经验的xdm,遇到这种情况要如何缓解跟领导的关系啊,我现在都不敢正眼看经理了。 贴两张图,今天跑闪送路过Oracle和IBM,IBM的大楼真气派,椭圆形的只有两层,超级长。
图片 图片



逆波兰表达式。思路:

遍历字符串数组,遇到数字就存入栈中,遇到运算符就把栈顶两个元素取出来计算,得出结果后再推入栈顶。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.empty()) return 0;

        stack<int> stk;
        int res = 0;
        for (int i = 0; i < tokens.size(); ++ i)
        {
            string str = tokens[i];
            if (str == "+" || str == "-" || str == "*" || str == "/")
            {
                int a = stk.top();                      //取得栈顶的两个数
                stk.pop();
                int b = stk.top();
                stk.pop();

                if (str == "+") stk.push(b + a);        //计算结果,再推入栈
                else if (str == "-") stk.push(b - a);
                else if (str == "*") stk.push(b * a);
                else if (str == "/") stk.push(b / a);
            }
            else                        
            {
                stk.push(stoi(str));    //当前为数字就直接入栈,为运算符就出栈两个数来计算
            }
        }
        res = stk.top();                //最后剩下的栈顶元素即是逆波兰表达式的计算结果
        return res;
    }
};



思路:

  1. 一天有24小时,1440分钟,开一个1440长度的布尔数组模拟哈希表,把时间换算成0~1439之间的数值,将数值对应数组中的位置设置为true
  2. 遍历数组,找离得最近的两个时间点。
class Solution {
private:
    const int maxDiffTime = 1440;

public:
    int findMinDifference(vector<string>& timePoints) {
        //大于1440个时间,必有两个时间是重复的,即最小间隔为0
        if (timePoints.size() > maxDiffTime) return 0; 

        bool minuteFlags[1440] = {0};    //不要用vector来存bool类型的值,因为不安全,取地址会报错
        for (string& time : timePoints)
        {
            //将字符串表示的时间转换成总的分钟数
            int minute = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
            if (minuteFlags[minute]) return 0;  //若该时间在数组中出现过,则最小时间间隔为0
            minuteFlags[minute] = true;
        }

        //以上是一些优化操作,下面才开始遍历数组找最小间隔
        return helper(minuteFlags);
    }

    int helper(bool minuteFlags[])
    {
        int minDiff = maxDiffTime - 1;      //最小时间间隔初始化为最大
        int prev = -1;
        int first = maxDiffTime - 1;        //first表示数组中最早的时间,last表示最晚的时间
        int last = -1;                      //主要是为了计算00:00与23:59这类情况的

        for (int cur = 0; cur < maxDiffTime; ++ cur)
        {
            if (minuteFlags[cur])
            {
                if (prev >= 0) minDiff = min(minDiff, cur - prev);

                prev = cur;                 //更新上一节点,first和last节点
                first = min(first, cur);
                last = max(last, cur);
            }
        }

        //计算00:00与23:59这类情况
        minDiff = min(minDiff, first + maxDiffTime - last);
        return minDiff;
    }
};



思路:
1. 数组模拟哈希,数组下标代表字母,值代表该字母在字母表中的位置;
2. 扫描两个单词中的字母找出第一个不相同的字母,哪个单词中第一个不相同的字母位置靠前,排序的时候它就在前面,如果没有找到不相同的字母,那么短的单词排在前面。

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> orderArray(26, 0);
        for (int i = 0; i < order.length(); ++ i)
        {
            orderArray[order[i] - 'a'] = i;                 //数组模拟哈希
        }

        for (int i = 0; i < words.size() - 1; ++ i)
        {
            if (!isSorted(words[i], words[i + 1], orderArray))
            {
                return false;
            }
        }

        return true;
    }

    bool isSorted(string& word1, string& word2, vector<int>& orderArray)
    {
        int i = 0;
        for (; i < word1.length() && i < word2.length(); ++ i)
        {
            if (orderArray[word1[i] - 'a'] > orderArray[word2[i] - 'a'])
            {
                return false;
            }
            if (orderArray[word1[i] - 'a'] < orderArray[word2[i] - 'a'])
            {
                return true;
            }
        }
                                        //退出循环时,i等于俩单词中较短单词的长度
        return i == word1.length();     //短的单词应该排前面,所以最后要判断前面的单词是否是短的
    }
};



如果一组词是异位词,那么将每个词的字母排序后的它们结果是一样的。建一个哈希表,键是排序后的词(字符串),值是原始的词所组成的集合(字符串数组),它们是同一组异位词。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hash;

        for (string& s:strs)                    //遍历每个单词
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());       //将当前单词内的字母排序
            hash[tmp].push_back(s);             //将原始单词存入属于它的异位词组中
        }                                       //hash[tmp]表示tmp这组异位词的集合

        for (auto& vec : hash)                  //遍历哈希表,将值存入结果集中
        {
            res.push_back(vec.second);
        }

        return res;
    }
};



只有小写字母,可以用长度为26的数组模拟哈希表。

class Solution {
public:
    bool isAnagram(string s, string t) {
        //字符串长度不同,或者完全相同,都不属于异位词
        if (s.length() != t.length() || s == t) return false;

        vector<int> hash(26, 0);
        for (int i = 0; i < s.length(); ++ i)   //先把第一个字符串放入哈希表
        {
            hash[s[i] - 'a'] ++ ;
        }

        for (int i = 0; i < t.length(); ++ i)   //在哈希表中减去第二个字符串
        {
            if (hash[t[i] - 'a'] == 0) return false;
            hash[t[i] - 'a'] -- ;
        }

        return true;
    }
};



使用双链表+哈希表实现,之所以不用单链表,是因为在实现删除节点的操作时双链表只需要$O(1)$的时间复杂度。

class LRUCache {
public:
    struct Node     //构造双链表结构体
    {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val):key(_key), val(_val), left(nullptr), right(nullptr){}
    }*L, *R;

    unordered_map<int, Node*> hash;     //哈希表的键是val,值是结构体Node,即(key, val)键值对
    int n;                              //n表示哈希表的容量大小

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);     //初始化双链表的两个哨兵节点
        L->right = R, R->left = L;                      //哨兵节点最初互相指向
    }

    void remove(Node* p)                //删除一个节点
    {
        p->left->right = p->right;
        p->right->left = p->left;   
        //注意这里不能delete p,因为p节点并不是真的删除掉不用了
        //可能仅仅只是从当前的位置中抽离出来,会再放到双链表头部
    }

    void insert(Node* p)                //在双链表头部插入一个节点
    {
        p->left = L;
        p->right = L->right;
        L->right->left = p;
        L->right = p;
    }

    int get(int key) {
        if (!hash.count(key)) return -1;

        Node* p = hash[key];
        remove(p);                      //删除又插入等于更新该节点到链表头部
        insert(p);
        return p->val;
    }

    void put(int key, int value) {
        if (hash.count(key))            //若待插入值已存在
        {
            Node* p = hash[key];
            p->val = value;             //则更新其值
            remove(p);
            insert(p);
        }
        else                            //若待插入值不存在,分两种情况
        {
            if (hash.size() == n)       //1.若哈希表已满,则删除链表尾元素再插入
            {
                Node* p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }                           //2.若哈希表未满,构造新节点直接插入
            Node* p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};



本题有两个难点:随机返回元素和用$O(1)$时间删除数组中元素,解决思路如下:

  1. 随机返回元素,使每个元素有相同的概率返回

    如果只用哈希表则不能等概率返回其中的每个数值,如果数值是保存在数组中的话,那么就可以通过rand()函数轻易做到等概率返回。我们开一个数组来存数值,并在哈希表中储存每个数值及其在数组中的下标。

  2. 在$O(1)$时间复杂度内删除数组中元素

    如果直接remove数组中的元素,那么数组中后面的元素会向前移动,时间复杂度为$O(n)$。我们需要先从哈希表中得到待删除数字的下标,将数组中该下标元素与数组末尾元素调换位置,再删除数组末尾元素,这样就做到了时间复杂度$O(1)$的删除。

class RandomizedSet {
private:
    unordered_map<int, int> hash;
    vector<int> nums;

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (hash.count(val)) return false;  //哈希表中已存在该数值,不用再插入

        hash[val] = nums.size();            //哈希表的键是数值,值是数值在数组中的位置
        nums.push_back(val);                //数值放入数组中
        return true;
    }

    bool remove(int val) {
        if (!hash.count(val)) return false; //哈希表中不存在该数值,无法删除

        nums[hash[val]] = nums.back();      //将数组尾部的数值放到待删除数值的位置
        hash[nums.back()] = hash[val];      //在哈希表中更新原数组尾部数值的位置
        hash.erase(val);                    //从哈希表中删除该数值
        nums.pop_back();                    //从数组中删除该数值
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];  //随机返回集合内一数值
    }
};