力扣热题2-盛最多水的容器
按照leetcode刷一遍:leetcode hot
7. 整数反转
题目给定,不允许存储64位整数,也就是边界条件要自行判断:
如果反转后整数超过 32 位的有符号整数的范围
[−2^31, 2^31 − 1]
,就返回 0。
class Solution {
public int reverse(int x) {
if(x==Integer.MIN_VALUE) return 0;
int result = 0;
int sign = x<0?-1:1;
x = Math.abs(x);
int LASTLIMIT = Integer.MAX_VALUE/10;
int cur;
while(x!=0) {
//System.out.println(result);
cur = x%10;
if(result>LASTLIMIT) {
return 0;
} else if(result==LASTLIMIT&&((sign==1&&cur>=8)||(sign==-1&&cur>8))) {
return 0;
} else {
result = result*10+cur;
x/=10;
}
}
return result*sign;
}
}
在java里面的话,取余操作是先按照正数然后加上符号来做的,所以这里我的去符号操作可以省略。
8. 字符串转换整数 (atoi)
可以看看边界条件的限定方法。
class Solution {
public int myAtoi(String s) {
if(s==null) return 0;
s = s.trim();
if(s.length()==0) return 0;
int idx = 0;
int n = s.length();
int result = 0;
int sign = 1;
if(s.charAt(0)=='-') {
sign=-1;
idx++;
} else if(s.charAt(0)=='+') {
idx++;
} else if(s.charAt(0)<'0'||s.charAt(0)>'9') {
return 0;
}
for(;idx<n;idx++) {
if(s.charAt(idx)<'0'||s.charAt(idx)>'9') {
return sign*result;
}
//直接在这里把最大值最小值也返回了
if(result>Integer.MAX_VALUE/10||
(result==Integer.MAX_VALUE/10&&((s.charAt(idx)>='7'&&sign==1)||(s.charAt(idx)>='8'&&sign==-1)))) {
return sign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;
}
//这里不会出现最大值最小值
result = result*10+(int)(s.charAt(idx)-'0');
}
return result*sign;
}
}
10. 正则表达式匹配
写了很久才写出来。两点吧:
- 在判断当前位时判断下一位是不是星号
- 记忆化
class Solution {
public boolean isMatch(String s, String p) {
int[][] state = new int[s.length()][p.length()];
//0:没有状态
//1:true
//-1:false
return isMatch0(s,0,p,0,state);
}
private boolean isMatch0(String s,int s_start,String p,int p_start,int[][] state) {
if(s.length()==s_start&&p.length()==p_start) {
return true;
}
if(s.length()==s_start) {
if(p_start+1<p.length()&&p.charAt(p_start+1)=='*') {
return isMatch0(s,s_start,p,p_start+2,state);
}
return false;
}
if(p.length()==p_start) {
return false;
}
if(state[s_start][p_start]!=0) {
return state[s_start][p_start]==1;
}
boolean star = false;
boolean noStar = false;
if(p_start+1<p.length()&&p.charAt(p_start+1)=='*') {
star |= isMatch0(s,s_start,p,p_start+2,state); //跳过x*,不管等不等都可以跳过
//等才能继续
if(s.charAt(s_start)==p.charAt(p_start)||p.charAt(p_start)=='.') {
star |= isMatch0(s,s_start+1,p,p_start,state); //s前进一位
}
} else {
if(s.charAt(s_start)==p.charAt(p_start)||p.charAt(p_start)=='.') {
noStar |= isMatch0(s,s_start+1,p,p_start+1,state);
}
}
state[s_start][p_start] = (star|noStar)?1:-1;
return star|noStar;
}
}
(没想出来)11. 盛最多水的容器
没做出来。
双指针法。
例如最开始如上图,实际上只能移动短的,也就是h=3的。因为如果移动h=7的,得到的新的盛水量肯定比当前小,因为左边h=3水都漏跑了。也就是排除了长边移动的所有情况。
class Solution {
public int maxArea(int[] height) {
int result = 0;
int left = 0;
int right = height.length-1;
while(left<right) {
result = Math.max(result,(right-left)*Math.min(height[left],height[right]));
if(height[left]<height[right]) {
left++;
} else {
right--;
}
}
return result;
}
}
13. 罗马数字转整数
这一题的问题就在于怎么写的简洁吧,我的还行。
class Solution {
public int romanToInt(String s) {
Map<Character,Integer> map = new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
int result = map.get(s.charAt(0));
for(int idx = 1;idx<s.length();idx++) {
char c = s.charAt(idx);
if(map.get(c)>map.get(s.charAt(idx-1))) {
result+=map.get(c)-2*map.get(s.charAt(idx-1));
} else {
result+=map.get(c);
}
}
return result;
}
}
14. 最长公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
int idx = 0;
String headStr = strs[0];
while(true) {
if(idx>=headStr.length()) {
return strs[0].substring(0,idx);
}
for(int i=1;i<strs.length;i++) {
String str = strs[i];
if(idx>=str.length()||str.charAt(idx)!=headStr.charAt(idx)) {
return strs[0].substring(0,idx);
}
}
idx++;
}
}
}
(再看看)15. 三数之和
刚开始写出来的版本,效率比较低。
避免重复问题,就让三元组都必须是递增的形式,同时排序之后再相等的略过。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
Map<Integer,Integer> numMap = new HashMap<>();
for(int n:nums) {
numMap.put(n,numMap.getOrDefault(n,0)+1);
}
for(int i=0;i<nums.length;i++) {
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j=i+1;j<nums.length;j++) {
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(0-nums[i]-nums[j]<nums[j]) continue;
int tmp = 0;
if(0-nums[i]-nums[j]==nums[i]) tmp++;
if(0-nums[i]-nums[j]==nums[j]) tmp++;
if(numMap.getOrDefault(0-nums[i]-nums[j],0)>tmp) {
result.add(Arrays.asList(nums[i],nums[j],0-nums[i]-nums[j]));
}
}
}
return result;
}
}
啊,没想起来,排完序就不用用map了,直接双指针。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i=0;i<=nums.length-3;i++) {
if(i>0&&nums[i]==nums[i-1]) continue;
int left = i+1;
int right = nums.length-1;
int target = 0-nums[i];
while(left<right) {
if(left>i+1&&nums[left]==nums[left-1]) {
left++;
} else if(right<nums.length-1&&nums[right]==nums[right+1]) {
right--;
} else if(nums[left]+nums[right]>target) {
right--;
} else if(nums[left]+nums[right]==target) {
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
} else {
left++;
}
}
}
return result;
}
}