Leetcode day01 --hl

题目解法

217.存在重复元素

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

c++java

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

思路
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()

思路
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；

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

思路
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;
    }
};

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;
    }
}