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);
}
在遇到二维数组时,要注意为空的不同情况
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。
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!