No.3 二維數(shù)組中查找數(shù)字 思路：從右上角（左下角）開始比較
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(); }推廣：將兩個數(shù)組按序合并，在原位置
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 用兩個棧實現(xiàn)一個隊列
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(); }新聞熱點
疑難解答
