Leetcodeday01--hl

Leetcode每日两题 day01

题目解法

217.存在重复元素

c++java 53、最大子数组和

c++java 题目解法 217.存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

c++

思路
1、将数组从小到大排序，相邻两个数字相等则说明存在重复元素。

class Solution {public: bool containsDuplicate(vector& nums) { if(nums.size()<=1){return false;} sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size()-1; i++){ if(nums[i]==nums[i+1]){ return true; } } return false; }};

2、将数组放入set中，若size不变，则说明没有重复元素。

return set(nums.begin(), nums.end()).size()!=nums.size();

知识点
1、c++中STL
STL序列式容器包括array vector deque list。所有顺序容器都提供了快速顺序访问元素的能力。顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

STL关联式容器包括map set。关联容器中的元素是按关键字来保存和访问的。存储机制基于红黑树。

map的key、set中的元素都是排序好的map的key、set中的元素都是唯一的，没有重复的

STL无序关联式容器包括unordered_map unordered_set。存储机制基于hash表。

2、c++中vector排序

sort(nums.begin(), nums.end());//由小到大 sort(nums.rbegin(), nums.rend());//由大到小

3、c++中vector大小

nums.size()

java

思路
1、将数组从小到大排序，相邻两个数字相等则说明存在重复元素。

class Solution { public boolean containsDuplicate(int[] nums) { if(nums.length<=1){return false;} Arrays.sort(nums); for(int i = 0; i < nums.length-1; i++){ if(nums[i]==nums[i+1]){ return true; } } return false; }}

2、将数组中的所有数字放进hashset中，如果每次都能成功add，那么说明没有重复元素。

class Solution { public boolean containsDuplicate(int[] nums) { Set set = new HashSet(); for (int x : nums) { if (!set.add(x)) { return true; } } return false; }}

知识点
1、java中数组排序

Arrays.sort(nums);

2、java中数组大小

nums.length

3、java中hashset
Set.add() 方法用来向 Set 集合添加对象。如果 Set 集合中已经包含相同的对象，则不改变 Set 集合。该方法返回值为 boolean 对象，如果 Set 集合中不包含要添加的对象，则添加对象并返回 true，否则返回 false。

4、java中hashmap
HashMap 是 Map 接口的常用实现类。系统将 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。
当程序执行 map.put(“语文” , 80.0); 时，系统将调用"语文"的 hashCode() 方法得到其 hashCode 值（每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值），之后系统会根据该 hashCode 值来决定该元素的存储位置。
hash(key)冲突时生成链表
详细链接: link

4、Java 中只有3类数据类型：原生类型（primitive8个）、数组、Object；

53、最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

c++

思路
1、贪心算法
如果当前数字之前连续的数字串和小于0，那么直接从自身开始；如果大于等于0，那么将自身加入数字串。设定一个result记录连续数字串和的最大值。

class Solution {public: int maxSubArray(vector& nums) { int sum = 0; int result = nums[0]; for(int i = 0; i < nums.size(); i++){ sum += nums[i]; result = max(result,sum); if(sum<0){ sum = 0; } } return result; }};

2、递归算法
思路相同

class Solution {public: int maxSubArray(vector& nums) { int m = nums[0]; for(int i = 1; i < nums.size(); i++){ nums[i] = max(nums[i], nums[i]+nums[i-1]); m = max(m ,nums[i]); } return m; }};

java

1、贪心算法(消耗时间最少)

class Solution { public int maxSubArray(int[] nums) { int result = nums[0]; int sum = 0; for(int i = 0; i < nums.length; i++){ sum += nums[i]; result = Math.max(sum, result); if(sum<0){ sum = 0; } } return result; }}

2、递归算法

class Solution { public int maxSubArray(int[] nums) { int result = nums[0]; for(int i = 1; i < nums.length; i++){ nums[i] = Math.max(nums[i], nums[i]+nums[i-1]); result = Math.max(nums[i], result); } return result; }}