牛客网 - 剑指Offer（上）
2018-04-09 本文已影响99人
JYGod丶
1. 二维数组中的查找
时间限制：1秒 空间限制：32768K
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
public class Solution {
public boolean Find(int target, int [][] array) {
int rowSize = array.length;
int colSize = array[0].length;
if (rowSize == 0 || colSize == 0) {
return false;
}
for (int i = 0; i < rowSize; i++) {
int first = array[i][0];
int last = array[i][colSize - 1];
if (target == first || target == last) {
return true;
} else if (target > first && target < last) { //二分查找
int head = 1;
int tail = colSize - 2;
while (head <= tail) {
if (array[i][head] == target || array[i][tail] == target) {
return true;
}
int mid = (head + tail) / 2;
if (array[i][mid] < target) {
head = mid + 1;
tail --;
} else if (array[i][mid] > target) {
tail = mid - 1;
head ++;
} else {
return true;
}
}
} else {
continue;
}
}
return false;
}
}
运行时间：310ms
占用内存：19992k
2. 替换空格
时间限制：1秒 空间限制：32768
题目描述
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuilder builder = new StringBuilder();
char mChar;
for (int i = 0; i < str.length(); i++) {
mChar = str.charAt(i);
if (str.charAt(i) == ' ') {
builder.append("%20");
} else {
builder.append(mChar);
}
}
return builder.toString();
}
}
运行时间：24ms
占用内存：22744k
3. 从尾到头打印表单
时间限制：1秒 空间限制：32768K
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<Integer> listRes = new ArrayList<Integer>();
if (listNode == null) {
return list;
}
while (listNode != null) {
list.add(listNode.val);
listNode = listNode.next;
}
int size = list.size();
for (int i = 0; i < size; i++) {
listRes.add(list.get(size - i - 1));
}
return listRes;
}
}
运行时间：14ms
占用内存：8280k
4. 重建二叉树
时间限制：1秒 空间限制：32768K
思路： 针对每一个节点，先根据提供的线索找到左右孩子结点、以及左右孩子节点的左孩子先序、中序数组和右孩子数组，然后就形成了一个子问题的递归求解。
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
import java.util.Arrays;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root = null;
if (pre.length == 0) {
return root;
}
root = new TreeNode(pre[0]);
return createTree(pre, in, root);
}
public TreeNode createTree(int [] pre, int [] in, TreeNode root) {
int len = pre.length;
if (len == 0 || root == null) {
return root;
}
int index = -1;
for (int i = 0; i < len; i ++) {
if (in[i] == root.val) {
index = i;
break;
}
}
int[] inLeft = new int[index];
int[] preLeft = new int[index];
int[] inRight = new int[len - index - 1];
int[] preRight = new int[len - index - 1];
for (int i = 0; i < len; i++) {
if (i < index) {
inLeft[i] = in[i];
} else if(i > index){
inRight[i - index - 1] = in[i];
}
if (i == 0) {
continue;
}
if (i <= index) {
preLeft[i - 1] = pre[i];
} else {
preRight[i - index - 1] = pre[i];
}
}
TreeNode leftChild = null;
TreeNode rightChild = null;
if (index > 0) {
leftChild = new TreeNode(pre[1]);
}
if (index < len - 1) {
rightChild = new TreeNode(pre[index + 1]);
}
root.left = leftChild;
root.right = rightChild;
createTree(preLeft, inLeft, leftChild);
createTree(preRight, inRight, rightChild);
return root;
}
}
5. 用两个栈实现队列
时间限制：1秒 空间限制：32768K
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (!stack2.empty()) {
return stack2.pop();
} else {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}
运行时间：12ms
占用内存：8396k
6. 旋转数组的最小数字
时间限制：3秒 空间限制：32768K
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public class Solution {
public int minNumberInRotateArray(int [] array) {
int size = array.length;
if (size == 0) {
return 0;
}
int last = 0;
for (int i = 0; i < size; i++) {
if (array[i] < last) {
return array[i];
}
last = array[i];
}
return array[0];
}
}
运行时间：344ms
占用内存：27852k
7. 斐波那契数列
时间限制：1秒 空间限制：32768K
问题描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
} else if ( n == 1 || n == 2) {
return 1;
} else {
return getFib(n, 1, 1);
}
}
public int getFib(int n, int p1, int p2) {
if (n == 3) {
return p1 + p2;
} else {
return getFib(n - 1, p2, p1 + p2);
}
}
}
运行时间：11ms
占用内存：8304k
8. 跳台阶
时间限制：1秒 空间限制：32768K
问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloor(int target) {
if (target == 0) {
return 0;
} else if (target == 1) {
return 1;
} else if (target == 2) {
return 2;
} else {
return getFib(target, 1, 2);
}
}
public int getFib(int n, int p1, int p2) {
if (n == 3) {
return p1 + p2;
} else {
return getFib(n - 1, p2, p1 + p2);
}
}
}
运行时间：20ms
占用内存：15256k
9. 变态跳台阶
时间限制：1秒 空间限制：32768K
问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloorII(int target) {
int res = 0;
if (target == 0 || target == 1) {
return 1;
}
for (int i = 0; i < target; i++) {
res += JumpFloorII(i);
}
return res;
}
}
运行时间：27ms
占用内存：8792k
10. 矩阵覆盖
时间限制：1秒 空间限制：32768K
问题描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
public class Solution {
public int RectCover(int target) {
if (target > 2) {
return RectCover(target - 1) + RectCover(target - 2);
} else if (target == 2) {
return 2;
} else if (target == 1) {
return 1;
}
return 0;
}
}
11. 二进制中1的个数
时间限制：1秒 空间限制：32768K
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
public class Solution {
public int NumberOf1(int n) {
String binaryStr = Integer.toBinaryString(n);
int count = 0;
int len = binaryStr.length();
for (int i = 0; i < len; i++) {
if (binaryStr.charAt(i) == '1') {
count++;
}
}
return count;
}
}
12. 数值的整数次方
时间限制：1秒 空间限制：32768K
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base, Double.parseDouble(String.valueOf(exponent)));
}
}
13. 调整数组顺序使奇数位于偶数前面
时间限制：1秒 空间限制：32768K
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
/**
* System.arraycopy(arr1, n, arr2, m, p)
* 参数说明:
* arr1: 原数组
* n: 从原数组的第n位开始复制
* arr2: 目标数组
* m: 从目标数组第n位开始接受复制
* p: arr1 需要被复制的长度
*/
public class Solution {
public void reOrderArray(int [] array) {
int oddSize = 0;
int evenSize = 0;
int len = array.length;
for (int i = 0; i < len; i++) {
if (array[i] % 2 == 1) {
oddSize++;
}
}
evenSize = len - oddSize;
int[] oddArr = new int[oddSize];
int[] evenArr = new int[evenSize];
int oddIndex = 0;
int evenIndex = 0;
for (int i = 0; i < len; i++) {
if (array[i] % 2 == 1) {
oddArr[oddIndex] = array[i];
oddIndex++;
} else {
evenArr[evenIndex] = array[i];
evenIndex++;
}
}
System.arraycopy(oddArr, 0, array, 0, oddSize);
System.arraycopy(evenArr, 0, array, oddSize, evenSize);
}
}
14. 链表中倒数第k个节点
时间限制：1秒 空间限制：32768K
题目描述
输入一个链表，输出该链表中倒数第k个结点。
import java.util.Stack;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
Stack<ListNode> stack = new Stack<ListNode>();
int size = 0;
while (head != null) {
stack.push(head);
head = head.next;
size++;
}
if (size < k) {
return null;
}
for (int i = 0; i < k; i++) {
head = stack.pop();
}
return head;
}
}
15. 反转链表
时间限制：1秒 空间限制：32768K
题目描述
输入一个链表，反转链表后，输出链表的所有元素。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode temp = null;
while (cur != null) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
16. 合并两个排序的链表
时间限制：1秒 空间限制：32768K
思路: 同时比较两个链表的表头，将较小的那个扔进队列，知道其中一个链表为空。
import java.util.LinkedList;
import java.util.Queue;
/*
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 resNode = null;
ListNode head = null;
if (list1 == null && list2 == null) {
return null;
} else if (list1 == null && list2 != null) {
return list2;
} else if (list1 != null && list2 == null) {
return list1;
} else {
Queue<Integer> valQueue = new LinkedList<Integer>();
while(list1 != null && list2 != null) {
int val1 = list1.val;
int val2 = list2.val;
if (val1 < val2) {
valQueue.offer(val1);
list1 = list1.next;
} else {
valQueue.offer(val2);
list2 = list2.next;
}
}
int pollVal = valQueue.poll();
resNode = new ListNode(pollVal);
head = resNode;
while(valQueue.size() > 0 && (pollVal = valQueue.poll()) != -1) {
ListNode nodeTemp = new ListNode(pollVal);
resNode.next = nodeTemp;
resNode = resNode.next;
}
if (list1 != null) {
resNode.next = list1;
} else {
resNode.next = list2;
}
}
return head;
}
}
17. 树的子结构
时间限制：1秒 空间限制：32768K
题目描述
输入两棵二叉树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 (root2 == null || root1 == null) {
return false;
}
StringBuilder builder1 = new StringBuilder();
StringBuilder builder2 = new StringBuilder();
builder1 = saveInfo(builder1, root1);
builder2 = saveInfo(builder2, root2);
if (builder1.toString().contains(builder2.toString())) {
return true;
}
return false;
}
public StringBuilder saveInfo(StringBuilder builder, TreeNode node) {
builder.append(node.val);
if (node.left == null && node.right == null) {
return builder;
}
if (node.left != null) {
builder = saveInfo(builder, node.left);
}
if (node.right != null) {
builder = saveInfo(builder, node.right);
}
return builder;
}
}
18. 二叉树的镜像
时间限制：1秒 空间限制：32768K
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
/**
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) {
return;
} else {
TreeNode temp = null;
temp = root.left;
root.left = root.right;
root.right = temp;
}
if (root.left != null) {
Mirror(root.left);
}
if (root.right != null) {
Mirror(root.right);
}
}
}
19. 顺时针打印矩阵
时间限制：1秒 空间限制：32768K
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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.
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (matrix.length == 0) {
return result;
}
roundTraverse(0, 0, matrix.length - 1, matrix[0].length - 1, result, matrix);
return result;
}
public void roundTraverse(int rowStart, int colStart, int rowEnd,
int colEnd, ArrayList<Integer> list, int [][] matrix) {
if (rowStart > rowEnd || colStart > colEnd) {
return;
} else {
for (int i = colStart; i <= colEnd; i++) {
list.add(matrix[rowStart][i]);
}
for (int i = rowStart + 1; i <= rowEnd; i++) {
list.add(matrix[i][colEnd]);
}
if (rowStart != rowEnd) {
for (int i = colEnd - 1; i >= colStart; i--) {
list.add(matrix[rowEnd][i]);
}
}
if (colStart != colEnd) {
for (int i = rowEnd - 1; i > rowStart; i--) {
list.add(matrix[i][colStart]);
}
}
roundTraverse(rowStart + 1, colStart + 1, rowEnd - 1, colEnd - 1, list, matrix);
}
}
}
20. 包含min函数的栈
？？？ 这道题抽风了？
21. 栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int index = 0;
int popIndex = 0;
int size = pushA.length;
for(int i = 0; i < size; i++) {
if (index > size - 1) {
break;
}
for (int j = index; j < size; j++) {
index++;
if (pushA[j] != popA[i]) {
if (j == size - 1) {
return false;
}
stack.push(pushA[j]);
} else {
break;
}
}
popIndex = i + 1;
}
if (popIndex == size) {
return true;
} else {
while (!stack.isEmpty()) {
if (stack.pop() != popA[popIndex]) {
return false;
} else {
popIndex++;
}
}
}
return true;
}
}
22. 从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
TreeNode leftChild = node.left;
TreeNode rightChild = node.right;
if (leftChild != null) {
queue.offer(leftChild);
}
if (rightChild != null) {
queue.offer(rightChild);
}
}
return list;
}
}
