JZ1
問題描述：
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序送火，每一列都按照從上到下遞增的順序排序买乃。請(qǐng)完成一個(gè)函數(shù)珍剑，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)贫堰，判斷數(shù)組中是否含有該整數(shù)。
思路：
- 邊界條件判斷待牵，如果數(shù)組為空直接false
- 從二維數(shù)組左下角的元素開始遍歷
- 如果當(dāng)前數(shù)等于目標(biāo)值其屏，返回true
- 如果當(dāng)前值大于目標(biāo)值，行索引自減
- 如果當(dāng)前值小于目標(biāo)值缨该，列索引自增
- 如果行索引或者列索引越界偎行，返回false
代碼：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array.length == 0 || array[0].length == 0) return false;
int m = array.length, n = array[0].length;
int r = m - 1, c = 0;
while(r >= 0 && c < n){
if(array[r][c] == target) return true;
if(array[r][c] > target) r--;
else if(array[r][c] < target) c++;
}
return false;
}
}
JZ2
問題描述：
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的每個(gè)空格替換成“%20”压彭。例如睦优，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
思路：
- 直接遍歷字符串壮不，使用StringBuilder接收遍歷結(jié)果
- 如果當(dāng)前為空格汗盘，加入指定字符串
代碼：
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer res = new StringBuffer();
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' '){
res.append("%20");
}else{
res.append(str.charAt(i));
}
}
return res.toString();
}
}
JZ3
問題描述：
輸入一個(gè)鏈表，按鏈表從尾到頭的順序返回一個(gè)ArrayList询一。
思路一：
- 遍歷鏈表隐孽，每次在0索引的位置插入元素
思路二：
- 將鏈表反轉(zhuǎn)，之后遍歷
思路三：
- 正向遍歷健蕊，然后使用Collections工具類反轉(zhuǎn)
代碼：
public class Solution {
ArrayList<Integer> res = new ArrayList<Integer>();
// 思路一：
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null) return res;
ListNode t = listNode;
while(t != null) {
res.add(0, t.val);
t = t.next;
}
return res;
}
// 思路二：
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null) return res;
ListNode pre = null, next = null;
while(listNode != null) {
next = listNode.next;
listNode.next = pre;
pre = listNode;
listNode = next;
}
while(pre != null) {
res.add(pre.val);
pre = pre.next;
}
return res;
}
// 思路三：
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null) return res;
while(listNode != null) {
res.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(res);
return res;
}
}
JZ4
問題描述：
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果菱阵，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字缩功。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}晴及，則重建二叉樹并返回。
思路一：
- 前序遍歷順序：根節(jié)點(diǎn) —— 根節(jié)點(diǎn)左子樹 —— 根節(jié)點(diǎn)右子樹
- 中序遍歷順序：根節(jié)點(diǎn)左子樹 —— 根節(jié)點(diǎn) —— 根節(jié)點(diǎn)右子樹
- 首先確定根節(jié)點(diǎn)嫡锌，前序遍歷序列第一個(gè)值就是根節(jié)點(diǎn)的值
- 在中序遍歷序列中找到上一步根節(jié)點(diǎn)所在位置
- 然后遞歸進(jìn)行左子樹和右子樹的計(jì)算
代碼：
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
int n = pre.length;
return create(pre, 0, n - 1, in, 0, n - 1);
}
private TreeNode create(int[] pre, int pl, int pr, int[] in, int il, int ir) {
if (pl > pr) return null;
if (pl == pr) return new TreeNode(pre[pl]);
// 首先確定頭節(jié)點(diǎn)的值
int cur = pre[pl];
TreeNode root = new TreeNode(cur);
int ii = 0;
for (int i = il; i <= ir; i++) {
if (in[i] == cur) {
ii = i;
break;
}
}
int len = ii - il;
root.left = create(pre, pl + 1, pl + len, in, il, ii - 1);
root.right = create(pre, pl + len + 1, pr, in, ii + 1, ir);
return root;
}
}
JZ5
問題描述：
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列虑稼，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型势木。
思路一：
- 隊(duì)列的特點(diǎn)：先進(jìn)先出
- 入隊(duì)列的時(shí)候蛛倦，直接加入指定的數(shù)據(jù)棧中（data）
- 出隊(duì)列的時(shí)候，在專用的操作棧（opt）中取數(shù)據(jù)
- 如果操作棧為空啦桌，將數(shù)據(jù)棧中的元素全部彈過來
- 如果操作棧不為空溯壶，直接彈出元素即可
代碼：
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.isEmpty() && stack2.isEmpty()) throw new RuntimeException("隊(duì)列為空");
if(stack2.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
