code-016

一、题目描述 二、动态转移方程 三、题解12345678910111213141516171819class Solution {public: //动态规划 int maxProfit(vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; vector<int> dp; dp.resize(n, 0); int minprice = prices[0]; for(int i = 1; i < n; ++i) { minprice = min(minprice, prices[i]); dp[i] = max(dp[i - 1], prices[i] - minprice); } return dp[n - 1]; }} ...

一、题目描述 二、算法分析 三、题解代码12345678910111213141516171819202122232425class Solution {public: int rob(vector<int>& nums) { int house_len = nums.size(); vector<int> dp; dp.reserve(house_len); for (int i = 0; i < house_len; ++i) { if (i == 0) { dp[i] = nums[i]; } else if (i == 1) { dp[i] = max(nums[i - 1], nums[i]); } else { dp[i] = max(dp[i-1], dp[i - 2] + nums[i]); } } return dp[house_len - 1];}};

一、题目描述 二、代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<vector>using namespace std;void Robits(vector<vector<int>>& dp){ for (int i = 0; i < dp.size(); ++i) { for (int j = 0; j < dp[i].size(); ++j) { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i ...

一、引言 二、最长公共子序列 三、解题思路 四、代码12345678910111213141516171819202122232425262728int LSCLen(char* arr, char* brr, int m, int n){ //if (nullptr == arr || nullptr == brr) return 0; if (m == 0 || n == 0) return 0; else { if (arr[m] == brr[n]) { return LSCLen(arr, brr, m - 1, n - 1) + 1; } else { int max1 = LSCLen(arr, brr, m - 1, n ); int max2 = LSCLen(arr, brr, m, n - 1); return max1 > max2 ? max1 : max2; } }}int main(){ char x[] = "#ABCB ...

一、题目描述 通过使用分治策略，打印一个数组元素的所有子集输入：1 2 3输出：1 2 31 21 312 323 二、解题思路通过这个程序的思路进行分析 1234567891011121314void fun(int i, int n){ if(i >= n) return; else { fun(i + 1, n); fun(i + 1, n); }}int main(){ fun(0, 3);} 上述程序的递归活动如下我们在递推的过程中将brr[i] = 1; 回归的过程中将brr[i] = 0; 最终通过brr[i] == 1 ？ 打印 ： 不打印； 三、代码实现123456789101112131415161718192021222324252627282930//打印子集#if 1void PrintSon(int* arr, int* brr,int left, int right){ if (left >= right) { for (int i = 0; i < ...

一、题目描述 二、思路分析若R = {1, 2, 3} 对应的全排列就是1 3 22 1 32 3 13 2 13 1 2 进行层次分析： 三、递归程序1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;#if 1void Perm(int* arr, int left, int right){ if (left == right) { //确定只剩下一个元素时 for (int i = 0; i <= right; ++i) { cout << arr[i] << " "; } cout << endl; } else { //需要确定相对首元素 for (int i = left; i <= right; ++i) { swap(arr[left ...

一、描述 一维最接近点对问题：也就是寻找无序不重复数组的最小差值 解题思想：分治策略 二、思路 三、代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596//寻找非负整数序列(不重复)的最小差值#if 1//两边向中间划分int OnePartition(int* arr, int left, int right){ int tmp = arr[left]; int i = left; int j = right; while (i < j) { while (i < j && arr[j] > tmp) { --j; } arr[i] = arr[j]; while (i & ...

一、关于分治策略分治策略： 简单来说就是将问题的规模变小，问题本身不变 解题步骤： 分解： 将原问题划分成子问题，规模变小 递归： 递归求解子问题，若子问题规模足够小，此时停止递归，直接求解 合并： 将小规模的解合并成原规模的解 注意： 分治策略是一种处理问题的思想，递归是一种算法。 二、使用分治策略+递归解题（1）快速排序123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118#include<iostream>#include<stack>#include<limits.h>using namespace st ...

题目描述 解题思路 题解123456789101112131415161718192021222324252627282930313233class Solution {private: //反转降序的后部分 void reverse(vector<int>& nums, int left, int right) { while(left < right) { swap(nums[left++], nums[right--]); } }public: void nextPermutation(vector<int>& nums) { int len = nums.size(); if (len < 1) return; //反遍历，找到非降序的首元素 int i = len - 2; while (i > ...

题目描述 解题思路快慢指针 题解1234567891011121314151617181920class Solution {public: int removeElement(vector<int>& nums, int val) { int len = nums.size(); if(len < 1) return 0; //快慢指针 int fast = 0; int slow = 0; while(fast < len) { if(nums[fast] != val) { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
...