第一道题目. 单词规律:
拿到这道题目之初，便想到了很明显的hash映射痕迹在其中. 然后就是字符串解析. 看到s串空格分割，我不由得想到了stringstream. 我放入s串到stringstream对象中, 借助operator>>流出来，可以解析获取到word.
首先对比左右len 是不是对应的， 如果不对应一定是false 对应之后再判断是不是满足pattern类型的
然后continue: 干他. 这个不是so easy: 拿下
class Solution { public: bool wordPattern(string pattern, string s) { int len1 = pattern.size(); int len2 = 1; for (auto& e : s) { len2 += (e == ' '); } if (len1 != len2) return false; unordered_map<char, string> mp; stringstream ss(s); for (int i = 0; i < len1; ++i) { char ch = pattern[i]; string str; ss >> str; if (mp.find(ch) == mp.end()) { mp[ch] = str; } else {//已经出现过了, 判断是否匹配 if (mp[ch] != str) return false; } } return 1; } };
很遗憾: 这个没有完全通过:
观察观察, 貌似貌似忽略了一个小小的细节呀:
需要双向映射: 于是卧槽，这个a 跟着 b 咋不同的字母都映射到了相同的value值，必然不可以呀. 所以我还需要判断的是不能存在重复的value. 但是C++中的hash table 也就是unordered_map 并不存在查找containValue的这种内置函数, 咋搞，反向再来一个map映射value到key呗
class Solution { public: bool wordPattern(string pattern, string s) { int len1 = pattern.size(); int len2 = 1; for (auto& e : s) { len2 += (e == ' '); } if (len1 != len2) return false; unordered_map<char, string> mp1; unordered_map<string, char> mp2; stringstream ss(s); for (int i = 0; i < len1; ++i) { char ch = pattern[i]; string str; ss >> str; if (mp1.find(ch) == mp1.end()) { mp1[ch] = str; if (mp2.find(str) != mp2.end()) return false; //已经映射过了, 不是一一映射了， 思考a, b 都对应dog场景 mp2[str] = ch; } else {//已经出现过了, 判断是否匹配 if (mp1[ch] != str) return false; } } return 1; } };
拿到题目之初，还是最简单的思考了一下, 简单呀，提取每一位元素到数组中，然后对数组中的元素进行有条件交换，最后再提取数组作为结果即可，最初我想的是用一个整形数组算了. 但是后面我一想，为啥我不用string. 先将其直接转换为string 操作不就是相当于数组吗, 最后再转换回到整形即可.
然后我第一个思路诞生了。说白了我就是在右边往左走，走到第一个出现较小的位的num 然后将其交换成后面较大的数字，整体就变大了一点点。为啥从右走, 为啥找第一个出现.
这个不都是为了满足题目的大一点点的要求么? 将大的数往高位换，你肯定尽量的换低位才能尽可能小呀. 所以思路出来了，我找到第一个小的位置换了. 换了之后, 对于换了的位置之后进行一个sort, 升序（高位小数，低位大数，让数据尽可能小）.
第一次的swap: 为了保证比原来的数字大. 后面的sort, 为了保证是刚刚大一点
为了找左边第一个小的元素，我自然而然的我想到了单调栈.
class Solution { public: int nextGreaterElement(int n) { string numstr = to_string(n); stack<int> moreStack;//递增栈 int posind, ind; for (ind = numstr.size()-1; ind>=0; ind--) { char ch = numstr[ind]; if (moreStack.empty() || ch >= numstr[moreStack.top()]) { moreStack.push(ind); continue; } posind = ind;//need swap while (!moreStack.empty() && ch < numstr[moreStack.top()]) { ind = moreStack.top(); moreStack.pop(); } break; } if (ind == -1) return -1; swap(numstr[ind], numstr[posind]); //posind 之后将小的位往前转 sort(numstr.begin()+posind+1, numstr.end()); if (stol(numstr) > INT_MAX) { return -1; } return stoi(numstr); } };
单调栈，找右边第一个小于的元素, 或者找第一个大于的元素简直就是神器，用过的人都知道哈哈哈，其实本质就是很简单的. 遥望原理: 你往前看. 肯定只能看到比你高的。比你高的自然不可能是第一个矮的. 那出现的第一个矮的，就是你前面所有哪些高的的后面的第一个矮的
由于存在右边第一个, 而且是单调递增的特性，由配合栈的先进先出，就具备了这一完美的找右边第一个小于或者第一个大于的特性呀.
