LeetCode刷题——Day4

小鱼儿 2022-03-27 10:26 226阅读 0赞

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

**示例 1:**

输入: 121
    输出: true

**示例 2:**

输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

思路：比较对称的字母是否相等，想等的话继续遍历，一旦出现不相等就说明不是回文，立即跳出循环。（负数肯定不是回文，所以在开头可以先加一个判断，可是我加了判断以后执行时间更长了，不过我觉得加上更好）

class Solution {
        public boolean isPalindrome(int x) {
            		boolean b=true;
    	char[] ch=String.valueOf(x).toCharArray();
    	for(int i=0;i<ch.length/2;i++) {
    		if(ch[i]!=ch[ch.length-1-i])
    		{
    			b=false;
    			break;
    			}
    	}
    	return b;
        }
    }

10、[正则表达式匹配][Link 1]

给定一个字符串 (`s`) 和一个字符模式 (`p`)。实现支持 `'.'` 和 `'*'` 的正则表达式匹配。

'.' 匹配任意单个字符。
    '*' 匹配零个或多个前面的元素。

匹配应该覆盖**整个**字符串 (`s`) ，而不是部分字符串。

**说明:**

*  `s` 可能为空，且只包含从 `a-z` 的小写字母。
 *  `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符 `.` 和 `*`。

**示例 1:**

输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。

**示例 2:**

输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
    
    示例 4:
    输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"

事实上java中本身就有一个函数可以实现这个功能了：

class Solution {
        public boolean isMatch(String s, String p) {
            if(s.matches(p))
                return true;
            else
                return false;
        }
    }

如果自己实现的话，思路是：

首先分成两大类情况：1）当前比较的模式字符串的下一个字符是“\*”2）当前比较的模式字符串的下一个字符不是“\*”

在1）下又可分三个情况：1、当前比较的字符串和模式字符串字母不相等，而且模式字符不是“.”，那么直接返回false

2、当前比较的字符串和模式字符串字母不相等，但是模式字符是“.”，那么都后退一步，比较各自的下一个字符

3、当前比较的字符串和模式字符串字母相等，那么也后退一步，比较各自的下一个字符

在2）下又可分四个情况：1、当前相等，而且字符串后一个字母和当前是一样的，那么，字符串后退一步，模式不动

2、当前相等，而且字符串后一个字母和当前是不一样的，那么，字符串后退一步，模式后退两步

3、当前不等，字符串后退一步，模式后退两步（这个感觉只能这样用函数迭代做，单单判断的话，数组就会越界）

class Solution {
     public boolean isMatch(String s, String p) {
       if (s == null || p == null){
                return false;  
            }
            if (p.equals(".*")){
                return true;
            }
            int strIndex = 0, patternIndex = 0;                 // 从字符串和模式的第一位开始进行匹配
            return match(s, strIndex, p, patternIndex);
        }
    public boolean match(String str, int strIndex, String pattern, int patternIndex){
    
            if (strIndex == str.length() && patternIndex == pattern.length()){  // 字符串和模式同时都到末尾
                return true;
            }
            if (strIndex != str.length() && patternIndex == pattern.length()){  // 模式先到末尾
                return false;
            }
            if (patternIndex + 1 < pattern.length() && pattern.charAt(patternIndex + 1) == '*'){  
            // 下一个字符是*
                if ((strIndex != str.length() && str.charAt(strIndex) == pattern.charAt(patternIndex)) ||
                        (strIndex != str.length() && pattern.charAt(patternIndex) == '.') ){
                    return match(str, strIndex, pattern, patternIndex + 2) ||
                            match(str, strIndex + 1, pattern, patternIndex + 2) ||
                            match(str, strIndex + 1, pattern, patternIndex);
                }else {
                    return matchChar(str, strIndex, pattern, patternIndex + 2);
                }
            }else if ((strIndex!=str.length() && str.charAt(strIndex) == pattern.charAt(patternIndex)) ||
                    (strIndex != str.length() && pattern.charAt(patternIndex) == '.')){
                // 下一个字符不是*，字符串当前字符和模式中的当前字符相匹配
                return match(str, strIndex + 1, pattern, patternIndex + 1);
            }
            return false;
        }
    
    }

11、[盛最多水的容器][Link 2]

给定 *n* 个非负整数 *a*1，*a*2，...，*a*n，每个数代表坐标中的一个点 (*i*, *ai*) 。在坐标内画 *n* 条垂直线，垂直线 *i* 的两个端点分别为 (*i*, *ai*) 和 (*i*, 0)。找出其中的两条线，使得它们与 *x* 轴共同构成的容器可以容纳最多的水。

**说明：**你不能倾斜容器，且 *n* 的值至少为 2。

![question_11.jpg][]

图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

**示例:**

输入: [1,8,6,2,5,4,8,3,7]
    输出: 49

思路：两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 max来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max，并将指向较短线段的指针向较长线段那端移动一步。

class Solution {
        public int maxArea(int[] height) {
                   int l=0,max=0;
    	       int r=height.length-1;
    	       while(l<r) {
    	    	   int area=(Math.min(height[l], height[r]))*(r-l);
    	    	   max=Math.max(max, area);
    	    	   if(height[l]> height[r])
    	    	   {
    	    		   r--;
    	    	   }
    	    	   else {
    	    		   l++;
    	    	   }
    	       }
    	   return max;
        }
    }

12、[整数转罗马数字][Link 3]

罗马数字包含以下七种字符： `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 的范围内。

class Solution {
        public String intToRoman(int num) {
            if(num<1||num>3999)
    		{return "";}
    		 int[] values={1000,900,500,400,100,90,50,40,10,9,5,4,1};
    	    String[] symbol={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    	    StringBuilder s=new StringBuilder();
    	    for(int i=0;i<values.length;i++) {
    	    	while(num>=values[i]) {
    	    		num=num-values[i];
    	    		s.append(symbol[i]);
    	    		
    	    	}
    	    	if(num==0)
    	    	{
    	    		break;
    	    	}
    	    }
    	    return s.toString();
        }
    }

13、[罗马数字转整数][Link 4]

思路：就是上面那一题反过来想，首先建立一个HashMap来映射字母和值，然后对字符串从左到右遍历字符，如果当前字符代表的值大于等于右边字符的值，就加上该值；否则就用右边的值减去左边的，同时向后进两步遍历其他的字符。以此类推到最左边的字符，最终得到结果。

class Solution {
        public int romanToInt(String s) {
            if(s==null||s==""){return 0;}
         
            		int total=0;
    		
    		    Map<Character,Integer> map=new HashMap<>();
    	map.put('M', 1000);
    	map.put('D', 500);
    	map.put('C', 100);
    	map.put('L', 50);
    	map.put('X', 10);
    	map.put('V', 5);
    	map.put('I', 1);
    if(s.length()==1)
    {
        return map.get(s.charAt(0));
    }
    		  for(int i=0;i<s.length()-1;) {
    			
    			  char c1=s.charAt(i);
    			  char c2=s.charAt(i+1);
    			  if(map.get(c1)<map.get(c2)) {
    				  total=total+map.get(c2)-map.get(c1);
    				  i+=2;
    				
    			  }
    			  else {
    				  total=total+map.get(c1); 
    				  i++;
    				 
    			  }
    			    if(i==s.length()-1) {
    				  total+=map.get(s.charAt(s.length()-1));
    			  }
    		  }
          
    		return total;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/regular-expression-matching/
[Link 2]: https://leetcode-cn.com/problems/container-with-most-water/
[question_11.jpg]: /images/20220327/24911eed76c145cf921340e497dbf620.png
[Link 3]: https://leetcode-cn.com/problems/integer-to-roman/
[Link 4]: https://leetcode-cn.com/problems/roman-to-integer/