本文已收录于专栏

🌻

《刷题笔记》

前言

hi~ ，我是刹那芳间，本专栏题目来源参考阿秀学长的刷题笔记，小戴只是把 C++的题解改成了 Java版本，并整理了其他思路，便于自己的学习~

如果解题有更好的方法，本文也会及时进行更新~

希望对你有帮助~ 一起加油哇~

🎨 1、数值的整数次方

牛客原题链接

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方

保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数

思路一（直接运算）

先处理一些 base 和 exponent 各自为0的情况，

用flag标记 exponent 正负情况，

如果指数为正，直接循环乘就好了，负的话，返回 1/结果

public class Solution {public double Power(double base, int exponent) {if(exponent==0) return 1.0;if(base==0) return 0.0;boolean flag = true; // 判断指数是否为正if(exponent < 0){flag = false;exponent = -exponent;}double res = 1.0;for(int i=0; i<exponent; i++){res *= base;}if(flag == true){return res;}else{return 1 / res;}}
}

思路二（快速幂递归版）

假设求 2的n次方，

当 n为奇数时，2的n次方可以表示为2的二分之n次方乘以
2的二分之n次方再乘以2，

当 n为偶数时，2的n次方可以表示为2的二分之n次方乘以
2的二分之n次方，

我们可以把2的二分之n次方这个中间值用一个变量直接存储

public class Solution {public double Power(double base, int exponent) {if (exponent == 0) return 1.0;if (base == 0) return 0.0;if (exponent == 1) return base;boolean flag = true;if (exponent < 0) {flag = false;exponent = -exponent;}double c = Power(base, exponent >> 1); // 用c保存double res = 1.0;if ((exponent & 1) == 1) { //奇数res = c * c * base;} else { // 偶数res = c * c;}if (flag) {return res;} else {return 1 / res;}}
}

思路三（快速幂非递归版）

public class Solution {public double Power(double base, int exponent) {if(exponent == 0) return 1.0;if(base == 0) return 0.0;long n = exponent;//当n == INT_MIN时,正数时大于INT_MAX的，所以要用一个大于 INT_MAX的类型来保存if(exponent < 0){n = exponent*(-1.0); //因为n返回结果是一个double型}double res = 1.0;while(n!=0){if((n&1) == 1){res *= base;}base *= base;n >>= 1;}return exponent>0 ? res : 1/res;}
}

🎨 2、调整数组顺序使奇数位于偶数前面

牛客原题链接

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变

思路一（暴力）

借用辅助数组，先遍历目标数组，把奇数存进辅助数组，再遍历目标数组，把偶数存进辅助数组

mport java.util.*;public class Solution {public void reOrderArray(int [] array) {int len = array.length;int[] n = new int [len];int j = 0;for (int i = 0; i < len; i++) {if ((array[i] % 2) == 1) { // 奇数n[j] = array[i];j++;}}for (int i = 0; i < len; i++) {if ((array[i] % 2) == 0) { // 偶数n[j] = array[i];j++;}}for(int i = 0; i < len; i++){array[i] = n[i];}}
}

思路二

这个思路类似冒泡，每次判断是否前面是偶数、奇数在后面，前偶后奇就交换

import java.util.*;
public class Solution {public void reOrderArray(int [] array) {int len = array.length;for(int i=0; i<=len/2+1; i++){for(int j=len-1; j>i; j--){if((array[j]&1)==1 && (array[j-1]&1)==0){ // 前偶后奇就交换int temp = array[j];array[j] = array[j-1];array[j-1] = temp;}}}}
}

🎨 3、链表中倒数第k个结点

牛客原题链接

题目描述

输入一个链表，输出该链表中倒数第k个结点

思路（快慢指针）

fast 指针先走k步，之后 slow 和 fast 同时走，直到 fast 到最后一个位置

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(head==null || k==0){return null;}ListNode slow =  head;ListNode fast = slow;for(int i=0; i<k; i++){if(fast==null){return null;}fast = fast.next;}while(fast!=null){slow = slow.next;fast = fast.next;}return slow;}
}

🎨 4、反转链表

牛客原题链接

题目描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头

思路（栈）

像这种，把东西反过来的，直接先思考栈

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
import java.util.*;
public class Solution {public ListNode ReverseList(ListNode head) {// 用栈Stack<ListNode> stack = new Stack<>();while(head != null){stack.push(head);head = head.next;}if(stack.isEmpty()){return null;}ListNode node = stack.pop();ListNode l = node;while(!stack.isEmpty()){ListNode temp = stack.pop();node.next = temp;node = node.next;}node.next = null;return l;}
}

郁金香