leetcode解题思路分析（四十）335 - 343 题

灰太狼 2022-12-03 05:15 326阅读 0赞
  1. 路径交叉
    给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。
    编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。

本题的关键在于画图分析各种类型会相交的情况，最后总结成解法

  1. class Solution { 
  2. public:
  3.     bool isSelfCrossing(vector<int>& x) { 
  4.         int x_size=x.size();
  5.         for (int i=3;i<x_size;++i)
  6.         { 
  7.             if (i>=3 && x.at(i-1)<=x.at(i-3) && x.at(i)>=x.at(i-2))
  8.                 return true;
  9.             if (i>=4 && x.at(i-3)==x.at(i-1) && x.at(i)+x.at(i-4)>=x.at(i-2))
  10.                 return true;
  11.             if (i>=5 && x.at(i)+x.at(i-4)>=x.at(i-2) && x.at(i-1)+x.at(i-5)>=x.at(i-3) 
  12.             && x.at(i-2)>x.at(i-4) && x.at(i-3)>x.at(i-1))
  13.                 return true;
  14.         }
  15.         return false;
  16.     }
  17. };
  1. 回文对
    给定一组互不相同的单词， 找出所有不同的索引对(i, j)，使得列表中的两个单词，words[i] + words[j] ，可拼接成回文串。

本题主要关注点在于：如果s1 + s2可以构成回文对，那么要么s1长要么s2长要么两个等长。长的一个一定有回文子串以及另一个单次的逆序。查找子串回文串可以用马拉车或者暴力搜索，存储其他串逆序可以用哈希表或者字母数

  1. struct Trie { 
  2.     struct node { 
  3.         int ch[26];
  4.         int flag;
  5.         node() { 
  6.             flag = -1;
  7.             memset(ch, 0, sizeof(ch));
  8.         }
  9.     };
  11.     vector<node> tree;
  13.     Trie() {  tree.emplace_back(); }
  15.     void insert(string& s, int id) { 
  16.         int len = s.length(), add = 0;
  17.         for (int i = 0; i < len; i++) { 
  18.             int x = s[i] - 'a';
  19.             if (!tree[add].ch[x]) { 
  20.                 tree.emplace_back();
  21.                 tree[add].ch[x] = tree.size() - 1;
  22.             }
  23.             add = tree[add].ch[x];
  24.         }
  25.         tree[add].flag = id;
  26.     }
  28.     vector<int> query(string& s) { 
  29.         int len = s.length(), add = 0;
  30.         vector<int> ret(len + 1, -1);
  31.         for (int i = 0; i < len; i++) { 
  32.             ret[i] = tree[add].flag;
  33.             int x = s[i] - 'a';
  34.             if (!tree[add].ch[x]) { 
  35.                 return ret;
  36.             }
  37.             add = tree[add].ch[x];
  38.         }
  39.         ret[len] = tree[add].flag;
  40.         return ret;
  41.     }
  42. };
  44. class Solution { 
  45. public:
  46.     vector<pair<int, int>> manacher(string& s) { 
  47.         int n = s.length();
  48.         string tmp = "#";
  49.         tmp += s[0];
  50.         for (int i = 1; i < n; i++) { 
  51.             tmp += '*';
  52.             tmp += s[i];
  53.         }
  54.         tmp += '!';
  55.         int m = n * 2;
  56.         vector<int> len(m);
  57.         vector<pair<int, int>> ret(n);
  58.         int p = 0, maxn = -1;
  59.         for (int i = 1; i < m; i++) { 
  60.             len[i] = maxn >= i ? min(len[2 * p - i], maxn - i) : 0;
  61.             while (tmp[i - len[i] - 1] == tmp[i + len[i] + 1]) { 
  62.                 len[i]++;
  63.             }
  64.             if (i + len[i] > maxn) { 
  65.                 p = i, maxn = i + len[i];
  66.             }
  67.             if (i - len[i] == 1) { 
  68.                 ret[(i + len[i]) / 2].first = 1;
  69.             }
  70.             if (i + len[i] == m - 1) { 
  71.                 ret[(i - len[i]) / 2].second = 1;
  72.             }
  73.         }
  74.         return ret;
  75.     }
  77.     vector<vector<int>> palindromePairs(vector<string>& words) { 
  78.         Trie trie1, trie2;
  80.         int n = words.size();
  81.         for (int i = 0; i < n; i++) { 
  82.             trie1.insert(words[i], i);
  83.             string tmp = words[i];
  84.             reverse(tmp.begin(), tmp.end());
  85.             trie2.insert(tmp, i);
  86.         }
  88.         vector<vector<int>> ret;
  89.         for (int i = 0; i < n; i++) { 
  90.             const vector<pair<int, int>>& rec = manacher(words[i]);
  92.             const vector<int>& id1 = trie2.query(words[i]);
  93.             reverse(words[i].begin(), words[i].end());
  94.             const vector<int>& id2 = trie1.query(words[i]);
  96.             int m = words[i].size();
  98.             int all_id = id1[m];
  99.             if (all_id != -1 && all_id != i) { 
  100.                 ret.push_back({ i, all_id});
  101.             }
  102.             for (int j = 0; j < m; j++) { 
  103.                 if (rec[j].first) { 
  104.                     int left_id = id2[m - j - 1];
  105.                     if (left_id != -1 && left_id != i) { 
  106.                         ret.push_back({ left_id, i});
  107.                     }
  108.                 }
  109.                 if (rec[j].second) { 
  110.                     int right_id = id1[j];
  111.                     if (right_id != -1 && right_id != i) { 
  112.                         ret.push_back({ i, right_id});
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.         return ret;
  118.     }
  119. };
  1. 打家劫舍3

动态规划可解，每个节点可以选择或者不选。如果不选则可以选其子节点，否则不可以。

  1. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  2. struct SubtreeStatus { 
  3.     int selected;
  4.     int notSelected;
  5. };
  7. class Solution { 
  8. public:
  9.     SubtreeStatus dfs(TreeNode* o) { 
  10.         if (!o) { 
  11.             return { 0, 0};
  12.         }
  13.         auto l = dfs(o->left);
  14.         auto r = dfs(o->right);
  15.         int selected = o->val + l.notSelected + r.notSelected;
  16.         int notSelected = max(l.selected, l.notSelected) + max(r.selected, r.notSelected);
  17.         return { selected, notSelected};
  18.     }
  20.     int rob(TreeNode* o) { 
  21.         auto rootStatus = dfs(o);
  22.         return max(rootStatus.selected, rootStatus.notSelected);
  23.     }
  24. };
  1. 比特位计数
    给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

对于一个数字和它的二分之一，其实就是移位操作，带来的数字1的个数的差别就在于最后一位，因此采取位操作即可

  1. class Solution { 
  2. public:
  3.     vector<int> countBits(int num) { 
  4.         vector<int> ret(num + 1);
  5.         for (int i = 1; i <= num; ++i)
  6.             ret[i] = ret[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
  7.         return ret;
  8.     }
  9. };
  1. 扁平化嵌套列表迭代器
    给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表

遍历一遍即可

  1. class NestedIterator { 
  2. public:
  3.     vector<int> data;
  4.     vector<int>::iterator it;
  5.     NestedIterator(vector<NestedInteger> &nestedList) { 
  6.         parse(nestedList);
  7.         it = data.begin();
  8.     }
  10.     void parse(vector<NestedInteger> &nestedList){ 
  11.         for(auto nes : nestedList){ 
  12.             if(nes.isInteger()) data.push_back(nes.getInteger());
  13.             else parse(nes.getList());
  14.         }
  15.     }
  17.     int next() { 
  18.         return *it++;
  19.     }
  21.     bool hasNext() { 
  22.         return it != data.end();
  23.     }
  24. };
  1. 4的幂
    给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

4的次方数一定是2的次方数，但2的次方数不一定是4的次方数，通过4的次方数二进制可以发现4的次方数二进制中1只出现在奇数位。因此可以通过于奇数位都是1，偶数为都是0的数（1010101010101010101010101010101）进行与运算，结果仍为原来数。

  1. class Solution { 
  2. public:
  3.     bool isPowerOfFour(int num) { 
  4.         return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
  5.     }
  6. };
  1. 整数拆分
    给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

本题可以用贪心算法求解，但是最佳解决方案肯定是推导数学规律直接求最大值

  1. class Solution { 
  2. public:
  3.     int integerBreak(int n) { 
  4.         if (n <= 3) { 
  5.             return n - 1;
  6.         }
  7.         int quotient = n / 3;
  8.         int remainder = n % 3;
  9.         if (remainder == 0) { 
  10.             return (int)pow(3, quotient);
  11.         } else if (remainder == 1) { 
  12.             return (int)pow(3, quotient - 1) * 4;
  13.         } else { 
  14.             return (int)pow(3, quotient) * 2;
  15.         }
  16.     }
  17. };

发表评论

表情：
评论列表 （有 0 条评论，326人围观）

还没有评论，来说两句吧...

相关阅读