资讯详情

程序员代码面试指南（左程云著）java学习笔记

总结常见问题

  1. 读取输入数据有两种方法 （BufferedReader比较快，不容易报错)

    1、 Scanner  s = new Scanner(System.in);    int i = s.nextInt();   2、 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  String[] inputDate = br.readLine().trim().split(" ");  int i = Integer.parseInt(inputDate[0]);

  2. 有一题while(fast.next.next != null && fast.next != null)空指针出现异常错误。正确应改为while(fast.next != null && fast.next.next != null)

第一章 栈和队列

描述

在实现栈基本功能的基础上，实现特殊功能的栈，然后实现返回栈中最小元素的操作。

输入描述：

第一行输入整数N，表示栈的操作总数。

下面N行每行输入一个字符串S，表示操作类型。

如果S为"push"，后面还有一个整数X，表示将整数X压入X。

如果S为"pop"，表示弹出栈顶操作。

如果S为"getMin"，这意味着询问当前栈中的最小元素是多少。

输出描述：

对于每个getMin操作，输出线表示当前栈中最小元素是多少。

示例1

输入：

6 push 3 push 2 push 1 getMin pop getMin

输出：

1 2

备注：

1<=N<=1000000  -1000000<=X<=1000000  数据保证没有非法操作

解答

import java.util.Scanner; import java.util.Stack;  public class Main { 
             public static class MyStack1     { 
                private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1()
        { 
        
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public void push(int newNum)
        { 
        
            if (this.stackMin.isEmpty())
            { 
        
                this.stackMin.push(newNum);
            }
            else if (newNum <= this.getMin())
            { 
        
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }

        public int getMin()
        { 
        
            if (this.stackMin.isEmpty())
            { 
        
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }

        public int pop()
        { 
        
            if (this.stackData.isEmpty())
            { 
        
                throw new RuntimeException("Your stack is empty.");
            }
            int value = this.stackData.pop();
            if (value == this.getMin())
            { 
        
                this.stackMin.pop();
            }
            return value;
        }

    }

    public static class MyStack2
    { 
        
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack2()
        { 
        
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }
        public void push(int newNum)
        { 
        
            if (stackMin.isEmpty())
            { 
        
                this.stackMin.push(newNum);
            }
            else if (newNum <= this.getMin())
            { 
        
                this.stackMin.push(newNum);
            }
            else
            { 
        
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }

        public int getMin()
        { 
        
            if (this.stackData.isEmpty())
            { 
        
                throw new RuntimeException("Your stack is empty");
            }
            return this.stackMin.peek();
        }

        public int pop()
        { 
        
            if (this.stackData.isEmpty())
            { 
        
                throw new RuntimeException("Your stack is empty");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }
    }
    public static void main(String[] args)
    { 
        
        /* MyStack1 myStack1 = new MyStack1(); Scanner scanner = new Scanner(System.in); int n = Integer.parseInt(scanner.nextLine()); for (int i = 1; i <= n; i++) { String[] inputData = scanner.nextLine().split(" "); if (inputData[0].equals("push")) { myStack1.push(Integer.parseInt(inputData[1])); } else if (inputData[0].equals("pop")) { myStack1.pop(); } else if (inputData[0].equals("getMin")) { System.out.println(myStack1.getMin()); } } scanner.close(); */
        MyStack2 myStack2 = new MyStack2();
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 1; i <= n; i++)
        { 
        
            String[] inputData = scanner.nextLine().split(" ");
            if (inputData[0].equals("push"))
            { 
        
                myStack2.push(Integer.parseInt(inputData[1]));
            }
            else if (inputData[0].equals("pop"))
            { 
        
                myStack2.pop();
            }
            else if (inputData[0].equals("getMin"))
            { 
        
                System.out.println(myStack2.getMin());
            }
        }
        scanner.close();

    }
}

在这里插入图片描述

描述

用两个栈实现队列，支持队列的基本操作。

输入描述：

第一行输入一个整数N，表示对队列进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。

如果S为"poll"，则表示弹出队列头部操作。

如果S为"peek"，则表示询问当前队列中头部元素是多少。

输出描述：

对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。

示例1

输入：

6
add 1
add 2
add 3
peek
poll
peek

输出：

1
2

备注：

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

解答

import java.util.Scanner;
import java.util.Stack;

public class Main
{ 
        
    public static class TwoStacksQueue
    { 
        
        // 定义两个栈StackPush\ StackPop
        public Stack<Integer> StackPush;
        public Stack<Integer> StackPop;

        // 构造函数

        public TwoStacksQueue()
        { 
        
            this.StackPush = new Stack<Integer>();
            this.StackPop = new Stack<Integer>();
        }

        // pushToPop函数
        // 两个前提条件： stackPop非空才能倒入， stackPush必须倒完
        public void pushToPop()
        { 
        
            if (this.StackPop.isEmpty())
            { 
        
                while (!this.StackPush.isEmpty())
                { 
        
                    this.StackPop.push(this.StackPush.pop());
                }
            }
        }
        // add函数
        public void add(int x)
        { 
        
            this.StackPush.push(x);
            pushToPop();
        }
        // poll函数
        public int poll()
        { 
        
            // 如果栈都为空则报错
            if (this.StackPush.isEmpty() && this.StackPop.isEmpty())
            { 
        
                throw new RuntimeException("Your queue is empty");
            }
            pushToPop();
            return this.StackPop.pop();

        }
        // peek函数
        public int peek()
        { 
        
            if (this.StackPush.isEmpty() && this.StackPop.isEmpty())
            { 
        
                throw new RuntimeException("Your queue is empty");
            }
            pushToPop();
            return this.StackPop.peek();
        }
    }

    public static void main(String[] args) { 
        
        TwoStacksQueue queue = new TwoStacksQueue();
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 1; i <= n; i++)
        { 
        
            String[] inputData = scanner.nextLine().split(" ");
            if (inputData[0].equals("add"))
            { 
        
                queue.add(Integer.parseInt(inputData[1]));
            }
            else if (inputData[0].equals("poll"))
            { 
        
                queue.poll();
            }
            else if (inputData[0].equals("peek"))
            { 
        
                System.out.println(queue.peek());
            }
        }

        scanner.close();
    }
}

描述

一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

输入描述：

输入数据第一行一个整数N为栈中元素的个数。

接下来一行N个整数X_iX**i表示一个栈依次压入的每个元素。

输出描述：

输出一行表示栈中元素逆序后的栈顶到栈底的每个元素

示例1

输入：

5
1 2 3 4 5

输出：

1 2 3 4 5

解答

import java.util.Scanner;
import java.util.Stack;

public class Main
{ 
        
    // 递归函数一：将栈底的元素返回并移除
    public static int getAndRemoveLastElement(Stack<Integer> stack)
    { 
        
        // 记录位置方便递归
        int x = stack.pop();
        if (stack.isEmpty())
        { 
        
            return x;
        }
        else
        { 
        
            int last = getAndRemoveLastElement(stack);
            stack.push(x); // 恢复原来顺序
            return last;
        }
    }
    public static void reverse(Stack<Integer> stack)
    { 
        
        if (stack.isEmpty())
        { 
        
            return ;
        }
        int x = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(x);
    }

    
    public static void main(String[] args)
    { 
        
        Stack<Integer> stack = new Stack<>();
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 1; i <= n; i++)
        { 
        
            int x = scanner.nextInt();
            stack.push(x);
        }
        reverse(stack);
        while (!stack.isEmpty())
        { 
        
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}

描述

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

输入描述：

第一行输入一个N，表示栈中元素的个数

第二行输入N个整数a_ia**i表示栈顶到栈底的各个元素

输出描述：

输出一行表示排序后的栈中栈顶到栈底的各个元素。

示例1

输入：

5
5 8 4 3 6

输出：

8 6 5 4 3

备注：

1 <= N <= 10000 -1000000 <= a_nan <= 1000000

代码

import java.util.Scanner;
import java.util.Stack;

public class Main
{ 
        
    // 要排序的栈为stack, 辅助栈为help, 在stack栈进行pop操作，弹出的元素记作cur
    // 分两种情况讨论： 1、 cur <= help栈顶元素， 则将cur直接压入help栈中
    // 2、 cur > help栈顶元素 stack.push(help.pop())直到cur <= help栈顶元素位置， 最后把cur压入help中
    public static void sortStackByStack(Stack<Integer> stack)
    { 
        
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty())
        { 
        
            int cur = stack.pop();
            while (!help.isEmpty() && cur > help.peek())
            { 
        
                stack.push(help.pop());
            }
            help.push(cur);
        }

        while (!help.isEmpty())
        { 
        
            stack.push(help.pop());
        }
    }

    public static void main(String 

        标签： cd106系列电感
 
锐单商城拥有海量元器件数据手册、
          IC替代型号，打造
          电子元器件IC百科大全！

锐单商城 - 一站式电子元器件采购平台