C++ 算法（一）

C++ 算法（一）

在一个长度为n+1的数组里的所有数字都在1 ~n的范围内，所以数组中至少有一个数字是重复 的。从数组中找出任意一个重复的数字，但不能 修改输入的数组。如{2,3,5,4,3,2,6,7}得到2或者3

#include #include using namespace std;int duplicateInArray0(vector& nums) { //暴力 n*n int n = nums.size(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] ^ nums[j] == 0) return nums[i]; } } return 0;}int duplicateInArray(vector& nums) { //二分 n* logn int l = 1, r = nums.size() - 1; while (l < r) { int mid = l + r >> 1; //[l, mid] [mid+ 1, r] int count = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] >= l && nums[i] <= mid) count++; } if (count > mid - l + 1) r = mid; else l = mid + 1; } return l;}int main(){ int a[8] = { 2, 3, 5, 4, 3, 2, 6, 7 }; vector nums; //将a的所有元素插入到b中 nums.insert(nums.begin(), a, a + 9); cout << "暴力解答：" << duplicateInArray(nums) << endl; cout << "二分解答：" << duplicateInArray(nums) << endl; return 0;}

找出数组中重复的数字：

class Solution{public: bool duplicate(int nums[], int n, int* out) { for (int i = 0; i < n; i++) { while (nums[i] != i) { if (nums[i] == nums[nums[i]]) { out[0] = nums[i]; return true; } else swap(nums[i], nums[nums[i]]); } } return false; } void swap( int i, int j) { }};

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一 列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判 断数组中是否含有该整数。

bool Find(int target, vector> array){ if (array.empty() || array[0].empty()) return false; int i = 0, j = array[0].size() - 1; while (i <= array.size() - 1 && j >= 0) { if (array[i][j] == target) return true; if (array[i][j] > target) j--; else i++; } return false; }

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字 符串为We Are Happy.则经过替换之后的字符串为We%20Are% 20Happy。

void replaceSpace(char* str, int length){ int count = 0; for (int i = 0; i < length; i++) { if (str[i] == ' ') count++; } for (int i = length - 1; i >= 0; i--) { if (str[i] != ' ') str[i + count * 2] = str[i]; if (str[i] == ' ') { count--; str[i + count * 2] = '%'; str[i + count * 2 + 1] = '2'; str[i + count * 2 + 2] = '0'; } }}

输入一个链表，按链表从尾到头的顺序返回一个ArrayList

struct ListNode{ int val; struct ListNode* next; ListNode(int x) : val(x), next(NULL) { }};vector printListFromTailToHead(ListNode* head){ /*ListNode* p = head; stack stk; vector result; while (p != NULL) { stk.push(p->val); p = p->next; } int len = stk.size(); for (int i = 0; i < len; i++) { result.push_back(stk.top()); stk.pop(); } return result;*/ ListNode* p = head; vector result; while (p!=NULL) { result.push_back(p->val); p = p->next; } return vector(result.rbegin(), result.rend());}

//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍

//历的结果中都不含重复的数字。例如输入前序遍历序列{ 1,2,4,7,3,5,6,8 }和中序遍历序列//{ 4,7,2,1,5,3,8,6 }，则重建二叉树并返回

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) :val(x), left(NULL), right(NULL) { }};unordered_map pos;TreeNode* reConstructBinaryTree(vector pre, vector vin) { int n = pre.size(); for (int i = 0; i < n; i++) pos[vin[i]] = i; return dfs(pre, vin, 0, n - 1, 0, n - 1);}TreeNode* dfs(vector pre, vector vin, int pl, int pr, int vl, int vr){ //前序 根左右 pre[pl] //中序 左根右 if (pl > pr) return NULL; if (pl > pr) return NULL; //找根节点 TreeNode* root = new TreeNode(pre[pl]); //左子树的长度k int k = pos[pre[pl]] - vl; //vl + k 根节点 root->left = dfs(pre, vin, pl + 1, pl + k, vl, vl + k - 1); root->right = dfs(pre, vin, pl + k + 1, pr, vl + k + 1, vr); return root;}

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点 不仅包含左右子结点，同时包含指向父结点的指针。

struct TreeLinkNode{ int val; struct TreeLinkNode* left; struct TreeLinkNode* right; struct TreeLinkNode* next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { }};TreeLinkNode* GetNext(TreeLinkNode* p) { //右子树存在 右子树最左边的结点 if (p->right) { p = p->right; while (p->left) p = p->left; return p; } //右子树不存在 只有左子树 while (p->next) { //p不是根节点 if (p == p->next->left) return p->next; p = p->next; } return NULL;}

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型

//先进后出 栈//先进先出 队列stack stack1, stack2;void push(int node) { stack1.push(node);}void copy(stack& a, stack& b) { while (a.size()) { b.push(a.top()); a.pop(); }}int pop() { copy(stack1, stack2); int res = stack2.top(); stack2.pop(); copy(stack2, stack1); return res;}

要求输入一个整数n，请你输出斐波那契数列的第n项（从0开 始，第0项为0)

int Fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; int first = 0, second = 1; int res = 0; for (int i = 2; i <= n; i++) { res = first + second; first = second; second = res; } return res;}

旋转数组的最小数字:

int minNumberInRotateArray(vector nums) { int n = nums.size() - 1; if (n < 0) return 0; while (nums[n] == nums[0] && n > 0) n--; if (nums[n] >= nums[0]) return nums[0]; int l = 0, r = n; while (l < r) { int mid = l + r >> 1; //[l, mid] [mid+1, r] if (nums[mid] < nums[0]) r = mid; else l = mid + 1; } return nums[r];}

矩阵中的路径

bool hashPath(char* matrix, int rows, int cols, char* str){ if (rows == 1 && cols == 1) { if (matrix[0] == str[0]) return true; else return false; //matrix 一维 //str 目标字符串 str \0 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (dfs(matrix, rows, cols, str, 0, i, j)) return true; } } return false; }}bool dfs(char* matrix, int rows, int cols, char* str, int u, int x, int y){ if (str[u] == '\0') return true; int dx[4] = { -1, 0, 1,0 }, dy[4] = { 0, 1, 0, -1 }; for (int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; if (a >= 0 && a < rows && b >= 0 && b < cols && matrix[a * cols + b] == str[u]) { char t = matrix[a * cols + b]; matrix[a * cols + b] = '*'; if (dfs(matrix, rows, cols, str, u + 1, a, b)) return true; matrix[a * cols + b] = t; } } return false;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。