- 查询无效交易
我花了一段时间在思考这道题目，想要找到一个较为高效的 分享一些我的思考吧。这道题目有三个条件 人名，地点以及时间。从维度上来看，是3维的，我是把它想做了一个三维空间。
我们要求的就是相同人名，不用地点近似时间，那么问题就来了，我们需要降低维度，只看相同人名下的空间，即二维空间。问题是求城市这一维度不同，时间这
一维度相近似的解（差60）。我本来是想用滑动窗口在时间维度上进行遍历，然后用总和减去城市相同的，即我们通过全集减去反集求解，因为我们很好求出在同
一窗口下同一city下的城市。
以上就是我的理想思路，实际操作中，我没用实现滑动窗口去完成这个搜索，因为确实这道题的数目只有1000，最暴力的方案应该也是可以的，所以我是对时间维
度进行了排序，从第一点向前向后搜索来求解答案。
class Solution {
public:struct Node{ //代表每一个的具体账单int time;int val;int city;//创建city映射表 对字符串操作越少 效率越高int id; //避免对字符串的操作Node(int t, int v, int c, int i) :time(t), val(v), city(c), id(i){}Node(){}};static bool check_node(const Node& n1, const Node& n2){return n1.time < n2.time;}struct User{vector<Node> user_bills; //用户的账单User(){}vector<int> get_illegal_bill(){vector<int> ret;//sort for billssort(user_bills.begin(), user_bills.end(), check_node);//searchfor (auto i = 0; i < user_bills.size(); ++i){if (user_bills[i].val > 1000){ret.push_back(user_bills[i].id); continue;}bool flag = false;//check preint p = i - 1;while( p >= 0 && user_bills[i].time - user_bills[p].time <= 60){if(user_bills[p].city != user_bills[i].city) {ret.push_back(user_bills[i].id); flag = true; break;}p--;}if(flag) continue;p = i + 1;//check endwhile( p < user_bills.size() && user_bills[p].time - user_bills[i].time <= 60){if(user_bills[p].city != user_bills[i].city) {ret.push_back(user_bills[i].id); break;}p++;}}return ret;}};//根据实际情况写的解析函数Node string_to_node(string& s, string& name, unordered_map<string, int>& city_map, int& map_count, int id){int p = 0;while (p < s.size() && s[p] != ','){name = name + s[p++];} p++;int time = 0;while (p < s.size() && s[p] != ','){time = time * 10 + s[p++] - '0';} p++;int val = 0;while (p < s.size() && s[p] != ','){val = val * 10 + s[p++] - '0';} p++;string city = "";while (p < s.size()){city = city + s[p++];}auto it = city_map.find(city);if (it == city_map.end()){city_map.insert(pair<string, int>(city, map_count++));}return Node(time, val, city_map[city], id);}vector<string> invalidTransactions(vector<string>& transactions) {unordered_map<string, User> user_table;int map_count = 0;unordered_map<string, int> city_map;vector<string> retStr;//initfor (auto i = 0; i < transactions.size(); ++i){string name = "";Node n = string_to_node(transactions[i], name, city_map, map_count, i);user_table[name].user_bills.push_back(n);}//get resultfor (auto it = user_table.begin(); it != user_table.end(); it++){vector<int> ret = it->second.get_illegal_bill();for (auto i = 0; i < ret.size(); ++i){retStr.push_back(transactions[ret[i]]);}}return retStr;}
};
- K 个一组翻转链表
思路很简单
reverseLink 用来反转链表
一个指针每次向前搜索K个大小的链表，然后反转
需要注意的是如何链接，写错了很容易出现链表边环。
void reverseLink(ListNode *begin, ListNode *end){// if(begin == end) return;ListNode *p = begin->next, *pre = begin;while(p != end){ListNode* copy = p->next;p->next = pre;pre = p; p = copy;}p->next = pre;begin->next = NULL;}ListNode* reverseKGroup(ListNode* head, int k) {if(k == 1) return head;ListNode feak_head = ListNode(0);feak_head.next = head;ListNode *p = head, *pre = &feak_head;while(p){ListNode *begin = p, *end = p;int count = 1;while(count < k && end->next){end = end->next; count++;}if(count < k){pre->next = begin;break;//链表长度不足，提前结束} p = end->next; // 迭代reverseLink(begin, end);pre->next = end; pre = begin;}return feak_head.next;}