16.?合并两个排序的链表
描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
分析
借助辅助指针
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode list3 = new ListNode(Integer.MIN_VALUE);
ListNode cur = list3;
while (list1 != null && list2 != null)
{
if (list1.val < list2.val)
{
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}
else
{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if (list1 == null)
{
cur.next = list2;
}
else
{
cur.next = list1;
}
//注意这里返回的是list3的next而不是cur的，cur一直在指向两个参数中listnode的更小值
return list3.next;
}
}
?
17.??树的子结构
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null)
{
return false;
}
// 如果A和B在当前树节点相等则调用judge方法继续判断下去，否则递归继续调用该方法，移动A树
// 节点并且继续与B的当前树节点进行判断
if (root1.val == root2.val)
{
if (judge(root1, root2))
return true;
}
// 注意此处使用的是||运算符，因为找的是A中任意一块部分和B完全一致，B就可以是A的子结构了
return (HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2));
}
public boolean judge(TreeNode root1,TreeNode root2)
{
// B被遍历完，因此A中有和B完全一致的部分，返回true
if (root2 == null)
return true;
// B没有被遍历完，A中没有和B完全一致的部分，返回false
if (root1 == null)
return false;
// 如果在当前A和B的树节点相等，则用&&运算符继续判断接下来的左右树节点是否完全一致
if (root1.val == root2.val)
{
return (judge(root1.left, root2.left) && judge(root1.right, root2.right));
}
return false;
}
}
18.?二叉树的镜像?
描述
操作给定的二叉树，将其变换为源二叉树的镜像。
分析
注意使用递归的思想，并且借助辅助树节点交换源树的左右节点
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
if (pRoot == null)
return null;
TreeNode tmp = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = tmp;
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
}
19.?顺时针打印矩阵?
描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
则依次打印出数字
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
分析
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<Integer>();
int right = 0, down = 0, left = matrix[0].length-1, up = matrix.length-1;
while (true)
{
for (int i=right; i<left+1; i++)
list.add(matrix[down][i]);
if (++down > up)
break;
for (int i=down; i<up+1; i++)
list.add(matrix[i][left]);
if (--left < right)
break;
for (int i=left; i>=right; i--)
list.add(matrix[up][i]);
if (--up < down)
break;
for (int i=up; i>=down; i--)
list.add(matrix[i][right]);
if (++right > left)
break;
}
return list;
}
}
20.??包含min函数的栈
描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
分析
注意min()的时间复杂度为O(1)
import java.util.Stack;
public class Solution {
//借助辅助栈sb完成时间复杂度是O(1)的min()方法
Stack<Integer> sa = new Stack<Integer>();
Stack<Integer> sb = new Stack<Integer>();
public void push(int node) {
sa.push(node);
if(sb.empty() || node<sb.peek())
{
sb.push(node);
}
else
sb.push(sb.peek());
}
public void pop() {
sa.pop();
sb.pop();
}
public int top() {
return sa.peek();
}
public int min() {
return sb.peek();
}
}
|