剑指Offer（一）

• • 剑指 Offer 03. 数组中重复的数字
  • 剑指 Offer 04. 二维数组中的查找
  • 剑指 Offer 05. 替换空格
  • 剑指 Offer 06. 从尾到头打印链表
  • 剑指 Offer 07. 重建二叉树
  • 剑指 Offer 09. 用两个栈实现队列

	
	public int findRepeatNumber(int[] nums) {
		Set set = new HashSet<>();
		for(int i:nums) {
			if(set.contains(i)) return i;
			set.add(i);
		}
		return -1;	
	}
	
	
	public int findRepeatNumber2(int[] nums) {
        Set set = new HashSet();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;	
    }

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

	
	public boolean findNumberIn2DArray(int[][] matrix, int target) {		
		int m = matrix.length;		
		if(m == 0) return false;
		int n = matrix[0].length;
		if(n == 0 || matrix[0][0] > target) return false;
		
		for(int i=0; i//按行遍历
			//System.out.println("matrix[0][n-1] = " + matrix[0][n-1]);
			//System.out.println("target = " + target);
			if(matrix[i][n-1] >= target){//这一行可以
				//System.out.println("ok");
				for(int j=0; j
					if(matrix[i][j] == target) return true;
				}
			}
		}		
		return false;
	}

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
一遍过

	public String replaceSpace(String s) {
        StringBuffer sb = new StringBuffer();
		for(int i=0; i
			if(s.charAt(i) == ' '){
				sb.append('%');
				sb.append('2');
				sb.append('0');
			}else{
				sb.append(s.charAt(i));
			}
		}
		return sb.toString();
    }

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
注意deuqe的长度在pop之后是会变化的，不能将其size作为for的结束条件

	
	public int[] reversePrint(ListNode head) {
		Deque deque = new LinkedList<>();
		while(head != null){
			deque.offerFirst(head.val);
			head = head.next;
		}
		//System.out.println(deque.toString());
		int len = deque.size();
		int[] res = new int[len];
		for(int i=0; i
			res[i] = deque.pollFirst();
		}
		return res;
	}

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

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		int prelen = preorder.length;
		int inlen = inorder.length;
		return builder(preorder, 0, prelen-1, inorder, 0, inlen-1);
    }	
	
	public TreeNode builder(int[] preorder, int prel, int prer, 
			int[] inorder, int inl, int inr) {
		//1. 空的返回null
		if(inl > inr || prel > prer) return null;
		//System.out.println(prel);
		//System.out.print("中序排列为：");show(inorder, inl, inr);System.out.print("; ");
		//System.out.print("前序排列为：");show(preorder, prel, prer);System.out.print("n");
		//2. 只有一个值，返回他本身
		if(inl == inr) return new TreeNode(inorder[inl]);
		//3. 如果不只一个，前序第一个是root
		TreeNode root = new TreeNode(preorder[prel]);//不是0！！是preleft!!
		//4. 找到root.val在中序中的位置（以左右子树结点个数分割前序）
		int idx = 0;
		for(int i=inl; i<=inr; i++) {
			if(inorder[i] == root.val) {
				idx = i;
				break;
			}
		}
		//5. 递归左子树：
		//   前序起始位置变为prel+1，前序末尾位置变为（前序起始位置+前序个数-1）
		//   中序起始位置不变，中序末尾位置变为rootindex-1
		//   前序当前序列个数  = idx - inl 
		root.left = builder(preorder, prel+1, prel+idx-inl,
				inorder, inl, idx-1);
		//6. 递归右子树：
		//   前序起始位置变为，前序起始位置变为（前序起始位置+前序个数），前序末尾位置不变prer
		//   中序起始位置rootindex+1, 中序末尾位置不变
		//   前序当前序列个数  = rootindex - inl 
		root.right = builder(preorder, prel+idx-inl+1, prer,
				inorder, idx+1, inr);
		//7. 返回root
		return root;
	}

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

		
	class CQueue1 {
	    //两个栈，一个出栈，一个入栈
	    private Stack stack1;
	    private Stack stack2;
	    
	    public CQueue1() {
	        stack1 = new Stack<>();
	        stack2 = new Stack<>();
	    }
	    
	    public void appendTail(int value) {
	        stack1.push(value);
	    }
	    
	    public int deleteHead() {
	        if(!stack2.isEmpty()){
	            return stack2.pop();
	        }else{
	            while(!stack1.isEmpty()){
	                stack2.push(stack1.pop());
	            }
	            return stack2.isEmpty() ? -1 : stack2.pop();
	        }
	    }
	}
	
	class CQueue {
		Stack s1 = new Stack();
	    Stack s2 = new Stack();
	    public CQueue() {
	    	
	    }
	    
	    public void appendTail(int value) {
	    	s1.add(value);
	    }
	    
	    public int deleteHead() {
	    	int ans = -1;
	    	if(s1.size() == 0){
	    		return ans;
	    	}else{
	    		while(s1.size() != 0) s2.push(s1.pop());
	    		ans = s2.pop();
	    		while(s2.size() != 0) s1.push(s2.pop());
	    	}
	    	return ans;
	    }
	}