调整数组顺序使奇数位于偶数前面 题目链接 Solution 让奇数排在偶数前面。当然可以暴力的扫一遍，将奇数偶数分开然后组合合并。但是algorithm库中的sort函数支持自定义排序函数，即让奇数偶数作为权值排序。即用数字模2作为大小排序。使用方式详见代码，代码较为简单易懂。 Code class Solution { public: static bool cmp(int a,int b){ return (a % 2) > (b % 2); } void reOrderArray(vector<int> &array)...

数字在升序数组中出现的次数 题目链接 Solution 暴力。询问一个数出现的次数，扫一遍数组，如果当前数和这个数相等，答案+1。没有什么太难的地方，详见代码，代码比较简单易懂。当然因为数组是升序的，可以二分出第一个大于这个数的位置和第一个小于这个数的位置，然后做差得到答案，但是数据范围较小，可以直接复杂度过。 Code class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int ans = 0; for (int i = 0; i < (int)da...

旋转数组 题目链接 Solution 模拟。新建一个vector，先加入后面n-m个元素，然后加入前面m个元素即可。代码实现较为简单，需要注意下m如果大于n的情况，需要让m模n。 Code class Solution { public: vector<int> solve(int n, int m, vector<int>& a) { vector<int> ans; m %= n; for (int i = n - m; i < n; ++i) ans.push_back(a[i]);...

最长公共前缀 题目链接 Solution 求n个串的最长公共前缀。从0开始枚举答案，然后依次比较所有字符串的这一位，如果都相同，那么答案+1。注意一下答案最大是最小的字符串的长度。数据范围较小，暴力可过。 Code class Solution { public: string longestCommonPrefix(vector<string>& strs) { string ans; if (strs.empty()) return ans; int n = 1e9; for (int i = 0;...

换钱的最少货币数 题目链接 Solution 问n种货币凑成一个面额所需要的最少货币数。动态规划。 表示凑成面额i的需要的最少货币数。然后枚举每个面额的货币，更新dp数组即可。 Code class Solution { public: int minMoney(vector<int>& arr, int aim) { int dp[aim + 5]; dp[0] = 0; for (int i = 1; i <= aim; ++i) dp[i] = 1e9; for (int i = 0; i...

连续子数组的最大和 题目链接 Solution 最大子段和问题，可以使用动态规划解决此问题。设表示以i结束的子段的最大子段和。所以到i时有两种选择，和前面的最大子段结合，自己构成一个新的子段。得到转移方程 Code class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int n = array.size(); int dp[n + 5]; dp[0] = array[0]; for (int i = 1; i &...

求路径 题目链接 Solution 从左上角走到右下角，只能向右走或者向下走，求方案数。这是一个经典的问题。问题转化为走n+m-2次，其中向右走m-1次，向下走n-1次。也就是类似“右右下右下下...”的序列有多少个。所以方案数就是在n+m-2个位置中选择m-1个位置是右，剩下的是下。所以答案就是或者。 Code class Solution { public: int uniquePaths(int m, int n) { int C[105][105]; C[0][0] = C[1][0] = C[1][1] = 1; for (i...

palindrome-number 题目链接 Solution 判断一个数字是否是回文串。回文串的定义是正着读和反着读相同，所以我们可以把数字反转后，判断两个数字是否一样即可。反转数字的方法是将n不断对10取模，然后除以10。 Code class Solution { public: bool isPalindrome(int x) { // write code here if (x < 0) return false; int tmp = x, y = 0; while (tmp) { ...

数组中出现次数超过一半的数字 题目链接 Solution 求出现次数大于一半的数。直接开一个map，统计每个数字出现的个数，最后扫一遍原数组，找到出现次数大于一半的数字即可。 Code class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { map<int,int> cnt; for (int i = 0; i < (int)numbers.size(); ++i) cnt[numbers[i]] ++; fo...

反转数字 题目链接 Solution 将一个数字反转，思路比较简单，可以考虑分成两步。首先将数字拆分成0-9，存下。将拆分后的数字从后往前组合起来，即可实现反转操作。 Code class Solution { public: int reverse(int x) { int ans = 0, f = 1; if (x < 0) f = -1, x = -x; while (x) { ans = ans * 10 + x % 10; x /= 10; } ...

牛客题霸--进制转换 题目链接 Solution 进制转换的方法较为经典。对于一个十进制的是数，每次对M取模，然后除以M（M为转换后的进制）即可得到M进制数。因为M进制的数第一位时，第二位时，第三位所以如果10进制的数n大于（k是最大的，即）则说明第k+1位上必定是，然后让 依次类推即可。对于代码实现，可以反过来，不断模M，除以M即可，详见代码。 Code class Solution { public: string solve(int M, int N) { int f = 1; string tmp, ans; char str[...

买卖股票的最好时机 题目链接 Solution 因为只有一次买入卖出的机会，所以可以枚举在哪天卖出。对于卖出的那一天，买入的那一天一定在这一天之前，并且是价格最低的。所以从前往后扫，记录并更新最小值即可。 Code class Solution { public: int maxProfit(vector<int>& prices) { // write code here? int ans = 0, mn = prices[0]; for (int i = 1; i < (int)prices.size()...

数组中只出现一次的数字 题目链接 Solution 只有两个数字出现了1次，其他数字都出现两次。所以定义一个map，记录每个数字出现的次数。最后扫一遍数组，找出只出现一次的数字即可。 Code class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { ap<int,int>mp; bool fir = 0; for (int i = 0; i < (int)data.size(); ++i)...

两数之和 题目链接 Solution 寻找两个数，使它们的和等于所给的值。因为数据范围较小，所以可以直接枚举两个数，求和计算比较即可。 Code class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { // write code here vector<int> ans; for (int i = 0; i < numbers.size(); ++i) for (...