JZ1
问题描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
- 边界条件判断，如果数组为空直接false
- 从二维数组左下角的元素开始遍历
- 如果当前数等于目标值，返回true
- 如果当前值大于目标值，行索引自减
- 如果当前值小于目标值，列索引自增
- 如果行索引或者列索引越界，返回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
问题描述：
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
- 直接遍历字符串，使用StringBuilder接收遍历结果
- 如果当前为空格，加入指定字符串
代码：
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
问题描述：
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路一：
- 遍历链表，每次在0索引的位置插入元素
思路二：
- 将链表反转，之后遍历
思路三：
- 正向遍历，然后使用Collections工具类反转
代码：
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
问题描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路一：
- 前序遍历顺序：根节点 —— 根节点左子树 —— 根节点右子树
- 中序遍历顺序：根节点左子树 —— 根节点 —— 根节点右子树
- 首先确定根节点，前序遍历序列第一个值就是根节点的值
- 在中序遍历序列中找到上一步根节点所在位置
- 然后递归进行左子树和右子树的计算
代码：
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]);
// 首先确定头节点的值
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
问题描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路一：
- 队列的特点：先进先出
- 入队列的时候，直接加入指定的数据栈中（data）
- 出队列的时候，在专用的操作栈（opt）中取数据
- 如果操作栈为空，将数据栈中的元素全部弹过来
- 如果操作栈不为空，直接弹出元素即可
代码：
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("队列为空");
if(stack2.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
网友评论