题目来源：剑指offer（牛客网），可在牛客网进行练习：https://www.nowcoder.com/ta/coding-interviews

Leetcode最近也出了，个人还是比较喜欢在这个上面刷题 https://leetcode-cn.com/problemset/lcof/

题目的顺序和牛客网保持一致，题目描述和代码部分以Leetcode为准，每题都会列出对应的链接地址

主要是每次去翻感觉很麻烦，就自己开个帖子总结一下，方便自己回头看。

还没有写完，暂时先把代码列出来，慢慢写思路......

第一题：二维数组中的查找

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

这个题没什么难度，自己把递增的顺序写出来就明白了，应该从左下角(or右上角)开始查找

public boolean Find(int target, int [][] array) {
//二维数组的判空
if (array == null || array.length == 0 || array[0].length == 0) return false;
int rows = array.length; //数组的行
int cols = array[0].length; //数组的列
int row = rows - 1;
int col = 0;
//从最后一行的第一列开始查找
while(row >= 0 && row < rows && col >= 0 && col < cols) {
if (array[row][col] == target) return true;
else if (array[row][col] > target) row --;
else col ++;
}
return false;
}

第二题：替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

这个直接使用String的API就好

 public String replaceSpace(String s) {
return s.replace(" ", "%20");
}

第三题：从尾到头打印链表

题目描述：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

从尾到头的问题，首先要想到用 栈 这个数据结构来实现

public int[] reversePrint(ListNode head) {
Stack stack = new Stack();
while(head != null) {
stack.push(head.val);
head = head.next;
}
int len = stack.size();
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) stack.pop();
}
return arr;
}

 第四题：重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

第五题：用两个栈实现队列

题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

主要考虑出队列的操作，需要把第一个栈中出栈顺序加入第二个栈中。

class CQueue {
Stack stack1;
Stack stack2;
public CQueue() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(stack2.isEmpty()) {
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return (Integer)stack2.pop();
}
}

第六题：旋转数组的最小数字

题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

最简单的方法是直接遍历一遍找出左边比右边小的数字，但是有序数组中的查找最好都用 二分法 来实现

public int minArray(int[] numbers) {
if (numbers.length == 0) return 0;
int left = 0, right = numbers.length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else if (numbers[mid] < numbers[right]) {
right = mid;
} else {
right --;
}
}
return numbers[left];
}

第七题：斐波那契数列

题目描述：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。

链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

斐波那契没什么好说的，递推or递归 都可以实现

public int fib(int n) {
if(n <= 1) return n;
int f1 = 0, f2 = 1, f3 = 0;
for (int i = 1; i < n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3 % 1000000007;
}
return f2;
}

 第八题：跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

链接：https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

//可以看做每次从i-1层跳一次到i层
public int JumpFloor(int target) {
if(target == 1) return 1;
if(target == 2) return 2;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}

第九题：变态跳台阶

题目描述：一只青蛙一次可以跳上1级台阶,也可以跳上2级...它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

链接：https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

易知 f(n)=f(n-1)+f(n-2)+……f(1)   f(n-1)=f(n-2)+……f(1)   两式相减得f(n)=2f(n-1)

public int JumpFloorII(int target) {
if (target <= 2) return target;
int a = 2, b = 0;
for (int i = 3; i <= target; i++) {
b = 2 * a;
//递推公式推出来
a = b;
}
return a;
}

 第十题：矩形覆盖

题目描述：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

链接：https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6

public int RectCover(int target) {
if (target <= 2) return target;
return RectCover(target - 1) + RectCover(target - 2);
}

第十一题：二进制中1的个数

题目描述：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

用&来判断末尾是不是1，需要注意int32位但是首位是符号位

public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
/*if ((n & 1) == 1) {
count += 1;
}*/
count += n & 1; // 与末尾的数值一样
n = n >>> 1;
}
return count;
}

第十二题：数值的整数次方

题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

public class Solution {
public double Power(double base, int exponent) {
if (base == 0)
return 0;
int temp = 0;
double res = 1;
if (exponent > 0) {
temp = exponent;
} else if (exponent < 0) {
temp = -exponent;
} else {
return 1;
//指数为0
}
while (temp != 0) {
if ((exponent & 1) == 1) {
res *= base;
}
base *= base;
temp >>= 1;
}
return exponent>0 ? res : 1/res;
}
}

第十三题：调整数组顺序使奇数位于偶数前面

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

链接：https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593

如果不考虑相对位置，直接就用双指针交换就行了，现在是遍历一遍，遇到奇偶交换使用冒泡的思想去做

public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0)
return;
int i = 0, j;
while (i < array.length) {
while (i < array.length && !isEven(array[i]))
i++;
j = i + 1;
while (j < array.length && isEven(array[j]))
j++;
if (j < array.length) {
int tmp = array[j];
for (int j2 = j - 1; j2 >= i; j2--) {
//冒泡排序
array[j2 + 1] = array[j2];
}
array[i++] = tmp;
} else {// 查找失敗
break;
}
}
}
boolean isEven(int n) {
//偶数true
if (n % 2 == 0)
return true;
return false;
}
}

第十四题：链表中倒数第k个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

/*
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 (k < 1 || head == null) {
return null;
}
ListNode cur = head;
//走K-1步正好有K个节点
for (int i = 0; i < k-1; i++) {
if (cur.next != null)
cur = cur.next;
else
return null;
}
while (cur.next != null) {
head = head.next;
cur = cur.next;
}
return head;
}
}

第十五题：反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。

/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}

第十六题：合并两个排序的链表

题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
cur = cur.next;
list1 = list1.next;
} else {
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if (list1 == null) {
cur.next = list2;
}
if (list2 == null) {
cur.next = list1;
}
return head.next;
}
}

第十七题：树的子结构

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
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 (root1 == null || root2 == null) return false;
return isSameTree(root1, root2) ||
HasSubtree(root1.left, root2) ||
HasSubtree(root1.right, root2);
}
private boolean isSameTree(TreeNode root1,TreeNode root2) {
if (root2 == null) return true;
if (root1 == null) return false;
if (root2.val == root1.val) {
return isSameTree(root1.left,root2.left) && isSameTree(root1.right,root2.right);
} else {
return false;
}
}
}

第十八题：二叉树的镜像

题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if (root != null) {
TreeNode tree = root.left;
root.left = root.right;
root.right = tree;
Mirror(root.left);
Mirror(root.right);
}
}
}

第十九题：顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

第二十题：包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

public class Solution {
Stack<Integer> dataStack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
public void push(int node) {
dataStack.push(node);
if (minStack.isEmpty() || node <= minStack.peek()){
minStack.push(node);
}
}
public void pop() {
if (dataStack.peek() == minStack.peek()) {
minStack.pop();
}
dataStack.pop();
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
}

第二十一题：栈的压入、弹出序列

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (stack.size() > 0 && stack.peek() == popA[j]) {
stack.pop();
j ++;
}
}
return stack.size() == 0;
}
}

第二十二题：从上往下打印二叉树

题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
while (!queue.isEmpty()) {
TreeNode t = queue.remove();
list.add(t.val);
if (t.left!=null)
queue.add(t.left);
if (t.right!=null)
queue.add(t.right);
}
}
return list;
}
}

第二十三题：二叉搜索树的后序遍历序列

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0 || sequence == null) return false;
return judge(sequence,0,sequence.length-1);
}
private boolean judge(int[] seq,int left,int right) {
if (left >= right) return true;
//空树或叶子节点
int i = right;
while (i > left && seq[i-1] > seq[right])
//i是右子树的开始节点
i --;
for (int j = i-1; j >= left; j--) {
if (seq[j] > seq[right])
return false;
}
return judge(seq,left,i-1) && judge(seq,i,right-1);
}
}

第二十四题：二叉树中和为某一值的路径

题目描述：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

public class Solution {
private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root == null)
return result;
list.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null)
result.add(new ArrayList<>(list));
FindPath(root.left,target);
FindPath(root.right,target);
list.remove(list.size()-1);
return result;
}
}

第二十五题：复杂链表的复制

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

第二十六题：二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null)
return null;
Stack<TreeNode> stack = new Stack<>();
TreeNode root = pRootOfTree;
TreeNode pre = null;
boolean isFirst = true;
while (root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (isFirst) {
pRootOfTree = root; //中序遍历的第一个节点赋值
pre = root;
isFirst = false;
} else {
pre.right = root;
root.left = pre;
pre = root;
}
root = root.right;
}
return pRootOfTree;
}
}

第二十七题：字符串的排列

题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if (str != null && str.length() != 0) {
char[] chars = str.toCharArray();
ss (chars,0,list);
}
Collections.sort(list);
return list;
}
private void ss(char[] chars, int i, ArrayList<String> list) {
for (int j = 0; j < chars.length; j++) {
if (i == chars.length-1) {
String str = String.valueOf(chars);
if (!list.contains(str)) {
list.add(str);
}
} else {
swap(chars,i,j);
ss(chars,i+1,list);
swap(chars,i,j);
}
}
}
public void swap (char[] chars, int a, int b) {
char temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
}
}

第二十八题：数组中出现次数超过一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int count = 1;
int num = array[0];
for (int i = 0; i < array.length; i++) {
if (count == 0) {
count = 1;
num = array[i];
} else {
if (num == array[i]) {
count ++;
} else {
count --;
}
}
}
count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == num) {
count ++;
}
}
if (count*2 <= array.length) {
return 0;
}
return num;
}
}

第二十九题：最小的K个数

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input==null||input.length==0||input.length<k||k<=0) {
return res;
}
int i = 0, j = input.length-1;
int index = partition(i,j,input);
while (index != k-1) {
if (index < k-1) {
i = index+1;
} else {
j = index-1;
}
index = partition(i,j,input);
}
for (int l = 0; l < k; l++) {
res.add(input[l]);
}
return res;
}
public int partition (int left, int right, int[] a) {
int temp = a[left];
int i = left, j = right + 1;
while (true) {
while (++i <= right && a[i] < temp);
while (--j >= left && a[j] > temp);
if (i >= j) break;
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
a[left] = a[j];
a[j] = temp;
return j;
}
}

第三十题：连续子数组的最大和

题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int ans = array[0];
int sum = 0;
for (int i = 0; i < array.length; i++) {
if (sum > 0) {
sum += array[i];
} else {
sum = array[i];
}
ans = Math.max(ans,sum);
}
return ans;
}
}

31-40题：

41-50题：

51-60题：

61-66题： 

最后

以上就是成就花卷为你收集整理的java版剑指offer（更新中）31-40题：41-50题：51-60题：61-66题： 的全部内容，希望文章能够帮你解决java版剑指offer（更新中）31-40题：41-50题：51-60题：61-66题： 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。