一般般帅
上一篇:13~18题
19~24题
2036 2018-11-16 2020-06-25
前言：牛客网剑指Offer编程题19~24题。
一、顺时针打印矩阵
1、题目描述
考点让抽象形象化，输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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。
2、我的代码
static class Nineteen {
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return list;
}
int i = 0;
while (list.size() != matrix.length * matrix[0].length) {
dealOne(i++, matrix, list);
}
return list;
}
private void dealOne(int index, int[][] arr, ArrayList<Integer> list) {
int i = index;
int j = i;
int iEnd = arr.length - 1 - i;
int jEnd = arr[0].length - 1 - i;
if (i == iEnd) {
for (;j <= jEnd; j++) {
list.add(arr[i][j]);
}
return;
} else if (j == jEnd) {
for (;i <= iEnd; i++) {
list.add(arr[i][j]);
}
return;
}
do {
list.add(arr[i][j]);
if (i < iEnd && j < jEnd) {
j++;
} else if (i < iEnd) {
i++;
}
} while (i != iEnd || j != jEnd);
do {
list.add(arr[i][j]);
if (i != index && j != index) {
j--;
} else if (i != index){
i--;
}
} while (i != index);
}
private static void test() {
int[][] arr = new int[][]{
{1, 2, 3, 4},
{2, 3, 4, 5},
{3, 4, 5, 6},
{4, 5, 6, 7},
{5, 6, 7, 8}
};
int[][] arr1 = new int[][]{
{1}, {2}, {3}, {4}, {5}
};
List<Integer> list = new Nineteen().printMatrix(arr1);
System.out.println(list);
}
}
我的思路就是由外而内，一个一个来。
3、思路总结
这个问题有几个难点：
- 一是圈数的确定，这里我偷了个懒，直接使用list.size() != matrix.length * matrix[0].length来判断，更为聪明的一种判断方法是circle = ((row > col ? col : row ) + 1 ) / 2。首选圈数是取决于最小的那个，其次可以通过发现确定出这个值。
- 二就是方向的变换，需要确定边界初始值和终止值。我是由外到内，采用递归的思想。还有其他的思路：如不使用递归，直接通过几个变量完全控制遍历的方向、如还有一种旋转解法，每次都取第一行，取完就逆时针旋转。
二、包含min函数的栈
1、问题描述
考点举例让抽象具体化，定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
2、我的代码
static class Twenty {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
public void push(int node) {
list1.add(node);
if (list2.size() == 0) {
list2.add(node);
} else {
int min = min();
if (min > node) {
list2.add(node);
} else {
list2.add(min);
}
}
}
public void pop() {
if (list1.size() != 0) {
list1.remove(list1.size() - 1);
list2.remove(list2.size() - 1);
}
}
public int top() {
if (list1.size() != 0) {
return list1.get(list1.size() - 1);
} else {
throw new RuntimeException("空栈");
}
}
public int min() {
if (list2.size() != 0) {
return list2.get(list2.size() - 1);
} else {
throw new RuntimeException("空栈");
}
}
}
之前题目理解的有错误，后面改正了
三、栈的压入、弹出序列
1、题目描述
考点举例让抽象具体化，输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）。
2、我的代码
思路还是采用模拟栈的真实压入弹出，需要注意的是i和j所代表的含义。
static class TwentyOne {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int i = 0;
int j = i;
while (i != pushA.length) {
if (pushA[i] != popA[j]) {
stack.push(pushA[i]);
i++;
} else {
i++;
j++;
}
}
while (!stack.isEmpty()) {
if (j == pushA.length || popA[j++] != stack.pop()) {
return false;
}
}
return true;
}
private static void test() {
int[] arr = new int[]{1,2,3,4,5};
int[] arr1 = new int[]{1,2,5,4,3};
int[] arr2 = new int[]{2,1,5,3,4};
int[] arr3 = new int[]{1,2,3,4,5};
int[] arr4 = new int[]{3,5,4,2,1};
boolean result = new TwentyOne().IsPopOrder(arr, arr1);
System.out.println(result);
}
}
3、python二刷
牛客网有点坑，转战lettcode。
class Solution(object):
def validateStackSequences(self, pushV, popV):
stack = list()
_len = len(pushV)
i, j = 0, 0
while i < len(pushV):
if pushV[i] != popV[j]:
if not stack or stack[-1] != popV[j]:
stack.append(pushV[i])
elif stack[-1] == popV[j]:
stack.pop()
j += 1
i -= 1
elif pushV[i] == popV[j]:
j += 1
i += 1
while len(stack) != 0:
if stack.pop() != popV[j]:
return False
j += 1
return len(stack) == 0
四、从上往下打印二叉树
1、题目描述
考点举例让抽象具体化，从上往下打印出二叉树的每个节点，同层节点从左至右打印。
2、我的代码
// 其实就是广度遍历
static class TwentyTwo {
static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}
}
3、python二刷
def PrintFromTopToBottom(self, root):
_list = list()
_stack = list()
_stack.append(root)
while len(_stack) != 0:
head = _stack.pop(0)
if head is None:
continue
_list.append(head.val)
_stack.append(head.left)
_stack.append(head.right)
return _list
太简单了。
五、二叉搜索树的后序遍历序列
1、题目描述
考点举例让抽象具体化，输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输入的数组的任意两个数字都互不相同。
2、我的代码
static class TwentyThree {
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
int index = index(sequence);
// 顺序不符合遍历规则
if (index == -1) {
return false;
} else if (index == sequence.length - 1 || index == 0) {
// 针对两种极端情况
return true;
}
int[] left = left(index, sequence);
int[] right = right(index, sequence);
return VerifySquenceOfBST(left) && VerifySquenceOfBST(right);
}
private int index(int[] arr) {
int index = -1;
// 找到分界点，这里偏向后半部分（也可以偏向前部分），前半部分都小于最后值，后半部分都大于最后值
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= arr[arr.length - 1]) {
index = i;
break;
}
}
// 处理54321极端情况
if (index == 0) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
continue;
}
return -1;
}
return 0;
}
// 判断后半部分是否存在小于分界点的值，最后值除外
for (int i = index + 1; i < arr.length - 1; i++) {
if (arr[i] < arr[index]) {
return -1;
}
}
// 注意这里会存在12345的极端情况
if (index == arr.length - 1) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < arr[i + 1]) {
continue;
}
return -1;
}
return arr.length - 1;
}
return index;
}
private int[] left(int index, int[] arr) {
int[] left = new int[index];
for (int i = 0; i < left.length; i++) {
left[i] = arr[i];
}
return left;
}
private int[] right(int index, int[] arr) {
int[] right = new int[arr.length - index - 1];
for (int i = 0; i < right.length; i++) {
right[i] = arr[index + i];
}
return right;
}
private static void test() {
int[] arr = new int[]{3,5};
int[] arr1 = new int[]{2,4,3,6,8,7,5};
int[] arr2 = new int[]{1,2,3,4,5};
int[] arr3 = new int[]{5,4,3,2,1};
boolean result = new TwentyThree().VerifySquenceOfBST(arr3);
System.out.println(result);
}
}
我觉得我的思想还是不错的。
3、python二刷
class Solution:
def VerifySquenceOfBST(self, sequence):
if not sequence:
return False
tail = sequence[-1]
in_seq = sorted(sequence)
index = in_seq.index(tail)
left_arr = sequence[0:index]
right_arr = sequence[index:len(sequence) - 1]
for i in left_arr:
if i >= tail:
return False
for i in right_arr:
if i <= tail:
return False
if (left_arr and not self.VerifySquenceOfBST(left_arr)) or (right_arr and not self.VerifySquenceOfBST(right_arr)):
return False
return True
豁然开朗。
六、二叉树中和为某一值的路径
1、题目描述
考点举例让抽象具体化，输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径（注意: 在返回值的list中，数组长度大的数组靠前）。
2、我做不出来
我放弃了。
3、别人的代码
static class TwentyFour {
static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
ArrayList<Integer> list = new ArrayList<>();
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root == null) {
return lists;
}
list.add(root.val);
int needValue = target - root.val;
if (needValue == 0 && root.left == null && root.right == null) {
lists.add(new ArrayList<>(list));
}
FindPath(root.left, needValue);
FindPath(root.right, needValue);
list.remove(list.size() - 1);
return lists;
}
public static void test() {
TreeNode node1 = new TreeNode(10);
TreeNode node2 = new TreeNode(5);
TreeNode node3 = new TreeNode(12);
TreeNode node4 = new TreeNode(3);
TreeNode node5 = new TreeNode(7);
// TreeNode node5 = new TreeNode(1);
// TreeNode node6 = new TreeNode(1);
// TreeNode node7 = new TreeNode(3);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
System.out.println(new TwentyFour().FindPath(node1, 22));
}
}
这种思路很神奇，需要好好体会。本来一天6道题的，结果被这道题拖了3天，我承认我心态有点崩了。
4、python二刷
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
all_list = list()
temp_list = list()
cur_value = 0
count_value(root, cur_value, expectNumber, temp_list, all_list)
return all_list
def count_value(root, cur_value, expectNumber, temp_list, all_list):
if not root:
return
if root.val + cur_value < expectNumber:
temp_list.append(root.val)
count_value(root.left, cur_value + root.val, expectNumber, temp_list, all_list)
count_value(root.right, cur_value + root.val, expectNumber, temp_list, all_list)
temp_list.pop()
elif root.val + cur_value == expectNumber and not root.left and not root.right:
temp_list.append(root.val)
all_list.append(list(temp_list))
temp_list.pop()
算法真的有意思。
总访问次数: 295次, 一般般帅 创建于 2018-11-16, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！