leetcode算法题解(Java版)-3-广搜+HashMap
一、运算符——异或"^"
题目描述
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路
- 题目很简单,考到了一个知识点——异或:比较两个操作数的二进制的各个位置,相同则为0不同则为1。所以,1.与0异或是本身2.与和自己一样的异或是0.
代码
public class Solution { public int singleNumber(int[] A) { int res=0; for(int i=0;i<A.length;i++){ res^=A[i]; } return res; } }
二、动态规划
题目描述
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
思路:
- 一开始看错题了,孩子们本来站好队了,我按权重从大到小排了一下。。。看了别人的代码,思路并不难:先给每人一个糖果,两个循环解决问题,一,从前往后扫一遍,如果下一个比上一个权重大就在上一个基础上加一;再从后往前扫一遍,如果前面的比后面的权重大且糖果比他少就再后面的基础上加一刷新原有的值。
- 语法点:
Arrays.fill(array,val);Arrays.sort(array);
代码
import java.util.Arrays; public class Solution { public int candy(int[] ratings) { if(ratings==null||ratings.length==0){ return 0; } int len=ratings.length; int [] cnt=new int [len]; Arrays.fill(cnt,1); for(int i=1;i<len;i++){ if(ratings[i]>ratings[i-1]){ cnt[i]=cnt[i-1]+1; } } int sum=0; for(int i=len-1;i>0;i--){ if(ratings[i-1]>ratings[i]&&cnt[i-1]<=cnt[i]){ cnt[i-1]=cnt[i]+1; } sum+=cnt[i]; } return sum+cnt[0]; } }
三、模拟题(环状)
题目描述
There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
思路
- 设置start和end,分别放在首尾。如果能继续走就让end++,不能则让start退一个。结束while循环有两种可能结果,一个是sum>=0,则最后相会的点就是出发点,另一个则不可能。
代码
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int len=gas.length; int start=len-1; int end=0; int sum=0; sum=gas[start]-cost[start]; while(end<start){ if(sum>=0){ sum+=gas[end]-cost[end]; end++; } else{ start--; sum+=gas[start]-cost[start]; } } return sum>=0?start:-1; } }
四、BFS+HashMap
题目描述
Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.
思路
- 广搜,然后用map存储原来的和克隆的一一映射
- HashMap中通过get()来获取value,通过put()来插入value,containsKey()则用来检验对象是否已经存在
- Stack:
st.push(node);st.pop();st.empty();
代码
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ import java.util.Stack; import java.util.HashMap; public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node==null){ return null; } HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>(); Stack<UndirectedGraphNode> stackNode=new Stack<>(); stackNode.push(node); while(!stackNode.empty()){ UndirectedGraphNode tempNode=stackNode.pop(); if(map.containsKey(tempNode)){ continue; } UndirectedGraphNode copyNode=new UndirectedGraphNode(tempNode.label); for(UndirectedGraphNode uNode:tempNode.neighbors){ copyNode.neighbors.add(uNode); if(map.containsKey(uNode)){ continue; } stackNode.push(uNode); } map.put(tempNode,copyNode); } return map.get(node); } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Android项目实战(九):CustomShapeImageView 自定义形状的ImageView
原文: Android项目实战(九):CustomShapeImageView 自定义形状的ImageView 一个两年前出来的第三方类库,具有不限于圆形ImageView的多种形状ImageView,项目开发必备 github下载地址:https://github.com/MostafaGazar/CustomShapeImageView 1、首先源码中有一个第三方类库 :library 先要把Library导入到项目中, 不会的可以看下导入方法:关于Eclipse 和 IDEA 导入library库文件 的步骤 2、源码中res文件夹下有一个raw文件夹 复制到自己的项目中(选择性复制,是一些特殊的图形) 可以看到这里有一堆.svg格式的文件。 SVG可以算是目前最最火热的图片文件格式,这里作者已经给我们写好了几个特殊的图形 如果想要自定义更多形状的话,可以学习下SVG 1、shape_5.svg 五边形 2、shape_circle_2.svg 贝壳形 3、shape_flower.svg 花形 4、shape_heart.svg 心形 5、shape_star 星形1 6、s...
- 下一篇
Python——基本的方法(2)
Python内置了很多有用的函数,我们可以直接调用。 要调用一个函数,需要知道函数的名称和参数,可以直接从Python的官方网站查看文档。 常见的方法: 绝对值方法abs(-100),得到100; 最大值方法max(1,2,23,-20,100),得到100; 数据类型转换方法int('221'),得到数字221;int(12.344)得到12;bool(1)得到True,bool()得到False >> int('123') 123 >>> int(12.34) 12 >>> float('12.34') 12.34 >>> str(1.23) '1.23' >>> str(100) '100' >>> bool(1) True 函数名其实就是指向一个函数对象的引用,完全可以把函数名赋给一个变量,相当于给这个函数起了一个“别名 >>> a = abs # 变量a指向abs函数 >>> a(-1) # 所以也可以通过a调用abs函数 1 请利用P...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,7,8上安装Nginx,支持https2.0的开启