205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,

Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Note:

You may assume both s and t have the same length.

最初的思路和290. Word Pattern差不多,只是把字符串s当做那道题中的字符串pattern,而把字符串t当做那道题中的str即可,建立从s到t的一个映射,之后排除掉一些需要返回false的情况即可,代码如下:

/*solution1,use two unordered_map,24ms*/
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if(s.size()!=t.size())
            return false;
        unordered_map<char,char> hash;
        int i=0;
        for(i=0;i<s.size();i++){
            if(hash.find(s[i])!=hash.end()){
                if(hash[s[i]]!=t[i])
                    return false;
            }
            else{
                for(unordered_map<char,char>::iterator it=hash.begin();it!=hash.end();it++){
                    if(it->second==t[i])
                        return false;
                }
                hash[s[i]]=t[i];
            }
        }
        return i==s.size();
    }
};

可以看出,两道题的代码极其相似,由于用了两个哈希表,所以运行时间较长,那么我们考虑到这道题给出的测试样例中应该都是 ASCII编码的字符,于是我们可以运用之前学到的使用数组代替哈希表的技巧来优化这个算法。代码如下:

/*solution2,use two arrays,8ms*/
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int map1[256]={0},map2[256]={0},i=0;/*数组要初始化为0*/
        for(i=0;i<s.size();i++){
            if(map1[s[i]]!=map2[t[i]])/*如果s中的字符映射之后和t中字符映射之后不相等,则返回false;
			                           首次进入循环时,两个字符映射之后的值都为0,所以不会返回false*/
                return false;
            map1[s[i]]=map2[t[i]]=i+1;/*否则将其更新为同一个值*/
        }
        return i==s.size();
    }
};

知识共享许可协议
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。

你为什么招不到人?那些搞通信的都去哪了?

image 前几天,有个兄弟叫我帮他招100人,我信心满满地答应了他,结果却令人沮丧,只招到了10人。

我发誓再也不发招聘信息了,这打击太大了。

是夜,辗转伏枕,无法入眠。那些通信人都到哪里去了?祖国的通信事业到底怎么了?我陷入了沉思,一支接一支的猛抽着烟,思绪穿透过缭绕的烟雾,来到两年前的一个清晨。

还没起床的我突然接到一个电话,那头传来一个怯生生而又熟悉的声音:

“X总,我… 我要离职。”

话音刚落,空气瞬间凝固了,能清晰的听见电话里的电流声。

电话的那头是一个工作三年的年轻通信工程师。我太熟悉了,当年是我亲自面试的,面试场景记忆犹新。

那是一个晴朗的下午,我们对坐在公司的小会议室里,透过窗外,楼下车水马龙,川流不息,而我的双眼没有离开过他半秒。

他的眼神,他的味道,太熟悉了。我欣喜若狂,已经很久没有闻到这样的味道了,那是一个通信工程师的味道,我以一个老通信狗敏锐的嗅觉告诉自己。

接下来的面试,这厮果然骨骼生的清奇,一定是个干通信的奇才。

祖国的通信事业终于后继有人了,我差点没叫出来,长舒一口气,整个人都轻松了,笑脸凝固了一下午,仿若电影里经常看到的那种含笑而死。

接下来,我给他安排了最优秀的导师,最刁难的项目。天降大任与斯人也,必先苦其心志,劳其筋骨…

年轻人,未来的通信事业就靠你了。

可是,今天,他居然向我提出辞职。

不行,为了祖国的通信事业,我决不答应,祖国人民也不会答应。

我苦口婆心,软硬兼施,威逼利诱,和他讲了一大通道理。

他似乎很平静,一直静静的听我装逼。

等我口也干了,词也穷了,他终于开口了。

“你讲的道理我都懂,但是,没用的,我必须走,没有办法,我也不想。”

大哥,你不早说。

接下来,他竟然跟我讲述了一个在台湾青春偶像剧里经常出现的桥段:

一个富二代,挣脱了父亲为他设计的人生道路,拒绝继承家族事业,为了理想,毅然走上苦逼的通信之路。

他讲得声泪俱下,不禁为之动容。(果然是个干通信的奇才)

接下来剧情发生了转折。

他那富一代老爸连续三天给他打电话,打电话的时间选择也真巧,凌晨2点左右,结果真不巧,这位满怀梦想的年轻人刚好连续三天加班到凌晨2点。

事情闹大了。家里人一致决定不能让他再干通信,包括了最疼爱他的爷爷、奶奶、姥姥、姥爷。

但年轻人依然不屈,坚持要为祖国的通信事业奋斗终身。此处应该有掌声!

然而,他终于还是被最后的那根稻草压垮了,那是他老妈一句话:

你都做通信三年了,你的成绩在哪里?你职位提升了多少?你薪水又上涨了多少?

年轻人终于扛不住了,他倒下了,潸然泪下,作别通信,再见理想。

一位通信奇才就这样离开了他心爱的通信,留下了背影。

我望着他的背影,那一刻,我感觉好孤独,有点冷。

我甚至感觉到了这个行业有点青黄不接。当年那些一起打拼的兄弟们,如今还坚守通信的剩下几个?但凡有点门路的,早就不干了。而那些新进的年轻工程师们,离职率越来越高,和以往从一家通信公司跳到另一家通信公司不同,很大一部分是选择离开了这个行业,跳出三界之外。

是因为这行太苦太累吗?不,我都干上通信了,你竟然跟我讲苦讲累?

那句名言说得好,原因只有两点:钱没给够,心委屈了。

钱没给够吗?

这几年,通信业收入整体确实在下滑,这是不争的事实,但这种下滑绝不是断崖式的。总体来说,还是能维持在社会平均水平之上,我想这不至于让那些温水里的青蛙都死命挣扎往外跳,何况那些年轻的工程师,没有经历过通信业辉煌时期,内心的落差也不会太大。

剩下的原因只有一个了:心委屈了。

心是怎么委屈的?这个问题很复杂,在通信产业链条里,不同的环节情况不一样。举例聊一聊乙方和第三方,因为招人难这个问题在产业链的中下游尤为突出,这也是通信工程师的集中地。

有个已转行互联网的朋友告诉我,现在做互联网也很累,经常加班。但相比通信,没那么多瞎折腾,更新鲜有趣,让他每天充满希望。

他说,以前做通信项目,总是无数次的重复着这样的场景:项目来了就赶标,投标,结果中标了又哭没人用,赶紧招人,人招到了,上项目了,又哭客户考核严,人不好使,得撤掉重新招人。

折腾。

而这种折腾最受伤的还是一线的兄弟们。

一线的工程师们是怎样受伤的?我们这次不谈KPI,不谈加班,也不谈钱,太俗套,我们来讲点新鲜的 — 项目结构。

以网优项目为例,大部分都是单价合同。所谓单价合同,就是预先定好了每个工程师的单价,一个中级工程师每月多少钱,一个高级工程师每月又是多少钱,项目合同额就等于各个工程师的单价乘以工程师数量,再乘以项目时间的总和。

就是卖人合同。

这种合同方式比较省事,对甲乙双方来说风险都是最小的。当然,这种计算方式更透明,更容易控制成本,让投机者毫无空隙可钻。

但这对于工程师,特别是年轻的工程师们,是不幸的。

这种合同方式注定了项目人员配置就是一个萝卜一个坑。如果你是一个初级工程师,只要在这个项目上,几乎没有升级中级工程师的机会。

因为一旦项目中有一个初级工程师升级为中级,这就超出了项目范围。在这个成本为先的时代,没有人愿意自掏腰包补这个差价,甲方不愿意,乙方不愿意,丙方更不愿意。

当然,也有一种可能。某个中级工程师离职了,机会来了,另一个初级工程师顶上去。但是,既然你能升级到中级,说明你在初级这个位置干得还是不错的,既然你这颗萝卜把坑填得这么好,我又何必把你拔出来呢?况且,我拔了你这颗萝卜还得找另一颗萝卜来填你留下的坑,万一新填的那颗萝卜尺寸不符呢?得了,你还是在你的坑里老老实实待着吧,我从外面再招一个中级工程师。省心省事。

于是,那个本来可以荣升中级的初级工程师就悲催了,继续每天枯燥的跑着路测、上站掰天线。暗无天日。

有一天,他终于受不了了。在某个基站的天台上,对着天空怒吼:为什么?为什么?老天大概被他的愤怒吓坏了,那头并没有传来回音。

年纪人终于清醒的认识到:靠天是靠不住的,只能靠自己了。

于是,他辞职了,离开了通信,留下一个坑。

后来,另一个年轻人走了过来,跳进了这个坑,不过,他的命运与前任出奇的相似。

这个故事告诉我们,看不到希望有多可怕,有多委屈。

是的,他们看不到希望。我指的希望没有眼过风云千樯那么远,我指的是眼前的希望。不要跟我提通信的未来有多么美好,万物互联如何无穷如天地,如果我连伸手都看不见五指,我如何知道前方的路在哪里?

希望是一个好东西,但绝望的人不屑拥有它。

领导们,规则制定者们,多看看那些一线的工程师们吧!他们的要求其实并不高,无非就是能看到点点希望。

竭泽而渔,岂不获得?而明年无鱼。

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true.

pattern = “abba”, str = “dog cat cat fish” should return false.

pattern = “aaaa”, str = “dog cat cat dog” should return false.

pattern = “abba”, str = “dog dog dog dog” should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

这道题需要我们对给定的字符串进行判断,判断其是否符合一个模式(其实小学语文中就有这个概念),那么主要的思路还是使用一个哈希表建立起pattern字符串和需要判断的字符串的映射即可。

建立之后,我们首先查找pattern字符串的元素是否存在于哈希表中,如果存在,则判断其映射的字符串是否和当前字符串相等,若不相等,则返回false;

如果第一步判断出不存在,则需要遍历整个哈希表,判断其映射的字符串是否存在于哈希表中,如果存在,则返回false,否则,才可以将这个pattern字符串及其映射的字符串加入到哈希表中去。

最后返回true的条件是i==pattern.size(),因为只有完成整个循环后才能说明是完全匹配的,代码如下:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char,string> hash;
        istringstream in(str);/*构造字符串流时,空格会成为其内部分界,这也是拆分含有空格的字符串的方法之一*/
        int i=0;
        for(string word;in>>word;i++){
            if(hash.find(pattern[i])!=hash.end()){
                if(hash[pattern[i]]!=word)
                    return false;
            }
            else{
                for(unordered_map<char,string>::iterator it=hash.begin();it!=hash.end();it++){
                    if(it->second==word)
                        return false;
                }
                hash[pattern[i]]=word;
            }
        }
        return i==pattern.size();
    }
};

299. Bulls and Cows

You are playing the following Bulls and Cows game with your friend:

You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"

In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

一个定义新运算的问题,本质上是对两个字符串的比较,如果串secret中的元素与guess中的元素等值同位,则’Bull’的值+1;如果串guess中的元素在串guess中出现过,则’Cow’的值+1.

这个问题可以用两个哈希表来解决,两个哈希表中分别存储两个串中每个元素的出现次数即可,不过这里我们并不需要进行频繁的查找操作,只是需要一个映射而已,所以我们大可不必用一个哈希表来解决问题,所以下面介绍一个编程技巧:

核心思想是用一个数组充当哈希表起到的计数作用,具体实现如下:

Using array as a simple counter

A simple array could be used as a counter. An array could be used to keep track of the frequency of each character. For example, if the input consists of ASCII characters, we could just use an integer array of size 256 to keep track of the frequency.

For example, the following program calculates each character’s frequency using a simple array of size 256.

private static void printFreq(char[] str) {
    int[] freq = new int[256];
    for (int i = 0; i < str.length; i++) {
        freq[str[i]]++;
    }
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            System.out.println("[" + (char)(i) + "] = " + freq[i]);
        }
    }
}

public static void main(String[] args) {
    char[] str = "Hello world".toCharArray();
    printFreq(str);
}

Output:

[ ] = 1 
[H] = 1 
[d] = 1 
[e] = 1 
[l] = 3 
[o] = 2 
[r] = 1 
[w] = 1 

Why do we choose size 256? Why not 128 or 26? The reason is because there are a total of 256 possible ASCII characters, from 0 to 255. If you are sure that the input characters are all lowercase letters (a - z), then you can save some space by using an array of size 26:

private static void printFreq(char[] str) {
    int[] freq = new int[26];
    for (int i = 0; i < str.length; i++) {
        // 'a' has an ascii value of 97, so there is an offset in accessing the index.
        freq[str[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            System.out.println("[" + (char)(i + 'a') + "] = " + freq[i]);
        }
    }
}

public static void main(String[] args) {
    char[] str = "helloworld".toCharArray();
    printFreq(str);
}

Output:

[d] = 1 
[e] = 1 
[h] = 1 
[l] = 3 
[o] = 2 
[r] = 1 
[w] = 1 

Using a hash table

Now, what if the input contains unicode characters? In Java, each character is represented internally as 2 bytes, or 16 bits. That means you can increase the array size to 2^{16} = 65536 2^16=65536, which would work but seems like a waste of space. For example, what if your input has only 10 characters? Most of the array elements will be initialized to 0 and to print the frequencies we need to traverse all 65536 elements one by one, which is inefficient.

A better method is to use a hash table, in Java it’s called HashMap, in C++ it’s called unordered_map, and in Python it’s called dict.

private static void printFreq(char[] str) {
    Map<Character, Integer> freq = new HashMap<>();
    for (int i = 0; i < str.length; i++) {
        if (freq.containsKey(str[i])) {
            freq.put(str[i], freq.get(str[i]) + 1);
        } else {
            freq.put(str[i], 1);
        }
    }
    for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
        System.out.println("[" + (char)(entry.getKey()) + "] = " + entry.getValue());
    }
}

public static void main(String[] args) {
    char[] str = "◣⚽◢⚡◣⚾⚡◢".toCharArray();
    printFreq(str);
}

Output:

[⚡] = 2 
[◢] = 2 
[◣] = 2 
[⚽] = 1 
[⚾] = 1 

引用自Leetcode course部分,原文写的很好,在此就不再造轮子了。

对于这道题,思路是:如果两个字符串相比较,对应位置上的元素相等,则bull+1,否则,统计不成对元素出现次数,代码如下:

class Solution {
public:
    string getHint(string secret, string guess) {
        if(secret.empty()||guess.empty())
            return "0A0B";
        vector<int> countS(10,0);
        vector<int> countG(10,0);
        string res;
        int countA=0,countB=0;
        for(int i=0;i<secret.size();i++){
            if(secret[i]==guess[i])
                countA++;
            else{
                /*统计不成对元素个数*/
				countS[secret[i]-'0']++;
                countG[guess[i]-'0']++;
            }
        }
        for(int i=0;i<countS.size();i++)
            countB+=min(countS[i],countG[i]);
        res=to_string(countA)+'A'+to_string(countB)+'B';
        return res;
    }
};

你连世界都没有观过,哪里来的世界观?

“为什么我比你有才还没你混得好?”

“因为我见得比你多啊”

-01-

很多时候你不是不能,而是不知道。

记得去年八月份时,我还是一个正在谈情说爱的准大二专科学生。 那个时候,我每天想的都是今天看什么电视剧、发什么说说、怎样让男票多喜欢我一点。 但是那时这样的我,是班上的班长,班上的大多数人是书都不会翻开的那种,更别说去上课了。

而我会翻翻书,自我安慰证明自己还是在学,因此大多数同学都认为我很上进和优秀。 我就被这样的认为迷得神魂颠倒,那个时候,我还真觉得自己很不错的。 至少,相比起来我还会看看书,我还知道要上进。我已经很棒了。

直到十月份的时候,我的爱情友情都出现了问题,因为太过于迷茫,我决定要去外面看看,于是我一个人去成都参加了一个两天一夜的活动。 参加活动的人大多都是重点大学的学生,知道后,我突然有点不自信,因为自己是一个专科学生。

他们有的马上去外省参加国际辩论赛、有的在准备自己的GAP YEAR、有的在创业、有的准备出国留学等等。 那个时候,我才发现自己一直自以为的还不错,其实什么能力什么亮点都没有,学历更没有,还如此骄傲自满。

比我努力比我优秀的人真的多得多。 那次活动,就像是打开了我的一个新世界,算是对我未来方向的一个大转变。 我发现原来除了每天讨论什么电视剧好看、怎样穿好看,还可以这样活。为了自己的梦想而活,做自己真正想做的事。

参加完活动后,我开始看书、开始参加更多的活动、开始接触更多的人。 就算是到成都需要坐两个小时的车,我也愿意去。 如果我不出去看看,去接触比我优秀的人,我可能就只会听到别人说“比你牛逼的人还比你努力”,却从来都不会真切的感受到。

我可能还会继续的在我舒适圈里活着,自以为自己很努力了。

-02-

我们总以为自己很多事都做不了,但实际可以。

加入猫群之前,我觉得能开公众号写作的人,就是超级厉害的人。 而觉得自己肯定不行,我高中语文就及格过一次,文笔一点都不好,又何谈写作。 加入猫群之后,发现很多人都在写作,打造自己的个人品牌。 我一开始觉得做这个好难啊,但在两个月的时间内,看着猫群的小伙伴迅速地成长,从粉丝0到了1000+,从无个人品牌到开通了在行。

从来没有想到过自己能开通公众号,开始写作,还和猫群的小伙伴们坚持每日一更。 只有自己开始写作了,才发现每日一更真的好困难。 可猫群里有很多白天上班,晚上回家后还要带孩子的伙伴,都在坚持每日一更。 我问她们是怎么做到的?

“利用碎片时间,等人的时间、坐车的时间、走路的时间(用语音记录)、做菜的时间(听课程音频),实在不行就早起一小时,时间挤挤总会有的。”

这个回答真心触动到我了。 我开始利用碎片时间构思文章、我开始尝试5点就起床看书写字。虽然我写得不是很好,但我相信有努力就会有收获的,至少在成长。 而在我坚持更文的这一周里,有编辑找、有公众号请求转载、整理的文章被大V转载。这仅仅是一周内所发生的事情,这些都是我以前从未想过的。

原来,我还可以写作。 想到了猫爷说的一句: “当你的视野打开后,你就会知道更多的生命可能性,也许你就不会像现在这样活着,你会找到人生的方向。 而一个人一旦找到自己的方向,找到自己喜欢的东西,他的执行力肯定不会差。”

-03-

在我告诉我同学我开通了微信公众号,想学习新媒体的时候。 她问我:“什么是微信公众号?什么是新媒体?” 我算是在我们学校里到外面参加活动最多的一个了,我收获不少,总想着跟身旁的同学分享心得。 却被问一句:“你是不是参加的什么传销组织啊!?”

被问到这种问题时的我,才发现自己已经走得很远了。 但身旁很多人依旧是在没有任何危机感的原地踏步。 很多人问我,你怎么突然就这么努力了? 有时候想开始努力,不是因为喝了太多的鸡汤,只是因为我见到了更大的世界,我发现人生不仅仅只为赚钱、结婚、生子,我发现我人生有很多种可能性,很多种活法。 这么有趣的人生,我当然想努力的把它过好啊!

视野究竟有多重要?

如果我不出去看看, 我可能现在还在郁郁寡欢地四处问别人:“要怎么才能俘获男人的心?”; 我可能现在还在反复地自拍,然后P图半个小时,直到自己完美为止,再发朋友圈; 我可能现在还在跟朋友吐槽今天谁谁谁说了哪句话又怎样怎样了。

无法想象自己再次过着那样的生活。 你没有视野你就知道的太少了,你知道的生命可能性也太少了,你总觉得自己这样不行,那样也不行。 继而你对自己的期待不会放开,不会有所提高,于是你所付出的努力也会与别人不一样。

-END-

千万个惠 简书作者 19岁大三医学生