LeetCode过程中值得反思的细节

以下题号均指LeetCode剑指offer题库中的题号

本文章将每周定期更新,当内容达到10题左右时将会开下一节。

二维数组越界问题04

public static void main(String[] args) {
    int[][]x = {{}};
    System.out.println(x.length+" "+x[0].length);
    int[][]y = {{1}};
    System.out.println(y.length+" "+y[0].length);
    int[][]z = {};
    System.out.println(z.length);
}

image-20210331232106168

在遇到二维数组时,要注意为空的不同情况

String和char[]的相互转换05

char[] s = {'a','b','c'};
String s1 = new String(s); //这里为String的构造函数
String s2 = "abc";
System.out.println(s1.equals(s2));
System.out.println(s1.equals(s));
System.out.println(s2.equals(s));

char[] s3 = new char[8];
s3[0]='a';s3[1]='b';s3[2]='c';
String s4 = new String(s3);
System.out.println(s4.equals(s2));
System.out.println(s2.equals(s4.trim()));//或者括号内为new String(s3,0,3)   String(char[],off,length)

注意,char[]强制转换为String,相互比较结果不经处理恒为false。

原因:由equals源码决定

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String aString = (String)anObject;
        if (!COMPACT_STRINGS || this.coder == aString.coder) {
            return StringLatin1.equals(value, aString.value);
        }
    }
    return false;
}

String对象的内部也是一个char数组,通过char数组创建String时,如果不指定start和count,会将使用整个数组,即连同后面的空字符,输出结果不会受到影响。另外,String.trim()就是删除String 的char数组 前后的空白字符和空字符,使用trim()后再比较就得到值完全一样的String了。

集合数组互转06

    // int[] 转 List<Integer>
    List<Integer> list1 = Arrays.stream(data).boxed().collect(Collectors.toList());
    // Arrays.stream(arr) 可以替换成IntStream.of(arr)。
    // 1.使用Arrays.stream将int[]转换成IntStream。
    // 2.使用IntStream中的boxed()装箱。将IntStream转换成Stream<Integer>。
    // 3.使用Stream的collect(),将Stream<T>转换成List<T>,因此正是List<Integer>。
 
    // int[] 转 Integer[]
    Integer[] integers1 = Arrays.stream(data).boxed().toArray(Integer[]::new);
    // 前两步同上,此时是Stream<Integer>。
    // 然后使用Stream的toArray,传入IntFunction<A[]> generator。
    // 这样就可以返回Integer数组。
    // 不然默认是Object[]。
 
    // List<Integer> 转 Integer[]
    Integer[] integers2 = list1.toArray(new Integer[0]);
    //  调用toArray。传入参数T[] a。这种用法是目前推荐的。
    // List<String>转String[]也同理。
 
    // List<Integer> 转 int[]
    int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray();
    // 想要转换成int[]类型,就得先转成IntStream。
    // 这里就通过mapToInt()把Stream<Integer>调用Integer::valueOf来转成IntStream
    // 而IntStream中默认toArray()转成int[]。
 
    // Integer[] 转 int[]
    int[] arr2 = Arrays.stream(integers1).mapToInt(Integer::valueOf).toArray();
    // 思路同上。先将Integer[]转成Stream<Integer>,再转成IntStream。
 
    // Integer[] 转 List<Integer>
    List<Integer> list2 = Arrays.asList(integers1);
    // 最简单的方式。String[]转List<String>也同理。
 
    // 同理
    String[] strings1 = {"a", "b", "c"};
    // String[] 转 List<String>
    List<String> list3 = Arrays.asList(strings1);
    // List<String> 转 String[]
    String[] strings2 = list3.toArray(new String[0]);

ArrayList.get(); ArrayList.set(index,value);

重建二叉树的两种方法07

根据先序和中序递归还原二叉树

先序:根节点,{左子树},{右子树}

中序:{左子树},根节点,{右子树}

两种思路:递归和迭代

递归:

class Solution {
    private HashMap<Integer,Integer> indexmap = new HashMap<>();

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderleft,int preorderright,int inorderleft,int inorderright){
        if(preorderleft>preorderright)
            return null;
        TreeNode root = new TreeNode(preorder[preorderleft]);
        int inorderroot = indexmap.get(preorder[preorderleft]);
        int prelen = inorderroot - inorderleft;
        root.left = myBuildTree(preorder,inorder,preorderleft+1,preorderleft+prelen,inorderleft,inorderroot-1);
        root.right = myBuildTree(preorder,inorder,preorderleft+prelen+1,preorderright,inorderroot+1,inorderright);
        return root;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for(int i = 0 ; i < len ; i++){
            indexmap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,len-1,0,len-1);
    }
}

将以上算法后四个参数 (int preorderleft,int preorderright,int inorderleft,int inorderright) 分别称为A,B,C,D,则A和B相当于建立的树的先序遍历的左边指针和右边指针,C和D相当于中序遍历的左指针和右指针,用来标记多次遍历过程的左子树边界和右子树边界。

迭代思路中,则需要用到栈stack

可利用deque接口实现stack

  • deque支持两端元素插入和移除的线性集合。 名称deque是“双端队列”的缩写,通常发音为“deck”。 大多数Deque实现对它们可能包含的元素的数量没有固定的限制,但是该接口支持容量限制的deques以及没有固定大小限制的deques。
Deque<TreeNode> stack = new LinkedList<TreeNode>();

stack.peek()取栈顶元素,不弹出

stack.push()压入元素

stack.pop()取栈顶元素,并弹出

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0)
            return null;
        int len = preorder.length;
        int index = 0;   //中序遍历的指针
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        TreeNode node;
        for(int i = 1 ; i < len ; i++){
            if((node = stack.peek()).val != inorder[index]){
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            }
            else{
                while(!stack.isEmpty() && stack.peek().val==inorder[index]){ //stack存当前构造树的左节点,可能会有多个构造的树
                    node = stack.pop();
                    index++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

在这个思路中,主要应用中序遍历的第一个元素将是树的左边界,以先序遍历的顺序与该元素进行比较,若根节点与其相同,则无左子树;不同的话即为压入栈的栈顶元素的左节点。这个思路主要在于先序遍历和中序遍历的过程特点,递归主要利用的是先序和中序的结构特点。

重要在于理解:每次遍历过程中,操作的是栈顶元素,而遍历的当前i在栈顶元素的后面。

利用两个栈实现队列 09

队列要实现的是先进先出,而栈实现的是先进后出,所以可以建立两个stack

栈1负责压入元素,而当需要删除的时候,只需将栈1中的元素转入栈2

stack2.push(stack1.pop());

这样的话,栈2中,栈顶元素为最开始添加进去的元素,为队列头,直至栈2删除完后,若栈1还有元素,继续转移,若没有,则返回0。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/gaoyuan206/p/14642301.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!