#include <iostream> #include <vector> using namespace std; bool indexIsValue(const vector<int>& A, int low, int high) { if (low == high) { if (A[low] == low) return true; return false; } int mid = (low + high) / 2; if (A[mid] > mid) return indexIsValue(A, low, mid - 1); else if (A[mid] < mid) return indexIsValue(A, mid + 1, high); else return true; } int main() { vector<int> vec{ -1,1,3,4,6 }; cout << indexIsValue(vec, 0, vec.size() - 1) << endl; system("pause"); return 0; }
#include <iostream> #include <vector> using namespace std; int gcd(int a, int b) { int high = a, low = b; if (high % low == 0) return low; if (!high % 2 && !low % 2) return 2 * gcd(high / 2, low / 2); else if (high % 2 == 0 && low % 2 != 0) { if (high % 2 > low) return gcd(high % 2, low); else return gcd(low, high / 2); } else if (high % 2 != 0 && low % 2 == 0) return gcd(high, low / 2); else return gcd((high + low) / 2, (high - low) / 2); } int main() { cout << gcd(4, 3) << endl; system("pause"); return 0; }
// a 最小子序列和 int minSumRec(const vector<int>& a) { int minSum = a[0], thisSum = 0; for (size_t i = 0; i < a.size(); ++i) { thisSum += a[i]; minSum = min(minSum, thisSum); thisSum = min(thisSum, 0); } return minSum; } // b 最小正子序列和, 目前只会这种暴力求解的方式,插个眼 int minPosSumRec(const vector<int>& a) { int minPosSum = 0; for (int i = 0; i < a.size(); ++i) { int thisSum = 0; for (int j = i; j < a.size(); ++j) { thisSum += a[j]; if ((minPosSum == 0 && thisSum > 0) || (thisSum > 0 && thisSum < minPosSum)) minPosSum = thisSum; } } return minPosSum; } // c 最大子序列乘积, int maxProduct(const vector<int>& nums) { int maxpro = nums[0], minpro = nums[0], answer = nums[0]; for (size_t i = 1; i < nums.size(); ++i) { int mx = maxpro, mn = minpro; maxpro = max(mx * nums[i], max(mn * nums[i], nums[i])); minpro = min(mx * nums[i], min(mn * nums[i], nums[i])); answer = max(maxpro, answer); } return answer; }
leetcode 最大子序列乘积
#include <iostream> #include <vector> using namespace std; double func(double x) { return x * x - x - 1; } double solveZero(double (*func)(double x), double low, double high) { while (func(low) * func(high) < 0) { double mid = (low + high) / 2; if (func(mid) == 0) return mid; else if (func(mid) * func(low) < 0) high = mid; else if (func(mid) * func(high) < 0) low = mid; } } int main() { cout << solveZero(func, 1, 2) << endl; system("pause"); return 0; }
// 只做了算法4的,算法4有些错误,不能对纯负数进行求解,下面代码已经更正 #include <iostream> #include <vector> using namespace std; int maxSubSum4(const vector<int>& a, int& start, int& end) { start = end = 0; int maxSum = a[0], thisSum = 0; // 原代码maxSum = 0; int thisSumStart = 0; for (int j = 0; j < a.size(); ++j) { thisSum += a[j]; if (thisSum > maxSum) { maxSum = thisSum; start = thisSumStart; end = j; } if (thisSum < 0) // 原代码 else if (thisSum < 0) { thisSum = 0; thisSumStart = j + 1; } } return maxSum; } int main() { vector<int> vec{ -4, 2, -1, 4, -3, 2, 2 }; int start, end; cout << maxSubSum4(vec, start, end) << endl; cout << "(" << start << "," << end << ")" << endl; system("pause"); return 0; }
#include <iostream> #include <vector> using namespace std; bool isPrimeNum(int N) { if (N == 1) return false; else if (N == 2) return true; for (int i = 2; i <= pow(N, 0.5); ++i) { if (N % i == 0) return false; } return true; } int main() { cout << isPrimeNum(97) << endl; system("pause"); return 0; }
// 下面的代码是在解第20题的时候写的,有需要的再修改一下吧 #include <iostream> #include <vector> using namespace std; bool isPrimeNum(int N, vector<int>& vec) { if (N <= 1) return false; else if (N == 2) { vec.push_back(2); return true; } vec.push_back(2); int n = N; for (int i = 3; i <= N; ++i) { size_t j = 0; while (j < vec.size() && vec[j] <= pow(N, 0.5)) if (i % vec[j++] == 0) break; if (j >= vec.size() || vec[j] > pow(N, 0.5)) vec.push_back(i); } if (*(vec.end() - 1) == N) return true; return false; } int main() { vector<int> primeNumVec; cout << isPrimeNum(98, primeNumVec) << endl; for (auto iter = primeNumVec.begin(); iter < primeNumVec.end(); ++iter) { cout << *iter << " "; } cout << endl; system("pause"); return 0; }
double Pow2(double x, unsigned int n) { double result = 1; while (n) { if (n & 1) result *= x; n >>= 1; x *= x; } return result; }
原文链接
求主元素,这题有大佬会吗
#include <iostream> #include <list> #include <vector> using namespace std; bool existInMatrix(const int elems, const vector<vector<int>>& mat) { size_t curRow = 0; size_t curCol = mat[0].size() - 1; while (mat[curRow][curCol] != elems) { if (mat[curRow][curCol] > elems) { --curCol; if (curCol < 0) return false; } else { ++curRow; if (curRow >= mat[0].size()) return false; } } return true; } int main() { vector<vector<int>> Mat{ {1, 5, 9, 13},{2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12,16} }; cout << existInMatrix(7, Mat) << endl; system("pause"); return 0; }