import java.util.ArrayList;
import java.util.Stack;
//https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?
public class 从尾到头打印链表 {
public ArrayList printListFromTailToHead_1(ListNode listNode) {
//定义待返回数组
ArrayList arr = new ArrayList<>();
//合法性判断
if (listNode == null){
return arr;
}
//倒叙排列，栈结构先进后出
Stack stack = new Stack<>();
//listNode不是空的化顺序入栈
while (listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
//while循环跳出时，所有元素已经存入栈中，出栈让入动态数组就是倒叙
while (!stack.isEmpty()){
arr.add(stack.pop());
}
return arr;
}
public ArrayList printListFromTailToHead_2(ListNode listNode) {
//定义待返回数组
ArrayList arr = new ArrayList<>();
//合法性判断
if (listNode == null){
return arr;
}
//调用方法帮助操作（在arr中添加合适的元素）
fun_2Help(arr , listNode);
return arr;
}
public void fun_2Help(ArrayList arr , ListNode listNode){
//合法性判断,不合法就返回null，也是递归判出条件
if (listNode == null){
return ;
}
//如果不为空的话继续向下递归到它后面的元素；
fun_2Help(arr , listNode.next);
//遇到边界时开始返回把元素添加到动态数组中
arr.add(listNode.val);
}
//题目的listNode类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
}
《重建二叉树》：题目地址
题解：
//https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?
public class 重建二叉树 {
public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
//合法性判断
if (pre == null || vin == null){
return null;
}
return funHelp(pre , 0 , pre.length - 1 , vin , 0 , vin.length - 1);
}
//根据前序遍历与中序遍历和他们的边界构建二叉树
public TreeNode funHelp (int[] pre , int preStart , int preEnd , int[] in , int inStart , int inEnd){
//合法性判断，边界合理性
if (preStart > preEnd || inStart > inEnd){
return null;
}
//创建一个带返回二叉树
TreeNode root = new TreeNode(pre[preStart]);
//循环中序遍历的数组找到其前序遍历第一个值（树根）可以将中序数组分成左右半部分；记住for循环知识确定根的过程，构建在左右子树确定时发生,右边界要相等哟
for (int i = inStart; i <= inEnd; i++) {
//确定好根的位置（即pre的第一个是根在in中找到所以其左右子树也可以确定好）
if (in[i] == pre[preStart]){
//确认左子树，注：因为preStart是树根所以肯定不是左子树，所以其左子树值边界preStart + 1开始到
//pre右边界：i是从in中查找到的i-inStart的距离就是左子树的长度+preStart就是左子树右边界
root.left = funHelp(pre , preStart + 1 , preStart + i - inStart , in , inStart , i - 1);
//确定右子树
root.right =funHelp(pre , preStart + i - inStart + 1 , preEnd , in , i + 1 , inEnd );
//左右子树都确定好了，跳出即可
break;
}
}
return root;
}
//题目给定二叉树类
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}
《斐波那契数列》：题目地址
题解：
//https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?
import java.util.HashMap;
import java.util.Map;
public class 斐波那契数列 {
public int Fibonacci_1(int n) {
if (n == 1 || n == 2)
return 1;
else return Fibonacci_1(n - 1) + Fibonacci_1(n - 2);
}
public int Fibonacci_2(int n) {
//记录初始的n == 1和n == 2时的值
int n1 = 1;
int n2 = 1;//n2记录的就是n=？时的值
//n3单纯为了辅助计算用
int n3 = 1;
while (n > 2){
n3 = n1;
n1 = n2;
n2 = n3 + n1;
n -= 1;
}
return n2;
}
public int Fibonacci_3(int n){
Map map = new HashMap<>();
if (n == 1 || n == 2){
return 1;
}
//n1:n - 1;n2:n - 2
//计算n - 1的值记录为n1
int n1 = 0;
if (map.containsKey(n - 1)){
n1 = map.get(n - 1);
}else {
n1 = Fibonacci_3( n - 1);
map.put(n - 1 , n1);
}
//计算n - 2的值记录为n2
int n2 = 0;
if (map.containsKey(n - 2)){
n2 = map.get(n - 2);
}else {
n2 = Fibonacci_3(n - 2);
map.put(n - 2 , n2);
}
return n1 + n2;
}
public int Fibonacci_4(int n){
int[] arr = new int[n + 1];
arr[1] = 1;
arr[2] = 1;
for (int i = 3; i < arr.length; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
}
《矩形覆盖》：题目地址
题解：
这里只已斐波那契数列的一种解法完成，其他方法类似，可以参考上一道题《斐波那契数列》：《斐波那契数列》
//https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?
public class 矩形覆盖 {
public int rectCover(int target) {
//特殊情况考虑
if (target < 2)
return target;
//定义数组进行保存中间一些重复的计算量
int[] arr = new int[target + 1];
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i < arr.length; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[target];
}
}
《二进制中1的个数》：题目地址
题解：
我们以一种相对简单的方法来完成
//https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?
public class 二进制中1的个数 {
public int NumberOf1(int n) {
//计数用
int con = 0;
//&运算时会使n的2进制数的最后一个"1"变成"0"
while (n != 0){
n &= n - 1;
con ++;
}
return con;
}
}
小tips如下；“&”运算的效果
