leetcode算法题解(Java版)-5-简单模拟,字符串处理
一、简单贪心
题目描述
Given n non-negative integers a1 , a2 , ..., an , where each represents a point at coordinate (i, ai ). n vertical lines are drawn such that the two endpoints of line i is at (i, ai ) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
思路
- 这题在一分钟内就想了个笨方法,迅速敲完,KO!
- 因为题目还是很简单,不考虑将装水的容器倾斜,所以只要考虑梯形中最短的边和底边的乘积就行了:正反两遍循环数组,第一遍从0~len,先固定最左边的边,从右往左遍历数组,如果碰到大于等于最左边边长的边,那就判断是否大于当前的最大盛水体积并跟新,然后就停止这次循环,将最左边的边向右移动一格,重复操作;第二遍从len~0,和第一遍一样。
代码
public class Solution { public int maxArea(int[] height) { int len=height.length; if(len==0){ return 0; } int maxW=0; for(int i=0;i<len;i++){ for(int j=len-1;j>i;j--){ if(height[j]>=height[i]){ if(height[i]*(j-i)>maxW){ maxW=height[i]*(j-i); } break; } } } for(int i=len-1;i>0;i--){ for(int j=0;j<i;j++){ if(height[j]>=height[i]){ if(height[i]*(i-j)>maxW){ maxW=height[i]*(i-j); } break; } } } return maxW; } }
思路2
- 好吧,虚心学习,看了一下其他人的代码。发现一个好方法:
- 从两边往中间走,每次舍弃较短的边,因为宽度减小,要通过高度的增加来弥补
代码
public class Solution { public int maxArea(int[] height) { int len=height.length; if(len==0){ return 0; } int l=0; int r=len-1; int maxW=0; while(l<r){ maxW=Math.max(maxW,Math.min(height[l],height[r])*(r-l)); if(height[l]<height[r]){ l++; } else{ r--; } } return maxW; } }
二、简单回文数字
题目描述
Determine whether an integer is a palindrome. Do this without extra space.
click to show spoilers.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
思路
- 题目有个限制,就是不能开辟新的空间。
- 那就和一般的回文串做法不同了,可以这么来搞:干脆求出它翻转过来的整型,最后比较是否值相等。
- 想到这个思路,是因为int型的特殊基本数据类型,特别对待,哈哈哈
代码
public class Solution { public boolean isPalindrome(int x) { if(x<0){ return false; } int reverse=0; int x_rel=x; while(x!=0){ reverse=reverse*10+x%10; x/=10; } return reverse==x_rel; } }
三、字符串,模拟
题目描述
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
spoilers alert... click to show requirements for atoi.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
思路
- 细节要求比较多,正负号,非法字符,溢出等都要考虑。
代码
public class Solution { public int atoi(String str) { if(str==null||str.length()==0){ return 0; } int pos=0; while(str.charAt(pos)==' '){ pos++; } int flag=1; if(str.charAt(pos)=='-'){ flag=-1; pos++; } if(str.charAt(pos)=='+'){ flag=1; pos++; } int len=str.length(); int res=0; for(int i=pos;i<len;i++){ char c=str.charAt(i); if(c<'0'||c>'9'){ break; } if(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&&c>'7')){ if(flag>0){ return Integer.MAX_VALUE; } else{ return Integer.MIN_VALUE; } } res=res*10+(c-'0'); } return res*flag; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
java基础加强之内省
java基础加强之内省 ============================================================================= 内省(Introspector类) —> JavaBean ----------------------------------------------------------------------------- 一、为什么要学内省? 开发框架时,经常需要使用java对象的属性来封装程序的数据, 每次都使用 反射技术 完成此类操作过于麻烦,所以SUN公司开发了一套API,专门用于操作java对象的属性。 ----------------------------------------------------------------------------- 二、什么是JavaBean和属性的读写方法? bean就是类,javabean就是java类。 ----------------------------------------------------------------------------...
- 下一篇
复现HITB PHP lover代码审计
参考文献:https://www.anquanke.com/post/id/104952 一直想学代码审计来着,看到了一篇大佬的关于php代码审计的wp,决定自己试一下 源码下载地址:https://hitbxctf2018.xctf.org.cn/contest_challenge/里面的web题目中的PHP lover 代码结构 Controller 控制器,只有index.controller.php Core 类及方法定义 templates 前端的各种html界面 uploads 里面是两张图片 back.sql 创建的数据表 config.php 连接数据库 function.php 定义过滤函数 index.php 入口文件 从index.controller.php看下主要功能 public function login() public function register() public function add() public function view() public function edit() public function export() logi...
相关文章
文章评论
共有0条评论来说两句吧...