剑指offer java版（二）
链表中倒数第k个结点
问题描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路
经典的双指针法。定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动，从第k步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时，第二个指针刚好指向倒数第k个节点。
public void findK(LinkNode node, int k) {
if (node == null || node.next == null) return;
// 判断链表长度是否超过k
int num = 1;
while (node.next != null) {
num++;
if (num == k) break;
}
if (num < k) return;
LinkNode node1 = node;
LinkNode node2 = node;
for (int i = 0; i < k - 1; i++) {
node1 = node1.next;
}
while (node1.next != null) {
node1 = node1.next;
node2 = node2.next;
}
System.out.println("倒数第k个元素值" + node2.value);
}反转单链表
问题描述
反转单链表。
解题思路
两个思路：循环和递归
- 循环
public void method1(LinkNode head) {
if (head == null || head.next == null) return;
LinkNode pre = null;
LinkNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
System.out.println(pre.value);
while (pre.next != null) {
System.out.println(pre.next.value);
pre = pre.next;
}
}- 递归
public LinkNode method2(LinkNode head) {
if (head == null || head.next==null) return head;
LinkNode pre = method2(head.next);
head.next.next = head;
head.next = null;
return pre;
}合并两个有序链表
问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
public LinkNode merge(LinkNode node1, LinkNode node2) {
// 如果其中一个为空，就返回另一个链表
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
// 先确定头结点
LinkNode head = null;
if (node1.value <= node2.value) {
head = node1;
node1 = node1.next;// 后移
} else {
head = node2;
node2 = node2.next;// 后移
}
// 将头结点赋给另一个变量，头结点不能直接参与循环，否则会改变头结点值
LinkNode cur = head;
// 两个链表都不为空时
while (node1 != null && node2 != null) {
if (node1.value <= node2.value) {
cur.next = node1;
node1 = node1.next;
} else {
cur.next = node2;
node2 = node2.next;
}
cur = cur.next;
}
// 一方已遍历完成后
if (node1 == null) {
cur.next = node2;
} else if(node2 == null){
cur.next = node1;
}
return head;
}树的子结构
问题描述
输入两棵二叉树A、B，判断B是不是A的子树。（我们约定空树不是任意一个树的子树）
解题思路
递归思想，如果根节点相同则递归调用IsSubtree()，如果根节点不相同，则判断root1的左子树和roo2是否相同，再判断右子树和root2是否相同;注意节点为空的条件，hasChild，只要有树为空就返回false;
isSub，要先判断root2，如果root2为空，则说明第二棵树遍历完了，即匹配成功。
public boolean hasChild(TreeNode nodeA, TreeNode nodeB) {
if (nodeA == null || nodeB == null) return false;
boolean result;
result = isSub(nodeA, nodeB);
if (!result) {
result = hasChild(nodeA.left, nodeB);
}
if (!result) {
result = hasChild(nodeA.right, nodeB);
}
return result;
}
public boolean isSub(TreeNode nodeA, TreeNode nodeB) {
if (nodeB == null) return true;
if (nodeA == null) return false;
if (nodeA.value == nodeB.value) {
return isSub(nodeA.left, nodeB.left) && isSub(nodeA.right, nodeB.right);
} else {
return false;
}
}二叉树镜像
问题描述
操作给定的二叉树，将其变换为源二叉树的镜像。
解题思路
通过对以上两棵树的观察，我们可以总结出这两棵树的根节点相同，但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。
public void image(TreeNode root) {
//当前节点为空，直接返回
if (root == null) return;
//当前节点没有叶子节点，直接返回
if (root.left == null && root.right == null) return;
// 交换
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归
if (root.left != null) {
image(root.left);
}
if (root.right != null) {
image(root.right);
}
}顺时针打印矩阵
问题描述
顺时针打印矩阵（二维数组）
解题思路
顺时针打印,核心在于控制上下左右四个坐标，循环条件是left和right相撞 并且top和bottom相撞
public void print(int[][] matrix) {
if (matrix == null) return;
int col = matrix[0].length;
int row = matrix.length;
if (row == 0 || col == 0) return;
List<Integer> list = new ArrayList<>();
int left = 0;
int top = 0;
int right = col - 1;
int bottom = row - 1;
while (left <= right && top <= bottom) {
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
top++;
for (int i = top; i <= bottom; i++) {
list.add(matrix[i][right]);
}
right--;
for (int i = right; i >= left; i--) {
list.add(matrix[bottom][i]);
}
bottom--;
for (int i = bottom; i >= top; i--) {
list.add(matrix[i][left]);
}
left++;
}
for (Integer i : list) {
System.out.println(" " + i);
}
}包含min函数的栈
问题描述
设计一个数据结构实现栈的基本功能，和获取最小值的函数。
解题思路
用一个栈stack保存数据，用另外一个栈temp保存依次入栈最小的数 比如，stack中依次入栈 5, 3, 4, 10, 2, 12, 1, 8 则temp依次入栈 5, 3, 3，3, 2, 2, 1, 1
每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则用最小元素入栈。
public class MyStack {
Stack<Integer> stack1 = new Stack<>();// 存放数据
Stack<Integer> stack2 = new Stack<>();// 存放对应size最小值
int min = Integer.MAX_VALUE;
public void push(Integer i) {
stack1.push(i);
if (i < min) {
min = i;
}
stack2.push(min);
}
public Integer pop() {
if (!stack1.isEmpty()) {
int i = stack1.pop();
stack2.pop();
return i;
} else {
throw new RuntimeException("Stack is Empty");
}
}
public Integer min() {
if (!stack2.isEmpty()) {
int i = stack1.pop();
stack2.push(i);
return i;
} else {
throw new RuntimeException("Stack is Empty");
}
}
}栈的压入、弹出序列
问题描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解题思路
模拟堆栈操作的过程，将原数列依次压栈，把栈顶元素与所给出栈队列相比，如果相同则出栈，如果不同则继续压栈，直到原数列中所有数字压栈完毕。最后，检测栈中是否为空，若空，说明出栈队列可由原数列进行栈操作得到。否则，说明出栈队列不能由原数列进行栈操作得到。
public boolean isPopOrder(int[] push, int[] pop) {
if (push.length != pop.length || push.length == 0 || pop.length == 0)
return false;
Stack<Integer> stack = new Stack<>();
int index = 0;
for (int i = 0; i < push.length; i++) {
stack.push(push[i]);
while (!stack.isEmpty() && stack.peek() == pop[index]) {
stack.pop();
index++;
}
}
return stack.isEmpty();
}广度优先遍历二叉树
问题描述
广度优先遍历二叉树
解题思路
借助集合逐层遍历
public void print(TreeNode node) {
if (node == null) return;
List<TreeNode> list = new ArrayList<>();
list.add(node);
for (int i = 0; i < list.size(); i++) {
System.out.println(" " + list.get(i).value);
if (list.get(i).left != null) {
list.add(list.get(i).left);
}
if (list.get(i).right != null) {
list.add(list.get(i).right);
}
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-03-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录