2018-12-24T11:22:51.000Z
Hackerrank题解
Java Inheritance I
题目详情
分析
本题考查子类继承父类以后，如何拓展子类的方法。直接在子类声明里面声明方法即可。
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Animal{
void walk()
{
System.out.println("I am walking");
}
}
class Bird extends Animal
{
void fly() {
System.out.println("I am flying");
}
// 直接在这里声明 sing 函数，按照要求完成输出内容即可
void sing() {
System.out.println("I am singing");
}
}
public class Solution{
public static void main(String args[]){
Bird bird = new Bird();
bird.walk();
bird.fly();
bird.sing();
}
}Java Inheritance II
题目详情
分析
本题继续考查继承的知识点，根据题目给出的 Arithmetic 和 Adder 之间的描述得知两者是父子类的关系，且 add 方法是由父类来实现的。
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
//Write your code here
class Arithmetic {
public int add(int a, int b) {
return a + b;
}
}
// 子类只需要继承父类即可
class Adder extends Arithmetic {
}
public class Solution{
public static void main(String []args){
// 实例化一个 Adder 对象
Adder a = new Adder();
// Print the name of the superclass on a new line
// 通过一些方法来取得父类的名字
System.out.println("My superclass is: " + a.getClass().getSuperclass().getName());
// Print the result of 3 calls to Adder's `add(int,int)` method as 3 space-separated integers:
System.out.print(a.add(10,32) + " " + a.add(10,3) + " " + a.add(10,10) + "\n");
}
}Java Abstract Class
题目详情
分析
题目给出了一个 Book 的抽象类，内含一个抽象方法 setTitle 和一个放回 String 类型的 getTitle 方法。根据调用方法可以得知真正调用的是 MyBook 类的实例化对象 new_novel 的 setTitle方法来设置 title，通过 getTitle 方法来获取成员变量 title。那么只需要让 MyBook 类继承 Book 类，然后具体实现 setTitle 方法即可。需要注意的是，在子类当中是通过关键字super来访问父类。
import java.util.*;
abstract class Book{
String title;
abstract void setTitle(String s);
String getTitle(){
return title;
}
}
//Write MyBook class here
// 继承抽象类，然后实现 setTitle 的方法
class MyBook extends Book {
void setTitle(String s) {
super.title = s; // 通过super来访问父类
}
}
public class Main{
public static void main(String []args){
//Book new_novel=new Book(); This line prHMain.java:25: error: Book is abstract; cannot be instantiated
Scanner sc=new Scanner(System.in);
String title=sc.nextLine();
MyBook new_novel=new MyBook();
new_novel.setTitle(title);
System.out.println("The title is: "+new_novel.getTitle());
sc.close();
}
}Java Interface
题目详情
分析
题目要求 MyCalculator 在继承 AdvancedArithmetic 接口的前提下，通过实现 divisor_sum 函数来满足既定的需求（输入一个整数 n ，返回能被 n 整除的整数之和）。
import java.util.*;
interface AdvancedArithmetic{
int divisor_sum(int n);
}
//Write your code here
// 继承 AdvancedArithmetic 接口
class MyCalculator implements AdvancedArithmetic {
public int divisor_sum(int n) {
int result = 0;
if (n != 0) {
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
result += i;
}
}
}
return result;
}
}
class Solution{
public static void main(String []args){
MyCalculator my_calculator = new MyCalculator();
System.out.print("I implemented: ");
ImplementedInterfaceNames(my_calculator);
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(my_calculator.divisor_sum(n) + "\n");
sc.close();
}
/*
* ImplementedInterfaceNames method takes an object and prints the name of the interfaces it implemented
*/
// 这个方法要求传入参数类型是对象
static void ImplementedInterfaceNames(Object o){
Class[] theInterfaces = o.getClass().getInterfaces();
for (int i = 0; i < theInterfaces.length; i++){
String interfaceName = theInterfaces[i].getName();
System.out.println(interfaceName);
}
}
}
Java Method Overriding
题目详情
分析
根据例子重写父类的同名方法。
import java.util.*;
class Sports{
String getName(){
return "Generic Sports";
}
void getNumberOfTeamMembers(){
System.out.println( "Each team has n players in " + getName() );
}
}
class Soccer extends Sports{
@Override
String getName(){
return "Soccer Class";
}
@Override
void getNumberOfTeamMembers() {
System.out.println("Each team has 11 players in " + getName());
}
}
public class Solution{
public static void main(String []args){
Sports c1 = new Sports();
Soccer c2 = new Soccer();
System.out.println(c1.getName());
c1.getNumberOfTeamMembers();
System.out.println(c2.getName());
c2.getNumberOfTeamMembers();
}
}
Java Method Overriding 2 (Super Keyword)
题目详情
分析
掌握通过关键字 super 来访问父类，包括调用父类的方法。
import java.util.*;
import java.io.*;
class BiCycle{
String define_me(){
return "a vehicle with pedals.";
}
}
class MotorCycle extends BiCycle{
String define_me(){
return "a cycle with an engine.";
}
MotorCycle(){
System.out.println("Hello I am a motorcycle, I am "+ define_me());
String temp=super.define_me(); //Fix this line
System.out.println("My ancestor is a cycle who is "+ temp );
}
}
class Solution{
public static void main(String []args){
MotorCycle M=new MotorCycle();
}
}
Java Instanceof keyword
题目详情
分析
考查使用instanceof关键字来确定对象是否是某一个类的实例，返回的是一个布尔类型的值。
只要判断当前对象是三个类的哪一个，然后给计数+1即可。
import java.util.*;
class Student{}
class Rockstar{ }
class Hacker{}
public class InstanceOFTutorial{
static String count(ArrayList mylist){
int a = 0,b = 0,c = 0;
for(int i = 0; i < mylist.size(); i++){
Object element=mylist.get(i);
if(element instanceof Student)
a++;
if(element instanceof Rockstar)
b++;
if(element instanceof Hacker)
c++;
}
String ret = Integer.toString(a)+" "+ Integer.toString(b)+" "+ Integer.toString(c);
return ret;
}
public static void main(String []args){
ArrayList mylist = new ArrayList();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0; i<t; i++){
String s=sc.next();
if(s.equals("Student"))mylist.add(new Student());
if(s.equals("Rockstar"))mylist.add(new Rockstar());
if(s.equals("Hacker"))mylist.add(new Hacker());
}
System.out.println(count(mylist));
}
}
Java Iterator
题目详情
分析
本题考查的是对于 Java 迭代器 的基本认识。根据题目提示，需要找出标记为###字符串后面的所有字符串，而###之前的所有输入都不是String，那么配合上一题的 instanceof 找出 String的第一个实例（“###”）即可。
import java.util.*;
public class Main{
static Iterator func(ArrayList mylist){
Iterator it=mylist.iterator();
while(it.hasNext()){
Object element = it.next();
if(element instanceof String)//Hints: use instanceof operator
break;
}
return it;
}
@SuppressWarnings({ "unchecked" })
public static void main(String []args){
ArrayList mylist = new ArrayList();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 0;i<n;i++){
mylist.add(sc.nextInt());
}
mylist.add("###");
for(int i=0;i<m;i++){
mylist.add(sc.next());
}
Iterator it=func(mylist);
while(it.hasNext()){
Object element = it.next();
System.out.println((String)element);
}
}
}
Java数据结构
Maximum Element
题目详情
分析
题目其实可以转转化分析为，如何快速查找栈中的最大值（最小值也同理）。我们通过使用双栈即可，一个记录数字的顺序，另一个则用于记录最大值（当遇到的新的输入值大于栈中顶部的数，则把新的数字放入栈中，以保证栈顶的数是最大值）。
当遇到删除指令，则需要加一层判断，看此数字是否在记录最大值的栈的顶部，如果是的话就要一并进行移除。
需要打印最大值的时候则使用 peek 命令来获取最大值栈的顶部数值。
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
Stack<Integer> stack = new Stack<>();
Stack<Integer> top = new Stack<>();
int step = sc.nextInt();
while(sc.hasNext()) {
int type = sc.nextInt();
switch(type) {
case 1:
int t = sc.nextInt();
stack.push(t);
if (top.empty() || t >= top.peek()){
top.push(t);
}
break;
case 2:
if (!stack.empty()) {
int j = stack.pop();
if (j == top.peek()) {
top.pop();
}
}
break;
case 3:
System.out.println(top.peek());
}
}
sc.close();
}
}Balanced Brackets（括号平衡）
题目详情
分析
这题也是考查对栈的应用。
首先要判断目标字符串的长度，如果小于2的话就可以直接返回false了（有的题目要求如果字符串为空的话，结果为true，这个也应该在一开始进行判断，就可以节省代码执行时间）。
遍历字符串的时候，遇到左括号就可以直接压入栈中；
当遇到右括号的时候，先检查栈是否为空（为空的话就直接返回 false ，因为这时候没有左括号可供消除），必须是会与栈顶的左括号想匹配的（如果不匹配的话就可以返回 false 了），匹配的话就对执行栈执行 pop 操作。
遍历结束以后，如果栈的长度为空，说明已经消除了全部的左括号，否则就是还有左括号没有被平衡。
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the isBalanced function below.
static String isBalanced(String s) {
Stack<Character> stack = new Stack<>();
if (s.length() < 2) {
return "NO";
}
for(int i = 0; i< s.length(); i++) {
char t = s.charAt(i);
if ((t == '(') || (t == '[') || (t == '{')) {
stack.push(t);
} else {
if (!stack.empty()) {
// 这里的判断条件可以用一个 if 语句完成，这里分开写只是为了容易理解。
if (stack.peek() == '(' && t == ')') {
stack.pop();
}else if (stack.peek() == '[' && t == ']') {
stack.pop();
}else if (stack.peek() == '{' && t == '}') {
stack.pop();
} else {
return "NO";
}
}else {
return "NO";
}
}
}
return stack.size() == 0 ? "YES" : "NO";
}
}Equal Stacks
题目详情
分析
贪心解决。
public class Solution {
static int equalStacks(int[] h1, int[] h2, int[] h3) {
// 用三个栈按顺序存储输入的数组
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
Stack<Integer> s3 = new Stack<Integer>();
// 三个用于存储栈内数字总和的变量
int sum1 = 0;
int sum2 = 0;
int sum3 = 0;
// 分别填充栈和计算总和
for (int i = h1.length-1; i >= 0; i--) {
sum1 += h1[i];
s1.push(h1[i]);
}
for (int i = h2.length-1; i >= 0; i--) {
sum2 += h2[i];
s2.push(h2[i]);
}
for (int i = h3.length-1; i >= 0; i--) {
sum3 += h3[i];
s3.push(h3[i]);
}
// 其实这里的判断条件可以为 sum1 == sum2 && sum1 == sum3
// 但考虑到如果出现为0（也就是无法匹配里面的逻辑条件的话），就不需要继续 while 循环了，所以也可以用true
// 处理方法就是，找到总数最大的栈，然后取出顶部数字，同时所对应的 sum* 变量也跟着自减
// 贪心处理就可以解决
while(true){
if (sum1 > sum2 || sum1 > sum3) {
sum1 -= s1.pop();
}else if (sum2 > sum3 || sum2 > sum1) {
sum2 -= s2.pop();
}else if (sum3 > sum1 || sum3 > sum2) {
sum3 -= s3.pop();
}else {
break;
}
}
return sum1;
}方法二
public class Solution {
static int equalStacks(int[] h1, int[] h2, int[] h3) {
// 先用sum方法来计算数组总和
int sum1 = sum(h1);
int sum2 = sum(h2);
int sum3 = sum(h3);
// 同来记录操作下标
int i1 = 0;
int i2 = 0;
int i3 = 0;
// 这里改为用下标来当做上个方法中的栈的顶部指针
// 这样的方法还是比较巧妙，不直接使用栈，但利用了栈处理的思想
while (true) {
if (sum1 > sum2 || sum1 > sum3) {
sum1 -= h1[i1++];
} else if (sum2 > sum1 || sum2 > sum3) {
sum2 -= h2[i2++];
} else if (sum3 > sum1 || sum3 > sum2) {
sum3 -= h3[i3++];
} else {
break;
}
}
return sum1;
}
// 用来计算数组中的所有元素的总和
static int sum(int[] arr) {
int result = 0;
for (int i : arr) {
result += i;
}
return result;
}
}Game of Two Stacks
题目详情
分析
一开始使用的贪心最小策略，但是提交的时候有部分测试不通过。后来也想明白了原因，就是假如你专注于比较每次栈顶数字的大小，会错过后面的小数字的，就是说不应该使用贪心最小策略。
这题还有点像动态规划的样子，但其实要留意一点：每次从a栈或者b栈中取数字，都必须要从顶部开始。
这样的话我们可以先假设全部从b栈中取数字，看能取到什么程度。然后再把b栈已经取得的最后一位数字退回去，改用a栈的来代替。这样就可以尝试两边都取。最优解的结果只有一个，虽然有可能实现的路径有多个，正因为如此选择从a栈开始或者b栈开始都没有关系。
得好好琢磨一下才行。
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the twoStacks function below.
*/
static int twoStacks(int x, int[] a, int[] b) {
int sum = 0;
int ib = 0;
// 可以不用栈，但应该有栈的特性（先进后出）
// 所以应该有下标来记录栈顶的位置，同时也能记录操作次数
// 遍历数组b，在符合条件内将可以获取的数都取出来
// 用ib记录
while(ib < b.length && sum + b[ib] <= x) {
sum += b[ib];
ib += 1;
}
// 经过上面的操作以后，先假设全部针对b数组的操作的次数是最大值
int max = ib;
// 然后遍历数组a，先把b的顶部数取出来，把a的头部放进去，如果小于x，则继续。如果大于x，就中断
// 每次对比a的遍历次数 + b 的遍历次数
for (int ia = 1; ia <= a.length; ia++) {
sum += a[ia-1];
// 这里比较关键，首先sum已经添加了a数组的最后一项
// 如果sum 比x大而且也仍从B中获取数字，就应该试一下从sum中减去b的顶部
while (sum > x && ib > 0) {
// 因为在上面的while循环里面的判断跳出条件是
// ib > b.length;
// 所以这里要对ib进行自减，才是b数组中已经取得的最后一位有效的数字（是已经拿走的数字队列中的最后一位，而不是数组的最后一位，类似于栈的顶部指针索引一样）
ib -=1;
sum -= b[ib];
}
// 这里和上面并不冲突
if (sum > x) {
break;
}
max = Math.max(max, ia + ib);
}
return max;
}
}
Largest Rectangle（最大的矩形）
题目详情
分析
先给高度数组尾部添加一个0（用于结束循环）。
遍历高度数组，当 i 所指向的高度的矩形比前一个矩形要高，就把其索引压入栈中（或者当栈是空的时候）。 当遇到一个矩形的的高度小于前一个矩形高度的时候，先把栈的顶部元素排出并记录为top，就先计算top的矩形的面积，上一个矩形面积（高 X 宽，此时的宽是1，由遍历数组的 i 来计算的话，应该是 i - 当前栈顶的索引的矩形高度 - 1），然后跟存储的最大矩形面积相比，替换。此后步骤重复执行，每次执行结束以后，i—。
刚开始栈中为空，压入下标0；然后当i=1时，2<=1不成立，下标出栈，栈变为空，计算此时面积res=2；
依次将高度 1,5,6 所对应的索引 1,2,3 压入栈，直到i=4, 6 > 2，下标3要出栈，此时计算的面积就是6（单一个矩形的面积），宽是如何确定的呢？i (4) - stack.peek() (2) - 1 = 4 - 2 - 1
栈顶元素为2，其对应的高度为5>2（此时，还要和下标i=4的高度比较），所以，栈顶元素2出栈，计算面积为res=10；
栈顶元素是2，对应的高度 1 < 2，就把 i= 4 入栈，直到了最后一个高度为0的索引。当遍历到 i = 6，此高度为0，所有的元素都比这个大，便向前进行计算面积。 栈顶为 5，就计算此面积为4。
栈顶元素是4，对应的高度是2 > 0，把栈顶4 出栈，计算绿色部分的面积（最大的绿色矩形,从 2 => 5），得出8
栈顶元素是1，对应的高度是1 > 0，把栈顶1 出栈（此时为空栈了），计算面积方式就改为： 高度 x i，得出绿色方框部分的面积。
直到最后，最大面积是10，所以返回10。
public class LargestRectangle {
static int solve(int[] h) {
if (h.length < 1) {
return 0;
}
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int[] arr = Arrays.copyOf(h, h.length + 1);
for (int i = 0; i < arr.length; i++) {
if (stack.empty() || arr[i] >= arr[stack.peek()]) {
stack.push(i);
} else {
int top = stack.pop();
int area = arr[top] * (stack.empty() ? i : i - stack.peek() - 1);
maxArea = Math.max(area, maxArea);
i--;
}
}
return maxArea;
}
}
public static void main(String[] args) {
int[] a = new int[]{2, 1, 5, 6, 2, 3};
int k = solve(a);
System.out.println(k);
}在LeetCode中看到有一种方法是这样的：
static int solve(int[] heights) {
// 1、如果已知height数组是升序的，应该怎么做？
// 比如1,2,5,7,8
// 那么就是(1*5) vs. (2*4) vs. (5*3) vs. (7*2) vs. (8*1)
// 也就是max(height[i]*(size-i))
// 2、使用栈的目的就是构造这样的升序序列，按照以上方法求解。
// 但是height本身不一定是升序的，应该怎样构建栈？
// 比如2,1,5,6,2,3
// （1）2进栈。s={2}, result = 0
// （2）1比2小，不满足升序条件，因此将2弹出，并记录当前结果为2*1=2。
// 将2替换为1重新进栈。s={1,1}, result = 2
// （3）5比1大，满足升序条件，进栈。s={1,1,5},result = 2
// （4）6比5大，满足升序条件，进栈。s={1,1,5,6},result = 2
// （5）2比6小，不满足升序条件，因此将6弹出，并记录当前结果为6*1=6。s={1,1,5},result = 6
// 2比5小，不满足升序条件，因此将5弹出，并记录当前结果为5*2=10（因为已经弹出的5,6是升序的）。s={1,1},result = 10
// 2比1大，将弹出的5,6替换为2重新进栈。s={1,1,2,2,2},result = 10
// （6）3比2大，满足升序条件，进栈。s={1,1,2,2,2,3},result = 10
// 栈构建完成，满足升序条件，因此按照升序处理办法得到上述的max(height[i]*(size-i))=max{3*1, 2*2, 2*3, 2*4, 1*5, 1*6}=8<10
// 综上所述，result=10
int res = 0;
Stack<Integer> stack = new Stack<Integer>();
int count = 1;
for (int i = 0; i < heights.length; i++) {
if (stack.size() == 0 || stack.peek() <= heights[i]) {
stack.push(heights[i]);
} else {
int counter = 0;
while (stack.size() != 0 && stack.peek() > heights[i]) {
counter++;
res = Math.max(res, stack.peek() * counter);
stack.pop();
}
while (counter != 0) {
stack.push(heights[i]);
counter--;
}
stack.push(heights[i]);
}
}
while (!stack.isEmpty()) {
res = Math.max(res, stack.peek() * count);
stack.pop();
count++;
}
return res;
}参考博客1 很神奇的解法！怎么求柱状图中的最大矩形？ 参考博客2
Simple Text Editor
题目详情
分析
利用栈存储每一次操作之后的字符串结果。
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack<String> st = new Stack<>();
String result = "";
st.push(result);
int l = sc.nextInt();
for (int i = 0; i < l; i++) {
int op = sc.nextInt();
switch (op) {
case 1:
result = st.peek() + sc.next();
st.push(result);
break;
case 2:
if (!st.empty()) {
int end = sc.nextInt();
result = result.substring(0, result.length() - end);
st.push(result);
}
break;
case 3:
if (!st.empty()) {
result = st.peek();
char x = result.charAt(sc.nextInt() - 1);
System.out.println(x);
}
break;
case 4:
if (!st.empty()) {
st.pop();
result = st.peek();
}
break;
}
}
sc.close();
}
}Queue using Two Stacks
题目详情
分析
使用两个栈（s1 和 s2）来实现队列的特性（先进先出）。
一开始想这样：一个栈用于存储，另一个栈待命。当遇到了要 pop 或者 peek 的时候，就把 s1 所有元素 pop 到 s2，然后再进行操作，完成以后再全部转回去。
不出意外，超时了。。。
问题就出在了其实没有必要每次都进行栈内元素的转移，非常耗费时间的。换个角度，用一个类来模拟queue，实现三个方法（push、pop、peek）。当需要push进入队列，就正常 push 到 s1。pop与peek操作的对象其实是 s2，因为 s2 的存在是给我们存储的元素倒序的，假如s2 栈为空，就转移 s1 的元素到 s2 就好了。
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
QueueWithTwoStacks q = new QueueWithTwoStacks();
for (int i = 0; i < l; i++) {
int op = sc.nextInt();
switch (op) {
case 1:
q.push(sc.nextInt());
break;
case 2:
q.pop();
break;
case 3:
System.out.println(q.peek());
break;
default:
break;
}
}
sc.close();
}
public static class QueueWithTwoStacks {
private Stack<Integer> s1;
private Stack<Integer> s2;
public QueueWithTwoStacks() {
super();
this.s1 = new Stack<Integer>();
this.s2 = new Stack<Integer>();
}
public void push(int t) {
if (s2.empty()) {
while(!s1.empty()) {
s2.push(s1.pop());
}
}
s1.push(t);
}
public int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
}
}