剑指Offer II --- 2021/9/2

一时失言乱红尘 2022-09-09 14:53 97阅读 0赞

### 目录 ###

*  剑指Offer II 116. 朋友圈
 *  剑指Offer II 098. 路径的数目
 *  剑指Offer II 068. 查找插入位置
 *  剑指Offer II 078. 合并排序链表
 *  剑指Offer II 066. 单词之和
 *  剑指Offer II 070. 排序数组中只出现一次的数字
 *  剑指Offer II 076. 数组中的第 k 大的数字
 *  剑指Offer II 080. 含有 k 个元素的组合
 *  剑指Offer II 002. 二进制加法
 *  剑指Offer II 084. 含有重复元素集合的全排列

# 剑指Offer II 116. 朋友圈 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]  
分析：  
  并查集，参考：[并查集的介绍及简单应用—蓝桥杯真题：合根植物][Link 1]  
代码：

class Solution { 
    private:
        int get_root(int x) { 
            if(fa[x] != x) { 
                fa[x] = get_root(fa[x]);
            }
            return fa[x];
        }
        
        void merge(int a, int b) { 
            fa[get_root(a)] = get_root(b);
        }
        
        bool query(int a, int b) { 
            return get_root(a) == get_root(b);
        }
        
    public:
        vector<int> fa;
        int findCircleNum(vector<vector<int>>& isConnected) { 
            int n = isConnected.size();
            fa = vector<int>(n);
            for(int i = 0; i < n; i++) { 
                fa[i] = i;
            }
            for(int i = 0; i < n; i++) { 
                for(int j = 0; j < n; j++) { 
                    if(isConnected[i][j]) { 
                        merge(i, j);
                    }
                }
            }
            set<int> s;
            for(int i = 0; i < n; i++) { 
                s.insert(get_root(i));
            }
            return s.size();
        }
    };

# 剑指Offer II 098. 路径的数目 #

[不同路径][Link 2]

# 剑指Offer II 068. 查找插入位置 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
分析：  
  要求O(logn)，所以使用二分查找。  
代码：

class Solution { 
    public:
        int searchInsert(vector<int>& nums, int target) { 
            int low = 0, high = nums.size() - 1;
            while(low <= high) { 
                int mid = low + (high - low) / 2;
                if(target > nums[mid]) { 
                    low = mid + 1;
                }else if(target < nums[mid]) { 
                    high = mid - 1;
                }else { 
                    return mid;
                }
            }
            return low;
        }
    };

# 剑指Offer II 078. 合并排序链表 #

[合并K个升序链表][K]

# 剑指Offer II 066. 单词之和 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
分析：  
  遍历判断是否满足条件再相加。  
代码：

class MapSum { 
    public:
        /** Initialize your data structure here. */
        unordered_map<string, int> mp;
        MapSum() { 
    
        }
        
        void insert(string key, int val) { 
            mp[key] = val;
        }
        
        int sum(string prefix) { 
            int res = 0, n = prefix.size();
            for(auto& [x, y] : mp) { 
                if(x.size() >= n && x.substr(0, n) == prefix) { 
                    res += y;
                }
            }
            return res;
        }
    };
    
    /** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */

# 剑指Offer II 070. 排序数组中只出现一次的数字 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
方法一：  
  异或运算。  
代码：

class Solution { 
    public:
        int singleNonDuplicate(vector<int>& nums) { 
            int ret = 0;
            for(int x : nums) { 
                ret ^= x;
            }
            return ret;
        }
    };

方法二：  
  二分法：将所有数字两两分组，比如112334488分为11 23 34 48 8，然后二分查找某一个组，如果该组的两个数不相等但其前面一组两个数相等就返回。  
代码：

class Solution { 
    public:
        int singleNonDuplicate(vector<int>& nums) { 
            int left = 0;
            int right = nums.size() / 2 - 1;
            while (left <= right) { 
                int mid = left + ((right - left) >> 1);
                int i = 2 * mid;
                if (nums[i] != nums[i + 1]) { 
                    if (i == 0 || nums[i - 1] == nums[i - 2]) { 
                        return nums[i];
                    }
                    right = mid - 1;
                }
                else { 
                    left = mid + 1;
                }
            }
            return nums.back();
        }
    };

# 剑指Offer II 076. 数组中的第 k 大的数字 #

[数组中的第K个最大元素][K 1]

# 剑指Offer II 080. 含有 k 个元素的组合 #

[组合][Link 3]

# 剑指Offer II 002. 二进制加法 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
分析：  
  从尾开始模拟二进制加法。  
代码：

class Solution { 
    public:
        string addBinary(string a, string b) { 
            string res = "";
            int n = a.size(), m = b.size();
            int i = n - 1, j = m - 1, cnt = 0;
            while(i >= 0 || j >= 0) { 
                int x, y;
                if(i < 0) { 
                    x = 0;
                }else { 
                    stringstream ss;
                    ss << a[i];
                    ss >> x;
                }
                if(j < 0) { 
                    y = 0;
                }else { 
                    stringstream ss;
                    ss << b[j];
                    ss >> y;
                }
                int sum = x + y + cnt;
                // cout << sum << endl;
                cnt = sum / 2;
                res += to_string(sum % 2);
                i--;
                j--;
            }
            if(cnt != 0) { 
                res += to_string(cnt);
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

# 剑指Offer II 084. 含有重复元素集合的全排列 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
分析：  
  c++的next\_permutation()。  
代码：

class Solution { 
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) { 
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());
            do { 
                res.push_back(nums);
            }while(next_permutation(nums.begin(), nums.end()));
            return res;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/05c173a860144632b3607c5eb654abdf.png
[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/106054630
[Link 2]: https://blog.csdn.net/Cyril_KI/article/details/119272100
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/e0feaee1afff43c0af1ed93811331a05.png
[K]: https://blog.csdn.net/Cyril_KI/article/details/119547932
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/8b1f6d4238c94d7f9718c9f90d84d72c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/74e88681be3041c9bb1645714d899d3a.png
[K 1]: https://blog.csdn.net/Cyril_KI/article/details/119345922
[Link 3]: https://blog.csdn.net/Cyril_KI/article/details/118853036
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/d54195e9e37844959578ed3359592bc5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ3lyaWxfS0k_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/92162686e6924a039ad5ccb6f0ace391.png