C/C++每日一练(20230227)

目录

1. 按要求排序数组  ★

2. Z 字形变换  ★★

3. 下一个排列  ★★

---

1. 按要求排序数组

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中，数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。请你返回排序后的数组。

代码：

#include<stdio.h>
#include<stdlib.h>
int oneNum(int x)
{int cnt = 0;while(x){cnt++;x = x & (x - 1);}return cnt;
}
int cmp(const void *a,const void*b)
{int al,bl;int ret;al = *(int*)a;bl = *(int*)b;ret =  oneNum(al) - oneNum(bl);return  ret ? ret : al - bl;
}
int main()
{int s[]={1,2,3,5,6,7,8},i;int len = sizeof(s)/sizeof(*s);qsort(s,len,4,cmp);for(i = 0 ; i < len ; i++){printf("%d\n",s[i]);}
}

---

2. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

代码： 

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:string convert(string s, int numRows){if (numRows == 1)return s;int len = s.size();if (len <= numRows)return s;int cycle_len = 2 * numRows - 2;int full_cycles = len / cycle_len;int left = len % cycle_len;string r;int i;for (i = 0; i < full_cycles; ++i){r += s[i * cycle_len];}if (left)r += s[i * cycle_len];for (i = 0; i < numRows - 2; ++i){int j;for (j = 0; j < full_cycles; ++j){r += s[j * cycle_len + i + 1];r += s[j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)];}if (left){if (j * cycle_len + i + 1 < len)r += s[j * cycle_len + i + 1];if (j * cycle_len + i + 1 + cycle_len - 2 * (i + 1) < len)r += s[j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)];}}for (i = 0; i < full_cycles; ++i)r += s[i * cycle_len + numRows - 1];if (left >= numRows)r += s[i * cycle_len + numRows - 1];return r;}
};int main()
{Solution sol;string s = "PAYPALISHIRING";int numRows = 3;cout << sol.convert(s, numRows) << endl;numRows = 4;cout << sol.convert(s, numRows) << endl;s = "A", numRows = 1;cout << sol.convert(s, numRows) << endl;return 0;
} 

输出：

PAHNAPLSIIGYIR
PINALSIGYAHRPI
A

---

3. 下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：

输入：nums = [1]
输出：[1]

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

代码：

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;class Solution {
public:void nextPermutation(vector<int> &nums) {int n = nums.size();if (n < 2) return;for (int j, i = n - 2; i >= 0; --i) {if (nums[i + 1] > nums[i]) {for (j = n - 1; j > i; --j) {if (nums[j] > nums[i]) break;}swap(nums[i], nums[j]);reverse(nums.begin() + i + 1, nums.end());return;}}reverse(nums.begin(), nums.end());}
};int main()
{Solution s;vector<int> nums = {1,2,3};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {3,2,1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1,1,5};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;return 0;
} 

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size(), i = n - 2, j = n - 1;while (i >= 0 && nums[i] >= nums[i + 1]) --i;if (i >= 0) {while (nums[j] <= nums[i]) --j;swap(nums[i], nums[j]);}reverse(nums.begin() + i + 1, nums.end());}
};int main()
{Solution s;vector<int> nums = {1,2,3};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {3,2,1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1,1,5};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;return 0;
} 

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();int i = n - 1;for (; i > 0; i--) {if (nums[i] > nums[i - 1]) {for (int j = n - 1; j >= i; j--) {if (nums[j] > nums[i - 1]) {swap(nums[j], nums[i - 1]);break;}}break;}}for (int j = i, k = 1; j < (n + i) / 2; j++, k++) {swap(nums[n - k], nums[j]);}}
};int main()
{Solution s;vector<int> nums = {1,2,3};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {3,2,1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1,1,5};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;cout << endl;nums = {1};s.nextPermutation(nums);copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," "));;return 0;
} 

输出：

1 3 2
1 2 3
1 5 1
1

---

附录

排列与组合

是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

相关阅读：

https://hannyang.blog.csdn.net/article/details/125238660https://hannyang.blog.csdn.net/article/details/125238660