1涩禀、在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序健爬。請完成一個函數(shù)控乾，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)娜遵。
-
假如二維數(shù)組為
{{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};同時查找的值為15蜕衡。- 常規(guī)的思路為我們?nèi)〉矫總€二維數(shù)組的值，然后遍歷每個值设拟，判斷是否相等慨仿！同時我們知道會循環(huán)
16次。代碼如下private boolean lookUpInTwoDimensionalArrays(int[][] a, int num) { // 至少保證 長度至少為1纳胧，且還有元素镰吆， if (a == null || a.length < 1 || a[0].length < 1) { return false; } int b = 0; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { b++; if (num == a[i][j]) { // 一共循環(huán)多少次：12 System.out.println(TAG + "一共循環(huán)多少次：" + b); return true; } } } return false; } - 解題的思路如下
- 1、選取二維數(shù)組的中的第一個元素跑慕，比較最右邊的值万皿，如果相等，就查找結(jié)束
- 2核行、選取二維數(shù)組的中的第一個元素牢硅，比較最右邊的值，如果大于芝雪，查找的就是這個元素减余，同時角標(biāo)減去1，然后繼續(xù)查找
-
3惩系、選取二維數(shù)組的中的第一個元素位岔，比較最右邊的值，如果大于堡牡，查找的不是這個元素抒抬，就去查找下一個數(shù)組，然后繼續(xù)查找二維數(shù)組的查找過程.png
- 常規(guī)的思路為我們?nèi)〉矫總€二維數(shù)組的值，然后遍歷每個值设拟，判斷是否相等慨仿！同時我們知道會循環(huán)
最終的代碼如下
/**
* 數(shù)組是遞增的 悴侵，從左到右 從上到下,那么數(shù)組一定是個正方形的樣子
*
* @param arr 原始的數(shù)組
* @param num 需要查找的數(shù)字
* @return 是否找到了
*/
private boolean newLookUpInTwoDimensionalArrays(int[][] arr, int num) {
if (arr == null || arr.length < 1 || arr[0].length < 1) {
return false;
}
int rowTotal = arr.length;// 數(shù)組的行數(shù)
int colTolal = arr[0].length;// 數(shù)組的列數(shù)
//開始的角標(biāo)
int row = 0;
int col = colTolal - 1;
int i = 0;
while (row >= 0 && row < rowTotal && col >= 0 && col < colTolal) {
// 是二維數(shù)組的 arr[0][arr[0].length-1] 的值瞧剖，就是最右邊的值
i++;
if (arr[row][col] == num) {
System.out.println(TAG + "newLookUpInTwoDimensionalArrays 執(zhí)行了多少次" + i);
return true;
} else if (arr[row][col] > num) {// 如果找到的值 比目標(biāo)的值大的話，就把查找的列數(shù)減去1
col--;//列數(shù)減去1 可免，代表向左移動
} else {// 比目標(biāo)的num大的，就把行數(shù)加上1做粤，然后往下移動
row++;
}
}
return false;
}
- 如果查找的值為
15浇借，那么舊的代碼會執(zhí)行15次，新的代碼只會執(zhí)行3次怕品。
2妇垢、請實現(xiàn)一個函數(shù)，把字符串中的每個空格替換成"%20"，例如“We are happy.”闯估，則輸出“We%20are%20happy.”.
- 第一種方法:先判斷字符串中空格的數(shù)量灼舍。根據(jù)數(shù)量判斷該字符串有沒有足夠的空間替換成"%20"。如果有足夠空間涨薪，計算出需要的空間骑素。根據(jù)最終需要的總空間，維護一個指針在最后刚夺。從后到前献丑，遇到非空的就把該值挪到指針指向的位置，然后指針向前一位侠姑，遇到“ ”创橄，則指針前移，依次替換為“02%”莽红。
public char[] replaceBlank(char[] string, int usedLength) {
// 判斷輸入是否合法
System.out.println(TAG+"string.length="+string.length);
System.out.println(TAG+"usedLength="+usedLength);
if (string == null || string.length < usedLength) {
return null;
}
// 統(tǒng)計字符數(shù)組中的空白字符數(shù)
int whiteCount = 0;
for (int i = 0; i < usedLength; i++) {
if (string[i] == ' ') {
whiteCount++;
}
}
// 如果沒有空白字符就不用處理
if (whiteCount == 0) {
return string;
}
// 計算轉(zhuǎn)換后的字符長度是多少
int targetLength = whiteCount * 2 + usedLength;
//新的保存的字符串的數(shù)組
char[] newChars = new char[targetLength];
int tmp = targetLength; // 保存長度結(jié)果用于返回
// if (targetLength > string.length) { // 如果轉(zhuǎn)換后的長度大于數(shù)組的最大長度妥畏，直接返回失敗
// return -1;
// }
// todo 必須先做 這個，注意體會 --i 和 i-- 的區(qū)別
usedLength--; // 從后向前安吁，第一個開始處理的字符
targetLength--; // 處理后的字符放置的位置
// 字符中有空白字符咖熟，一直處理到所有的空白字符處理完
while (usedLength >= 0 && usedLength < targetLength) {
// 如是當(dāng)前字符是空白字符，進行"%20"替換
if (string[usedLength--] == ' ') {
newChars[targetLength--] = '0';
newChars[targetLength--] = '2';
newChars[targetLength--] = '%';
} else { // 否則移動字符
newChars[targetLength--] = string[usedLength];
}
usedLength--;
}
return newChars;
}
- 第二種方法柳畔，非常的消耗時間和內(nèi)存馍管。
private String idoWorkReplace(String str, String tagStr) {
if (str == null || str.length() < 1) {
return "";
}
String[] split = str.split(" ");
StringBuffer stringBuffer = new StringBuffer();
for (String s : split) {
stringBuffer.append(s);
stringBuffer.append(tagStr);
}
CharSequence charSequence = stringBuffer.subSequence(0, stringBuffer.length() - tagStr.length());
return charSequence.toString();
}
- 第三種方法，調(diào)用
replace方法薪韩，如果僅僅來講替換字符串的話确沸，是最好的方法，關(guān)鍵的方法是indexOf(this, targetStr, lastMatch).
StringBuffer sb = new StringBuffer();
sb.append(str);
// todo 最節(jié)能的方法
sb.toString().replace(" ", "%20");
- 第四種方法和第一種方法異曲同工:先統(tǒng)計空白的數(shù)量俘陷，然后計算出有多少空白的長度罗捎，然后設(shè)置新的長度
StringBuffer，通過插入最大角標(biāo)的地方拉盾，不斷的插入桨菜，就可以了
private String replaceSpaces(String string) {
//判斷是否 輸入合法
if (string == null || string.length() < 1) {
return "";
}
char[] chars = string.toCharArray();
// 統(tǒng)計有多少的空白的數(shù)組
int whiteCount = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' ') {
whiteCount++;
}
}
if (whiteCount == 0) {
return string;
}
//最原本的長度
int indexold = string.length() - 1;
// 轉(zhuǎn)換完成后的長度
int newlength = string.length() + whiteCount * 2;
//新的長度
int indexnew = newlength - 1;
StringBuffer stringBuffer = new StringBuffer(string);
//設(shè)置新的buffer的長度
stringBuffer.setLength(newlength);
for (; indexold >= 0 && indexold < newlength; indexold--) {
// 原來的 字符串的最后一位為空格
if (string.charAt(indexold) == ' ') {
stringBuffer.setCharAt(indexnew--, '0');
stringBuffer.setCharAt(indexnew--, '2');
stringBuffer.setCharAt(indexnew--, '%');
} else {//不為空的話，就直接放進去 就行了
stringBuffer.setCharAt(indexnew--, string.charAt(indexold));
}
}
return stringBuffer.toString();
}
3捉偏、輸入個鏈表的頭結(jié)點倒得，從尾到頭反過來打印出每個結(jié)點的值。
- 數(shù)據(jù)結(jié)構(gòu)
public static class ListNode {
int val;
ListNode next;
public ListNode(int v){
this.val=v;
}
}
- 初始化
ListNode listNode = new ListNode(10);
ListNode listNode1 = new ListNode(11);
ListNode listNode2 = new ListNode(12);
ListNode listNode3 = new ListNode(13);
ListNode listNode4 = new ListNode(14);
listNode.next=listNode1;
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
- 第一種方法的詳情,非常像二叉樹的遍歷夭禽，也是最簡單的方法霞掺。
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
arrayList.clear();
if (listNode != null) {
printListFromTailToHead(listNode.next);//指向下一個節(jié)點
arrayList.add(listNode.val);//將當(dāng)前節(jié)點的值存到列表中
}
return arrayList;
}
- 第二種方法,利用
Stack的特點，Stack類：繼承自Vector讹躯，實現(xiàn)一個后進先出的棧,不太明白的同學(xué)可以看這里常用集合的原理分析;
private static void doWhat(ListNode listNode) {
Stack<ListNode> stack = new Stack<>();
while (listNode!=null){
stack.push(listNode);
listNode=listNode.next;
}
System.out.println(" stack "+stack.size());
// for (int i=0;i<stack.size();i++){
// System.out.println("每個該打印的元素 ::"+stack.get(i).val);
// }
ListNode tmp;
while (!stack.empty()){
// 移除堆棧頂部的對象菩彬，并作為此函數(shù)的值返回該對象缠劝。
tmp = stack.pop();
System.out.println("tmp="+tmp.val);
// System.out.println("每個該打印的元素 ："+tmp.val);
}
}
4、輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果骗灶，請重建出該二叉樹惨恭。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。這個題的官方的答案耙旦，我本人持有嚴(yán)重的懷疑脱羡，也有可能是我根本沒有找到正確的答案！
- 認(rèn)識下什么二叉樹：二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)母廷。通常子樹被稱作“左子樹”
（left subtree）和“右子樹”（right subtree）轻黑。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。樹的數(shù)據(jù)結(jié)構(gòu)能夠同時具備數(shù)組查找快的優(yōu)點以及鏈表插入和刪除快的優(yōu)點 - 代碼結(jié)構(gòu)
public interface Tree {
//查找節(jié)點
Node find(int key);
//插入新節(jié)點
boolean insert(int data);
//中序遍歷
void infixOrder(Node current);
//前序遍歷
void preOrder(Node current);
//后序遍歷
void postOrder(Node current);
//查找最大值
Node findMax();
//查找最小值
Node findMin();
//刪除節(jié)點
boolean delete(int key);
}
- Node
public class Node {
int data; //節(jié)點數(shù)據(jù)
Node leftChild; //左子節(jié)點的引用
Node rightChild; //右子節(jié)點的引用
public Node(int data){
this.data = data;
}
//打印節(jié)點內(nèi)容
public void display(){
System.out.println(data);
}
@Override
public String toString() {
return super.toString();
}
}
- 插入數(shù)據(jù)的過程
BinaryTree bt = new BinaryTree();
// 第一個插入的結(jié)點是 根節(jié)點
bt.insert(50);
bt.insert(20);
bt.insert(80);
bt.insert(10);
bt.insert(30);
bt.insert(60);
bt.insert(90);
bt.insert(25);
bt.insert(85);
bt.insert(100);
- insert 代碼
//插入節(jié)點
public boolean insert(int data) {
Node newNode = new Node(data);
if (root == null) {//當(dāng)前樹為空樹琴昆，沒有任何節(jié)點
root = newNode;
return true;
} else {
Node current = root;
Node parentNode = null;
while (current != null) {
parentNode = current;
if (current.data > newNode.data) {//當(dāng)前值比插入值大氓鄙，搜索左子節(jié)點
current = current.leftChild;
if (current == null) {//左子節(jié)點為空，直接將新值插入到該節(jié)點
parentNode.leftChild = newNode;
return true;
}
} else {
current = current.rightChild;
if (current == null) {//右子節(jié)點為空业舍，直接將新值插入到該節(jié)點
parentNode.rightChild = newNode;
return true;
}
}
}
}
return false;
}
二叉樹插入數(shù)據(jù)的過程.png
二叉樹最終的結(jié)構(gòu).png
- 最終的圖解如下
二叉樹 insert 圖解.jpg
- 二叉樹的前序遍歷：根節(jié)點>>左子樹>>右子樹
public void preOrder(Node current) {
if (current != null) {
System.out.print(current.data + " ");
infixOrder(current.leftChild);
infixOrder(current.rightChild);
}
}
- 1抖拦、根節(jié)點50，查找左節(jié)點舷暮，找到20态罪，然后找到10，輸出10下面，然后找到25 复颈，然后30 。到這里輸出的結(jié)果是 50 10 20 25 30
- 2沥割、查找根節(jié)點的50的右節(jié)點耗啦，然后找出80，找出80的左節(jié)點60.接著80机杜，查找80的右節(jié)點95帜讲，輸出85 然后 90 ，最后輸出100
- 3椒拗、最終的輸出的結(jié)果50 10 20 25 30 60 80 85 90 100
前序遍歷.png
- 二叉樹中序遍歷：首先遍歷左子樹似将，然后訪問根結(jié)點，最后遍歷右子樹蚀苛。 左子樹 ---》根節(jié)點----》 右子樹
public void infixOrder(Node current) {
if (current != null) {
infixOrder(current.leftChild);
System.out.print(current.data + " ");
infixOrder(current.rightChild);
}
}
- 1在验、傳入根節(jié)點 值為50 ，查找50的左節(jié)點為20不為null枉阵，再次查找20的左節(jié)點译红，為10，也不為null兴溜，然后在查找10的左節(jié)點侦厚，為null ，輸出10拙徽，第一個節(jié)點輸出完成為 10
- 2刨沦、接下來，查找的10的右節(jié)點膘怕，為null想诅，不進入輸出語句
- 3、這下輸出語句20岛心，查找20右節(jié)點来破，查找到值為30，第一步查找的值為左節(jié)點忘古，查找到的值為25徘禁，查找右節(jié)點為null
- 4、到這里輸出的結(jié)果為 10 20 25 30
- 5髓堪、這樣子50左節(jié)點就全部查找完了
- 6送朱、接下來查找50的右節(jié)點，查找右節(jié)點80干旁，然后查找80的左節(jié)點驶沼，查找到的值為60,60沒有右節(jié)點，繼續(xù)查找80的右節(jié)點争群，到這里 輸出的結(jié)果10 20 25 30 50 60 80
- 7回怜、查找80右節(jié)點，查到到值為90换薄，接著查找90的左節(jié)點玉雾，查到到的值85，接著85的左右節(jié)點為null专控，返回直接查找90的右節(jié)點抹凳，查找到了100，
- 8伦腐、最終輸出的結(jié)果赢底，10 20 25 30 50 60 80 85 90 100
二叉樹的中序遍歷.png
- 后序遍歷:在二叉樹中，先左后右再根柏蘑，即首先遍歷左子樹幸冻，然后遍歷右子樹，最后訪問根結(jié)點咳焚。
- 1洽损、根節(jié)點50，查找左節(jié)點20革半，在繼續(xù)查找20的左節(jié)點10,10沒有左右節(jié)點碑定，打印10,然后查找到20的右節(jié)點30,30繼續(xù)查找到25流码，第一次輸出為 10 20 25 30
- 2、最終輸出10 20 25 30 60 80 85 90 100 50
二叉樹的后序遍歷.png
- 查找最大值或者是最小值
//找到最大值
public Node findMax() {
Node current = root;
Node maxNode = current;
while (current != null) {
maxNode = current;
current = current.rightChild;
}
return maxNode;
}
//找到最小值
public Node findMin() {
Node current = root;
Node minNode = current;
while (current != null) {
minNode = current;
current = current.leftChild;
}
return minNode;
}
- 例如：前序遍歷序列
｛50 10 20 25 30 60 80 85 90 100｝和中序遍歷序列｛10 20 25 30 50 60 80 85 90 100}延刘， 重建二叉樹并輸出它的頭結(jié)點漫试。 - 原始節(jié)點的遍歷結(jié)果,可以很清楚的看到，有多少左右節(jié)點碘赖，那個節(jié)點是那個的節(jié)點等等的信息驾荣。
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node50 是那邊啊 根
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node20 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node10 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node30 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node25 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node80 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node60 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node90 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node85 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node100 是那邊啊 右
- 解決方法一：
public static Node reConstructBinaryTree(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length)//如果先序或者中序數(shù)組有一個為空的話，就無法建樹普泡，返回為空
return null;
else {
return reBulidTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
}
/**
* @param pre
* @param startPre
* @param endPre
* @param in
* @param startIn
* @param endIn
* @return
*/
private static Node reBulidTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn)//先對傳的參數(shù)進行檢查判斷
return null;
int root = pre[startPre];//數(shù)組的開始位置的元素是跟元素
int locateRoot = locate(root, in, startIn, endIn);//得到根節(jié)點在中序數(shù)組中的位置 左子樹的中序和右子樹的中序以根節(jié)點位置為界
if (locateRoot == -1) //在中序數(shù)組中沒有找到跟節(jié)點播掷，則返回空
return null;
Node treeRoot = new Node(root);//創(chuàng)建樹根節(jié)點
treeRoot.leftChild = reBulidTree(pre, startPre + 1, startPre + locateRoot - startIn, in, startIn, locateRoot - 1);//遞歸構(gòu)建左子樹
treeRoot.rightChild = reBulidTree(pre, startPre + locateRoot - startIn + 1, endPre, in, locateRoot + 1, endIn);//遞歸構(gòu)建右子樹
return treeRoot;
}
//找到根節(jié)點在中序數(shù)組中的位置，根節(jié)點之前的是左子樹的中序數(shù)組撼班，根節(jié)點之后的是右子樹的中序數(shù)組
private static int locate(int root, int[] in, int startIn, int endIn) {
for (int i = startIn; i < endIn; i++) {
if (root == in[i])
return i;
}
return -1;
}
- 但是這個的輸出結(jié)果如下歧匈，很明顯沒有重建二叉樹成功，它的執(zhí)行流程如上面的代碼权烧，由于個人認(rèn)為沒有重建眯亦，所以就沒有輸出示意圖
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 新新----的中序遍歷的開始
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node50 是那邊啊 根
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node10 是那邊啊 左
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node20 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node25 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node60 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node80 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node85 是那邊啊 右
09-02 05:51:53.177 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node90 是那邊啊 右
09-02 05:51:53.185 2590-2590/com.android.interview I/System.out: 新新----的中序遍歷的結(jié)束
- 解決方法二:解題思路也是不斷地遍歷，代碼如下
public static Node reConstructBinaryTreeNew(int[] pre, int[] in) {
if (pre.length == 0 || in.length == 0)
return null;
Node node = new Node(pre[0]);
for (int i = 0; i < pre.length; i++) {
if (pre[0] == in[i]) {
node.leftChild = reConstructBinaryTreeNew(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
node.rightChild = reConstructBinaryTreeNew(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return node;
}
- 輸出的結(jié)果和方法一的結(jié)果是一樣的般码。二叉樹的結(jié)果還是不一樣妻率。
09-02 05:51:53.185 2590-2590/com.android.interview I/System.out: 新新----的中序遍歷的開始------------
09-02 05:51:53.185 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node50 是那邊啊 根
09-02 05:51:53.185 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node10 是那邊啊 左
09-02 05:51:53.186 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node20 是那邊啊 右
09-02 05:51:53.194 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node25 是那邊啊 右
09-02 05:51:53.211 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node30 是那邊啊 右
09-02 05:51:53.212 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node60 是那邊啊 右
09-02 05:51:53.212 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node80 是那邊啊 右
09-02 05:51:53.212 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node85 是那邊啊 右
09-02 05:51:53.213 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node90 是那邊啊 右
09-02 05:51:53.213 2590-2590/com.android.interview I/System.out: 這個值是什么啊 Node100 是那邊啊 右
09-02 05:51:53.214 2590-2590/com.android.interview I/System.out: 新新----的中序遍歷的結(jié)束------------
解決方法三：由前序遍歷的第一個節(jié)點可知根節(jié)點。根據(jù)根節(jié)點板祝，可以將中序遍歷劃分成左右子樹宫静。在前序遍歷中找出對應(yīng)的左右子樹，其第一個節(jié)點便是根節(jié)點的左右子節(jié)點券时。按照上述方式遞歸便可重建二叉樹孤里。
這三種的方式的結(jié)果也是一樣的，我自己認(rèn)為二叉樹沒有重構(gòu)成功橘洞，如果有大佬明白的捌袜，可以指點下，謝謝了!
-
謝謝以下資料給與我的幫助
