Silhouettes

vivo2021提前批笔试题

2020-06-07

全是leetcode原题
1.605.种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花）返回在不打破种植规则的情况下能种入花的最大值。

1	0	0	0	0	0	1	0	1	0	0	0	0	1	0	0	0

关键思路：能种花的位置的前中后三个位置一定是0，否则就不能种花！！
代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int res = 0;
        for(int i=0; i<flowerbed.length; i++){
            if( flowerbed[i] == 0 && ((i-1<0) || flowerbed[i-1] == 0) && ((i+1>=flowerbed.length) || flowerbed[i+1]==0)){
                flowerbed[i] = 1;
                res++;
            }
        }
        return res;
    }
}

2.887.鸡蛋掉落
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

这题理解起来都费劲，之前见过，可是没记下来咋做的。

复杂链表的复制

2020-05-31

剑指offer

题目
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

1.HashMap

用HashMap<RandomListNode, RandomListNode>来保存原有的节点和新建节点的对应关系。再遍历一遍原链表，利用map找出对应的random节点，更新新链表的random值。

代码

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null) return null;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = pHead;
        map.put(null, null);
        
        while(p != null){
            RandomListNode temp = new RandomListNode(p.label);
            map.put(p, temp);
            p = p.next;
        }
        p = pHead;
        while(p != null){
            RandomListNode cur = map.get(p);
            RandomListNode next = map.get(p.next);
            RandomListNode random = map.get(p.random);
            cur.next = next;
            cur.random = random;
            p = p.next;
        }
        return map.get(pHead);
    }
}

2.构造法

思路
分3步：
1.复制节点
2.添加random指向
3.拆分链表
在原有链表的每个节点后面构造label相等的新的节点，再遍历一遍链表，查询原节点的random指向，更新新节点的random, 最后拆分该链表。

代码

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null) return null;
        RandomListNode p = pHead;
        while(p != null){
            RandomListNode temp = new RandomListNode(p.label);
            RandomListNode pNext = p.next;
            temp.next = pNext;
            p.next = temp;
            p = pNext;
        }
        p = pHead;
        while(p != null){
            if(p.random != null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        p = pHead;
        RandomListNode newHead = pHead.next;
        RandomListNode p1 = newHead;
        while(p != null){
            p.next = p.next.next;
            p = p.next;
            if(p1.next != null)
            p1.next = p1.next.next;
            p1 = p1.next;
            
        }
        return newHead;
        
    }
}

二叉搜索树的后序遍历序列

2020-05-30

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

思路

二叉搜索树的特点是 left < root < right, 其后续遍历序列的最后一个元素一定是该二叉搜索树的根节点，因此判断思路是，遍历给定序列找到第一个大于root的节点值，判断后面的其他节点是否都大于root, 若都大于的话再去递归判断两个子树的序列，否则的话返回false;递归终止条件为left>=right。

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;
        int length = sequence.length;
        return verify(sequence, 0, length-1);
    }
    
    public boolean verify(int [] seq, int left, int right){
        if(left >= right) return true;
        int root = seq[right];
        int i=left;
        while(i < right){
            if(seq[i] > root) break;
            i++;
        }
        int temp = seq[right];
        int idx = i;
        while(i < right){
            if(seq[i] < temp) return false;
            i++;
        }
        //left,i-1, i,right-1
        return verify(seq, left, idx-1) || verify(seq, idx, right-1);
    } 
}

从上往下打印二叉树

2020-05-30

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

思路
bfs遍历二叉树可按层序遍历节点，为了识别出每一层在队列中的位置，用一个变量count来计数，count保存的是该层的节点数。

代码

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> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int count = 1;
        while(!q.isEmpty()){
           int size = count;
           count = 0;
           for(int i=0; i<size; ++i){
                TreeNode node = q.poll();
                res.add(node.val);
                if(node.left != null) {
                    q.offer(node.left);
                    count++;
                }
                if(node.right != null){
                    q.offer(node.right);
                    count++;
                }
            }
        }
        return res;
    }
}

知识点
java中对queue的操作有两种:

操作	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

栈的压入、弹出序列

2020-05-30

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

思路
用一个栈来模拟题目描述的操作，每次圧栈后判断栈顶元素是否和popA[idx]相等，相等的话就idx++, 并S.pop(), 不相等的话继续圧栈。如果popA是pushA对应的出栈顺序的话，最后S必定为空，若不是的话S不为空。所以最后返回S.isEmpty()即可。

代码

import java.util.Stack;

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

包含min函数的栈

2020-05-30

题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路
定义一个最小值栈，当push进来的元素小于minS栈顶元素是就把该元素压进栈，当pop出的元素等于minS栈顶元素时就把minS栈顶元素出栈

代码

import java.util.Stack;

public class Solution {
    Stack<Integer> S = new Stack<>();
    Stack<Integer> minS = new Stack<>();
    public void push(int node) {
        S.push(node);
        if(minS.isEmpty()){
            minS.push(node);
        }
        else{
            if(node < minS.peek()){
                minS.push(node);
            }
        }
    }
    
    public void pop() {
        int v = S.pop();
        if(v == minS.peek()){
            minS.pop();
        }
    }
    
    public int top() {
        return S.peek();
    }
    
    public int min() {
        return minS.peek();
    }
}

树的子结构

2020-05-29

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

思路
递归遍历这棵树，判断root1.val == root2.val, 若相等的话再判断以root1.left根的树是否完全包含root2以及以root1.right根的树是否完全包含root2,如包含的话就返回true;否则的话再递归判断 root1.left与root2 以及root1.right与root2

代码

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null) return false;
        if(root1.val == root2.val && isSub(root1.left, root2.left) && isSub(root1.right, root2.right)){
            return true;
        }
        else{
            return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
        }
        
    }
    public boolean isSub(TreeNode root1, TreeNode root2){
        if(root2 == null) return true;
        if(root1 == null) return false;
        if(root1.val != root2.val) return false;
        return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
    }
}

两个栈实现队列

2020-05-17

题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

思路
朴素的想法： stack1用来存元素，每次push新元素进stack1，队列pop的时候先将stack1的所有元素pop, 并push进stack2, res = stack2.pop(), 接着再将stack2中所有的元素pop，并push进stack1。

正解: 队列是先进先出，栈是先进后出，如何用两个栈来实现这种先进先出呢？
其实很简单，我们假设用stack1专门来装元素，那么直接stack1.pop肯定是不行的，这个时候stack2就要发挥作用了。

我们的规则是：只要stack2中有元素就pop，如果stack2为空，则将stack1中所有元素倒进satck2中，就是说，新元素只进stack1，元素出来只从stack2出来。

这样子，就能保证每次从stack2中pop出来的元素就是最老的元素了。

代码

import java.util.Stack;

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.isEmpty() ){
            while( !stack1.isEmpty() ){
                stack2.push( stack1.pop() );
            }
        }
        return stack2.pop();
    }
}

重建二叉树

2020-05-17

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

贴一张盗的图

代码

/**
 * 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) {
        return reConstructBinaryTree(pre, 0, in, 0, in.length-1);
    }
//	pre {1,2,4,7,3,5,6,8}
//	in  {4,7,2,1,5,3,8,6}
	
    private TreeNode reConstructBinaryTree(int [] pre, int preIdx, int[] in, int inL, int inR)
    {
        if( (preIdx >= pre.length) || (inL > inR) ) return null;
        int rootVal = pre[preIdx];
        TreeNode root = new TreeNode(rootVal);
        int i=0;
        for(i = inL; i <= inR; i++){
            if(rootVal == in[i]){
                break;
            }
        }
        root.left = reConstructBinaryTree(pre, preIdx+1, in, inL, i-1);
        root.right = reConstructBinaryTree(pre, preIdx+(i-inL+1), in, i+1, inR);
        return root;
    } 
}

最大正方形

2020-05-09

题目
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

方法1：
暴力法
遍历这个矩阵，通过矩阵的长宽和当前遍历的位置计算出最长的遍历边长，以当前点为正方形的左上点，遍历不同边长的正方形是否全为1,从全为1的正方形中找出最大的边长，边长的平方就是答案。

class Solution {
    public boolean allOne(char[][] matrix, int x, int y, int n){
        for(int i=x; i<=x+n; ++i){
            for(int j=y; j<=y+n; ++j){
                if(matrix[i][j] == '0') return false;
            }
        }
        return true;
    }
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length==0) return 0;
        int maxArea = 0;
        int height = matrix.length;
        int width = matrix[0].length;
        for(int i=0; i<height; ++i){
            for(int j=0; j<width; ++j){
                int n = Math.min(width-j, height-i)-1;
                // System.out.println(n);
                for(int k=0; k<=n; ++k){
                    int area=0;
                    // System.out.println(k);
                    if(allOne(matrix, i, j, k)){
                        area = (k+1) * (k+1);
                    }
                    maxArea = Math.max(maxArea, area);
                    // System.out.println(maxArea);
                }
            }
        }
        return maxArea;
    }
}

** 方法2 **
dp法

定义dp[i][j]为以i,j为右下点构成的正方形的最大边长，最终从所有的dp中找出最大的边长就是符合题目的正方形的边长。

动态规划最重要的第二点就是如何递推，这里首先观察dp[i][j], 由于dp[i][j]定义的是以i,j为右下点的正方形，因此只考虑右上的dp与dp[i][j]的关系，显然，如果dp[i-][j], dp[i][j-1], dp[i-1][j-1]中有一个为0的话那么dp[i][j]构成的最大正方形的边长只能是1，如果dp[i-][j], dp[i][j-1], dp[i-1][j-1]都不为0的胡，也就是它们都大于等于1的话才有可能构成边长大于1的正方形，构成的正方形的边长为min(dp[i-][j], dp[i][j-1], dp[i-1][j-1])+1。

考虑到边界时, dp[0][0] 对应的左边，上边，左上也应该要有dp，所以把dp的大小定义为原来matrix的大小+1，dp[i][j]对应的是matrix[i-1][j-1]。

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int h = matrix.length;
        int w = matrix[0].length;
        int[][] dp = new int[h+1][w+1];
        int res = 0;
        for(int i=1; i<h+1; ++i){
            for(int j=1; j<w+1; ++j){
                if(matrix[i-1][j-1] == '1'){
                    if((dp[i-1][j] != 0) && (dp[i][j-1] != 0) && (dp[i-1][j-1] != 0)){
                        dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    }
                    else{
                        dp[i][j] = 1;
                    }
                    System.out.println(dp[i][j]);
                    res = Math.max(res, dp[i][j]);
                }
                
            }
        }
        return res*res;
    }
}