1.数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
注意点：
1.exponent可以是负数，可以是0，可以是正数。
result等于exponent次的base乘积；如果是负数，result等于exponent次的base乘积的倒数；如果是0，除了base==0时，全都返回1（0的0次方无意义）
2.如果exponent是负数，base=0的时候，是没有意义的，这时应该报错
3.判断double类型是否相等时，不能直接==，而要使用精度判断（一般差值小于1e-即认为相等）
思路：
一个优化的表达。如果exponent是偶数，base^exponent = base(exponent/2)*base(exponent/2)；如果是奇数，base^exponent = base(exponent/2)*base(exponent/2)*base
public class Solution {
public double Power(double base, int exponent) {
if(isEqual(base,0.0)&&exponent<=0){
System.out.println("No meaningful input");
return 0;
}
double result;
if(exponent<0){
result = getAbsPower(base,Math.abs(exponent));
result = 1.0/result;
}else{
result = getAbsPower(base,exponent);
}
return result;
}
public double getAbsPower(double base,int absExponent){
if(absExponent==0){
return 1;
}
if(absExponent==1){
return base;
}
double result=1;
double halfResult = getAbsPower(base,absExponent>>1);
result = halfResult*halfResult;
if((absExponent&1)!=0){
result*=base;
}
return result;
}
public boolean isEqual(double a,double b){
return Math.abs(a-b)<0.0000001d;
}
}
2.调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：
1.类似插入排序。O(n^2)时间复杂度，O(1)空间复杂度。
将奇数前插，然后其余元素后移即可。直到最后遍历完整个数组
2.借助辅助数组。O(n)时间复杂度，O(n)空间复杂度。
先遍历一遍整个数组，找到奇数个数n。拷贝数组，然后对拷贝数组进行遍历，奇数依次从头赋值到原数组；偶数从下标n开始插入。
注意
1.数组拷贝的方式：
int[] dst = Arrays.copyOf(int[] src,int length)
int[] dst = Arrays.copyOfRange(int[] src,int from,int to)
System.arraycopy(int[] src,int srcStart,int[] dst,int dstStart,int copyLength);
2.考虑可扩展性，抽出判断部分单独成函数
import java.util.Arrays;
public class Solution {
public void reOrderArray(int [] array) {
int oddCount=0;
for(int i=0;i<array.length;i++){
if(isOdd(array[i]))oddCount++;
}
if(oddCount==0||oddCount==array.length)return;
int[] temp = Arrays.copyOf(array,array.length);
int oddPointer =0;
int evenPointer = oddCount;
for(int i=0;i<temp.length;i++){
if(isOdd(temp[i])){
array[oddPointer++] = temp[i];
}else{
array[evenPointer++] = temp[i];
}
}
}
public boolean isOdd(int i){
return (i&1)==1;
}
}
3.链表中倒数第k个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路：
如果不想遍历两遍，可以使用两个指针pre和after，pre先走k步，after再走。这样，当pre到达链表结尾的时候，after指向的节点就是倒数第k个节点
注意点
1.k==0时，直接return null
2.链表的长度可能小于k，此时也返回null
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int pre=0;
if(k==0){
return null;
}
ListNode kthNode=null;
ListNode node = head;
while(node!=null){
pre++;
if(pre==k){
kthNode = head;
}else if(pre>k){
kthNode = kthNode.next;
}
node = node.next;
}
return kthNode;
}
}
4.反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
注意：
1.结束条件 current.next==null，reverseHead = current
2.链表反转后，尾节点后跟null(head节点也要注意反转啊)
3.保存current.next防止断裂
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)return head;
ListNode pre = null;
ListNode mid = head;
ListNode reverseHead = null;
while(mid!=null){
ListNode after = mid.next;
mid.next = pre;
if(after==null){
reverseHead = mid;
break;
}
pre = mid;
mid = after;
}
return reverseHead;
}
}
5.合并两个排序链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null&&list2==null)return null;
if(list1==null)return list2;
if(list2==null)return list1;
ListNode newList;
if(list1.val<=list2.val){
newList = new ListNode(list1.val);
newList.next = Merge(list1.next,list2);
}else{
newList = new ListNode(list2.val);
newList.next = Merge(list1,list2.next);
}
return newList;
}
}
6.数的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
这题注意点在于，子结构不等于子树，A中包含一部分B即可
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2==null||root1==null){
return false;
}else if(root1.val==root2.val&&isContainTree(root1,root2)){
return true;
}else{
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
}
public boolean isContainTree(TreeNode root1,TreeNode root2){
if(root2==null&&root1==null){
return true;
}else if(root1==null){
return false;
}else if(root2==null){
return true;
}else if(root1.val!=root2.val){
return false;
}else{
return isContainTree(root1.left,root2.left)&&isContainTree(root1.right,root2.right);
}
}
}
如果是子树：把root2==null这个判断里的return true改成return false
