day5 6 7-牛客67道剑指offer-JZ43、45、49、50、51、52、53、55、79、数组中只出现一次的数字

文章目录

  • 1. JZ43 整数中1出现的次数（从1到n整数中1出现的次数）
  • 2. JZ45 把数组排成最小的数
  • 3. JZ49 丑数
    • 最小堆
    • 三指针法 动态规划
  • 4. JZ50 第一个只出现一次的字符
  • 5. JZ51 数组中的逆序对
  • 6. JZ52 两个链表的第一个公共结点
    • 迭代
    • 递归
  • 7. JZ53 数字在升序数组中出现的次数
  • 8. JZ55 二叉树的深度
    • 递归
    • 迭代
  • 9. JZ79 判断是不是平衡二叉树
    • 自底向上 后序遍历
    • 自上向底 前序遍历
  • 10. 数组中只出现一次的数字
    • 哈希表
    • 位运算
  • 补充内容 - 并归排序

1. JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

在这里插入图片描述题目描述：输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数。例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次，注意：11 这种情况算两次。
力扣K神的题解，在这里

在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述

  1. 总结起来就是，某位中 1 出现的次数，根据当前位 cur 的值，分为以下三种情况：
  • 当 cur=0 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：high×digit
  • 当 cur=1 时： 此位 1 的出现次数由高位 high 和低位 low 决定，计算公式为：high×digit+low+1
  • 当 cur=2~9 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：(high+1)×digit
  1. 举例，n = 32104，从个位开始计算：
  • 初始化 high=3210，cur=4，low=0，digit=1，result=0
  • 每一轮计算如下：
位数highcurlowdigit1的次数result
个位3210401（3210+1）× 1 = 32113211
十位3210410321×10 = 32106421
百位3210410032×100+4+1 = 32059626
千位321041000（3+1）× 1000 = 400013626
万位03210110000（0+1）× 10000 = 1000023626
  • 每一位数计算完1的出现次数后，都要更新位数：
while (high != 0 || cur != 0) { // 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出low += cur * digit; // 将 cur 加入 low ，组成下轮 lowcur = high % 10; // 下轮 cur 是本轮 high 的最低位high /= 10; // 将本轮 high 最低位删除，得到下轮 highdigit *= 10; // 位因子每轮 × 10
}

class Solution {
public:int NumberOf1Between1AndN_Solution(int n) {int result = 0;int digit = 1, low = 0, cur = n % 10, high = n / 10;while (high != 0 || cur != 0) //high=0 说明位数遍历结束{if(cur == 0) result += high * digit;else if (cur == 1) result += high * digit + low + 1;else result += (high + 1) * digit;//位数更新low += cur * digit;cur = high % 10; // 下一位位数 就是 当前高位 对10取余high = high / 10;digit *= 10; // 前进一位}return result;}
};
  • 另一种写法
    int NumberOf1Between1AndN_Solution(int n){if(n <= 0) return 0;if(n< 10 ) return 1;if(n == 10) return 2;int pow = 1, high = n,last = 0;while(high >= 10){high = high/10;pow *=10;}last = n - high*pow;// 除去最高位的数字，还剩下多少 0-999 1000- 1999 2000-2999 3000 3345int cut = high == 1 ? last+1: pow;return cut + high*NumberOf1Between1AndN_Solution(pow-1) + NumberOf1Between1AndN_Solution(last);}

2. JZ45 把数组排成最小的数

在这里插入图片描述

  1. 思路是要求排成最小的数，那么数组中数字越大的越靠前，拼接的数字就越小。

  2. 按照一定规则把数组排序，保证数组中的数字是降序。写一个布尔类型的排序规则函数，作为sort的比较函数。排序后从头遍历，逐一拼接数字。

  3. 排序规则是两个整数拼接，比较大小，返回拼接后较小的结果。具体地，把数字a、b转成字符串ab、ba，返回ab < ba 的结果。如果ab < ba为真，说明a在前b在后的排序正确，即降序，否则为升序。例如3、11，因为113 < 311，所以返回113 < 311，排序后为11、3。

  4. 写法1

#include <algorithm>
#include <string>
class Solution {
public:string result ="";string PrintMinNumber(vector<int>& numbers) {if(numbers.size() == 0) return result;sort(numbers.begin(), numbers.end(), cmpStr);for(int i=0; i<numbers.size(); i++){result += to_string(numbers[i]);}return result;}static bool cmpStr(int a, int b){/*把数字a、b转成字符串 ab ba 比较大小 返回 ab < ba 的结果。如11 3,因为113 < 311，所以排序后为11 3。要求排成最小的数 数字越大放在越前 拼接的数字越小*/string A="", B="";A += to_string(a);A += to_string(b);B += to_string(b);B += to_string(a);return A < B;//如果是排成最大 返回A > B}
};
  1. 写法2
#include <algorithm>
#include <string>
class Solution {
public:string result ="";string PrintMinNumber(vector<int>& numbers) {if(numbers.size() == 0) return result;//写法2vector<string> temp;for(int i=0; i<numbers.size(); i++){temp.push_back(to_string(numbers[i]));}sort(temp.begin(), temp.end(), [](const string& a, const string& b){return a + b < b + a;});for(int i=0; i<temp.size(); i++)result += temp[i];return result;}
};
  1. 有两点要注意的：
  • sort函数要定义为静态或者全局函数。sort中的比较函数cmpStr要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。 因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数，所以cmpStr函数前面要加关键字static。
  • 静态成员函数或者全局函数是不依赖于具体对象的,可以独立访问，无须创建任何对象实例就可以访问，同时静态成员函数不可以调用类的非静态成员。

在这里插入图片描述

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
#include <vector>
class Solution {
public:vector<int> PrintFromTopToBottom(TreeNode* root) {vector<int> result;if(root == nullptr) return result;//递归vector<vector<int>> temp;traverse(root, temp, 1);//送入一维数组for(int i=0; i<temp.size(); i++){for(int j=0; j<temp[i].size(); j++)result.push_back(temp[i][j]);}return result;}void traverse(TreeNode* root, vector<vector<int>>& result, int depth){if(root == nullptr) return;else{if(result.size() < depth) result.push_back(vector<int>{});result[depth-1].push_back(root->val);}traverse(root->left, result, depth + 1);traverse(root->right, result, depth + 1);}
};

3. JZ49 丑数

在这里插入图片描述

最小堆

递归写法就是找到根节点，根节点作为分割点，两边判断大小

#include <queue>
#include <unordered_map>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param index int整型 * @return int整型*/int GetUglyNumber_Solution(int index) {//最小堆if(index == 0) return 0;//排除0vector<int> factors = {2, 3, 5};//要乘的因数unordered_map<long, int> hashmap;//去重priority_queue<long, vector<long>, greater<long>> pq;//小顶堆hashmap[1LL] = 1;//1先进去pq.push(1LL);long result = 0;for(int i=0; i<index; i++){result = pq.top(); //每次取最小的pq.pop();for(int j=0; j<3; j++){long next = result * factors[j];//乘上因数if(hashmap.find(next) == hashmap.end()) //只取未出现过的{hashmap[next] = 1;pq.push(next);}}}return (int)result;}
};

三指针法 动态规划

#include <queue>
#include <type_traits>
#include <unordered_map>
class Solution {
public:int GetUglyNumber_Solution(int index) {//三指针if(index < 7) return index;vector<int> result(index, 0);result[0] = 1;int index2 = 0, index3 = 0, index5 = 0;int minNum = 0;for(int i=1; i<index; i++){//x是丑数 2、3、5倍的x也是丑数，找到三个数中最小的丑数//第一次是2、3、5比较，第二次是4、3、5比较，为什么是4了呢？因为上次2已经乘了一次了，所以接下去可以放的丑数在4、3、5之间minNum = min(min(index2 * 2, index2 * 3), index2 * 5);if(minNum == result[index2] * 2) index2++;//由2与已知丑数相乘得到的丑数if(minNum == result[index3] * 3) index3++;//由3与已知丑数相乘得到的丑数if(minNum == result[index5] * 5) index5++;//由5与已知丑数相乘得到的丑数result[i] = minNum;}return result[index-1];}
};

4. JZ50 第一个只出现一次的字符

题目： 在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1，需要区分大小写，从0开始计数。

class Solution {
public:int FirstNotRepeatingChar(string str) {//if(str.size() == 0) return -1;unordered_map<int, int> hashmap(str.size());for(int i=0; i<str.size(); i++){hashmap[str[i] - 'a']++;}for(int i=0; i<str.size(); i++){if(hashmap[str[i] - 'a'] == 1) return i;}return -1;}
};

5. JZ51 数组中的逆序对

在这里插入图片描述
构成逆序对的个数关键在于升序排列后该序列的长度，例如1、2、3，当遍历1时，长度=0，不构成逆序对；遍历2时，长度=1，逆序对数=2-1；遍历3时，长度=2，逆序对=3-1。所有逆序对数累加。
排序时使用并归排序，将数组分成两部分，按照升序排序。

  • 并归排序 升序
class Solution {
public:int InversePairs(vector<int>& nums) {if( nums.size() <= 1) return 0;vector<int> copy(nums);// 辅助数组，每次递归后有序return InversePairscore(nums, copy, 0, nums.size()-1);//for (int a : data) {//	cout << a << " ";//}//cout << endl;//for (int a : copy) {//	cout << a << " ";//}//cout << endl;}int InversePairscore(vector<int>& nums, vector<int>& copyvector, int start, int end){if (start >= end) return 0;int mid = start + (end - start) / 2;int low1 = start, high1 = mid, low2 = mid + 1, high2 = end;int left = InversePairscore(copyvector, nums, low1, high1);//注意这里 copyvector和nums交换位置 相当于赋值 减少了数据交换的这一步int right = InversePairscore(copyvector, nums, low2, high2);long res = 0;int copyIndex = low1;// 归并排序：相当于两个有序数组合成一个有序表//下面就开始两两进行比较，若前面的数大于后面的数，就构成逆序对while (low1 <= high1 && low2 <= high2) {if(nums[low1] <= nums[low2]) copyvector[copyIndex++] = nums[low1++];else{copyvector[copyIndex++] = nums[low2++];//说明 [low1,high1]此时都是大于 nums[low2]的res += high1 - low1 + 1;//这里千万注意要 +1 ，因为high1 - low1 就少一个 比如 3-0 = 4，但其实是4个数res %= 1000000007;}}while(low1 <= high1)copyvector[copyIndex++] = nums[low1++];while(low2 <= high2)copyvector[copyIndex++] = nums[low2++];return (left + right + res) % 1000000007;}
};

2. 题目难点

给定链表的头节点 head ，复制普通链表只需遍历链表，每轮建立新节点 + 构建前驱节点 pre 和当前节点 node 的引用指向即可。

本题链表的节点新增了 random 指针，指向链表中的 任意节点 或者 null 。这个 random 指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向 pre.next ，还要构建前驱节点和其随机节点的引用指向 pre.random 。

本题难点： 在复制链表的过程中构建新链表各节点的 random 引用指向。

3. 思路

class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;Node* dum = new Node(0), *pre = dum;while(cur != nullptr) {Node* node = new Node(cur->val); // 复制节点 curpre->next = node;                // 新链表的 前驱节点 -> 当前节点// pre->random = "???";          // 新链表的 「 前驱节点 -> 当前节点 」 无法确定cur = cur->next;                 // 遍历下一节点pre = node;                      // 保存当前新节点}return dum->next;}
};

4. 哈希表 迭代写法

在这里插入图片描述

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {//哈希表if(pHead == nullptr) return nullptr;unordered_map<RandomListNode*, RandomListNode*> hashmap;//原结点 复制的新结点RandomListNode* cur = pHead;//1. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 建立值映射 for(RandomListNode* p = cur; p != nullptr; p = p->next){hashmap[p] = new RandomListNode(p->label);}//2. 构建新链表的 next 和 random 指向 建立指向映射while(cur!=nullptr){//新结点hashmap[cur]的 指向 hashmap[cur]->next 就是 原结点cur的指向 cur->nexthashmap[cur]->next = hashmap[cur->next];hashmap[cur]->random = hashmap[cur->random];cur = cur->next;}return hashmap[pHead];}
};

5. 哈希表 递归写法

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {//2. 哈希表 递归if(pHead == nullptr) return nullptr;RandomListNode* newhead = new RandomListNode(pHead->label);//复制头结点hashmap[newhead] = pHead;//“原节点 -> 新节点” 的 Map 映射 值映射newhead->next = Clone(pHead->next);//next指向 if(pHead->random != nullptr) newhead->random = Clone(pHead->random);//如果有random指向return hashmap[newhead];}
private:unordered_map<RandomListNode*, RandomListNode*> hashmap;//原结点 复制的新结点
};

6. 拼接 + 拆分 原地解法
在这里插入图片描述

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:RandomListNode* Clone(RandomListNode* pHead) {if(pHead == nullptr) return nullptr;//3. 拼接 + 拆分 原地解法RandomListNode* cur = pHead;//复制结点及next指向while(cur != nullptr){RandomListNode* temp = new RandomListNode(cur->label);//复制结点 新结点temp->next = cur->next;// 新结点 -> 原下一个结点cur->next = temp;// 原结点 -> 新结点cur = temp->next;//cur = cur->next->next;//cur更新为 原结点的下一个结点}//复制结点的random指向cur = pHead;while (cur != nullptr) {//新结点cur->next 的random指向 = 原结点cur 的random指向if(cur->random != nullptr) cur->next->random = cur->random->next;cur = cur->next->next;//更新cur}//分离链表cur = pHead->next;//新结点表头RandomListNode* old = pHead, *result = pHead->next;while(cur->next != nullptr){old->next = old->next->next;//分离cur->next = cur->next->next;old = old->next;//更新cur = cur->next; }old->next = nullptr;// 单独处理原链表尾节点return result;}
};

6. JZ52 两个链表的第一个公共结点

在这里插入图片描述

迭代

统计长度，长的链表先走 两个链表长度差 步，然后再一起走，同时比较结点是否相等

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
#include <algorithm>
#include <utility>
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;int len1 = countLen(pHead1);int len2 = countLen(pHead2);if(len1 < len2){swap(pHead1, pHead2);swap(len1, len2);}int len = len1 - len2;while(len--) pHead1 = pHead1->next;while(pHead1 != nullptr && pHead2 != nullptr){if(pHead1 == pHead2) return pHead1;pHead1 = pHead1->next;pHead2 = pHead2->next;}return nullptr;}int countLen(ListNode* head){if(head == nullptr) return 0;int len = 0;while (head) {len++;head = head->next;}return len;}
};

递归

长度相同的：1. 有公共结点的，第一次就遍历到；2. 没有公共结点的，走到尾部NULL相遇，返回NULL；
长度不同的：1. 有公共结点的，第一遍差值就出来了，第二遍就会一起到公共结点；2. 没有公共结点的，第二次遍历一起到结尾NULL。

相当于省去了长度统计这一步，把链表看成一个环。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
#include <algorithm>
#include <utility>
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;//递归ListNode* p1 = pHead1, *p2 = pHead2;while(p1 != p2){p1 = (p1 == nullptr ? pHead2 : p1->next);p2 = (p2 == nullptr ? pHead1 : p2->next);}return p2;//p1 p2 都行}
};

7. JZ53 数字在升序数组中出现的次数


一个是利用count函数，直接返回个数return count(nums.begin(), nums.end(), k);
另外一个是用二分法 return count(nums.begin(), nums.end(), k);z

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @param k int整型 * @return int整型*/int GetNumberOfK(vector<int>& nums, int k) {return count(nums.begin(), nums.end(), k);//二分法int start = 0, mid = 0, end = nums.size()-1;//左闭右闭while(start <= end){mid = start + (end - start) / 2;if(nums[mid] < k) start = mid+1;else if (nums[mid] > k) end = mid;else//找到其中一个k的位置{int index = mid-1;int count=0;count++;//记录当前k//往回找到其他kwhile(index >= 0 && nums[index] == k){count++;index--;}index = mid+1;while(index <= end && nums[index] == k){count++;index++;}return count;}return 0;}}
};

8. JZ55 二叉树的深度

在这里插入图片描述

递归

看左右子树的长度；单层递归中，如果有左子树，左子树长度+1，如果有右子树，右子树长度+1；最后看哪个累加值最大。每一层+1是因为根节点的深度视为 1。有两种写法，如下：

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* pRoot) {if(pRoot == nullptr) return 0;//return dfs1(pRoot);//递归写法1return dfs2(pRoot);//递归写法2}int dfs1(TreeNode* root){if(root == nullptr) return 0;int leftdepth = dfs1(root->left) + 1;int rightdepth = dfs1(root->right) + 1;return max(leftdepth, rightdepth);}int dfs2(TreeNode* root){if(root == nullptr) return 0;int left = dfs2(root->left);int right = dfs2(root->right);return max(left, right) + 1;}
};

迭代

用一个元组对来维护当前遍历的结点及当前深度，队列实现,中序遍历

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
#include <utility>
class Solution {
public:int TreeDepth(TreeNode* pRoot) {if(pRoot == nullptr) return 0;return bfs(pRoot);}int bfs(TreeNode* root){queue<pair<TreeNode*, int>> que;que.push(make_pair(root, 1));int maxdepth = 1;int curdepth = 0;TreeNode* curnode = nullptr;while(!que.empty()){curnode = que.front().first;curdepth = que.front().second;que.pop();if(curnode)//当前结点不为空{maxdepth = max(maxdepth, curdepth);//更新最大深度que.push(make_pair(curnode->left, curdepth+1));//更新结点 左que.push(make_pair(curnode->right, curdepth+1));//更新结点 右}}return maxdepth;}
};

9. JZ79 判断是不是平衡二叉树

在这里插入图片描述

自底向上 后序遍历

  • 判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。
  • 统计深度，判断左右子树深度差的绝对值不超过1；后序遍历：左子树、右子树、根节点，先递归到叶子节点，然后在回溯的过程中来判断是否满足条件。
  • 统计深度时，可以直接判断，如果不满足平衡二叉树的定义，则返回-1，并且如果左子树不满足条件了，直接返回-1，右子树也是如此，相当于剪枝，加速结束递归。
/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot == nullptr) return true;//自底向上return getDepth1(pRoot) != -1;}int getDepth1(TreeNode * node){if(node == nullptr) return 0;int left = getDepth1(node->left);if(left == -1)  return -1;int right = getDepth1(node->right);if(right == -1) return -1;if(abs(left - right) > 1) return -1;elsereturn 1 + max(left,right);}
};

自上向底 前序遍历

根据平衡二叉树定义，如果能够求出以每个结点为根的树的高度，然后再根据左右子树高度差绝对值小于等于1，就可以判断以每个结点为根的树是否满足定义。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:
return bool布尔型bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot == nullptr) return true;//自上向底int leftdepth = getDepth(pRoot->left), rightdepth = getDepth(pRoot->right);//根借点if(abs(leftdepth - rightdepth) > 1) return false;return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right); //继续判断左右子树}int getDepth(TreeNode* root){if(root == nullptr) return 0;int leftdepth = getDepth(root->left);int rightdepth = getDepth(root->right);return max(leftdepth, rightdepth) + 1;}
};

10. 数组中只出现一次的数字

描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

哈希表

#include <unordered_map>
class Solution {
public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {unordered_map<int, int> hashmap;for(int i=0; i<data.size(); i++){hashmap[data[i]]++;}auto it = hashmap.begin();while(it != hashmap.end())//找到第一个{if(it->second == 1){*num1 = it->first;++it;break;}++it;}while(it != hashmap.end())//找到第二个{if(it->second == 1){*num2 = it->first;break;}++it;}}
};

位运算

又又又搬运力扣K神的题解了
在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 异或操作图解
    在这里插入图片描述力扣eddieVim的题解回答了我的问题

  1. 为什么要异或：两个数异或的结果 就是 两个数数位不同结果的直观表现。

  2. 计算m的意义

  • 数组依次遍历且疑惑操作后，找到两个不同的数了。此时难点在于如何对两个不同数字的分组。此时可以通过奇偶进行分组，那么就要想到 & 1 操作，通过判断最后一位二进制是否为 1 来辨别数字的奇偶性。
  • 也就是说，通过 & 运算来判断数字的奇偶性，并据此将一位数字分成两组。因此只需要找出不同的数字m，即可完成分组（ & m）操作。
  • 两个数异或的结果就是两个数数位不同结果的直观表现，所以可以通过异或后的结果去找 m！所有的可行 m 个数，都与异或后1的位数有关。
  1. mask示例
num1:       101110      110     1111
num2:       111110      001     1001
num1^num2:  010000      111     0110可行的mask:  010000      001     0010010     0100100     

#include <unordered_map>
class Solution {
public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {//位运算if (data.size() < 2) return;int res = 0, mask = 1;for(auto d : data)                  // 1. 遍历异或 结果为不同的两个数字的异或res ^= d;while ((res & mask) == 0)           // 2. 循环左移，计算 mask  mask = k & (-k) 这种方法也可以得到maskmask <<= 1;for(int num : data) {               // 3. 遍历 nums 分组if(num & mask) *num1 ^= num;    // 4. 当 num & mask != 0else *num2 ^= num;              // 4. 当 num & mask == 0}}
};

补充内容 - 并归排序

sunny-ll的并归排序简明扼要地说明了并归排序了

  1. 问题分析
    归并排序是比较稳定的排序方法。它的基本思想是把待排序的元素分解成两个规模大致相等的子序列。如果不易分解，将得到的子序列继续分解，直到子序列中包含的元素个数为1。因为单个元素的序列本身就是有序的，此时便可以进行合并，从而得到一个完整的有序序列。
  2. 算法设计
    （1）分解： 将待排序的元素分成大小大致一样的两个子序列。
    （2）治理： 对两个子序列进行个并排序。
    （3）合并： 将排好序的有序子序列进行合并，得到最终的有序序列。
    力扣第315、327、493题也是关于并归排序的，回头写。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/79750.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

当编程式事务写在了声明式事务的代码中，会怎么样？

当编程式事务写在了声明式事务的代码中，会怎么样？

1、背景 上一篇文章&#xff0c;为解决大事务问题&#xff0c;将for循环的每个订单的处理放在了编程式事务的代码中&#xff0c;但是在落地的时候&#xff0c;遇到了一个比较特殊的情况&#xff0c;外层方法中使用了 Transactional注解&#xff0c;内部再用编程式事务&#xf…
阅读更多...
大数据技术之Hadoop（二）

大数据技术之Hadoop（二）

目录 一、Hadoop的诞生 二、大数据概述 三、大数据软件生态 3.1 数据存储相关技术 3.2 数据计算相关技术 3.3 数据传输相关技术 四、什么是Hadoop 本篇主要讲解大数据的核心概念以及Hadoop的基本介绍。 一、Hadoop的诞生 大数据的发展与日益庞大的数据量是密不可分的。从…
阅读更多...
chaitin-Nginx+Docker

chaitin-Nginx+Docker

Nginx实战 任务一 1、源码包安装NGINX A&#xff0c;搭建Web Server&#xff0c;任意HTML页面&#xff0c;其8080端口提供Web访问服务&#xff0c;截图成功访问http(s)&#x1f615;/[Server1]:8080并且回显Web页面 官网地址&#xff1a;http://nginx.org/en/download.html 步骤…
阅读更多...
webpack基础知识十：与webpack类似的工具还有哪些？区别？

webpack基础知识十：与webpack类似的工具还有哪些？区别？

一、模块化工具 模块化是一种处理复杂系统分解为更好的可管理模块的方式 可以用来分割&#xff0c;组织和打包应用。每个模块完成一个特定的子功能&#xff0c;所有的模块按某种方法组装起来&#xff0c;成为一个整体(bundle) 在前端领域中&#xff0c;并非只有webpack这一款…
阅读更多...
力扣初级算法（二分查找）

力扣初级算法（二分查找）

力扣初级算法(二分法)&#xff1a; 每日一算法&#xff1a;二分法查找 学习内容&#xff1a; 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 2.二分查找流程&…
阅读更多...
深度学习——划分自定义数据集

深度学习——划分自定义数据集

深度学习——划分自定义数据集 以人脸表情数据集raf_db为例&#xff0c;初始目录如下&#xff1a; 需要经过处理后返回 train_images, train_label, val_images, val_label 定义 read_split_data(root: str, val_rate: float 0.2) 方法来解决&#xff0c;代码如下&#xff1a…
阅读更多...
[openCV]基于拟合中线的智能车巡线方案V3

[openCV]基于拟合中线的智能车巡线方案V3

import cv2 as cv import os import numpy as np# 遍历文件夹函数 def getFileList(dir, Filelist, extNone):"""获取文件夹及其子文件夹中文件列表输入 dir&#xff1a;文件夹根目录输入 ext: 扩展名返回&#xff1a; 文件路径列表"""newDir d…
阅读更多...
SpringBoot 自动配置--常用配置

SpringBoot 自动配置--常用配置

&#x1f600;前言 本篇博文是关于SpringBoot 自动配置的一些分享&#xff0c;希望能够帮助到您&#x1f60a; &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您…
阅读更多...
关于安卓jar包修改并且重新发布

关于安卓jar包修改并且重新发布

背景&#xff1a; 对于某些jar包&#xff0c;其内部是存在bug的&#xff0c;解决的方法无外乎就有以下几种方法&#xff1a; &#xff08;1&#xff09;通过反射&#xff0c;修改其赋值逻辑 &#xff08;2&#xff09;通过继承&#xff0c;重写其方法 &#xff08;3&#xff0…
阅读更多...
【java安全】CommonsBeanUtils1

【java安全】CommonsBeanUtils1

文章目录 【java安全】CommonsBeanUtils1前言Apache Commons BeanutilsBeanComparator如何调用BeanComparator#compare()方法&#xff1f;构造POC完整POC 调用链 【java安全】CommonsBeanUtils1 前言 在之前我们学习了java.util.PriorityQueue&#xff0c;它是java中的一个优…
阅读更多...
MyCat水平分表

MyCat水平分表

1.水平拆分案例场景 2.MyCat配置 这个表只是在 schema.xml配置的逻辑表&#xff0c;在具体的数据库里面是没有的 根据id的模确定数据存在哪个节点上&#xff01;&#xff01;
阅读更多...
数据结构与算法基础到高级，直击BTAJ，刷爆Letcode

数据结构与算法基础到高级，直击BTAJ，刷爆Letcode

数据结构与算法基础到高级&#xff0c;直击BTAJ&#xff0c;刷爆Letcode &#x1f384;前序补充&#x1f355;异或&#x1f354;对数器 &#x1f384;时间、空间复杂度&#x1f35f;空间复杂度基本概念&#x1f32d;时间复杂度基本概念&#x1f37f;基本的排序算法的时间复杂度…
阅读更多...
在linux系统上安装Nginx

在linux系统上安装Nginx

1、关闭防火墙 systemctl disable firewalld.service 2、上传压缩包并解压到目标文件 cd /usr/local tar -zxvf nginx-1.22.0.tar.gz 3、安装Nginx相关依赖 yum install -y gcc-c zlib zlib-developenssl openssl-devel pcre pcre-devel 4、安装完毕后&#xff0c;进入ng…
阅读更多...
MapTR论文笔记

MapTR论文笔记

MAPTR: STRUCTURED MODELING AND LEARNING FOR ONLINE VECTORIZED HD MAP CONSTRUCTION 目的 传统高精地图 通过一些离线的基于 SLAM 的方法生成&#xff0c;需要复杂的流程以及高昂的维护费用。基于 bev 分割的建图方法&#xff0c;缺少向量化 实例级的信息&#xff0c;比如…
阅读更多...
3年经验，面试测试岗只会功能测试开口要求18K，令我陷入沉思。

3年经验，面试测试岗只会功能测试开口要求18K，令我陷入沉思。

由于朋友临时有事&#xff0c; 所以今天我代替朋友进行一次面试&#xff0c;公司需要招聘一位自动化测试工程师&#xff0c;我以很认真负责的态度完成这个过程&#xff0c; 大概近30分钟。 主要是技术面试&#xff0c; 在近30分钟内&#xff0c; 我与被面试者是以交流学习的方式…
阅读更多...
Spring Boot3.0(一)：入门篇

Spring Boot3.0(一)：入门篇

什么是 Spring Boot Spring Boot 是由 Pivotal 团队提供的全新框架&#xff0c;其设计目的是用来简化新 Spring 应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。 用我的话来理解&#xff0c;就是 Spring…
阅读更多...
nginx的优化和防盗链 重要！！！

nginx的优化和防盗链 重要！！！

实验一、隐藏版本号 要把nginx的版本号隐藏起来&#xff0c;防止恶意攻击 方法一&#xff1a;修改配置文件 在http模块中加入一个命令 server_token off&#xff1b; 过程&#xff1a; 备份&#xff0c;改配置文件一定要备份 修改配置文件 在http模块中添加 server_tokens …
阅读更多...
MySQL插入数据的方法

MySQL插入数据的方法

插入数据方法&#xff1a; 1.insert into 表 values(value1, value2, value3....) 2.insert into 表 (字段1&#xff0c; 字段3&#xff0c; 字段5) values(value1, value2, value3) 3.insert into 表 [(字段1&#xff0c; 字段2&#xff0c; 字段3....)] values(value1, val…
阅读更多...
string类函数--深入浅出了解

string类函数--深入浅出了解

目录 1.为什么学习string类1.1C语言中的字符串1.2OJ题中的优势 2.标准库中的string类3.string类的常用接口函数3.1string类对象的常见构造3.2string类对象的容量操作3.3string类对象的访问及遍历操作3.4string类的修改操作3.5string类的非成员函数 总结 1.为什么学习string类 …
阅读更多...
JMeter命令行执行+生成HTML报告

JMeter命令行执行+生成HTML报告

1、为什么用命令行模式 使用GUI方式启动jmeter&#xff0c;运行线程较多的测试时&#xff0c;会造成内存和CPU的大量消耗&#xff0c;导致客户机卡死&#xff1b; 所以一般采用的方式是在GUI模式下调整测试脚本&#xff0c;再用命令行模式执行&#xff1b; 命令行方式支持在…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发