剑指Offer（一）

文章目录

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

剑指 Offer 03. 数组中重复的数字

	/*
	 * 1. 哈希
	 * 执行用时：7 ms, 在所有 Java 提交中击败了32.74%的用户
	 * 内存消耗：50 MB, 在所有 Java 提交中击败了30.56%的用户
	 */
	public int findRepeatNumber(int[] nums) {
		Set<Integer> set = new HashSet<>();
		for(int i:nums) {
			if(set.contains(i)) return i;
			set.add(i);
		}
		return -1;	
	}
	
	/*
	 * 2. 优化哈希，只用add，不用contains，提速
	 * 执行用时：4 ms, 在所有 Java 提交中击败了58.17%的用户
	 * 内存消耗：51.1 MB, 在所有 Java 提交中击败了9.12%的用户
	 */
	public int findRepeatNumber2(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;	
    }

剑指 Offer 04. 二维数组中的查找

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

	/*
	 * 1.初始判断m和n注意，m为0的话n不存在
	 * 2.依赖自己行进行判断，别依赖下一行，下一行不一定有
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：46.9 MB, 在所有 Java 提交中击败了84.53%的用户
	 */
	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<m; 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<n; j++){
					if(matrix[i][j] == target) return true;
				}
			}
		}		
		return false;
	}

剑指 Offer 05. 替换空格

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

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

剑指 Offer 06. 从尾到头打印链表

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

	/*
	 * 1.deque双端队列
	 * 2.栈
	 * 3.初始化一个数组，倒着放
	 */
	public int[] reversePrint(ListNode head) {
		Deque<Integer> 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<len; i++){
			res[i] = deque.pollFirst();
		}
		return res;
	}

剑指 Offer 07. 重建二叉树

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);
    }	
	/**
	 * 
	 * @param inorder 前序数组
	 * @param inl 当前处理的前序数组段的起始位置
	 * @param inr 当前处理的前序数组段的末尾位置
	 * @param postorder 中序数组
	 * @param postl 当前处理的中序数组段的起始位置
	 * @param postr 当前处理的中序数组段的末尾位置
	 */
	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;
	}

剑指 Offer 09. 用两个栈实现队列

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

	/*
	 * 2. 优化
	 * 负责出的那个栈为空的时候，才从入栈倒进去
	 * 执行用时：56 ms, 在所有 Java 提交中击败了50.77%的用户
	 * 内存消耗：48.1 MB, 在所有 Java 提交中击败了62.75%的用户
	 */	
	class CQueue1 {
	    //两个栈，一个出栈，一个入栈
	    private Stack<Integer> stack1;
	    private Stack<Integer> 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();
	        }
	    }
	}
	/*
	 * 1.每次删除所有元素d出来再d回去
	 * 执行用时：1173 ms, 在所有 Java 提交中击败了5.03%的用户
	 * 内存消耗：48 MB, 在所有 Java 提交中击败了71.78%的用户
	 */
	class CQueue {
		Stack<Integer> s1 = new Stack<Integer>();
	    Stack<Integer> s2 = new Stack<Integer>();
	    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;
	    }
	}