2.4学习内容

922. 按奇偶排序数组 IIhttps://leetcode.cn/problems/sort-array-by-parity-ii/

922. 按奇偶排序数组 II

给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

提示：

• 2 <= nums.length <= 2 * 104

• nums.length 是偶数

• nums 中一半是偶数

• 0 <= nums[i] <= 1000

题解：

自己的代码：

int* sortArrayByParityII(int* nums, int numsSize, int* returnSize) {
	for (int i = 0, j = 0; i < numsSize;) {
		int temp=0;
		if (i % 2 == 0) {
			if (*(nums + j) % 2 == 0) {
				temp=*(nums+i),*(nums+i)=*(nums+j),*(nums+j)=temp;
				++i, j = i;
			} else j++;
		}
		else {
			if(*(nums+j)%2==1){
				temp=*(nums+i),*(nums+i)=*(nums+j),*(nums+j)=temp;
				++i, j = i;
			}
			else j++;
		}
	}
	*returnSize=numsSize;
	return nums;
}

其他人的快速解法1：

int* sortArrayByParityII(int* nums, int numsSize, int* returnSize) {
	int i = 0, j = 1;
	while (i < numsSize) {
		if (nums[i] % 2 == 0) {
			i += 2; // 寻找偶数下标中最左边的奇数
		} else if (nums[j] % 2 == 1) {
			j += 2; // 寻找奇数下标中最左边的偶数
		} else {
			int tmp = nums[i];
			nums[i] = nums[j];
			nums[j] = tmp;
			i += 2;
			j += 2;
		}
	}
	*returnSize = numsSize;
	return nums;
}

 其他人的快速解法2：

int* sortArrayByParityII(int* A, int ASize, int* returnSize)
{   
	for (int even = 0, odd = 1; even < ASize; even += 2) {
		if (A[even] & 1) {
			while (A[odd] & 1) {
				odd += 2;
			} 
			A[odd] ^= A[even];A[even] ^= A[odd];A[odd] ^= A[even];
		}   
	}
	
	*returnSize = ASize;
	return A;
}

P4738 [CERC2017] Cumulative Codehttps://www.luogu.com.cn/problem/P4738

P4738 [CERC2017] Cumulative Code

题目描述

As you probably know, a tree is a graph consisting of n nodes and n−1 undirected edges in which any two nodes are connected by exactly one path. In a labeled tree each node is labeled with a different integer between 1 and n. The Prüfer code of a labeled tree is a unique sequence associated with the tree, generated by repeatedly removing nodes from the tree until only two nodes remain. More precisely, in each step we remove the leaf with the smallest label and append the label of its neighbour to the end of the code. Recall, a leaf is a node with exactly one neighbour. Therefore, the Prüfer code of a labeled tree is an integer sequence of length n−2. It can be shown that the original tree can be easily reconstructed from its Prüfer code. The complete binary tree of depth k, denoted with C_k , is a labeled tree with 2^k−1 nodes where node j is connected to nodes 2j and 2j+1 for all j<2^k−1. Denote the Prüfer code of Ck with p1,p2,...,p2^k−3. Since the Prüfer code of C_k can be quite long, you do not have to print it out. Instead, you need to answer n questions about the sums of certain elements on the code. Each question consists of three integers: a,d and m. The answer is the sum of the of the C′_k s Prüfer code elements p_a,p_a+d,p_a+2d,...,p_a+(m−1)d.

输入格式

The first line contains two integers k and q(2≤k≤30,1≤q≤300) — the depth of the complete binary tree and the number of questions. The j−th of the following q lines contains the j−th question:three positive integers a_j,d_j and mj  such that a_j,d_j  and a_j+(m_j−1)d_jare all at most 2^k−3.

输出格式

Output 1 lines. The j−th line should contain a single integer — the answer to the j−th question.