思路 稳定排序，奇数的权重小于偶数，奇数和偶数权重相同 开辟一个数组存储面试的时候大概会让你写第一种的，笔试的时候写第二种，这里给出插入排序的代码 代码 开辟辅助数组 public class Solution { public void reOrderArray(int [] array) { int[] arr=new int[array.length]; int p=0,q=0; for(int i=0;i<array.length;i++){ if(array[i]%2==1){ ...

思路 考虑负指数，把负指数变正，最后1/结果指数可分解，偶数提出来2，指数除2，奇指数，指数减一，结果乘上base 代码 import java.util.*; public class Solution { public double Power(double base, int exponent) { if(base==0){ return 0; } if(exponent==0){ return 1; } double res=1; bo...

思路 十进制转换为二进制，进制转换：取模倒排法（高中数学），这里是%2,然后原数除以2 位运算，除2可以转换为右移1，n&1二进制最低位的数字 lowbit函数，在树状数组结构中有一个函数名为lowbit函数 i&(i-1),，将最低位的1变成0；，比如 110变成100，由6变成4，4是小于6的最大的2的幂显然： 思路3>2>1再看看，Integer类的方法，lowesrOneBit()和highestOneBit() 分别是获得最小和最大的2个幂次的分量权重。比如6的二进制是110，分解为4+2+0，lowesrOneBit(6)=2，highestOneBi...

思路 7,8,9,10的思路都是一样的F(n)=F(n-1)+F(n-2) 递归：占内存，容易栈溢出 动态规划,一维数组保存前面所有状态，又由于本题只与前两个状态有关，所以用两个变量保存前两个状态即可 第7题 动态规划 public class Solution { public int Fibonacci(int n) { if(n<=0){ return 0; } if(n==1||n==2){ return 1; } int p=1,q=1; ...

思路： 这个数组的曲线如图所示对照上述图像，让p在左边，q在右边，应该比较easy思考规定：p<q,则array[q]<=array[p]mid=(p+q)/2二分查找分割线，这里规定了p<q，所以当p=q-1的时候刚好是找到，所以while(p<q-1); import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int p=0,q=array.length-1; while(p&lt...

思路 队列是先进先出FIFO,栈先进后出把后出变成先出，用另外一个栈存储逆序就可以了 代码思路 stack1用于push数据，push时，把所有数据放入stack1stack2用于pop数据,pop时，把所有数据放入stack2这样的作法，对于连续pop和push时效率高，均衡了push方法和pop方法还有一种作法是，pop时会把数据放入stack2,然后再全部放入到 stack1中，虽然push效率很高，但是pop效率低了。 import java.util.Stack; public class Solution { Stack<Integer> stack1 = n...

思路：递归二叉树有4种遍历方式：先根，中根，后根，层序。这个顺序值得是一个树分为根，左子树，右子树。层序不能递归遍历。先根和中根重建二叉树的思路，pre[0]为根节点，in中的元素通过pre[0]分为两部分，分别是左子树和右子树。 import java.util.*; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length<=0){//pre和in相同长度 return null; ...

思路： 从头遍历 ：如果知道java ArrayList的 add（）方法其实是插入方法add(0,val)，在0处插入，后面都往后移动一格， 理论上可以一次遍历输出，这个方法调用arraycopy方法把后面的元素往后移动一个位置，native方法，效率应该是很高了。 递归（栈）：这个思路和前序遍历二叉树一致，递归的缺点在于占内存。 反转链表：利用三个指针反转这个链表，然后遍历。 代码 从头遍历 import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListF...

思路及其优缺点 开辟String类或者Stringbuild，直接添加; 缺点在于增加了空间复杂度，优点思路简单，编程简单 直接在StringBuffer上修改，StringBuffer(StringBuild)本质上是一个数组，首先扩充数组，从后往前把字符复制到后面。但是需要统计空格数，所以需要遍历两次数组，时间复杂度换来了空间复杂度。另外一个缺点编程代码更长，考虑更多 代码 开辟新数组 public class Solution { public String replaceSpace(StringBuffer str) { String res=""; ...

思路 数组指针移动，从0 0出发 （更好的思路是从0，n和n,0出发），根据状态移动 二份查找o(nlogn)，因为有内置函数，更快完成本题 踩坑： 对于数组 [[]] array.length=1 array[0]=0,所以二维数组判空条件不仅仅是 array.length<=0实测没加 array==null也AC，保险起见加上， 代码 二分查找 //二分查找 import java.util.*; public class Solution { public boolean Find(int target, int [][] array) { i...

没什么技巧，就是逐个增加字符，然后判断是否是回文，因为前i个必定回文，从第i个开始判断是否回文。换句话说，就是求，包含最后一位字符的最大回文子串 import java.util.*; public class Main{ public static boolean func(String s,int p){ boolean flag; int q=s.length()-1; while(p<q){ if(s.charAt(p)!=s.charAt(q)){ return fa...

动态规划判断是否神奇（抄讨论区C++大佬的） import java.util.Arrays; import java.util.Scanner; public class Main { private static boolean judge(int a){ int[] ints = new int[9]; int sum = 0; for(int i = 0; i < 9; i++){ ints[i] = a % 10; sum += ints[i]; a...

数学方法，本题通过消元法转换为一元函数，但是编程不好实现，N个约束的转换编程把每种材料作为最小的哪个，取所有情况最小值 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); double v = scanner.nextDouble(); double[] a = ne...

import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] coins=new int[]{1,2,5,10,20,50,100}; int type=0; int cnt=0; for(int i=0;i<coins.length;i++){ ...