剑指offer刷题笔记（一）
面试题03找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，
也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
这个我的第一个思路就是建立一个简单的哈希表，建立一个新的长度为n的数组，扫描传入数组时，将每一个第一次遇见的值放入到自建数组对应下标处，当第二次碰见时，此时自建数组下标处已有值，就代表重复，返回。
class Solution {
public int findRepeatNumber(int[] nums) {
int n=nums.length;
for(int i=0;i<n;i++){
if(nums[i]<0||nums[i]>(n-1)){
return ++n;
}
}
int[] num=new int[n];
for(int i=0;i<n;i++){
if(num[nums[i]]!=nums[i]){
num[nums[i]]=nums[i];
}
else{
return nums[i];
}
}
return ++n;
}
}
这种方式的时间复杂度是O(n),空间复杂度也是O(n)，但是有一个问题，就是数组初始化时的就是0，因此当扫描数组中有两个0时，逻辑就会出现问题，因此我加了一个状态码来判断
class Solution {
public int findRepeatNumber(int[] nums) {
int n=nums.length;
int state=0;
for(int i=0;i<n;i++){
if(nums[i]<0||nums[i]>(n-1)){
return ++n;
}
}
int[] num=new int[n];
for(int i=0;i<n;i++){
if(num[nums[i]]!=nums[i]||(state==0&&nums[i]==0)){
num[nums[i]]=nums[i];
if(nums[i]==0){
state=1;
}
}
else{
return nums[i];
}
}
return ++n;
}
}
这种方式已经通过审查，但空间复杂度还是太高。能不能有一种降低空间复杂度的方法？
我可不可以不建立一个辅助数组帮助存储，直接在传入数组内部进行交换，当遇到第二次交换时，边代表数字重复
class Solution {
public int findRepeatNumber(int[] nums) {
int t;
int b;
for(int i=0;i<nums.length;i++){
if(nums[i]!=i){
if(nums[nums[i]]!=nums[i]){
t=nums[nums[i]];
b=nums[i];
nums[i]=t;
nums[b]=b;
}
else{
return nums[i];
}
}
}
return -1;
}
}
面试题04
题目描述
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
解题思路：
我们可以先思考一下都有哪些方法，一是暴力搜索，这样的话时间复杂度是O(m*n),空间复杂度是O(1),但仔细观察一下这个数组，这个数组是有规律的，我们可以看到，右上角的数字是它所处这一行中最大的，这一列中最小的，所以我们可以将数字与它进行比较，比他小，能够排除一列，比他大，则能排除一行，这样子搜索，我们就可以将时间复杂度缩短到O(m+n)
同理，右上角的数字是行中最大，列中最小，那么左下角的元素就是列中最大，行中最小，也可以以它为根据，来进行筛选。
以下为代码
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix==null||matrix.length==0||matrix[0].length==0){
return false;
}
int rows=0;
int cols=matrix[0].length;
while(rows<matrix.length&&cols>0){
if(target==matrix[rows][cols-1]){
return true;
}
else if(target<matrix[rows][cols-1]){
cols--;
}
else if(target>matrix[rows][cols-1]){
rows++;
}
}
return false;
}
}
面试题06:从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
思路:倒序打印链表，我们可以考虑栈的特性，先入后出，我们可以将链表压入栈中，在从栈中弹出放入数组中，顺序打印数组，就是我们需要的倒序打印链表，这种方式的时间复杂度是O(n),相当于遍历了两遍数组，空间复杂度是O(n)，建立了两个辅助存储。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> list=new Stack<>();
ListNode test=head;
while(test!=null){
list.push(test);
test=test.next;
}
int count=list.size();
int[] l=new int[count];
for(int i=0;i<count;i++){
l[i]=list.pop().val;
}
return l;
}
}
面试题07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解题思路：前序遍历的遍历顺序是从根节点->左节点->右节点，依次遍历下来，所以我们可以看到前序遍历的的一个节点就是根节点，而中序遍历则是从左节点->根节点->右节点，我们能从前序遍历中得到根节点，而在中序遍历中根节点的左侧就是左子树的节点，右侧是右子树的节点，递归调用，就可以取得左子树的根节点和右子树的根节点，以此类推，从而重构二叉树。
以下为代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||preorder.length==0){
return null;
}
Map<Integer,Integer> order=new HashMap<Integer,Integer>();
for(int i=0;i<inorder.length;i++){
order.put(inorder[i],i);
}
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1,order);
}
public TreeNode build(int[] preorder,int preStart,int preEnd,int[] order,int orderStart,int orderEnd,Map<Integer,Integer> ordermap){
if(preStart>preEnd){
return null;
}
TreeNode root=new TreeNode();
root.val=preorder[preStart];
if(preStart==preEnd){
return root;
}
else{
int i=ordermap.get(root.val);
int leftlength=i-orderStart;
int rightlength=orderEnd-i;
TreeNode left=build(preorder,preStart+1,preStart+leftlength,order,orderStart,i-1,ordermap);
TreeNode right=build(preorder,preStart+leftlength+1,preEnd,order,i+1,orderEnd,ordermap);
root.left=left;
root.right=right;
return root;
}
}
}
面试题09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
限制
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
解题思路：队是一种先进先出的数据结构，而栈则是先进后出，我们可以先将数据压入栈A中，而当做删除操作时，则将栈A中所有数据弹出，压入到栈B中，此时栈中元素顺序就做了一个反转，以数据为例，A,B,C依次压入栈A中，弹出顺序，C,B,A,因此压入栈B中的顺序就是C,B,A,此时再将栈B弹出，则弹出顺序又回到了A,B,C，与压入A中顺序相同，这时就做到了两个栈模拟一个队列的功能
class CQueue {
Stack<Integer> a=new Stack<Integer>();
Stack<Integer> b=new Stack<Integer>();
public CQueue() {
}
public void appendTail(int value) {
a.push(value);
}
public int deleteHead() {
if(a.size()==0&&b.size()==0){
return -1;
}
if(b.size()==0){
int c=a.size();
for(int i=0;i<c;i++){
b.push(a.pop());
}
}
return b.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
