leetcode解题思路分析（六十二）526 - 532 题

亦凉 2022-10-25 05:49 81阅读 0赞

1.  优美的排列  
    假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：  
    第 i 位的数字能被 i 整除  
    i 能被第 i 位上的数字整除  
    现在给定一个整数 N，请问可以构造多少个优美的排列？

**求全排列必然可以通过回溯解决。通过回溯解决就可以思考是否存在最优子结构或者通俗的说，是否存在相同的分支。通过记忆的方式剪枝，换个形式表达就是动态规划的数组dp。这里还有个小技巧：为了减少存储量，可以选择按位存储。用一个n位的二进制数表示二进制中为1的数字已任意顺序放在数组的前m位（m为该二进制数中1的个数）。dp\[n\]表示二进制数n代表的所有排列中有效情况的数量。对于二进制中为0的位，判断是否可以作为下一个放入数组中的数，若是则更新dp\[n | (1 << j)\] += dp\[n\]。例如010101中，第2位为0，判断其是否可放在数组第4位（因为数组已有3个数），显然可以（4%2==0），更新dp\[010101 | (1 << (2-1))\] += dp\[010101\]**

class Solution { 
    public:
        int countArrangement(int N) 
        {         
            vector<int> dp(1 << N, 0);
            //每个数都能放在第1位
            for(int i = 0; i < N; ++i)
            { 
                dp[1 << i] = 1;
            }
    
            for(int i = 0; i < (1 << N); ++i)
            { 
                int index = 1;
                int temp = i;
                //计算1的个数
                while (temp)
                { 
                    temp &= temp-1;
                    ++index;
                }
    
                for(int j = 0;j < N;++j)
                { 
                    //二进制位为0（未被选取）,且能放在第index位
                    if(!(i & (1 << j)) && ((j+1) % index == 0 || index % (j+1) == 0))
                    { 
                        dp[1 << j | i] += dp[i];
                    }
                }
            }
    
            return dp[(1 << N) -1];
        }
    };

1.  按权重随机选择  
    给定一个正整数数组 w ，其中 w\[i\] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w\[i\] 成正比。

**保存每个整数的边界，然后取随机数时二分查找**

class Solution { 
    public:
        vector<int> psum;
        int tot = 0;
        //c++11 random integer generation
        mt19937 rng{ random_device{ }()};
        uniform_int_distribution<int> uni;
    
        Solution(vector<int> w) { 
            for (int x : w) { 
                tot += x;
                psum.push_back(tot);
            }
            uni = uniform_int_distribution<int>{ 0, tot - 1};
        }
    
        int pickIndex() { 
            int targ = uni(rng);
    
            int lo = 0, hi = psum.size() - 1;
            while (lo != hi) { 
                int mid = (lo + hi) / 2;
                if (targ >= psum[mid]) lo = mid + 1;
                else hi = mid;
            }
            return lo;
        }
    };
    
    
    /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(w); * int param_1 = obj->pickIndex(); */

1.  扫雷游戏  
    给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，‘E’ 代表一个未挖出的空方块，‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，‘X’ 则表示一个已挖出的地雷。  
    现在给出在所有未挖出的方块中（‘M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：  
    如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’。  
    如果一个没有相邻地雷的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的未挖出方块都应该被递归地揭露。  
    如果一个至少与一个地雷相邻的空方块（‘E’）被挖出，修改它为数字（‘1’到’8’），表示相邻地雷的数量。  
    如果在此次点击中，若无更多方块可被揭露，则返回面板。

**深度优先搜索为例：我们定义递归函数 dfs(x, y) 表示当前在 (x,y)(x,y) 点，执行扫雷规则的情况，我们只要按照上面理出来的情况来进行模拟即可，在 \\textit\{cnt\}cnt 为零的时候，对当前点相邻的未挖出的方块调用递归函数，否则将其改为数字，结束递归。**

class Solution { 
    public:
        int dir_x[8] = { 0, 1, 0, -1, 1, 1, -1, -1};
        int dir_y[8] = { 1, 0, -1, 0, 1, -1, 1, -1};
    
        void dfs(vector<vector<char>>& board, int x, int y) { 
            int cnt = 0;
            for (int i = 0; i < 8; ++i) { 
                int tx = x + dir_x[i];
                int ty = y + dir_y[i];
                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) { 
                    continue;
                }
                // 不用判断 M，因为如果有 M 的话游戏已经结束了
                cnt += board[tx][ty] == 'M';
            }
            if (cnt > 0) { 
                // 规则 3
                board[x][y] = cnt + '0';
            } else { 
                // 规则 2
                board[x][y] = 'B';
                for (int i = 0; i < 8; ++i) { 
                    int tx = x + dir_x[i];
                    int ty = y + dir_y[i];
                    // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
                    if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') { 
                        continue;
                    }
                    dfs(board, tx, ty);
                }
            }
        }
    
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { 
            int x = click[0], y = click[1];
            if (board[x][y] == 'M') { 
                // 规则 1
                board[x][y] = 'X';
            } else { 
                dfs(board, x, y);
            }
            return board;
        }
    };

1.  二叉搜索树的最小绝对差  
    给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

**二叉搜索树中序遍历即为升序数组，所以直接比较相邻元素的差值即可。但是为了减少遍历，可以在中序遍历过程中直接做了**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        void dfs(TreeNode* root, int& pre, int& ans) { 
            if (root == nullptr) { 
                return;
            }
            dfs(root->left, pre, ans);
            if (pre == -1) { 
                pre = root->val;
            } else { 
                ans = min(ans, root->val - pre);
                pre = root->val;
            }
            dfs(root->right, pre, ans);
        }
        int getMinimumDifference(TreeNode* root) { 
            int ans = INT_MAX, pre = -1;
            dfs(root, pre, ans);
            return ans;
        }
    };

1.  数组中的k-diff数对  
    给定一个整数数组和一个整数 k，你需要在数组里找到不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。这里将 k-diff 数对定义为一个整数对 (nums\[i\], nums\[j\])，并满足下述全部条件：  
    0 <= i, j < nums.length  
    i != j  
    |nums\[i\] - nums\[j\]| == k  
    注意，|val| 表示 val 的绝对值。

**用红黑树存储自带排序，然后遍历一遍即可。单向查找可以避免重复。另外需要注意k为0需要单独讨论**

class Solution { 
    public:
        int findPairs(vector<int>& nums, int k) 
        { 
            int ret = 0;
            map<int, int> m_map;
    
            for (auto n : nums)
            { 
                m_map[n]++;
            }
    
            if (k == 0)
            { 
                for (auto p : m_map)
                { 
                    if (p.second > 1)
                    { 
                        ret++;
                    }
                }
                return ret;
            }
    
            for (map<int, int>::iterator iter = m_map.begin(); iter != m_map.end(); ++iter)
            { 
                if (m_map.count(iter->first + k))
                { 
                    ret++;
                    m_map[iter->first +k]--;
                }
            }
    
            return ret;
        }
    };