- 1.二維數(shù)組中的查找
題目描述
在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
思路：比較矩陣的右上角的數(shù)與target的大小，如果target比這個矩陣右上角的數(shù)大，由于矩陣的右上角的元素值是其所在行的最大的值，所以target肯定不在其所在的行了，所以這時候就應該在其下一行中去找這個target;
如果target比矩陣右上角的數(shù)A小，那么由于A所在的列中A是最小的，那么target就在其左邊的列中。
如果相等，返回true;
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;
while(row < array.length && col >= 0){
if(array[row][col] == target){
return true;
}else if(target > array[row][col]){
row++;
}else{
col--;
}
}
return false;
}
}
- 2.替換空格
題目描述
請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成“%20”。例如，當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
思路：兩種方式
① 如果允許使用StringBuffer自帶的函數(shù)如append()，則非常容易解決。見代碼函數(shù)replaceSpace1()。
②如果不允許使用StringBuffer自帶的函數(shù)，則理解為一個空格變成了%20，也就是說每有一個空格，長度要增加2，所以首先先計算有多少個空格，這樣長度就能增加多少，得到增加后的長度newStrLength。之后創(chuàng)建一個長度為newStrLength的字符數(shù)組，從尾到頭開始復制原來的數(shù)組，在復制的過程中，如果字符不是空格，直接復制，如果字符是空格，那么需要把這個空格變成%20（這個復制過程就是把新建的數(shù)組比如現(xiàn)在到了 K這個位置，然后就是K，K-1，K-2這三個位置依次變成0,2，%這三個字符，因為是從后往前復制的所以是倒序），重復這個過程就行。
public String replaceSpace(StringBuffer str) {
if(str == null){
return null;
}
StringBuffer result = new StringBuffer();
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' '){
result.append("%");
result.append("2");
result.append("0");
}else{
result.append(str.charAt(i));
}
}
return result.toString();
}
public String replaceSpace2(StringBuffer str) {
String str1 = str.toString();
if(str1.equals("")){
return str1;
}
int SpaceLength = 0;
char[] charArray = str1.toCharArray();
for(int i = 0; i < charArray.length;i++){
if(charArray[i] == ' '){
SpaceLength++;
}
}
int newStrLength = charArray.length + SpaceLength*2;
char[] resultCharArray = new char[newStrLength];
int j = resultCharArray.length - 1;
int i = charArray.length - 1;
while(i >= 0){
if(charArray[i] != ' '){
resultCharArray[j--] = charArray[i--];
}else{
resultCharArray[j--] = '0';
resultCharArray[j--] = '2';
resultCharArray[j--] = '%';
i--;
}
}
return new String(resultCharArray);
}
- 3.從尾到頭打印鏈表
題目描述
輸入一個鏈表，按鏈表值從尾到頭的順序返回一個ArrayList。
思路：
①劍指offer的思路，遞歸的思路，只要鏈表不為空，一直往后進行遍歷，然后直到到達鏈表的末尾，就開始用數(shù)組保存下來結果。
②如果?？捎玫那闆r下，先將鏈表值逐一入棧，再將棧內值逐一彈出至ArrayList中。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
if(listNode == null){
return result;
}
printListFromTailToHead(listNode,result);
return result;
}
public void printListFromTailToHead(ListNode listNode,ArrayList<Integer> list){
if(listNode.next != null){
printListFromTailToHead(listNode.next,list);
}
list.add(listNode.val);
}
public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> result = new ArrayList<>();
while(!stack.isEmpty()){
result.add(stack.pop());
}
return result;
}
}
- 4.用兩個棧實現(xiàn)隊列
題目描述
用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。
思路：針對隊列的push方法，使用棧的push()方法即可，對于隊列的pop方法，則需要將棧1的元素先逐一丟到棧二中，并把棧二的頂部元素返回，再丟回棧一中，以滿足先入先出的順序。
import java.util.Stack;
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() {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
int result = stack2.pop();
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return result;
}
}
- 5.旋轉數(shù)組的最小數(shù)字
題目描述
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。 輸入一個非減排序的數(shù)組的一個旋轉，輸出旋轉數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。
思路：根據(jù)題意說明是一個遞增數(shù)組的旋轉，所以如題所示【3,4,5】，【1,2】還是局部遞增的，使用二分的方式解答：
1.先取出array[mid]，和array[end]比較，如果array[mid]>array[end]，則說明mid之前的某些部分旋轉到了后面，所以下次尋找 start = mid+1 開始。
2.取出的array[mid]<array[end]，則說明從array[mid]到array[end]之間都應為被旋轉的部分，所以最小應該在mid的前面，但是也有可能當前的mid 就是最小的值 所以下次所需找的元素所在區(qū)間必然是【start,mid】故令end = mid。
3.當array[mid] = array[end]的時候，說明數(shù)組中存在著相等的數(shù)值，可能是這樣的形式 【2,2,2,2,1,2】所以 選擇start加1作為下次尋找的上界。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
if(array[array.length-1] > array[0]){
return array[0];
}
int start = 0;
int end = array.length - 1;
while(start != end){
int mid = (start + end) / 2;
if(array[mid] > array[end]){
start = mid + 1;
}else if(array[mid] < array[end]){
end = mid;
}else{
start++;
}
}
return array[end];
}
}
- 6.斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項（從0開始，第0項為0）。(n<=39)
思路：①遞歸（測試用例中肯定有一個棧深度極深，然后溢出）
②劍指offer思路，每次使用兩個變量a,b來計算下一個數(shù)的值sum,然后a,b,sum分別是斐波那契數(shù)列中的三個數(shù)，那么就令a=b,b=sum,這樣a和b就往下移動了一個位置，再計算sum就是第4個數(shù)了，重復這個過程即可。
public class Solution {
//遞歸方法
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n <= 1){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
//非遞歸方法
public int Fibonacci2(int n) {
int first = 0;
int second = 1;
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int sum = 0;
for(int i = 2; i <= n; i++){
sum = first+second;
first = second;
second = sum;
}
return sum;
}
}
- 7.跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。
思路：①遞歸
② 每次使用兩個變量a,b來計算下一個數(shù)的值sum,然后a,b,sum分別是斐波那契數(shù)列中的三個數(shù)，那么就令a=b,b=sum,這樣a和b就往下移動了一個位置，再計算sum就是第4個數(shù)了，重復這個過程即可。
public class Solution {
//遞歸方法
public int JumpFloor(int target) {
if(target == 0){
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2){
return 2;
}
return JumpFloor(target-1)+JumpFloor(target-2);
}
//非遞歸方法
public int JumpFloor(int target) {
if (target == 1) {
return 1;
}
if (target == 2){
return 2;
}
int first = 1;
int second = 2;
int sum = 0;
for(int i = 3; i <= target; i++){
sum = first + second;
first = second;
second = sum;
}
return sum;
}
}
- 8.變態(tài)跳臺階
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
思路： ①動態(tài)規(guī)劃法
② 因為n級臺階，第一步有n種跳法：跳1級、跳2級、到跳n級
跳1級，剩下n-1級，則剩下跳法是f(n-1)
跳2級，剩下n-2級，則剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因為f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
public class Solution {
//動態(tài)規(guī)劃
public int JumpFloorII(int target) {
if(target == 0) {
return 0;
}
int[] dp = new int[target+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= target; i++){
dp[i] = 0;
for(int j = 0; j < i; j++){
dp[i] += dp[j];
}
}
return dp[target];
}
}
//數(shù)學歸納法
public int JumpFloorII(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
return 2 * JumpFloorII(target - 1);
}
}
- 9.矩形覆蓋
題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
思路： ①遞歸
②每次使用兩個變量a,b來計算下一個數(shù)的值sum,然后a,b,sum分別是數(shù)列中的三個數(shù)，那么就令a=b,b=sum,這樣a和b就往下移動了一個位置，再計算sum就是第4個數(shù)了，重復這個過程即可。
public class Solution {
public int RectCover(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
int first = 1;
int second = 2;
int sum = 0;
for(int i = 3; i <= target; i++){
sum = first+second;
first = second;
second = sum;
}
return sum;
}
}
- 10.二進制中1的個數(shù)
題目描述
輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。其中負數(shù)用補碼表示。
思路：思路
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
}
- 11.鏈表中倒數(shù)第k個結點
題目描述
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點。
思路：快慢指針，快指針先走k-1步，然后快慢指針一起走，當快指針走到末尾，那么慢指針就到了倒數(shù)第K個節(jié)點了。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){
return null;
}
int length = 0;
ListNode temp = head;
while(temp != null){
length++;
temp = temp.next;
}
if(length < k){
return null;
}
ListNode fast_p = head;
ListNode slow_p = head;
for(int i = 0; i < k; i++){
fast_p = fast_p.next;
}
while(fast_p != null){
slow_p = slow_p.next;
fast_p = fast_p.next;
}
return slow_p;
}
}
- 12.翻轉鏈表
題目描述
輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。
思路：快慢指針，快指針先走k-1步，然后快慢指針一起走，當快指針走到末尾，那么慢指針就到了倒數(shù)第K個節(jié)點了。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null){
return head;
}
ListNode newH = null;
ListNode p = head;
while(p != null){
ListNode temp = p.next;
p.next = newH;
newH = p;
p = temp;
}
return newH;
}
}
- 12.合并兩個排序的鏈表
題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規(guī)則。
思路：歸并排序
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
curr.next = list1;
curr = curr.next;
list1 = list1.next;
}else{
curr.next = list2;
curr = curr.next;
list2 = list2.next;
}
}
if(list1 != null){
curr.next = list1;
}
if(list2 != null){
curr.next = list2;
}
return dummy.next;
}
}
- 13.數(shù)值的整數(shù)次方
題目描述
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
思路：窮舉
public class Solution {
public double Power(double base, int exponent) {
if(exponent == 0){ //指數(shù)是0
if(equalZero(base) == true){
return 0; //如果底數(shù)是0則返回0
}
return 1;//除了0的任何數(shù)的0次方是1
}
if(exponent > 0){
return complex(base,exponent);//直接計算base的exponent次方返回即可
}
if(equalZero(base)){
if(base > 0){
return Double.POSITIVE_INFINITY; //底數(shù)是正0
}
if(exponent % 2 == 0){//指數(shù)是偶數(shù)次方
return Double.POSITIVE_INFINITY;//返回正無窮
}
return Double.NEGATIVE_INFINITY;
}
return 1/complex(base,exponent);
}
double complex(double base,int exponent){
double result = 1.0;
if(exponent < 0)//如果指數(shù)小于0，比如2的-3次方，先計算2的3次方，然后求倒數(shù)
exponent = 0 - exponent;
for(int i = 0; i < exponent; i++)
result = result * base;
return result;
}
boolean equalZero(double base){
//判斷一個doule類型的數(shù)是不是0，必須這樣判斷，不能直接與0進行比較，因為浮點數(shù)本身不精確
if(base >0 && base < 0.00000001)
return true;
if(base < 0 && base > -0.00000001)
return true;
return false;
}
}
- 14.調整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目描述
輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。
思路：題目明確說了，不能修改相對位置，所以只能是用以下的新建兩個數(shù)組，一個奇數(shù)數(shù)組，一個偶數(shù)數(shù)組，然后把奇數(shù)和偶數(shù)分別保存到對應的數(shù)組，然后在賦值到原數(shù)組中.
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> odd = new ArrayList<>();
ArrayList<Integer> even = new ArrayList<>();
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
odd.add(array[i]);
}else{
even.add(array[i]);
}
}
for(int i = 0; i< odd.size();i++){
array[i] = odd.get(i);
}
for(int i = 0; i< even.size();i++){
array[odd.size()+i] = even.get(i);
}
}
}
- 15.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)
題目描述
數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。
思路：使用一個計數(shù)count = 1，并以number=array[0],每當數(shù)組中數(shù)和當前數(shù)number相同，那么count就加1，不相同就減1，因為是找出現(xiàn)的數(shù)超過數(shù)組的長度的一半，所以最后如果有出現(xiàn)的數(shù)超過數(shù)組長度一半的，count肯定是大于0的數(shù)。但是有一種特殊情況，即最后連續(xù)出現(xiàn)兩次該數(shù)，也可能導致count > 0，因此需要再次遍歷鏈表確定是否大于鏈表長度的1/2。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0){
return 0;
}
int count = 1;
int number = array[0];
for(int i = 1; i < array.length; i++){
if(array[i] == number){
count++;
}else{
count--;
if(count == 0){
number = array[i];
count = 1;
}
}
}
if(count > 0){
count = 0;
for(int i = 0; i < array.length; i++){
if(number == array[i]){
count++;
}
}
if(count > array.length/2){
return number;
}
}
return 0;
}
}
- 16.二叉樹的鏡像
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像。
思路：使用臨時變量保存左子樹（否則會被修改）。遞歸處理左右子樹。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null){
Mirror(root.left);
}
if(root.right != null){
Mirror(root.right);
}
}
}
}
- 17.第一個只出現(xiàn)一次的字符
題目描述
在一個字符串(0<=字符串長度<=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）.
思路：字符串中的字符都是英文的字母，所以每一個字母都有一個ASCII碼與其對應，然后建立一個字符數(shù)組長度是256，可以把每一個字符對應一個數(shù)組的下標
然后設立一個index！然后比如字符a第一次出現(xiàn)那么strArray[a字符對應的ASC碼] = index;然后如果下一次a再出現(xiàn)了，那么strArray[a字符對應的ASC碼] = -1；這樣子做，只要字符出現(xiàn)了大于等于2次，都會這樣子等于-1
而只出現(xiàn)一次的字符，由于index這個變量是每次遞增的！我們只需要遍歷一遍，找index最小的那個字符。
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str.equals("")){
return -1;
}
int[] temp = new int[256];
int index = 1;
char[] charArray = str.toCharArray();
for(int i = 0; i < charArray.length; i++){
if(temp[(int)charArray[i]] == 0){
temp[(int)charArray[i]] = index;
index++;
}else{
temp[(int)charArray[i]] = -1;
}
}
int minIndex = Integer.MAX_VALUE;
char ch = '1';
for(int i=0; i < temp.length; i++){
if(temp[i] > 0)
{
if(temp[i] < minIndex)
{//找最小的index對應的字符
minIndex = temp[i];
ch = (char)i;
}
}
}
int result = -1;
for(int i=0;i<charArray.length;i++)
{//去找這個字符的下標！
if(charArray[i] == ch)
return i;
}
return -1;
}
}
- 18.二叉樹的深度
題目描述
輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經(jīng)過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
思路：遞歸
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private int max_depth;
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left_depth = TreeDepth(root.left);
int right_depth = TreeDepth(root.right);
int max_depth = Math.max(left_depth,right_depth)+1;
return max_depth;
}
}
- 19.平衡二叉樹
題目描述
輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。
思路：遞歸
/**
public class Solution {
private boolean result = true;
public boolean IsBalanced_Solution(TreeNode root) {
maxDepth(root);
return result;
}
public int maxDepth(TreeNode root){
if(root == null){
return 0;
}
int left_depth = maxDepth(root.left);
int right_depth = maxDepth(root.right);
if ((Math.abs(left_depth-right_depth))>1){
result = false;
}
return Math.max(left_depth,right_depth)+1;
}
}
- 20.對稱二叉樹
題目描述
請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
思路：遞歸
/**
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
return isMirror(pRoot,pRoot);
}
boolean isMirror(TreeNode t1,TreeNode t2){
if(t1 == null && t2 == null){
return true;
}
if(t1 == null || t2 == null){
return false;
}
return ((t1.val == t2.val)&& isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left));
}
}
``
- **21.不用加減乘除做加法**
>**題目描述**
寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內不得使用+、-、*、/四則運算符號。
>**思路**：先想之前的十進制怎么加減，以5+8為例子，先進行按位計算，得到3，再考慮進位，得到10。之后再將10和3按位相加得到結果13。二進制也可以類似這樣的方法，舉個例子 4+5（即二進制100 + 101）先讓其按位進行異或運算，得到001先保存，在讓兩者進行按位與運算，得100，為其進位為，在將其左移一位，得1000。再令1000和001進行抑或運算得1001，再進行按位與運算，得0，跳出循環(huán)，則結果就是1001。
/**
/*
public class Solution {
public int Add(int num1,int num2) {
int sum = 0;
int carry = 0;
do{
sum = num1 ^ num2;
carry = num1 & num2;
if(carry != 0){
carry = carry << 1;
}
num1 = sum;
num2 = carry;
}while(carry != 0);
return sum;
}
}
- **22.求1+2+3+...+n**
>**題目描述**
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。
>**思路**：使用&&運算中的短路思想，遞歸的解決問題。
public class Solution {
private int result = 0;
public int Sum_Solution(int n) {
complex(n);
return result;
}
public int complex(int n){
boolean flag = (n-1) >= 0 && (result = result + n) > 0 && complex(n-1) > 0;
return result;
}
}
- **23.包含min函數(shù)的棧**
>**題目描述**
定義棧的數(shù)據(jù)結構，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復雜度應為O（1））。
>**思路**：使用一個輔助棧去維護最小值。
import java.util.Stack;
//時間復雜度O(1)
public class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if(stack2.isEmpty()){
stack2.push(node);
}else{
if(node <= (int)stack2.peek()){
stack2.push(node);
}else{
stack2.push(stack2.peek());
}
}
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return (int)stack1.peek();
}
public int min() {
return (int)stack2.peek();
}
}
- **24.棧的壓入、彈出序列**
>**題目描述**
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
>**思路**：使用一個輔助棧，先按壓入序列將第一個元素壓入，之后開始比較彈出序列與該棧棧頂是否相同，不同則繼續(xù)按壓入順序入棧，直到棧頂元素和彈出數(shù)列相等是出棧，如果入棧已超過壓入順序，且棧頂仍不與彈出數(shù)列的值相等，則不是對應的序列。
import java.util.ArrayList;
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length != popA.length){
return false;
}
Stack<Integer> stack = new Stack<>();
stack.push(pushA[0]);
int j = 1;
for(int i = 0; i < popA.length; i++){
while(j < pushA.length && (int)stack.peek() != popA[i]){
stack.push(pushA[j]);
j++;
}
if(j >= pushA.length && stack.peek()!=popA[i]){
return false;
}else{
stack.pop();
}
}
return true;
}
}
- **25.從上往下打印二叉樹**
>**題目描述**
從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。
>**思路**：使用一個隊列進行層序遍歷。
import java.util.ArrayList;
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> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return result;
}
queue.offer(root);
while(!queue.isEmpty()){
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
result.add(treeNode.val);
}
return result;
}
}
