【Leetcode做题记录】7. 整数反转,14. 最长公共前缀

7.整数反转

题目描述及官方解答：https://leetcode-cn.com/problems/reverse-integer/solution/

思路：

这里关键是如何弹出最后一位和组装反转后的数字。

这是弹出最后一位
pop = x % 10;
x /= 10;

这是生成结果，思路是将之前的结果全升一位，新的pop值加到后面。
temp = rev * 10 + pop;
rev = temp;

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

14. 最长公共前缀

题目描述及官方解答：https://leetcode-cn.com/problems/longest-common-prefix/solution/

思路1 暴力法

两个循环
选取第一个字符串用来截取前缀。
判断剩余字符串前缀是否与该前缀相同。
如全相同，则返回
如不相同，返回截取更短的前缀

我的代码：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs==null||strs.length==0){
            return "";
        }
        if(strs.length==1)
        {
            return strs[0];
        }        
        String end="";
        for(int i=0;i<strs[0].length();i++){
            
            String sub=strs[0].substring(0,i+1);
            boolean flag = true; 
            
            for(int j=1;j<strs.length;j++ ){
                if(strs[j].length()<i+1){
                    flag = false;
                    break;    
                }
                if(!strs[j].substring(0,i+1).equals(sub)){
                    flag = false;
                    break;       
                }else{
                }
            }
            if(flag){
                  end=sub;  
            }else{
                break;
            }
        }
    return end;
    }
}

执行最快的代码：
思路更巧妙，代码更简洁

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs==null||strs.length==0) {
            return "";
        }
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(res)!=0) {
                res=res.substring(0, res.length()-1);
            }
        }
        return res;
    }
}

20. 有效的括号

题目描述及官方解答：https://leetcode-cn.com/problems/valid-parentheses/solution/

思路:使用栈

class Solution {

  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }

    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}