LeetCode-020-有效的括号

发表于 2018-07-06

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例

1 2	输入: "()" 输出: true

思路

利用栈压入，每次压入都检查栈顶和数组的第一个元素是否匹配，直至栈为空

解答

class Solution {
    public boolean isValid(String s) {
       Stack<Character> result = new Stack<Character>();
        int n=s.length();
        if(n==0){
            return true;
        }
        for(int i=0;i<n;i++) {
            if(result.empty()){
                result.push(s.toCharArray()[i]);
            } else if(result.peek()=='('&&s.toCharArray()[i]==')'|| result.peek()=='['&&s.toCharArray()[i]==']'|| result.peek()=='{'&&s.toCharArray()[i]=='}'){
                result.pop();
            } else{
                result.push(s.toCharArray()[i]);
            }
        }
        return result.empty();
    }
}

LeetCode-013-罗马数字转整数

发表于 2018-07-06

题目描述

罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例

1
2
3

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思路

依照给出的条件进行编程

解答

class Solution {
    public int romanToInt(String s) {
        int temp = 0,i;
        char[] chars = s.toCharArray();
        for (i=0;i<chars.length;){
            if (chars[i] == 'I'&& (i+1)<chars.length && chars[i+1] =='V' ){
                temp =temp + 4;
                i=i+2;
            }else if (chars[i] == 'I'&& (i+1)<chars.length && chars[i+1] == 'X'){
                temp =temp + 9;
                i=i+2;
            }else if (chars[i] == 'X'&& (i+1)<chars.length && chars[i+1] == 'L'){
                temp = temp+40;
                i=i+2;
            }else if (chars[i] == 'X'&& (i+1)<chars.length && chars[i+1] == 'C'){
                temp = temp + 90;
                i=i+2;
            }else if (chars[i] == 'C'&& (i+1)<chars.length && chars[i+1] == 'D'){
                temp = temp + 400;
                i = i+2;
            }else if (chars[i] == 'C'&& (i+1)<chars.length && chars[i+1] == 'M'){
                temp = temp + 900;
                i = i+2;
            }else if (chars[i] == 'I'){
                temp = temp+1;
                i++;
            }else if (chars[i] == 'V'){
                temp = temp+5;
                i++;
            }else if (chars[i] == 'X'){
                temp = temp+10;
                i++;
            }else if (chars[i] == 'L'){
                temp = temp+50;
                i++;
            }else if (chars[i] == 'C'){
                temp = temp+100;
                i++;
            }else if (chars[i] == 'D'){
                temp = temp+500;
                i++;
            }else if (chars[i] == 'M'){
                temp = temp+1000;
                i++;
            }
        }
        return temp;
    }
}

LeetCode-009-回文数

发表于 2018-07-06

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例

1 2	输入: 121 输出: true

思路

额，一个指针从头，一个指针从尾，两者比较，直至到终点，相等返回true，否则返回false

解答

class Solution {
    public boolean isPalindrome(int x) {
       boolean flag = true;
        char[] temp = String.valueOf(x).toCharArray();
        for (int i = 0,j = temp.length - 1; j >= 0;i++, j--) {
            if (temp[i] != temp[j]) {
                flag = false;
                break;
            }
        }
        return flag;
    }
}

LeetCode-007-反转整数

发表于 2018-07-06

题目描述

给定一个 32 位有符号整数，将整数中的数字进行反转。

注意:假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

示例

1 2	输入: 123 输出: 321

思路

使用栈存入每一个值，利用栈的先进后出进行反转，注意边界问题

解答

class Solution {
    public int reverse(int x) {
         int temp = 0,j=0;
        boolean flag = true;
        Stack<Integer> stack = new Stack<>();
        char[] s = String.valueOf(x).toCharArray();

        if (x > Integer.MAX_VALUE ||x < Integer.MIN_VALUE){
            return 0;
        }

        for (int i=s.length-1;i>=0;i--){
            stack.push(s[i]-48);
        }
        while (stack.size()>0){
            if (stack.peek() == -3){
                flag = false;
                stack.pop();
            }else {
                temp = (int) (temp + Math.pow(10,j)*(stack).pop());
                ++j;
            }
        }
        if (!flag){
            return -temp;
        }else {
            return temp;
        }
    }
}

LeetCode-001-两数之和

发表于 2018-07-06

题目描述

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

使用选择排序的思想进行寻找两值等于目标值

解答

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
            for (int j=0;j<nums.length;j++){
                for (int k=j+1;k< nums.length;k++){
                    if (target == nums[j]+nums[k]){
                        result[0] = j;
                        result[1] = k;
                        return result;
                    }
                }
            }
            return nums;
    }
}

设计模式(6)

发表于 2018-07-04

创建型模式-原型模式

介绍

用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象。

实例

创建一个实现了Clonable接口的抽象类

public abstract class Shape implements Cloneable {
   
   private String id;
   protected String type;
   
   abstract void draw();
   
   public String getType(){
      return type;
   }
   
   public String getId() {
      return id;
   }
   
   public void setId(String id) {
      this.id = id;
   }
   
   public Object clone() {
      Object clone = null;
      try {
         clone = super.clone();
      } catch (CloneNotSupportedException e) {
         e.printStackTrace();
      }
      return clone;
   }
}

阅读全文 »

设计模式(5)

发表于 2018-07-04

创建型模式- 建造者模式

介绍

讲一个复杂的构建与其表示相分离，使得同样的构建过程可以创建不同的表示。
使用多个简单的对象一步一步构建成一个复杂的对象

实例

创建一个表示食物条目和食物包装的接口

 public interface Item {
   public String name();
   public Packing packing();
   public float price();    
}

public interface Packing {
   public String pack();
}

阅读全文 »

设计模式(4)

发表于 2018-07-04

创造型模式-单例模式

介绍

保证一个类仅有一个实例，并提供一个访问它的全局访问点

实例

创建Singleton类

public class SingleObject {
 
   //创建 SingleObject 的一个对象
   private static SingleObject instance = new SingleObject();
 
   //让构造函数为 private，这样该类就不会被实例化
   private SingleObject(){}
 
   //获取唯一可用的对象
   public static SingleObject getInstance(){
      return instance;
   }
 
   public void showMessage(){
      System.out.println("Hello World!");
   }
}

阅读全文 »

设计模式(3)

发表于 2018-07-04

创建型模式-抽象工厂模式

介绍

抽象工厂模式：提供一个创建一系列相关或者相互依赖对象的接口，而无需指定它们具体的类。

实例

创建一个形状接口

1
2
3

public interface Shape {
   void draw();
}

创建实现形状接口的实体类

public class Rectangle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Rectangle::draw() method.");
   }
}

public class Square implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Square::draw() method.");
   }
}

public class Circle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Circle::draw() method.");
   }
}

阅读全文 »

设计模式(2)

发表于 2018-07-04

创造型模式-工厂模式

介绍

定义一个创建对象的接口，让其子类自己决定实例化哪一个工厂类，工厂模式使其创建过程延迟到子类进行。

语言不够，代码来凑

创建一个接口

1
2
3

public interface Shape {
   void draw();
}

创建实现接口的实体类

public class Rectangle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Rectangle::draw() method.");
   }
}

public class Square implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Square::draw() method.");
   }
}


public class Circle implements Shape {
 
   @Override
   public void draw() {
      System.out.println("Inside Circle::draw() method.");
   }
}

阅读全文 »