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();
}
}
}