24年京东秋季笔试题
260. 牛牛的位置
链接：https://kamacoder.com/problempage.php?pid=1340
思路：记录当前的方向，以及维护一个前进方向的矩阵就行了，比如在最初始的方向为0°，前进的时候给x+0，y+1，即{0,1}；当往左边旋转90°的时候，前进的时候给x+(-1)，y+0，即{-1,0}；后面以此类推。考虑一个二维数组actions[4][2]={{0,1},{-1.0},{0,-1},{1,0}}。向左旋转90°的时候，便将记录方向的下标加一，如果超过了二维数组的下标，就将方向更新为0，即方向又向上了；向右转便是同理。
#include <iostream>using namespace std;int actions[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int main()
{int x = 0, y = 0;string str;getline(cin, str);int direction = 0;for (int i = 0; i < str.size(); ++i){if (str[i] == 'W'){x += actions[direction][0];y += actions[direction][1];}else if (str[i] == 'A'){direction = direction + 1 == 4 ? 0 : ++direction;}else if (str[i] == 'D'){direction = direction - 1 < 0 ? 3 : --direction;}else{continue;}}cout << x << " " << y << endl;return 0;
}
261.和为k的序列对数量
链接：https://kamacoder.com/problempage.php?pid=1341
思路：这题可以采用的思路为哈希表，首先用一个数组接收序列。然后在遍历当前数组的过程中，对于当前遍历到的元素，设其为x，那么我们需要求出前面已经出现过多少个k-x，假设已经出现了m个k-x，那么结果需要加上m*2，因为i和j可以反过来再组合一次；如果k-x==x，那么结果还需要额外加一，因为i和j可以相等。最后将当前的元素x加入到哈希表，令其对应的记录频数加一。
#include <iostream>
#include <unordered_map>using namespace std;int main()
{int n, k;cin >> n >> k;int nums[n];for (int i = 0; i < n; ++i){cin >> nums[i];}int result = 0;unordered_map<int, int> uNums;for (auto i : nums){int key = k - i;if(uNums.count(key)) {result += 2 * uNums[key];}if (key == i){++result;}++uNums[i];}cout << result << endl;return 0;
}
262. 生成指定数组的最少操作次数
链接：https://kamacoder.com/problempage.php?pid=1342
思路：首先考虑一个数从0变到x，最短需要多少步？因为这里只能进行+1和*2的操作，2操作可以看作是位运算符的左移操作，可以很清楚的知道，在位运算的左移过程中，是不会改变二进制位上1的数量的，只有+1会改变二进制位1的数量，所以我们将0变成x的最小步数就是**x的最高位1所在的位数+x的二进制位中1的数量。**1的数量表示我们要进行多少次+1操作，最高位的位数表示我们要进行多少次唯一运算，即2操作。
我们按照这个方法将数组的所有的数最低step全部求出来，然后对整个数组进行贪心。 由于这个数组里面的所有的数就表示每个数的最短操作次数。假设我们已经操作到第i个数了， 第i个数的操作次数是p，第i+1个数的操作次数是q，那么有下面的结论：
-
如果p > q: 那么q就可以和p共用操作次数，因为我们是可以选一段区间进行操作的；
-
如果q > p: 那么q就可以和p共用p次，然后需要额外对q再执行q - p次操作。
所以题目就转化为求相邻两项的差值和问题了，并且只有后面的项大于前面的项才进行累积。 设这个和为sum。那么最终的结果就是sum + step(b[0])。
#include <iostream>
#include <vector>using namespace std;int min_step(int x)
{int ans = 1;while (x > 1){if (x & 1) x = (x - 1) >> 1, ans += 2;else x >>= 1, ++ans;}return ans;
}int main()
{int t;cin >> t;while(t--){int n, ans = 0;cin >> n;vector<int> nums(n);for (int i = 0, x; i < n; ++i){cin >> x;nums[i] = min_step(x);}for (int i = 1, last = nums[0]; i < n; last = nums[i++]){if (last < nums[i]) ans += nums[i] - last;}cout << ans + nums[0] << endl;}return 0;
}