《剑指Offer》2.3数据结构 java版

2019-11-06 09:15:41

字体：大中小

来源：转载

供稿：网友

No.3 二维数组中查找数字思路：从右上角（左下角）开始比较

public boolean Find(int target, int [][] array) { if(array == null) return false; int row = array.length, column = array[0].length; int i = 0, j = column - 1; while( i < row && j >= 0){ if(array[i][j] == target) return true; if(array[i][j] > target) j--; else i++; } return false; }

No.4：将字符串中的空格替换为”%20“ 思路：第一种：可以新开辟空间存储；第二种，在原字符串上修改，从后往前

public String replaceSpace(StringBuffer str) { if(str == null || str.length() == 0) return str.toString(); int len = str.length(); StringBuilder sb = new StringBuilder(); for(int i = 0; i < len; i++){ if(str.charAt(i) == ' '){ sb.append("%20"); }else{ sb.append(str.charAt(i)); } } return sb.toString(); }

推广：将两个数组按序合并，在原位置

public int[] mergerDigital(int[] A,int[] B, int n1, int n2){ if(n2 == 0) return A; if(n1 == 0){ A = Arrays.copyOf(B, n2); return A; } int k = n1 + n2 - 1, i = n1 - 1, j = n2 - 1; while(i >= 0 && j >= 0){ A[k--] = A[i] >= B[j] ? A[i--] : B[j--]; } while(i >= 0){ A[k--] = A[i--]; } while(j >= 0){ A[k--] = B[j--]; } return A; }

No.5 将单向链表逆序输出思路：使用栈，后进先出；或者使用linkedlist

public ArrayList<Integer> PRintListFromTailToHead(ListNode listNode) { Stack s = new Stack(); while(listNode != null){ s.push(listNode.val); listNode = listNode.next; } ArrayList al = new ArrayList(); while(!s.empty()){ al.add(s.pop()); } return al; } public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { LinkedList s = new LinkedList(); while(listNode != null){ s.addFirst(listNode.val); listNode = listNode.next; } return new ArrayList<>(s); }

No.6 重建二叉树思路：递归思想

public TreeNode help(int[] preorder, int[] inorder, int pleft, int pright, int ileft, int iright) { if(pleft > pright || ileft > iright) return null; TreeNode root = new TreeNode(preorder[pleft]); int i; for(i = ileft; i <= iright; i++){ if(inorder[i] == preorder[pleft]) break; } root.left = help(preorder, inorder,pleft + 1, pleft + i - ileft, ileft, i - 1); root.right = help(preorder, inorder,pleft + i - ileft + 1, pright, i + 1, iright); return root; } public TreeNode reConstructBinaryTree(int [] pre,int [] in) { int len = pre.length; if(len == 0) return null; return help(pre, in, 0, len - 1, 0, len - 1); }

No.7 用两个栈实现一个队列

Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() throws Exception { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } if(stack2.isEmpty()) throw new Exception("队列为空，不能删除"); return stack2.pop(); }

上一篇：ReactiveX(rxjava)学习笔记

下一篇：Java常用知识点