leetcode算法题解(Java版)-5-简单模拟,字符串处理

简介: 因为题目还是很简单,不考虑将装水的容器倾斜,所以只要考虑梯形中最短的边和底边的乘积就行了:正反两遍循环数组,第一遍从0~len,先固定最左边的边,从右往左遍历数组,如果碰到大于等于最左边边长的边,那就判断是否大于当前的最大盛水体积并跟新,然后就停止这次循环,将最左边的边向右移动一格,重复操作;第二遍从len~0,和第一遍一样。

一、简单贪心

题目描述

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;
    }
}
目录
相关文章
|
4月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
4月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
102 3
|
4月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
182 0
|
3月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
334 58
|
2月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
|
2月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
125 0
|
2月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
59 0
|
5月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
126 3
|
7月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
8月前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。

热门文章

最新文章