1169. 查詢無效交易
      
      我花了一段時(shí)間在思考這道題目，想要找到一個(gè)較為高效的 分享一些我的思考吧。這道題目有三個(gè)條件 人名，地點(diǎn)以及時(shí)間。從維度上來看，是3維的，我是把它想做了一個(gè)三維空間。
      我們要求的就是相同人名，不用地點(diǎn)近似時(shí)間，那么問題就來了，我們需要降低維度，只看相同人名下的空間，即二維空間。問題是求城市這一維度不同，時(shí)間這
      一維度相近似的解（差60）。我本來是想用滑動(dòng)窗口在時(shí)間維度上進(jìn)行遍歷，然后用總和減去城市相同的，即我們通過全集減去反集求解，因?yàn)槲覀兒芎们蟪鲈谕?br /> 一窗口下同一city下的城市。
      以上就是我的理想思路，實(shí)際操作中，我沒用實(shí)現(xiàn)滑動(dòng)窗口去完成這個(gè)搜索，因?yàn)榇_實(shí)這道題的數(shù)目只有1000，最暴力的方案應(yīng)該也是可以的，所以我是對時(shí)間維
      度進(jìn)行了排序，從第一點(diǎn)向前向后搜索來求解答案。

class Solution {
public:struct Node{ //代表每一個(gè)的具體賬單int time;int val;int city;//創(chuàng)建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;}};//根據(jù)實(shí)際情況寫的解析函數(shù)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;}
};

25. K 個(gè)一組翻轉(zhuǎn)鏈表

思路很簡單
reverseLink 用來反轉(zhuǎn)鏈表
一個(gè)指針每次向前搜索K個(gè)大小的鏈表，然后反轉(zhuǎn)
需要注意的是如何鏈接，寫錯(cuò)了很容易出現(xiàn)鏈表邊環(huán)。

    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;//鏈表長度不足，提前結(jié)束} p = end->next; // 迭代reverseLink(begin, end);pre->next = end;  pre = begin;}return feak_head.next;}

總結(jié)

以上是生活随笔為你收集整理的leetcode日记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。