本文按照牛客網(wǎng)的順序睛竣，盼浚客網(wǎng)劍指offer刷題網(wǎng)址：https://www.nowcoder.com/ta/coding-interviews
本篇涉及的題目有：
1、順時(shí)針打印矩陣
2射沟、包含min函數(shù)的棧
3殊者、棧的壓入、彈出序列
4验夯、從上往下打印二叉樹
5猖吴、二叉搜索樹的后序遍歷序列
6、二叉樹中和為某一值的路徑
1挥转、順時(shí)針打印矩陣
問題描述
輸入一個(gè)矩陣海蔽，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，例如绑谣，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路解析
1党窜、首先可以看到，第一圈的第一個(gè)元素是（0借宵，0）幌衣，第二圈是（1，1）壤玫，所以我們可以找到左上角元素的規(guī)律
2豁护、這樣，我們可以循環(huán)的打印每一圈的值欲间，不過要注意最后一圈的情況
3楚里、打印第一行不會有問題
4、打印第一列括改，要保證最后一圈至少有兩行
5腻豌、打印第二行家坎，不僅要至少有兩行，而且至少有兩列
6吝梅、打印第二列虱疏，我們至少要有三行，兩列才可以
代碼實(shí)現(xiàn)
java
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> arr = new ArrayList<Integer>();
public ArrayList<Integer> printMatrix(int [][] matrix) {
if(matrix.length == 0)
return arr;
int rows = matrix.length;
int cols = matrix[0].length;
int start = 0;
while(rows > start * 2 && cols > start * 2){
printOneCircle(matrix,start,rows,cols);
start += 1;
}
return arr;
}
public void printOneCircle(int[][] matrix,int start,int rows,int cols){
int endrow = rows - start - 1;
int endcol = cols - start - 1;
for(int i=start;i<=endcol;i++){
arr.add(matrix[start][i]);
}
if(endrow > start)
for(int i = start+1;i<=endrow;i++){
arr.add(matrix[i][endcol]);
}
if(endrow > start && endcol > start)
for(int i=endcol - 1;i>=start;i--){
arr.add(matrix[endrow][i]);
}
if(endrow > start + 1 && endcol > start)
for(int i = endrow - 1;i>start;i--){
arr.add(matrix[i][start]);
}
}
}
python
# -*- coding:utf-8 -*-
class Solution:
# matrix類型為二維列表苏携，需要返回列表
def __init__(self):
self.res = []
def printMatrix(self, matrix):
# write code here
if not matrix:
return []
start = 0
rows = len(matrix)
cols = len(matrix[0])
while (rows > start * 2 and cols > start * 2):
self.printOneCircle(matrix,rows,cols,start)
start += 1
return self.res
def printOneCircle(self,matrix,rows,cols,start):
endrow = rows - 1 - start
endcol = cols - 1 - start
for i in range(start,endcol+1):
self.res.append(matrix[start][i])
if endrow > start:
for i in range(start+1,endrow+1):
self.res.append(matrix[i][endcol])
if endrow > start and endcol > start:
for i in range(endcol-1,start-1,-1):
self.res.append(matrix[endrow][i])
if endcol > start and (endrow - start > 1):
for i in range(endrow-1,start,-1):
self.res.append(matrix[i][start])
2做瞪、包含min函數(shù)的棧
問題描述
定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)右冻。
思路解析
單獨(dú)設(shè)計(jì)一個(gè)新棧装蓬，保存到當(dāng)前棧頂時(shí)棧的最小元素。
代碼實(shí)現(xiàn)
java
import java.util.Stack;
public class Solution {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
stack.push(node);
if(minStack.empty() || node < minStack.peek())
minStack.push(node);
else
minStack.push(minStack.peek());
}
public void pop() {
if(!stack.empty()){
stack.pop();
minStack.pop();
}
}
public int top() {
if(!stack.empty()){
return stack.peek();
}
else
return -1;
}
public int min() {
if(!minStack.empty())
return minStack.peek();
else
return -1;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, node):
# write code here
self.stack.append(node)
if not self.minStack or node < self.minStack[-1]:
self.minStack.append(node)
else:
self.minStack.append(self.minStack[-1])
def pop(self):
# write code here
if self.stack:
self.stack.pop()
self.minStack.pop()
def top(self):
# write code here
if self.stack:
return self.stack[-1]
else:
return None
def min(self):
# write code here
if self.minStack:
return self.minStack[-1]
else:
return None
3纱扭、棧的壓入牍帚、彈出序列
問題描述
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序乳蛾，請判斷第二個(gè)序列是否為該棧的彈出順序暗赶。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序肃叶，序列4蹂随，5,3,2,1是該壓棧序列對應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列因惭。（注意：這兩個(gè)序列的長度是相等的）
思路解析
模擬兩個(gè)棧的彈入彈出即可
代碼實(shí)現(xiàn)
java
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int index = 0;
for(int i=0 ;i<pushA.length;i++){
if(pushA[i] == popA[index]){
index += 1;
continue;
}
stack.push(pushA[i]);
}
for(;index<popA.length;index++){
if(popA[index]!=stack.pop())
return false;
}
return true;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
stack = []
index = 0
for i in pushV:
if i == popV[index]:
index = index + 1
continue
stack.append(i)
while index < len(popV):
if popV[index] != stack.pop():
return False
index = index + 1
return True
4岳锁、從上往下打印二叉樹
問題描述
從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印蹦魔。
思路解析
層次遍歷的思路激率。
代碼實(shí)現(xiàn)
java
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
Deque<TreeNode> deque = new LinkedList<TreeNode>();
deque.add(root);
while(!deque.isEmpty()){
TreeNode t = deque.pop();
list.add(t.val);
if(t.left != null) deque.add(t.left);
if(t.right != null) deque.add(t.right);
}
return list;
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回從上到下每個(gè)節(jié)點(diǎn)值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root:
return []
stack = [root]
res = []
while stack:
level = stack
stack = []
for node in level:
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res
5版姑、二叉搜索樹的后序遍歷序列
問題描述
輸入一個(gè)整數(shù)數(shù)組柱搜，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No剥险。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同聪蘸。
思路解析
遞歸進(jìn)行判斷，如果序列的長度小于等于2表制，那么一定是后序遍歷的結(jié)果健爬，否則根據(jù)BST和后序遍歷的性質(zhì)，遍歷結(jié)果的最后一個(gè)一定是根節(jié)點(diǎn)么介，那么序列中前面一部分小于根節(jié)點(diǎn)的數(shù)是左子樹娜遵，后面一部分是右子樹，遞歸進(jìn)行判斷壤短。
代碼實(shí)現(xiàn)
java
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0)
return false;
return isSequenceOfBST(sequence,0,sequence.length-1);
}
public boolean isSequenceOfBST(int[] sequence,int start,int end){
if(end - start < 2)
return true;
int flag = sequence[end];
int index = start;
while(sequence[index] < flag)
index += 1;
int j = index;
while(j<end){
if(sequence[j] < flag)
return false;
j += 1;
}
return isSequenceOfBST(sequence,start,index-1) && isSequenceOfBST(sequence,index,end-1);
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
# 7465 的問題
# [] 的問題,即開始和中間過程中出現(xiàn)的[]的處理是不同的设拟，所以定義了一個(gè)子函數(shù)
if len(sequence) == 0:
return False
return self.verifySubSequenceOfBST(sequence)
def verifySubSequenceOfBST(self, sequence):
if len(sequence) < 3:
return True
flag = sequence[-1]
index = 0
while sequence[index] < flag:
index = index + 1
j = index
while j < len(sequence) - 1:
if sequence[j] > flag:
j = j + 1
else:
return False
return self.verifySubSequenceOfBST(sequence[:index]) and self.verifySubSequenceOfBST(sequence[index:-1])
6慨仿、二叉樹中和為某一值的路徑
問題描述
輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑纳胧。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑镰吆。
思路解析
定義一個(gè)子函數(shù)，輸入的是當(dāng)前的根節(jié)點(diǎn)跑慕、當(dāng)前的路徑以及還需要滿足的數(shù)值万皿，同時(shí)在子函數(shù)中運(yùn)用回溯的方法進(jìn)行判斷。
代碼實(shí)現(xiàn)
java
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> arrs = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root==null)
return arrs;
ArrayList<Integer> arr = new ArrayList<Integer>();
subPath(root,arr,target);
return arrs;
}
public void subPath(TreeNode node,ArrayList<Integer> arr,int target){
if(node.left==null && node.right==null && target==node.val){
arr.add(node.val);
arrs.add(arr);
return;
}
arr.add(node.val);
ArrayList<Integer> left = (ArrayList<Integer>)arr.clone();
ArrayList<Integer> right = (ArrayList<Integer>)arr.clone();
arr = null;
if(node.left!=null){
subPath(node.left,left,target-node.val);
}
if(node.right!=null){
subPath(node.right,right,target-node.val);
}
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.res = []
# 返回二維列表核行，內(nèi)部每個(gè)列表表示找到的路徑
def FindPath(self, root, expectNumber):
# write code here
if not root:
return []
self.subPath(root,[],expectNumber)
return self.res
def subPath(self, root, path,number):
if not root.left and not root.right:
if number == root.val:
self.res.append(path+[root.val])
return
if root.left:
self.subPath(root.left,path+[root.val],number-root.val)
if root.right:
self.subPath(root.right,path+[root.val],number-root.val)
