题目描述：
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n^2) 。
方法一（暴力法）：
即针对数组的每一个元素都有两种选择，取或者不取（取的前提是当前元素大于上一个元素，则上升子序列++），最终递归到最后的一个元素，将结果返回。
实现如下：
int lengthOfLIS(vector<int>& nums) { return get_lengthOfLIS(nums, -1, 0);
}
int get_lengthOfLIS(vector<int> &num, int prev, int curr) { if(curr == num.size()) { return 0;}int taken = 0;if(num[curr] > prev) { taken = get_lengthOfLIS(num, num[curr], curr+1);}int notaken = get_lengthOfLIS(num, prev, curr+1);return max(taken, notaken);
}
但是因为暴力解法的时间复杂度较高，针对每个元素都有两种选择，时间复杂度为O(2^n)
方法二（DP动态规划）：
实现如下:
int lengthOfLIS(vector<int>& nums) { if(nums.size() <= 1) return nums.size();vector<int> dp(nums.size(),0);int res = 1,i = 1, j = 0;dp[0] = 1;for(i = 1;i < nums.size(); ++i) { dp[i] = 1;for (j = 0;j < i; ++j) { if(nums[i] > nums[j] && dp[i] < dp[j] + 1) { //找到nums[i]左边比nums[i]小的元素，取它的dp[j] + 1给到dp[i]dp[i] = dp[j]+1;}}if(res < dp[i]) { //res取最大即可res = dp[i];}}return res;
}
以上方法的时间复杂度为O(n^2)，j的遍历的层数和i的个数基本一致
方法三（递增栈 + 二分）：
维护一个持续递增的栈，元素添加进来有两种规则：
只有当满足第一中情况的时候栈的大小才会增加，否则栈的大小是固定的，优化的办法是使用二分法查找待插入的位置
实现如下：
int lengthOfLIS(vector<int>& nums) { if (nums.size() == 0) return 0;vector<int> stack;//使用vector代替栈stack.push_back(nums[0]);for (int i = 1;i < nums.size(); ++i) { if (nums[i] > stack.back()) { stack.push_back(nums[i]);} else { int pos = binary_search(stack,nums[i]);stack[pos] = nums[i];}}return stack.size();
}//二分查找，返回待插入元素的下标
int binary_search(vector<int> &stack,int target) { int index = -1;int begin = 0;int end = stack.size() - 1;while (index == -1) { int mid = (begin + end) / 2;if (target == stack[mid]) { index = mid;} else if (target < stack[mid]) { if (mid == 0 || target > stack[mid - 1]) { index = mid;}end = mid - 1;} else { if (mid == stack.size() - 1 || target < stack[mid + 1] ) { index = mid + 1;}begin = mid + 1;}}return index;
}
时间复杂度为O(N*logn)，遍历n次，每次二分查找的时间复杂度是logn
Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。 我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...
利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...
题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： 5 / 2 6 / 1 3示例 1： 输入: [1,6,3,2,5] 输出...
题目：调整数组顺序使奇数位于偶数前面 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例： 输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。 提示： 1 <= nums.length <=...
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1]...
题目描述： 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。 示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 该题目...
题目描述如下： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 方法一（暴力求解）： 针对数组中的每一个元素，穷举所有的可能性，...
WinForm绘制带有升序、降序的柱形图 private void HuiZhiTu( string strPaiXu){//初始数据int[] nums = { 150, 89, 200, 60, 70, 90 };if (strPaiXu == "升序"){//冒泡排序for (int i = 0; i <...
栈stack：stack 后入先出（LIFO） q.top()获取栈顶元素（并不删除）q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue：先入先出（FIFO） q.front()获取队首元素（并不删除）q.pop()删除队首元素q.push(x)向队列中加入元素q....
resize()，设置大小（size）; reserve()，设置容量（capacity）; size()是分配容器的内存大小，而capacity()只是设置容器容量大小，但并没有真正分配内存。 打个比方：正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说...
v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...
技巧一（推荐指数★★★★★） 采用top、right、bottom、left，可以不在乎父元素的宽度和高度，对GPU损耗低于技巧三，但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。 示例： MinStack minStack = new MinStack(); minStack...