1、有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？
2、有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。
初始集合是空的，有两种操作，要么给集合添加一个长度为 L 的木棒，要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。
3、给出 n 个字符串，对于每个 n 个排列 p，按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。
一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量，i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。
注：定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。
4、给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。
比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。
参考答案
1、参考代码：
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <assert.h>
#include <cstring>
using namespace std;
typedef unsigned long long ULL; // 最大要计算 12 位的正整数，所以还是用一个大点的类型吧
// 依据权重表 weight, 得到映射表 ret (即: 排位)
// 比如：
//
// | table | A | B | C | D | E | F | G | H | I | J |
// |-------|--------|----------|----|--------|-------|------|---|-----|-----|------|
// | weight|10000001| 1010001 | 20 | 100000 | 10000 | 1000 | 1 | 100 | 110 | 1000 |
// |-------|--------|----------|----|--------|-------|------|---|-----|-----|------|
// | ret | 9 | 8 | 1 | 7 | 6 | 5 | 0 | 2 | 3 | 4 |
//
void map_weight(ULL* weight, int* ret, const int n = 10) {
//
// 排位算法：
// 初值都为 9
// C(10, 2) : 从10个数中挑选两个数。
// 比较这两个数：谁小谁减一，相等的话随便挑选一个减一
//
assert(n == 10);
for (int i = 0; i < n; ++i) {
ret[i] = 9;
}
for (int i = 0; i < n; ++i) {
if (weight[i] == 0) {
ret[i] = 0;
continue;
}
for (int j = i + 1; j < n; ++j) {
if (weight[j] == 0) {
ret[j] = 0;
continue;
}
if (weight[i] < weight[j]) {
ret[i]--;
}
else {
ret[j]--;
}
// 因为映射不能重复，
// 所以当 weight[i] == weight[j] 权重相等时，
// 随意挑选一个减一即可。
// 例如： 'A' 和 'B' 权重值相等，但不能都映射为 9
// 此时，随意挑选一个使其映射值 减一 即可 9, 8
}
}
}
// 判断给定的字符 c 是否在 input 中有作为首字符出现
bool is_header(const char c, const vector<string>& input) {
const size_t len = input.size();
for (size_t i = 0; i < len; ++i) {
if (c == input[i][0])
return true;
}
return false;
}
// 依据给定的值，在映射表 ret 中查找对应的下标 (可进一步优化)
int get_pos(const int value, const int* ret, const int n = 10) {
for (int i = 0; i < n; ++i) {
if (value == ret[i])
return i;
}
return -1;
}
// 因为不能有 0 开头的数字，所以要修正一下映射表 ret
void fixed_ret(int *ret, char *table, const vector<string>& input,
const int n = 10) {
int pos_0 = get_pos(0, ret);
assert(pos_0 >= 0);
if (! is_header(table[pos_0], input)) return;
// 当前序列需调整
// 依次查找 最小非开头的映射值 i
int opt_pos = -1;
for (int i = 1; i < n; ++i) {
int pos = get_pos(i, ret);
assert(pos >= 0);
if (! is_header(table[pos], input)) {
// 找到了最小的不是 table[pos] 打头的值 i 了
// 记下下标即可
opt_pos = pos;
break;
}
}
if (opt_pos == -1) {
// 没有找到合适的值。（用例有问题）
return;
}
// 调整开始
// 比 ret[opt_pos] 小的值都加1，最后再将 ret[opt_pos] 置 0
for (int i = 0; i < n; ++i) {
if (ret[i] < ret[opt_pos]) {
ret[i]++;
}
}
ret[opt_pos] = 0;
}
template<typename T>
void show(const T& arr) {
for (auto& v : arr) {
cout << v << ' ';
}
cout << endl;
}
void check(const string& input_str) {
for (auto& s : input_str) {
assert(s >= 'A' && s <= 'J');
}
}
int main() {
int n;
cin >> n;
assert(n > 0 && n <= 50);
vector<string> input(n);
for (int i = 0; i < n; ++i) {
cin >> input[i];
const size_t len = input[i].size();
assert(len <= 12);
check(input[i]);
}
// 输入完毕，并完成合法性检查
char table[] = {'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'I', 'J'};
ULL weight[10] = {0}; // 权重表：A - J 每个字母的权重
// 遍历 input[], 统计权重
// 算法：
//
// 设
// 个位权值 为 1
// 十位权值 为 10
// 百位权值 为 100
// 依次类推， 没有出现的字母权值为 0
//
// 统计每个字母的累计权重值
//
// 例如输入两组数据：
//
// ABC
// BCA
//
// 则 A 的权重为 100 + 1 = 101
// B 的权重为 10 + 100 = 110
// C 的权重为 1 + 10 = 11
// D - J 的权重为 0
//
//
for (int i = 0; i < n; ++i) {
ULL w = pow(10, input[i].size() -1);
for (auto& v : input[i]) {
weight[v - 'A'] += w;
w /= 10;
}
}
#ifdef DEBUG
cout << endl << "weight = ";
show(weight);
#endif //DEBUG
// 依据权重高低依次映射 9 ~ 0
//
// 将统计而来的 权重表进行 排位，最高权重的映射为 9，
// 最小权重的映射为 0。
int ret[10];
map_weight(weight, ret, 10);
#ifdef DEBUG
cout << "ret = ";
show(ret);
#endif //DEBUG
// 修正 映射表， 因为 不能有 0 开头的数字
//
// 算法：检查当前映射表中 ret ，映射为 0 的字母是否在 input 中打头
// 若不打头什么也不做；
// 若打头，则将不打头的最小映射值 变更为 0，
// 比刚才发现的最小映射值小的所有映射值加 1
//
// 比如 映射表为 9 1 0 7 8 6 2 5 4 3
// 此时 0 对应的字母是 talble[2] 即 'C'
// 如果 'C' 有当过头字母，则需要修正映射表，
// 再如， 'B' 也出现过打头，但 'G' 没有出现过打头的情况，则映射表修正如下
// 9 2 1 7 8 6 0 5 4 3
//
fixed_ret(ret, table, input);
#ifdef DEBUG
cout << "after fixed:\nret = ";
show(ret);
#endif //DEBUG
// 计算结果
//
// 将 (权重表 x 映射表)，然后再累加起来就是题目要的答案
//
// 例如
//
// 输入例子：
// ABC
// BCA
//
// 设 table = A B C D E F G H I J
//
// 则
// 权重表
// weight = 101 110 11 0 0 0 0 0 0 0
// 进而得到
// 映射值
// ret = 8 9 7 0 0 0 0 0 0 0
//
// 则这些数的和为
//
// (101 * 8) + (110 * 9) + (11 * 7) = 1875
//
ULL sum = 0;
for (int i = 0; i < 10; ++i) {
sum += ((ULL)weight[i] * (ULL)ret[i]);
}
cout << sum << endl;
return 0;
}
2、参考代码：
import java.util.ArrayList;
import java.util.Scanner;
public class DailyNews2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int[][] op = new int[n][2];
for (int i = 0; i < n; i++) {
op[i][0] = scanner.nextInt();
op[i][1] = scanner.nextInt();
}
stickPuzzle(n, op);
}
}
public static void stickPuzzle(int n, int[][] op) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (op[i][0] == 1) {
list.add(op[i][1]);
} else {
list.remove(new Integer(op[i][1]));
}
if (canFormPoly(list)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
//判断能否构成多边形
//list：各边长
public static boolean canFormPoly(ArrayList<Integer> list) {
int len = list.size();
for (int i = 0; i < len; i++) {
int temp = list.remove(i);
int sum = 0;
for (int j = 0; j < len - 1; j++) {
sum += list.get(j);
}
if (sum <= temp) { //判断是否任意len-1条边之和大于剩余一条边
list.add(i, temp);
return false;
}
list.add(i, temp);
}
return true;
}
}
3、参考代码：
#include <iostream>
#include <vector>
#include <assert.h>
#include <cstring> // for strncmp
#include <algorithm> // for std::next_permutation
using namespace std;
bool is_eq_after_move(const string& str, const size_t offset) {
const size_t len = str.size();
if (offset == len) return true;
assert(offset >= 1 && offset < len);
// 左移 offset 位数后，与原串相等的情况之一：
// 每 offset 个数据块 都要相等
// 所以 这种情况 的字符串，长度首先必须是 offset 的 整数倍。
//
// 情况之二，串长不是 offset 的 整数倍，像这种: ABABAB , offset = 4
// 这种情况可以用递归来化解:
if (len % offset != 0) {
if (len % offset > len / 2) return false; // 加上此句可减少复杂度
return is_eq_after_move(str, len % offset);
}
// 程序能走到这的都是 之前提到的 情况一:
char* s = (char*)&str[0]; // 先指向首地址
for (size_t loop = 0, max_loop = len / offset - 1;
loop < max_loop; ++loop) {
if ( 0 != strncmp(s, s + offset, offset) ) {
return false;
}
s += offset;
}
return true;
}
void get_ret(size_t& ret, const int* pos, const size_t size,
const vector<string>& input, const size_t K) {
size_t count = 1; // 自身整体移动算一个
string newstring;
for (size_t i = 0; i < size; ++i) {
newstring += input[pos[i]];
}
const int len = newstring.size();
for (int offset = 1; offset < len; ++offset) {
// 只判断 和第一个相等的字符即可
if (newstring[offset] == newstring[0]) {
if (is_eq_after_move(newstring, offset)) {
count++;
}
}
}
if (count == K) {
ret++;
}
}
int main() {
size_t n, K;
cin >> n >> K;
vector<string> input(n);
size_t newstrlen = 0;
for (size_t i = 0; i < n; ++i) {
cin >> input[i];
newstrlen += input[i].size();
}
// 生成 0 ~ n-1 的全排列
int pos[n];
for (int i = 0; i < n; ++i) pos[i] = i;
size_t ret = 0;
do {
get_ret(ret, pos, n, input, K);
} while (std::next_permutation(pos, pos + n));
cout << ret << endl;
return 0;
}
4、参考代码：
#include <iostream>
using namespace std;
int main()
{
long long x, k;
cin >> x >> k;
long long bitNum = 1;
long long ans = 0;
//目标是把k的各位依次填在x中是0的位上
//bitNum用来移动到x中零的位置，然后把k的最低位放在x的零位上, k左移，将下一位变成最低位,bitNum一直左移，知道x中的下一个为0的位上。
while (k)
{
if ((x & bitNum) == 0) //x中当前bitNUM为0的话,把k的最低位放在这儿
{
ans += (bitNum*(k & 1)); //k&1是将k的最低位取出来, bitNum*(k&1)的结果就是得到bitNum位和当前k的最低位一样的一个数,而其它位都是0
//而ans原来的bitNum为肯定为0，ans+(bitNum*(k&1)) 就将k的最低位放在x的这个零上了。
k >>= 1;
}
bitNum <<= 1; //bitNum的1一直左移到x中第k个零的位置
}
cout << ans << endl;
return 0;
}
个人资料
推荐圈子
猜你感兴趣的圈子：
标签： ret、pos、offset、bitnum、len、面试题
