![java 剑指offer之[数据结构 简单] JZ81调整数组顺序使奇数位于偶数前面(二)](http://www.mshxw.com/aiimages/31/354082.png "java 剑指offer之[数据结构 简单] JZ81调整数组顺序使奇数位于偶数前面(二)")
题目的链接在这里：https://www.nowcoder.com/practice/0c1b486d987b4269b398fee374584fc8
- 题目大意
- 一、示意图
- 二、解题思路
- 动态规划
题目大意 输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。
数据范围：0 le n le 500000≤n≤50000，数组中每个数的值 0 le val le 100000≤val≤10000
要求：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)
一、示意图 二、解题思路
双指针动态规划
代码如下：
public class Solution {
public int cutRope(int target) {
int[] dp=new int[target+1];
//dp[n] 表示的是 当target为n时
//先进行边界判断
if(target<=3){
return target-1;
}
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(int i=4;i<=target;i++){
//这里细节就是i/2
for(int j=1;j<=i/2;j++){
dp[i]=Math.max(dp[i],dp[i-j]*dp[j]);
}
}
return dp[target];
}
}
