大数据问题的一般思路

• 

  利用位数组

• 利用基础类型（比如int）制作一个bit数组
• 比如一个int是32位，那么10个int就是320位的位数组
• 利用每个位的1和0计数数字的存在与否

  小空间词频统计

• 假如用一个小空间计算40亿个数字中unsigned int中的哪个不包括在内
  • 先申请允许内存大小的数组，检查系统内存能够允许的数组长度，找最近的长度为2的整数幂次的数组长度作为长度
  • 然后按照数组的长度均分unsigned int范围得到小的范围长度
  • 遍历整个数组，每个元素除以小范围的长度，结果向下取整得到自己属于哪个小范围
  • 将词频数组对应的index位置（上一步计算的结果）+1
  • 循环一遍之后，词频数组中肯定有某个位置的词频达不到理论上的小范围长度
  • 将整个统计范围的长度从整个unsigned int范围调整到上一个词频达不到满的小范围
  • 重复上述步骤遍历整个数据，丢弃所有不在范围内的数字，其他数字按照第二次划分的小范围分类，统计结束之后再看哪个位置的词频达不到此时的小范围
• 统计巨量URL的访问次数
  • 使用哈希函数将URL转换，然后分流到一定数量（按照服务器的内存资源决定）的小文件中，每个小文件使用一个利用URL被访问次数组织的大根堆
  • 将每个大根堆的堆顶组织成大根堆得到总堆
  • 结果就是依次将内容从总堆中弹出，弹出之后找到这个元素原来所在的大根堆，同样将这个元素弹出，然后弹出后的大根堆的头部放入总大根堆中。
• 利用位数组统计出现了两次的数字
  • 用两位表示一个数字是否出现过
  • 00没出现过，01出现一次，10出现两次，11出现大于2次
• 利用小空间找中位数
  • 同样利用小范围词频统计（第一种）操作
  • 统计到找出中位数在哪个小分区里
  • 然后对这个对应的小分区再等分找到具体的中位数的位置

    小空间给大数组

• 方法一
  • 小空间使用小根堆
  • 小根堆存储的内容是<数字，出现次数>的元组，有小根堆中存在的数字的时候，相应的出现次数+1
  • 小根堆不能直接用一条记录的空间计算，需要考虑一些额外的开销，实际可用的空间可能是总空间/16或者其他数值
  • 堆的大小用最接近的2的整数次幂次
  • 然后按照被排序的内容/堆的大小得到被排序内容按大小分的小段
  • 第一次处理落在最小部分段内的数据，第二次处理第二小部分段内的数据…
  • 都处理完即可得到所有排序
• 方法二
  • 使用一个大根堆存储此时数组中最小的几种数字
  • 假如此时一个新的数字小于此时大根堆中最大的数字，那么可以加入
  • 假如这个数字比大根堆中最大的数字还大，那么说明这个数字不属于整个数组中最小的k个数字之一，直接忽略（k为堆的大小）
  • 假如此时大根堆的数字超出数字限制，那么将最大的数字弹出然后将新的数字压入
  • 然后将大根堆内的所有数字逆序排出并清空堆，然后给堆设置最小值，等于上次弹出之前堆中最大的数字，以后只考虑大于这个数字的数

Morris遍历细节

• 
• 传统遍历方法的空间复杂度是O(树的高度)
• 利用底层叶节点的空指针节省空间
• 假如不允许修改题目给出的树就没法使用Morris遍历
• Morris遍历对于所有有左子树的节点都能到达两次
• 一个节点指针来到他的右子树之后就不会再次返回这个节点了
  • 判断第几次到达一个节点？
  • 根据左子树上最右节点的右指针指向谁，假如指向自己，那就是第二次到达

    public static void morris(Node head) { if (head == null) { return; } Node cur = head; Node mostRight = null; while (cur != null) { mostRight = cur.left; if (mostRight != null) {// z有左孩子否则直接退回大循环 while (mostRight.right != null && mostRight.right != cur) { // 找左树上的最右节点，右孩子不能等于当前节点 mostRight = mostRight.right; } if (mostRight.right == null) {// 第一次来到cur mostRight.right = cur; cur = cur.left;//向左子树发展 continue; } else { mostRight.right = null;// 第二次来到cur } } cur = cur.right;// 向右树移动 } }

• 时间复杂度: O(N)

  Morris遍历改为先序遍历：

• 如果一个节点只能到达一次，直接打印内容
• 如果可以到达两次，第一次打印

  public static void morrisPre(Node head) { if (head == null) { return; } Node cur = head; Node mostRight = null; while (cur != null) { mostRight = cur.left; if (mostRight != null) {// 有左子树 while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) {// 第一次来到这个节点 System.out.print(cur.value + " "); mostRight.right = cur; cur = cur.left; continue; } else {// 第二次来，不打印 mostRight.right = null; } } else {// 没有左子树 System.out.print(cur.value + " "); } cur = cur.right; } System.out.println(); }

  中序遍历

• 只经过一次的节点：直接输出
• 两次的节点：第二次经过的时候打印

  public static void morrisIn(Node head) { if (head == null) { return; } Node cur = head; Node mostRight = null; while (cur != null) { mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) {// 第一次经过会跳过打印 mostRight.right = cur; cur = cur.left; continue; } else { mostRight.right = null; } } // 跟原本代码唯一的区别就是此处加一个打印 System.out.print(cur.value + " "); cur = cur.right; } System.out.println(); }

  Morris后序遍历

• 将打印的时机安排在一个能回到自己两次的节点第二次被经过的时候
• 第二次回到自己的时候逆序打印自己左树的右边界
• 整个过程结束之后逆序打印整棵树的右边界

  逆序遍历如何实现

• 借用单链表逆序遍历的操作
• 指针逆序之后，打印然后再调整回去

  public static void morrisPos(Node head) { if (head == null) { return; } Node cur = head; Node mostRight = null; while (cur != null) { mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = cur; cur = cur.left; continue; } else { mostRight.right = null; printEdge(cur.left);// 第二次经过的时候逆序打印左树的右边界 } } cur = cur.right; } printEdge(head);// 整个结束之后逆序打印整棵树的右边界 System.out.println(); } public static void printEdge(Node head) {// 打印然后再逆序回去 Node tail = reverseEdge(head); Node cur = tail; while (cur != null) { System.out.print(cur.value + " "); cur = cur.right; } reverseEdge(tail); } public static Node reverseEdge(Node from) {// 单链表的逆序操作 Node pre = null; Node next = null; while (from != null) { next = from.right; from.right = pre; pre = from; from = next; } return pre; }

问题

• 了解数组中的一个数，左边最近的比这个数大的数，和右边最近的比这个数大的数在哪
• 在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景

  单调栈

  无重复数字

• 求某个数字附近最近的比他大的数字：
  • 使用一个栈，这个栈从下到上是由大到小的顺序
  • 新加入的数字符合单调性？直接加入
  • 不符合单调性？弹出栈顶的数字，此时记录，对于被弹出的这个数字而言：
    • 左边最近的比他大的数字就是弹出这个数字之后的栈顶元素
    • 右边最近的比他大的数字就是正要进栈的数字
    • 直到符合单调性为止
  • 最后结束的时候栈中还有数据怎么办？
    • 栈中剩余的所有数据的右边最近比他大的数字都是无
    • 左边最近的比他大的数字都是他在栈中的下一个元素
    • 栈底的最后一个元素左右都是无

      有重复数字

• 栈中放的内容都是链表，每个位置链表结点存放index
• 弹出的时候，右边最近比他大的数字是当前等待进栈的数字，左边最近的比他大的数字是栈中下面紧邻位置链表的最后一个位置
• 同样数字进栈的时候，将同样的数字对应的index串联在进栈位置链表的下一个位置

  public static int[][] getNearLessNoRepeat(int[] arr) { int[][] res = new int[arr.length][2]; // 只存位置！ Stack<Integer> stack = new Stack<>(); for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数，arr[i] while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) { int j = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek(); res[j][0] = leftLessIndex; res[j][1] = i; } stack.push(i); } while (!stack.isEmpty()) { int j = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek(); res[j][0] = leftLessIndex; res[j][1] = -1; } return res; } public static int[][] getNearLess(int[] arr) { int[][] res = new int[arr.length][2]; Stack<List<Integer>> stack = new Stack<>(); for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈 while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) { List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer popi : popIs) { res[popi][0] = leftLessIndex; res[popi][1] = i; } } if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) { stack.peek().add(Integer.valueOf(i)); } else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } } while (!stack.isEmpty()) { List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer popi : popIs) { res[popi][0] = leftLessIndex; res[popi][1] = -1; } } return res; }

Leetcode 739.每日温度

• 单调栈解法

• 可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

• 正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数设为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

Leetcode 42. 接雨水

• 此题也是找一个从下到上单调递减的栈

  class Solution { public: int trap(vector<int>& height) { stack<int> s; int retVal = 0; for(int i = 0; i<height.size(); ++i) { if(!s.size()) { s.push(i); continue; } int tmp = s.top(); while(s.size() && height[i]>height[tmp]) { s.pop(); if(s.size() == 0)break; int w = i-s.top()-1; int h = min(height[i], height[s.top()]) - height[tmp]; retVal+=w*h; tmp = s.top(); } s.push(i); } return retVal; } };

  Leetcode 84. 柱状图中最大的矩形

• 随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能够扩展到的最远范围。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        int maxArea = heights[0];
        for(int i = 0; i<heights.size(); ++i)
        {
            maxArea = max(maxArea, heights[i]);
            if(!s.size())
            {
                s.push(i);
                continue;
            }
            // 维护一个从下到上递增的栈
            while(s.size()>1 && heights[i]<heights[s.top()])
            {
                int tmp = s.top();
                s.pop();
                int l = s.top();
                maxArea = max(maxArea, heights[tmp]*(i-l-1));
            }
            s.push(i);
        }
        return maxArea;
    }
};

Leetcode 155.最小栈

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中

• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出

• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

leetcode 76.最小覆盖字串

• begin从0开始，end从-1开始
• 注意vector<>.size()返回的是无符号整数
• 不能直接与int比较大小，尤其是存在负数的情况
• 假如窗口的下一个元素是目标字符串中的
• 先把下一个加入窗口
• 假如此时需要的字符数量超过了目标字符串的数量
• 试图前移开头，删除元素直到没有窗口中没有多余的字母为止
• 注意， 假如此时窗口中的该字符数量已经超过了需要的该字符数量，那就不能再增加已经cover的字符计数了，否则会导致错误

  class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> um, uTarget; int covered = 0; int n = s.size(); for(int i = 0; i<t.size(); i++) { um[t[i]] = 0; if(!uTarget.count(t[i])) { uTarget[t[i]] = 1; } else { ++uTarget[t[i]]; } } int begin = 0; int end = -1; int minBegin = 0, minEnd = 0, minLen = INT_MAX; // cout<<end<<"|"<<n-1<<endl; while(end<(n-1)) { // cout<<'@'<<endl; if(um.count(s[end+1])) { if(um[s[end+1]]>=uTarget[s[end+1]]) { // ++covered; ++um[s[++end]]; while(begin<end&&((!um.count(s[begin]))||(um[s[begin]]>uTarget[s[begin]]))) { // cout<<'!'; if(um.count(s[begin])) { --um[s[begin]]; // --covered; } ++begin; } } else { ++covered; ++um[s[++end]]; while((begin<end)&&((um.count(s[begin]) == 0)||(um[s[begin]]>uTarget[s[begin]]))) { // cout<<'!'<<endl; if(um.count(s[begin])) { --um[s[begin]]; // --covered; } ++begin; } } } else ++end; if(covered>=t.size()) { if(end-begin+1<=minLen) { // cout<<"@"<<endl; minBegin = begin; minEnd = end; minLen = end-begin+1; } } // cout<<s.substr(begin, end-begin+1)<<(end-begin+1)<<'|'<<covered<<endl; } if(covered>=t.size()) { return s.substr(minBegin, minLen); } else return ""; } };

  leetcode 3.无重复字符的最长子串

• 使用滑动窗口，假如前面没有重复字符的话就把滑动窗口的后边缘往前移，假如有的话就把前边缘往前移到不重复为止

  class Solution { public: int lengthOfLongestSubstring(string s) { if(s.size()<=1)return s.size(); unordered_map<char, int> m; int maxLen = 0; int startInd = 0, endInd = -1; while (true) { while(m.count(s[endInd+1]) == 0||m[s[endInd+1]] == 0) { ++endInd; m[s[endInd]] = 1; maxLen = maxLen>=(endInd - startInd+1)?maxLen:(endInd - startInd+1); if(endInd == s.size() - 1) { return maxLen; } } while(m.count(s[endInd+1])>0&&m[s[endInd+1]]>0) { if(m.count(s[startInd])) { m[s[startInd]]-=1; ++startInd; } } } return maxLen; } };

双端队列

• 一种两端都可以进出的数据结构

  算法

• 保持双端队列的头部位置是窗口中最大的数字
• 窗口的运动是随意的，不是固定窗口大小的
• 将滑动窗口的右边界向右扩展的时候
• 双端队列中存储的是双端队列中数字的index，但是使用的是index对应的数字
  • 假如此时右边界新进入的数字比此时双端队列的末尾数字大的话就弹出此时双端队列末尾的数字，直到双端队列末尾的数字大于右边界新进入的数字（或者双端队列为空）。严格保证双端队列的单调性。
  • 假如此时窗口的左边界向右移动导致窗口内有数字被移出窗口，那么此时将被移出窗口的数字与双端队列头部的数字（也就是此时窗口的最大值）比较，假如二者相同（是同一个index对应的数字），则弹出双端队列头部的数字，否则不管。
  • 双端队列的信息实际上是假如此时滑动窗口的右边界不动，但是左边界前移，那么随着前移窗口中的最大值会是谁
  • 实际上是用下标大的大数字替换下标小的小数字

    时间复杂度

• 平均每个时刻都是O(1)

  public static int[] getMaxWindow(int[] arr, int w) { if (arr == null || w < 1 || arr.length < w) { return null; } // qmax 窗口最大值的更新结构 // 放下标 LinkedList<Integer> qmax = new LinkedList<Integer>(); int[] res = new int[arr.length - w + 1]; int index = 0; for (int R = 0; R < arr.length; R++) { while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) { qmax.pollLast(); } qmax.addLast(R); if (qmax.peekFirst() == R - w) { qmax.pollFirst(); } if (R >= w - 1) { res[index++] = arr[qmax.peekFirst()]; } } return res; }

  leetcode 220. 存在重复元素III

• 注意需要维护的是一个滑动窗口中的所有元素的排列，要能迅速找到最小值和最大值，同时可以任意删除任何一个元素，使用cpp的有序集合set实现

  class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int n = nums.size(); set<int> rec; for (int i = 0; i < n; i++) { auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t); if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) { return true; } rec.insert(nums[i]); if (i >= k) { rec.erase(nums[i - k]); } } return false; } };

• 注意有序集合查找最小值和最大值的方法是lower_bound函数
• set::lower_bound() 是 C++ STL 中的一个内置函数，用于在集合中查找一个元素。它返回一个迭代器，指向集合中第一个大于等于指定值的元素。如果指定值大于集合中的最大值，则返回指向集合末尾的迭代器。该函数的时间复杂度为 O(logn)，其中 n 是集合的大小。

leetcode 209. 长度最小的子数组

• 此题因为必须是连续数组，而且是求和，因此考虑使用滑动窗口的方法解决
• 如果当前窗口内的元素和大于等于目标值，就将开始位置前移，如果不够就将结束位置后移。

  class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int start = 0, end = -1; int sum = 0; int minLen = INT_MAX; do { // cout<<start<<' '<<end<<endl; if(sum<target) { if(end == nums.size()-1)break; ++end; sum+=nums[end]; } else { if(end-start+1<minLen) { minLen = end - start+1; } sum-=nums[start]; ++start; } }while(end<nums.size() && end>=start); return minLen == INT_MAX?0:minLen; } };

解决的问题

• 字符串的最长回文字串的问题（必须是连续的串）

  获得长度为奇数和偶数的字符串

• 奇数的话直接取每个字符向两边找扩展即可
• 针对偶数可以在每两个字符之间加入一个虚拟的字符，向左右两边扩展得到偶数长度的回文字符串
• 
• 将处理得到的字符串的长度直接/2就可以得到实际的回文串的长度
• 虚拟的字符可以是任意字符，即使是原串之中出现过的字符也可以
• 时间复杂度是O(N^2)

  Manacher

• 时间复杂度是O(N)
• 概念
  • 回文直径和半径
  • 
  • 回文直径7半径4
  • 生成一个回文半径数组
  • 之前扩展的所有位置中所到达过的回文最右边界，初始值是-1
  • 取得最远边界的时候的中心点的位置，与上一条同时更新
• 方法：
  • 假如此时index没在最右回文右边界之内，直接向两边暴力计算即可
  • 假如在最右边界之内：
    • 中心点一定在index的左侧
    • 
    • C是此时的最右回文串的中心位置，L是左边界，R是右边界
    • i’是i关于C的对称点，根据i’的回文状况分类：
      • 假如i’的回文在L和R范围内（用回文半径数组得到）
        • i位置和i’位置的回文半径相同
      • 假如i’的区域有一部分已经到L和R的外侧了
        • 
        • 此时i的答案是i到R的长度
      • 假如i’的左边界正好在L上
        • 
        • 首先i’自身的回文半径一定是回文，从R外的第一个字符开始继续验证即可
    • 

      manacher代码

      public static int manacher(String s) { if (s == null || s.length() == 0) { return 0; } // "12132" -> "#1#2#1#3#2#" char[] str = manacherString(s); // 回文半径的大小 int[] pArr = new int[str.length]; int C = -1; // 讲述中：R代表最右的扩成功的位置 // coding：最右的扩成功位置的，再下一个位置 int R = -1; int max = Integer.MIN_VALUE; for (int i = 0; i < str.length; i++) { // 0 1 2 // R第一个违规的位置，i>= R // i位置扩出来的答案，i位置扩的区域，至少是多大。 pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; while (i + pArr[i] < str.length && i - pArr[i] > -1) { if (str[i + pArr[i]] == str[i - pArr[i]]) pArr[i]++; else { break; } } if (i + pArr[i] > R) { R = i + pArr[i]; C = i; } max = Math.max(max, pArr[i]); } return max - 1; } public static char[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = new char[str.length() * 2 + 1]; int index = 0; for (int i = 0; i != res.length; i++) { res[i] = (i & 1) == 0 ? '#' : charArr[index++]; } return res; } // for test public static int right(String s) { if (s == null || s.length() == 0) { return 0; } char[] str = manacherString(s); int max = 0; for (int i = 0; i < str.length; i++) { int L = i - 1; int R = i + 1; while (L >= 0 && R < str.length && str[L] == str[R]) { L--; R++; } max = Math.max(max, R - L - 1); } return max / 2; }

联想y7000等同系列笔记本电脑CPU被降频以及蓝牙设置丢失解决办法

• CPU被降频为0.78或者CPU的占用封顶34%，同时没有任何风扇转动声音的情况
• 或者是蓝牙的设置直接丢失找不到，电脑失去蓝牙功能
• 拔掉电脑一些外设，包括电源线
• 关机
• 长按电脑开机键20-30s释放静电，再重启即可

KMP

• 求一个字符串是不是另一个字符串子串的问题
• 暴力方法是O(N*M)的复杂度

  最长前缀和后缀的匹配长度

• 一个字符位置存储的信息是匹配长度
• 
  • 上图中前缀从最左算起，后缀从最右算起，等于3的时候相等
  • 将这个信息记录在K这个字符的位置
  • 这个长度必须小于整体的长度
• 以上这个信息需要对str2（也就是较短的字符串）求的
  • 
  • 第一个是-1是人为定义的

    加速过程

• 
  • 当长字符串的匹配进行到x位置的时候发现匹配不能继续，假如此时短字符串的匹配进行到了y位置，那么不需要回退x，只需要回退y到最长前缀的末尾位置（图中画框的位置），相当于不需要从头开始匹配，而是从图上的j位置（下标三角）开始，只需要通过最长前缀和后缀跳过长字符串和短字符串中已经匹配过的段，实际上相当于将短字符串直接后移到最长前缀的位置，然后继续匹配即可。
  • 另一个问题是从i到j位置之间不可能有任何一个位置能够配出短字符串
• 举例
• 
  • 团上的行为是先从两个字符串的头位置开始比对两个字符串，然后到第一个字符串的e位置发现不对，然后寻找此时短字符串的w位置的最长前缀位置的下一个位置也就是t，但是t于e仍然不相等，那么就寻找t位置的最长前缀的下一个位置，也就是s与e比较，但是还不相等，那么就选择s位置的最长前缀的下一个位置是短字符串的开始位置，也不行，此时将长字符串的比较位置后移一位到e的下一个位置，重新开始比较

    如何求

    void getNext (int* next, const string& s) { next[0] = 0; int j = 0; for(int i = 1;i < s.size(); i++) { while(j > 0 && s[i] != s[j]) { j = next[j - 1]; } if(s[i] == s[j]) { j++; } next[i] = j; } }

• j指向的是前缀末尾位置，初始化为0
• i是后缀末尾位置，初始化为1
• next数组第一个位置也初始化为0
• 如果i和j位置的字母不相等，那么j开始回退到上一个位置的前缀结束位置（相当于前缀长度减少了1）
  • 直到前缀和后缀字母相同的位置
• 此时如果前后缀的最后一个位置字母相同，则给j的大小+1，因为相同的话后缀长度+1
• 然后将这个值赋给i位置（也就是当前后缀得末尾位置），记录下到这个位置的最长后缀长度

Leetcode 28. 找出字符串中第一个匹配项的下标

• 讲解
• 注意比较的时候
  • 如果二者不相等，needle就按照当前不匹配位置的前一个位置的next表持续回退到起始或者相等，使得前缀来到原来后缀的位置
  • 如果相等，就二者一起前进一位
  • 如果到达了needle的末尾，就认为是匹配到了，返回位置

    class Solution { public: void getNext(int* next, const string& s) { int j = 0; next[0] = 0; for(int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; } if (s[i] == s[j]) { j++; } next[i] = j; } } int strStr(string haystack, string needle) { if (needle.size() == 0) { return 0; } int next[needle.size()]; getNext(next, needle); int j = 0; for (int i = 0; i < haystack.size(); i++) { while(j > 0 && haystack[i] != needle[j]) { j = next[j - 1]; } if (haystack[i] == needle[j]) { j++; } if (j == needle.size() ) { return (i - needle.size() + 1); } } return -1; } };

并查集

• 参考链接
• 注意，实现的功能是添加边，将一条边两端的两个元素归为一个组合中的两个元素
• 在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根
• 在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u)
{
    if(u != father[u]) // 如果自己不是根节点
    {
		// 将自己的根节点直接改为最顶的根节点
        father[u] = find(father[u]);
    }
    return father[u];
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

Leetcode 1971. 寻找图中是否存在路径

• 此题的原理就是将所有的边加入并查集，最后查找二者是否对应同一个祖先

  class Solution { private: int n = 200005; // 节点数量 20000 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? u : father[u] = find(father[u]); } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } // 将v->u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; } public: bool validPath(int n, vector<vector<int>>& edges, int source, int destination) { init(); for (int i = 0; i < edges.size(); i++) { join(edges[i][0], edges[i][1]); } return isSame(source, destination); } };

Leetcode 684. 冗余连接

• 此题同样是使用并查集
• 主要是在插入之前检测是否边两端的节点已经是一个集合中的了
• 如果不是的话就插入，是的话说明边是冗余的

  class Solution { private: int n = 1005; // 节点数量3 到 1000 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? u : father[u] = find(father[u]); } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } // 将v->u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; } public: vector<int> findRedundantConnection(vector<vector<int>>& edges) { init(); for (int i = 0; i < edges.size(); i++) { if (isSame(edges[i][0], edges[i][1])) return edges[i]; else join(edges[i][0], edges[i][1]); } return {}; } };

最小生成树问题

• 此题是找能将所有点联通的最小代价的所有路径
• 使用kruskal算法
  • 初始化一个并查集，最开始每个节点都是独立的
  • 将所有路径加入一个代价从小到大的最小堆，每次取出一个路径
  • 如果路径两端的点在一个集合中，则忽略，如果不在，则该路径是必须的路径，加入需要的路径集合中并且加入总代价中

    #include <iostream> #include <vector> #include <queue> using namespace std; vector<int> father; struct edge { int start; int end; int val; }; int find(int u) { if(u != father[u]) { father[u] = find(father[u]); } return father[u]; } bool isSame(int u, int v) { return find(u) == find(v); } void join(int u, int v) { u = find(u); v = find(v); if(u == v)return; father[v] = u; } int main() { int n, e; cin>>n>>e; father = vector<int>(n+1, 0); for(int i = 1 ;i<=n; ++i) { father[i] = i; } auto cmp = [](const edge& a, const edge& b) { return a.val > b.val; }; // int conned = 1; priority_queue<edge, vector<edge>, decltype(cmp)> pq(cmp); struct edge tmp; for(int i = 0; i<e; ++i) { cin>>tmp.start>>tmp.end>>tmp.val; pq.push(tmp); } int sum = 0; while(pq.size()) { tmp = pq.top(); // cout<<tmp.val<<endl; pq.pop(); if(!isSame(tmp.start, tmp.end)) { sum+=tmp.val; join(tmp.start, tmp.end); } } cout<<sum<<endl; }

41. 岛屿数量（第四期模拟笔试）

• 链接
• 此题是标准的并查集问题

  #include <iostream> #include <vector> #include <cstdlib> using namespace std; int find(vector<int>& father, int u) { if(u!=father[u]) { father[u] = find(father, father[u]); } return father[u]; } bool isSame(int u, int v, vector<int>& father) { return find(father, u) == find(father, v); } bool join(vector<int>& father, int u, int v) { u = find(father, u); v = find(father, v); if(u == v)return false; else father[v] = u; return true; } int main() { int m, n, k; cin>>m>>n>>k; vector<vector<int>> map(m, vector<int>(n, 0)); vector<int> father(m*n, 0); for(int i = 0; i<m*n; ++i) { father[i] = i; } int a, b; int cnt = 0; for(int i = 0; i<k; ++i) { cin>>a>>b; if(a>=m || b>=n || a<0 || b<0) { cout<<cnt<<' '; continue; } if(!map[a][b]) ++cnt; map[a][b] = 1; bool tmp = false; if(a>0 && map[a-1][b]) { tmp = join(father, (a-1)*m+b, a*m+b); cnt-=tmp; } if(b>0 && map[a][b-1]) { tmp = join(father, (a*m+b-1), a*m+b); cnt-=tmp; } if(a<m-1 && map[a+1][b]) { tmp = join(father, (a+1)*m+b, a*m+b); cnt-=tmp; } if(b<n-1 && map[a][b+1]) { tmp =join(father, a*m+b+1, a*m+b); cnt-=tmp; } cout<<cnt<<' '; } }

哈希函数

• 哈希函数的输入数据一般是巨量的，输出数据的的范围往往是有限的

• 哈希函数的输出存在均匀性，也就是无论输入是什么，输入是否接近，输出均匀分布在整个输出域之中。

  哈希表处理冲突位置（映射）的方法

• 链接法：

  • 对于经过哈希函数得到同一个index的数据，利用链表（或者类似的形式）将其串联起来，寻找的时候先进行哈希得到index，然后再该index对应的位置逐个遍历链表得到要找的对象

• 其他方法参考链接 参考

  一致性哈希

• 用在给服务器分配数据问题减少迁移数据的工作量

• 一般情况下将输入数据的key值进行哈希，哈希得到的结果对服务器的数量取模，按照取得的结果分配到不同的服务器上，但是此时假如增加或者减少了服务器，就会因为取模的数字变化导致整个系统的哈希取模的数字都需要重新计算和分配，进而整体前迁移，工作量很大

• 引入一致性哈希得目的是减少上文描述得前移工作量

• 

• 将三个机器的特征名称进行哈希，哈希过后将三个机器放在一个由哈希结果范围组成的环上（最大值和最小值头尾相接）。此时得到一个数据，同样将数据进行哈希，哈希得到的结果在环上找距离最近（此处的算法可以更换）的服务器存储该数据，假如数据的哈希值比所有服务器的哈希值都大的话就找哈希值最小的服务器，因为大小首尾相接。

  增加机器

• 

• 假如此时需要增加M4，那么只需要将M3和M4之间的数据迁移到M4即可，不需要将所有数据进行重新计算迁移。

• 潜在问题：

  • 一开始的时候因为机器的地址是哈希得到的，未必均衡
  • 增加机器之后可能导致局部机器比较密集，同样负载不均衡

• 解决上述问题的方法：虚拟节点技术

  • 

  • 给每个服务器分配多个用于哈希的序列，每个服务器在环上具有多个对应的序列哈希得到的节点位置，相对均匀，同时也比较方便虚拟节点之间的数据迁移

  • 不同的机器可以根据机器性能和状态的不同分配不同数量的虚拟节点，实现对于负载比例的不同分配。

图对象的定义

package class16;

import java.util.HashMap;
import java.util.HashSet;

public class Graph {
	public HashMap<Integer, Node> nodes;
	public HashSet<Edge> edges;
	
	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>();
	}
}

边对象的定义

package class16;

public class Edge {
	public int weight;
	public Node from;
	public Node to;

	public Edge(int weight, Node from, Node to) {
		this.weight = weight;
		this.from = from;
		this.to = to;
	}

}

节点对象的定义

package class16;

import java.util.ArrayList;

// 点结构的描述
public class Node {
	public int value;
	public int in;
	public int out;
	public ArrayList<Node> nexts;
	public ArrayList<Edge> edges;

	public Node(int value) {
		this.value = value;
		in = 0;
		out = 0;
		nexts = new ArrayList<>();
		edges = new ArrayList<>();
	}
}

BFS

package class16;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Code01_BFS {

	// 从node出发，进行宽度优先遍历
	public static void bfs(Node start) {
		if (start == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		HashSet<Node> set = new HashSet<>();
		queue.add(start);
		set.add(start);
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			System.out.println(cur.value);
			for (Node next : cur.nexts) {
				if (!set.contains(next)) {
					set.add(next);
					queue.add(next);
				}
			}
		}
	}

}

• 主要是在添加一个节点的所有相邻节点到队列里的时候使用了一个set结构判断这个节点是否被添加过，防止无限循环的产生

  DFS

  package class16; import java.util.HashSet; import java.util.Stack; public class Code02_DFS { public static void dfs(Node node) { if (node == null) { return; } Stack<Node> stack = new Stack<>(); HashSet<Node> set = new HashSet<>(); stack.add(node); set.add(node); System.out.println(node.value); while (!stack.isEmpty()) { Node cur = stack.pop(); for (Node next : cur.nexts) { if (!set.contains(next)) { stack.push(cur); stack.push(next); set.add(next); System.out.println(next.value); break; } } } } }

• 使用一个栈的数据结构，每从栈中弹出一个节点的时候，遍历该节点的所有邻接点，如果不在已经遍历过的节点的set内，那么先将节点自身进栈，然后再将该邻接节点进栈

  最小生成树

• 对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（树中所有边上的权值和）也不同，设R为G的所有生成树的集合，若T为R中权值和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）

  kruskal算法

• 并查集：具有检查数据结构中的一些节点是否在同一个集合中、以及将不同的集合合并为一个集合的功能的数据结构

  package class16; import java.util.Collection; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; import java.util.Stack; //undirected graph only public class Code04_Kruskal { // Union-Find Set public static class UnionFind { // key 某一个节点， value key节点往上的节点 private HashMap<Node, Node> fatherMap; // key 某一个集合的代表节点, value key所在集合的节点个数 private HashMap<Node, Integer> sizeMap; public UnionFind() { fatherMap = new HashMap<Node, Node>(); sizeMap = new HashMap<Node, Integer>(); } public void makeSets(Collection<Node> nodes) { fatherMap.clear(); sizeMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); sizeMap.put(node, 1); } } private Node findFather(Node n) { Stack<Node> path = new Stack<>(); while(n != fatherMap.get(n)) { path.add(n); n = fatherMap.get(n); } while(!path.isEmpty()) { fatherMap.put(path.pop(), n); } return n; } public boolean isSameSet(Node a, Node b) { return findFather(a) == findFather(b); } public void union(Node a, Node b) { if (a == null || b == null) { return; } Node aDai = findFather(a); Node bDai = findFather(b); if (aDai != bDai) { int aSetSize = sizeMap.get(aDai); int bSetSize = sizeMap.get(bDai); if (aSetSize <= bSetSize) { fatherMap.put(aDai, bDai); sizeMap.put(bDai, aSetSize + bSetSize); sizeMap.remove(aDai); } else { fatherMap.put(bDai, aDai); sizeMap.put(aDai, aSetSize + bSetSize); sizeMap.remove(bDai); } } } } public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> kruskalMST(Graph graph) { UnionFind unionFind = new UnionFind(); unionFind.makeSets(graph.nodes.values()); // 从小的边到大的边，依次弹出，小根堆！ PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); for (Edge edge : graph.edges) { // M 条边 priorityQueue.add(edge); // O(logM) } Set<Edge> result = new HashSet<>(); while (!priorityQueue.isEmpty()) { // M 条边 Edge edge = priorityQueue.poll(); // O(logM) if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1) result.add(edge); unionFind.union(edge.from, edge.to); } } return result; } }

• findfFather函数是当一个节点具有多级的父亲的时候找到最高级别的父亲，并且修改一路上所有节点的父亲为最高级的父亲
• 算法的思路是先按照权值将图中所有的边都放入小根堆中，将图中所有节点放入并查集中独立存在，然后从堆中依次弹出边，假如边链接的两端不是同一个集合，那么将边放入结果中，同时在并查集中合并两个集合，直到无可合并为止。

  prim算法

  package class16; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; // undirected graph only public class Code05_Prim { public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> primMST(Graph graph) { // 解锁的边进入小根堆 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); // 哪些点被解锁出来了 HashSet<Node> nodeSet = new HashSet<>(); Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里 for (Node node : graph.nodes.values()) { // 随便挑了一个点 // node 是开始点 if (!nodeSet.contains(node)) { nodeSet.add(node); for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边 priorityQueue.add(edge); } while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边 Node toNode = edge.to; // 可能的一个新的点 if (!nodeSet.contains(toNode)) { // 不含有的时候，就是新的点 nodeSet.add(toNode); result.add(edge); for (Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); } } } } // break; } return result; } // 请保证graph是连通图 // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路 // 返回值是最小连通图的路径之和 public static int prim(int[][] graph) { int size = graph.length; int[] distances = new int[size]; boolean[] visit = new boolean[size]; visit[0] = true; for (int i = 0; i < size; i++) { distances[i] = graph[0][i]; } int sum = 0; for (int i = 1; i < size; i++) { int minPath = Integer.MAX_VALUE; int minIndex = -1; for (int j = 0; j < size; j++) { if (!visit[j] && distances[j] < minPath) { minPath = distances[j]; minIndex = j; } } if (minIndex == -1) { return sum; } visit[minIndex] = true; sum += minPath; for (int j = 0; j < size; j++) { if (!visit[j] && distances[j] > graph[minIndex][j]) { distances[j] = graph[minIndex][j]; } } } return sum; } public static void main(String[] args) { System.out.println("hello world!"); } }

• prim算法主要用到一个存储边用的小根堆和一个记录哪些点被解锁的set
• 首先在graph中随便选择一个点，将这个点加入记录解锁的点的集合，然后将这个点的所有边放入优先级队列中，然后开始while循环，每次从优先级队列中弹出一个权值最小的边，假如这个边指向的节点不在前面的set中的话就将这个边指向的节点放入点set中，将这条边放入结果中，然后将该节点延伸出的所有边放入优先级队列中。

  Dijkstra算法

• 该算法主要是找到指定起始点到图上剩余所有点的最近距离

  package class16; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; // no negative weight public class Code06_Dijkstra { public static HashMap<Node, Integer> dijkstra1(Node from) { HashMap<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(from, 0); // 打过对号的点 HashSet<Node> selectedNodes = new HashSet<>(); Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); while (minNode != null) { // 原始点 -> minNode(跳转点) 最小距离distance int distance = distanceMap.get(minNode); for (Edge edge : minNode.edges) { Node toNode = edge.to; if (!distanceMap.containsKey(toNode)) { distanceMap.put(toNode, distance + edge.weight); } else { // toNode distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight)); } } selectedNodes.add(minNode); minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; for (Entry<Node, Integer> entry : distanceMap.entrySet()) { Node node = entry.getKey(); int distance = entry.getValue(); if (!touchedNodes.contains(node) && distance < minDistance) { minNode = node; minDistance = distance; } } return minNode; } public static class NodeRecord { public Node node; public int distance; public NodeRecord(Node node, int distance) { this.node = node; this.distance = distance; } }

• 算法主要依赖一个记录到对应节点最近距离的哈希表和一个记录某个节点是否已经被锁定的set
• 在初始时刻将起始点到起始点放入哈希表，并且将其距离设置为0。
• 然后的while循环每次都对找出的当前尚未被锁定而且在哈希表中到起始位置距离最小的点指向的所有尚未被锁定的节点的距离进行重算，假如被指向的节点之前的距离小于从该点出发到被指向的点的距离，将被指向点的距离更新为被选中的点出发的距离。（假如被指向的点不存在于哈希表中的话认为被指向的点的距离为正无穷，同样添加该点的距离条目进行更新）。然后将当前选中的点锁定，也就是加入被锁定的点的set中，然后找到当前未被锁定而且从总出发点开始距离最短的点，再次重复循环。

卡码网 29. 安排超市（第一期模拟笔试）

• 此题先用bfs找到每个分立的区域，假如某个独立的区域里具有住户，则需要设置超市，超市尽可能的少
• 然后寻找到每个住户综合距离最小的超市，实际上可以从每个住户出发bfs遍历所在的区域，bfs每前进一层，意味着从住户出发到这个位置的距离+1，由此可以得出住户出发到这个区域每个位置的距离
• 对每个住户执行上述操作然后累加，就可以找出从每个位置出发到每个住户距离之和
• 找出每个区域中距离之和最小的位置即可作为超市的位置
• 注意bfs的时候需要一遇到某个点就在visited数组中标记这个位置，而不是从队列中弹出的时候再标记这个位置，否则会导致这个位置入队多次，使得算法超时

  #include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <climits> #include <algorithm> #include <numeric> using namespace std; // set<pair<int, int>> houses; // vector<vector<pair<short, short>>> regions; vector<vector<bool>> visited; vector<vector<short>> m; vector<vector<int>> dist; vector<vector<short>> region; // vector<vector<bool>> visitedDis; void bfs4Reg(int x0, int y0, int n, int reg) { queue<pair<int, int>> q; q.push({x0, y0}); region[x0][y0] = reg; visited[x0][y0] = true; while(q.size()) { auto tmp = q.front(); q.pop(); int x = tmp.first; int y = tmp.second; // if(m[x][y] == 1)houses.insert({x, y}); if(x>0 && !visited[x-1][y] && m[x-1][y]<2) { region[x-1][y] = reg; visited[x-1][y] = true; q.push({x-1, y}); } if(y>0 && !visited[x][y-1] && m[x][y-1]<2) { region[x][y-1] = reg; visited[x][y-1] = true; q.push({x, y-1}); } if(x<n-1 && !visited[x+1][y] && m[x+1][y]<2) { region[x+1][y] = reg; visited[x+1][y] = true; q.push({x+1, y}); } if(y<n-1 && !visited[x][y+1] && m[x][y+1]<2) { region[x][y+1] = reg; visited[x][y+1] = true; q.push({x, y+1}); } } } void disFromHouse(int x, int y, int n) { queue<pair<int, int>> q; q.push({x, y}); visited[x][y] = true; int curDis = 0; while (q.size()) { int v = q.size(); for(int i = 0; i<v; ++i) { auto tmp = q.front(); q.pop(); int x = tmp.first; int y = tmp.second; dist[x][y] += curDis; if(x>0 && !visited[x-1][y] && m[x-1][y]<2) { q.push({x-1, y}); visited[x-1][y] = true; } if(y>0 && !visited[x][y-1] && m[x][y-1]<2) { q.push({x, y-1}); visited[x][y-1] = true; } if(x<n-1 && !visited[x+1][y] && m[x+1][y]<2) { q.push({x+1, y}); visited[x+1][y] = true; } if(y<n-1 && !visited[x][y+1] && m[x][y+1]<2) { q.push({x, y+1}); visited[x][y+1] = true; } } ++curDis; } } int main() { int n; cin>>n; visited = vector<vector<bool>>(n, vector<bool>(n, false)); m = vector<vector<short>>(n, vector<short>(n, 0)); dist = vector<vector<int>>(n, vector<int>(n, 0)); region = vector<vector<short>>(n, vector<short>(n, 0)); // visitedDis = vector<vector<bool>>(n, vector<bool>(n, false)); char tmp; for(auto &row:m) { for(auto& i:row) { cin>>tmp; switch (tmp) { case '*': i = 2; /* code */ break; case '.': i = 0; break; case '#': i = 1; break; default: break; } } } if(n == 0) { cout<<0<<' '<<0<<endl; return 0; } int regCnt = 0; for(int i = 0; i<n; ++i) { for(int j = 0; j<n; ++j) { if(!visited[i][j] && m[i][j]<2) { bfs4Reg(i, j, n, regCnt++); } } } int sumOfDist = 0; int minDist = INT_MAX; vector<bool> hasHouse(regCnt, false); for(int i = 0; i<n; ++i) { for(int j = 0; j<n; ++j) { if(m[i][j] == 1) { visited = vector<vector<bool>>(n, vector<bool>(n, false)); disFromHouse(i, j, n); hasHouse[region[i][j]] = true; } } } vector<int> regMin(regCnt, INT_MAX); for(int i = 0; i<n; ++i) { for(int j = 0; j<n; ++j) { if(m[i][j]>1)continue; regMin[region[i][j]] = min(regMin[region[i][j]], dist[i][j]); } } int disSUm = 0; int marketCnt = 0; for(int i = 0; i<regCnt; ++i) { if(hasHouse[i]) { disSUm+=regMin[i]; ++marketCnt; } } cout<<marketCnt<<' '<< disSUm <<endl; // cout<<regions.size()<<' '<<0<<endl; }

牛客美团2024秋招第一场第三题

• 小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
  • 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
  • 小美想知道，自己最多可以染红多少个节点？
• 此题的关键是防止重复经过同一个节点，因此需要一个used数组，经过的时候设置为true，经过之后设置为false
• 此外就是回溯法寻找，注意一个节点有标红当前节点和不标红当前节点两种情况

  #include <cstring> #include <iostream> #include <cmath> #include <vector> using namespace std; vector<int>* to; int* arr; int* dp; int* dpf; bool* red; int n; bool* used; bool isSq(int n) { int x = sqrt(n); if (x*x != n) return false; return true; } int traversal(int beg, bool able) { if(used[beg])return 0; if(able && dp[beg]>=0)return dp[beg]; else if(!able && dpf[beg]>=0)return dpf[beg]; used[beg] = true; int sum = 0; int maxRet = 0; for(auto i : to[beg]) { sum+=traversal(i, true); } if(!able) { dpf[beg] = sum; used[beg] = false; return sum; } maxRet = sum; for(auto i : to[beg]) { if(!used[i] && isSq(arr[beg]*arr[i]) && i != beg) { // int iSum = 0; // cout<<i<<'|'<<beg<<endl; maxRet = max(maxRet, sum+2-traversal(i, true)+traversal(i, false)); } } dp[beg] = maxRet; used[beg] = false; return maxRet; } int main() { cin>>n; // cout<<isSq(92*19)<<'!'<<endl; to = new vector<int>[n]; arr = new int[n]; dp = new int[n]; dpf = new int[n]; red = new bool[n]; used = new bool[n]; memset(used, 0 ,sizeof(bool)*n); memset(red, 0, sizeof(bool)*n); for(int i = 0; i<n; ++i) { dp[i] = -1; dpf[i] = -1; } for(int i = 0; i<n; ++i) { cin>>arr[i]; } int u,v; for(int i = 0; i<n-1; ++i) { cin>>u>>v; to[u-1].push_back(v-1); to[v-1].push_back(u-1); } cout<<traversal(0, true)<<endl; } // 64 位输出请用 printf("%lld")