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

灰太狼 2022-12-03 05:15 169阅读 0赞

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

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

class Solution { 
    public:
        bool isSelfCrossing(vector<int>& x) { 
            int x_size=x.size();
            for (int i=3;i<x_size;++i)
            { 
                if (i>=3 && x.at(i-1)<=x.at(i-3) && x.at(i)>=x.at(i-2))
                    return true;
                if (i>=4 && x.at(i-3)==x.at(i-1) && x.at(i)+x.at(i-4)>=x.at(i-2))
                    return true;
                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) 
                && x.at(i-2)>x.at(i-4) && x.at(i-3)>x.at(i-1))
                    return true;
            }
            return false;
        }
    };

1.  回文对  
    给定一组互不相同的单词， 找出所有不同的索引对(i, j)，使得列表中的两个单词，words\[i\] + words\[j\] ，可拼接成回文串。

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

struct Trie { 
        struct node { 
            int ch[26];
            int flag;
            node() { 
                flag = -1;
                memset(ch, 0, sizeof(ch));
            }
        };
    
        vector<node> tree;
    
        Trie() {  tree.emplace_back(); }
    
        void insert(string& s, int id) { 
            int len = s.length(), add = 0;
            for (int i = 0; i < len; i++) { 
                int x = s[i] - 'a';
                if (!tree[add].ch[x]) { 
                    tree.emplace_back();
                    tree[add].ch[x] = tree.size() - 1;
                }
                add = tree[add].ch[x];
            }
            tree[add].flag = id;
        }
    
        vector<int> query(string& s) { 
            int len = s.length(), add = 0;
            vector<int> ret(len + 1, -1);
            for (int i = 0; i < len; i++) { 
                ret[i] = tree[add].flag;
                int x = s[i] - 'a';
                if (!tree[add].ch[x]) { 
                    return ret;
                }
                add = tree[add].ch[x];
            }
            ret[len] = tree[add].flag;
            return ret;
        }
    };
    
    class Solution { 
    public:
        vector<pair<int, int>> manacher(string& s) { 
            int n = s.length();
            string tmp = "#";
            tmp += s[0];
            for (int i = 1; i < n; i++) { 
                tmp += '*';
                tmp += s[i];
            }
            tmp += '!';
            int m = n * 2;
            vector<int> len(m);
            vector<pair<int, int>> ret(n);
            int p = 0, maxn = -1;
            for (int i = 1; i < m; i++) { 
                len[i] = maxn >= i ? min(len[2 * p - i], maxn - i) : 0;
                while (tmp[i - len[i] - 1] == tmp[i + len[i] + 1]) { 
                    len[i]++;
                }
                if (i + len[i] > maxn) { 
                    p = i, maxn = i + len[i];
                }
                if (i - len[i] == 1) { 
                    ret[(i + len[i]) / 2].first = 1;
                }
                if (i + len[i] == m - 1) { 
                    ret[(i - len[i]) / 2].second = 1;
                }
            }
            return ret;
        }
    
        vector<vector<int>> palindromePairs(vector<string>& words) { 
            Trie trie1, trie2;
    
            int n = words.size();
            for (int i = 0; i < n; i++) { 
                trie1.insert(words[i], i);
                string tmp = words[i];
                reverse(tmp.begin(), tmp.end());
                trie2.insert(tmp, i);
            }
    
            vector<vector<int>> ret;
            for (int i = 0; i < n; i++) { 
                const vector<pair<int, int>>& rec = manacher(words[i]);
    
                const vector<int>& id1 = trie2.query(words[i]);
                reverse(words[i].begin(), words[i].end());
                const vector<int>& id2 = trie1.query(words[i]);
    
                int m = words[i].size();
    
                int all_id = id1[m];
                if (all_id != -1 && all_id != i) { 
                    ret.push_back({ i, all_id});
                }
                for (int j = 0; j < m; j++) { 
                    if (rec[j].first) { 
                        int left_id = id2[m - j - 1];
                        if (left_id != -1 && left_id != i) { 
                            ret.push_back({ left_id, i});
                        }
                    }
                    if (rec[j].second) { 
                        int right_id = id1[j];
                        if (right_id != -1 && right_id != i) { 
                            ret.push_back({ i, right_id});
                        }
                    }
                }
            }
            return ret;
        }
    };

1.  打家劫舍3

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    struct SubtreeStatus { 
        int selected;
        int notSelected;
    };
    
    class Solution { 
    public:
        SubtreeStatus dfs(TreeNode* o) { 
            if (!o) { 
                return { 0, 0};
            }
            auto l = dfs(o->left);
            auto r = dfs(o->right);
            int selected = o->val + l.notSelected + r.notSelected;
            int notSelected = max(l.selected, l.notSelected) + max(r.selected, r.notSelected);
            return { selected, notSelected};
        }
    
        int rob(TreeNode* o) { 
            auto rootStatus = dfs(o);
            return max(rootStatus.selected, rootStatus.notSelected);
        }
    };

1.  比特位计数  
    给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

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

class Solution { 
    public:
        vector<int> countBits(int num) { 
            vector<int> ret(num + 1);
            for (int i = 1; i <= num; ++i)
                ret[i] = ret[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
            return ret;
        }
    };

1.  扁平化嵌套列表迭代器  
    给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表

**遍历一遍即可**

class NestedIterator { 
    public:
        vector<int> data;
        vector<int>::iterator it;
        NestedIterator(vector<NestedInteger> &nestedList) { 
            parse(nestedList);
            it = data.begin();
        }
        
        void parse(vector<NestedInteger> &nestedList){ 
            for(auto nes : nestedList){ 
                if(nes.isInteger()) data.push_back(nes.getInteger());
                else parse(nes.getList());
            }
        }
    
        int next() { 
            return *it++;
        }
        
        bool hasNext() { 
            return it != data.end();
        }
    };

1.  4的幂  
    给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

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

class Solution { 
    public:
        bool isPowerOfFour(int num) { 
            return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
        }
    };

1.  整数拆分  
    给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

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

class Solution { 
    public:
        int integerBreak(int n) { 
            if (n <= 3) { 
                return n - 1;
            }
            int quotient = n / 3;
            int remainder = n % 3;
            if (remainder == 0) { 
                return (int)pow(3, quotient);
            } else if (remainder == 1) { 
                return (int)pow(3, quotient - 1) * 4;
            } else { 
                return (int)pow(3, quotient) * 2;
            }
        }
    };