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,2,3]
输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<int>> permute(vector<int> &nums) { vector<vector<int>> res; vector<bool> used(nums.size()); dfs(nums, used, res); return res; } private: vector<int> stack; void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res) { if (stack.size() == nums.size()) { res.push_back(stack); } else { for (int i = 0; i < nums.size(); i++) { if (!used[i]) { used[i] = true; stack.push_back(nums[i]); dfs(nums, used, res); stack.pop_back(); used[i] = false; } } } } }; int main() { Solution s; vector<int> nums = {1,2,3}; for(auto vec: s.permute(nums)){ for(auto num: vec){ cout << num << " "; } cout << endl; } return 0; }
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
附录
排列与组合
是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
