LeetCode 算法练习 Problem 5&241

PRoblem 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.

Example:Input: "cbbd"Output: "bb"

解题思路:

1. 寻找最长的对称子串，从头开始遍历字符串，可以考虑从子串的中心出发，以当前字符为子串中心，同时向两端延伸，看是否两端的值是否一直相等，延伸到两端的值不相等后，以该字符为中心的对称子串寻找结束，记录长度，然后开始寻找以下一个字符为中心的对称子串。

2.对称的子串长度可能为奇数如“aba"，也可能为偶数"abba"，这两个情况下确定中心的方法不太一样，需要注意。长度为奇数时只需以当前字符为中心进行延伸，为偶数时，则需要以两个相同且连续的字符开始进行延伸。

代码如下：

public class Solution {   private int head = 0;   private int tail = 0;    public String longestPalindrome(String s) {    int length = s.length();                    int i = 0;           int j = 0;          if(length <= 1) return s;          for(i = 0;i < length;i++){                       findPalindrome(s,i,i);            findPalindrome(s,i,i+1);          }          return s.substring(head,tail+1);}private void findPalindrome(String s,int i,int j){   while(i >=0 && j < s.length() && s.charAt(i) == s.charAt(j)){              i--;              j++;            }            if(tail - head < --j - ++i){              head = i ;              tail = j ;            }}}
Problem 241.Different Ways to Add Parentheses
Given a string of numbers and Operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1Input: "2-1-1".
((2-1)-1) = 0(2-(1-1)) = 2
Output: [0, 2]
Example 2Input: "2*3-4*5"
(2*(3-(4*5))) = -34((2*3)-(4*5)) = -14((2*(3-4))*5) = -10(2*((3-4)*5)) = -10(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
解题思路：
这里说两种解题思路，一种是自己的，另一种是在评论上看到的。
首先是自己的并不能通过的方法，因为重复计算了相同的算式，所以输出的结果冗余，但是我觉得思路上应该没有太大的问题所以还是稍微写一下，希望大家引以为戒：
1. 中心思想就是利用递归，不断地把相邻的两个数字合并起来，直到最后只剩一个数，也就是最终的一个结果，存放起来，然后循环往复：例如 "1+2+3-1"，首先合并第一个和第二个数，合并之后变为"3+3-1"，再合并为"6-1"，最后得到结果5。然后考虑合并第二和第三个数...以此类推。
2.因为输入的是字符串，所以创建两个列表分别来存放读取出来的数字和符号。
代码如下：
public class Solution {  private List<Integer> ans = new ArrayList<>();    public List<Integer> diffWaysToCompute(String input) {      int length = input.length();      List<Integer> numList = getNums(input);      List<Character> optList = getOpts(input);      if(optList.size() == 0){        return numList;      }      else{        mergeNums(numList,optList);        return ans;      }    }    private List<Integer> getNums(String s){        List<Integer> numList = new ArrayList<>();        for(int i = 0;i< s.length();i++){        int temp = i;        while(temp < s.length() && s.charAt(temp) >= 48 && s.charAt(temp) <= 57){          temp++;        }        int tail = temp > i ? temp : i;        if(tail > i){          try {          int newNum = Integer.parseInt(s.substring(i,tail));          numList.add(newNum);          i = temp - 1;      } catch (NumberFormatException e) {          e.printStackTrace();        }               }        }        return numList;    }     private List<Character> getOpts(String s){        List<Character> optList = new ArrayList<>();        for(int i = 0;i< s.length();i++){          if(s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*'){            optList.add(s.charAt(i));          }                   }        return optList;    }    private void mergeNums(List<Integer> numlist, List<Character> optList){      if(numlist.size() >= 2){        for(int i = 0;i + 1 < numlist.size();i++){          List<Integer> newNumList = new ArrayList<>();          List<Character> newOptList = new ArrayList<>();          newNumList.addAll(numlist);           newOptList.addAll(optList);        int num1 = numlist.get(i);        int num2 = numlist.get(i+1);        int mer = 0;        switch(optList.get(i)){          case '+':            mer = num1 + num2;            break;          case '-':            mer = num1 - num2;            break;          case '*':            mer = num1 * num2;            break;          default:            break;        }                        newNumList.set(i,mer);          newNumList.remove(i+1);                   newOptList.remove(i);          mergeNums(newNumList,newOptList);        }      }      if(numlist.size() == 1){        ans.add(numlist.get(0));      }    }}
这个思路看起来是没有问题，的确把所有可能的等式全部考虑到了，但是考虑了许多重复的情况，测试用例中的：
"2*3-4*5"
它的所有可能等式情况为：
(2*(3-(4*5))) = -34((2*3)-(4*5)) = -14((2*(3-4))*5) = -10(2*((3-4)*5)) = -10(((2*3)-4)*5) = 10
输出应该为：[-34, -14, -10, -10, 10]
但是用上面的代码运行出来的结果为：
可以发现结果中多了一个-14，这是为什么呢？因为上面的算法是主要考虑两个数字合并，当算式中，2和3合并的时候，已经考虑过了((2*3)-(4*5)) = -14这个情况，但是到了4和5进行合并时，这个情况又再一次被考虑到，虽然重复了但是还是被记录到了结果中，所以不能通过测试，由于我暂时还没有找到修改的办法，所以这里介绍另外一种更加简洁到位的算法。
1. 也是采用分而治之的递归方法，核心思想不是考虑两个数字的合并，而是从操作符出发，不断地把字符串根据操作符进行分割，直到分到不再有操作符，只剩数字之后再进行操作。
2.这种方法不需要单独的把数字和操作符都提取出来，因为在递归的最后一步，操作符应全部被提取出去了。
3. 用到了HashMap来记录字符串和对应计算结果，利用了键值的唯一性防止了重复计算，提高了代码效率。
代码如下：
public class Solution {        Map<String, List<Integer>> map = new HashMap<>();        public List<Integer> diffWaysToCompute(String input) {        List<Integer> res = new ArrayList<>();        for (int i = 0; i < input.length(); i++) {            char c = input.charAt(i);            if (c == '+' || c == '-' || c == '*') {                String p1 = input.substring(0, i);                String p2 = input.substring(i + 1);                List<Integer> l1 = map.getOrDefault(p1, diffWaysToCompute(p1));                List<Integer> l2 = map.getOrDefault(p2, diffWaysToCompute(p2));                for (Integer i1 : l1) {                    for (Integer i2 : l2) {                        int r = 0;                        switch (c) {                            case '+':                                r = i1 + i2;                                break;                            case '-':                                r = i1 - i2;                                break;                            case '*':                                r = i1 * i2;                                break;                        }                        res.add(r);                    }                }            }        }        if (res.size() == 0) {            res.add(Integer.valueOf(input));        }        map.put(input, res);        return res;    }}看着自己快100行还不能通过的代码以及别人一小段就可以AC的代码后，内心是十分抗拒的，感觉还有很长的路要走，在考虑算法的时候，还是应该要更加谨慎，不能简单粗暴的直接全部过一遍，这样既耗费资源，效率也很低。