public class Solution {
/*//第一题
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
public boolean Find(int target, int[][] array) {
int n = array.length;//代表数组有n行
int m = array[0].length;//代表数组有m列
for (int i = 0; i < n && i < m; i++) {
if (target == array[i][i]) {
return true;
} else if (target > array[i][i]) {
continue;
} else {
//比较array[i-1][i]和array[i][i-1]
for (int j = 0; j < i; j++) {
if (target == array[j][i] || target == array[i][j]) {
return true;
}
}
}
}
if (n > m) {
for (int k = m; k < n; k++) {
for (int j = 0; j < m; j++) {
if (target == array[k][j]) {
return true;
}
}
}
} else if (n < m) {
for (int k = 0; k < n; k++) {
for (int j = n; j < m; j++) {
if (target == array[k][j]) {
return true;
}
}
}
} else {
return false;
}
return false;
}
//第二题
/*
请实现一个函数，将一个字符串中的空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
*/
public String replaceSpace(StringBuffer str) {
String[] strs = str.toString().split("");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
if (strs[i].equals(" ")) {
sb.append("%20");
} else {
sb.append(strs[i]);
}
}
return sb.toString();
}
//第三题
/*
输入一个链表，从尾到头打印链表每个节点的值。
*/
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> ai = new ArrayList<>();
while (listNode != null) {
ai.add(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> aii = new ArrayList<>();
for (int i = ai.size() - 1; i >= 0; i--) {
aii.add(ai.get(i));
}
return aii;
}
//第四题
/*
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
则重建二叉树并返回。
针对根的存放顺序来决定
先序遍历：中左右
中序遍历：左中右
后续遍历：左右中
*/
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == 0 || in.length == 0)
return null;
TreeNode node = new TreeNode(pre[0]);
for (int i = 0; i < pre.length; i++) {
if (pre[0] == in[i]) {
//Arrays.copyOfRange 表示数组复制，左闭右开
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return node;
}
//第五题
// 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);//实现队列的push操作
}
public int pop() {
int result;
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
result = stack2.pop();
} else {
result = stack2.pop();
}
return result;
}
//第六题，把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
// 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public int minNumberInRotateArray(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[i]) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
return array[0];
}
//第七题：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
public int Fibonacci(int n) {
int[] F = new int[n + 1];
if (n == 0) {
return 0;
}
F[0] = 0;
F[1] = 1;
for (int i = 2; i < F.length; i++) {
F[i] = F[i - 1] + F[i - 2];
}
return F[n];
}
//第8题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//1 1
// 2 2
// 3 3
// 4 5
// 5 8
// 6 13
public int JumpFloor(int target) {
if (target == 0) {
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
int[] array = new int[target + 1];
array[0] = 0;
array[1] = 1;
array[2] = 2;
array[3] = 3;
for (int i = 4; i < array.length; i++) {
int x1 = array[i - 2] - array[i - 3];
int x2 = array[i - 1] - array[i - 2];
array[i] = array[i - 1] + x1 + x2;//等于上一个值加上斐波那契数列
}
return array[target];
}
//第九题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public int JumpFloorII(int target) {
if (target == 0) {
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
int[] array = new int[target + 1];
array[0] = 0;
array[1] = 1;
array[2] = 2;
array[3] = 4;
for (int i = 4; i < array.length; i++) {
array[i] = array[i - 1] + (int) Math.pow(2, i - 2); //等于上一个值加上2的i-2次方
}
return array[target];
}
//第10题：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
//实际上是解一个斐波那契数列的修改版，需要通过分析可得
public int RectCover(int target) {
int[] F = new int[target + 1];
if (target == 0) {
return 0;
}
if (target == 1) {
return 1;
}
F[0] = 0;
F[1] = 1;
F[2] = 2;
for (int i = 3; i < F.length; i++) {
F[i] = F[i - 1] + F[i - 2];
}
return F[target];
}
//第11题：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
//解题思路：将10进制转换为二进制
//补码=反+1;
//此处可以用到：补码+原码=int型的2的32次方，因为int型占4个字节，一个字节8位，也就是占32位，故补码加原码的和为2的32次方
public int NumberOf1(int n) {
StringBuilder sb = new StringBuilder();
long nn = 0;
//求正数的原码
if (n < 0) {//针对负数，求其原码的补码，其补码=原码的反码+1
nn = (long) Math.pow(2, 32) + n;
} else {
nn = n;
}
while (nn > 0) {
if (nn % 2 == 1) {
nn = nn / 2;
sb.append(1);
} else {
nn = nn / 2;
sb.append(0);
}
}
int num = 0;
String[] ss = sb.toString().split("");
StringBuilder sb1 = new StringBuilder();
for (int i = ss.length - 1; i >= 0; i--) {
sb1.append(ss[i]);
if (ss[i].equals("1")) {
num++;
}
}
return num;
}
//第12题：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
public double Power(double base, int exponent) {
double ss = Math.pow(base, exponent);
return ss;
}
//第13题：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
// 所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public void reOrderArray(int[] array) {
int[] flag = new int[array.length];
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 0) {//表示偶数
flag[i] = 1;
} else {//表示基数
flag[i] = 0;
}
}
int[] array_new = new int[array.length];
int k = 0;
for (int i = 0; i < array.length; i++) {
if (flag[i] == 0) {
array_new[k] = array[i];
k++;
}
}
for (int i = 0; i < array.length; i++) {
if (flag[i] == 1) {
array_new[k] = array[i];
k++;
}
}
for (int i = 0; i < array_new.length; i++) {
array[i] = array_new[i];
}
}
//第14题：输入一个链表，输出该链表中倒数第k个结点。
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null) {
return null;
}
int sum = 1;
ListNode l = head;
while (head.next != null) {
head = head.next;
sum = sum + 1;
}//得到最后一个节点，跳出循环时，head属于最后一个节点,sum表示有多少个节点
if (sum < k) {
return null;
}
for (int i = 1; i < sum - k + 1; i++) { //循环到第sum-k个节点，我们需要返回的是sum-k+1个节点，故执行下列语句可以得到
l = l.next;
}
return l;
}
//第15题：输入一个链表，反转链表后，输出链表的所有元素。
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode ln = head;
int sum = 1;
while (head.next != null) {
head = head.next;
sum++;
}//得到链表的最后一个节点
int[] sb = new int[sum];
//将节点中的值存储在一个数组中
for (int i = 0; i < sum; i++) {
sb[i] = ln.val;
ln = ln.next;
}
//将数组中的值逆向赋值给一个新的链表
ListNode no = new ListNode(sb[sb.length - 1]);
if (sb.length == 1) {
return no;
}
ListNode sk = no;//当后文no的节点被赋予值的时候，sk节点的后文也被赋予值，只不过指向的是首节点
for (int i = sb.length - 2; i >= 0; i--) {
no.next = new ListNode(sb[i]);
no = no.next;
}
no.next = null;//此处no指向的是尾节点
return sk;
}
//第16题：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head;
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
head = list1;
head.next = Merge(list1.next, list2);
} else {
head = list2;
head.next = Merge(list1, list2.next);
}
return head;
}
public static void main(String[] args) {
ListNode no = new ListNode(1);
ListNode p = no;
for (int i =2;i<12;i++){
System.out.println(p.val);
ListNode next = new ListNode(i);
p.next = next;
p = p.next;
}
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}