力扣Hot100刷题日常（最大子数组和，合并区间， 缺失的第一个正数，电话号码的字母组合）
力扣Hot100刷题日常（最大子数组和，合并区间， 缺失的第一个正数，电话号码的字母组合）
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
题目分析：
这道题目使用到了动态规划，找到数组内某个子区间（一个数字也是区间）中和最大的一块区间，
1.当数组里全是负数，就是找哪个负数最大
2.当数组中有正有负的情况下，先滤清一个思路 当有正数的情况下，肯定先从正数可以算，不然前面从负数开始算，值肯定会变小 当和小于0时，这块区间就告一段落，得找下一个正数开始算
动态规划状态定义
-
dp[i]表示以nums[i]为结尾的子数组的最大和。
状态转移方程
对于每个位置 i：
- 如果将当前数字
nums[i]加到前一个位置的最大子数组和dp[i-1]上，结果更大，则当前dp[i] = nums[i] + dp[i-1]。 - 否则，
dp[i] = nums[i]（以nums[i]为新的子数组起点）。
状态转移方程： dp[i]=max(nums[i],nums[i]+dp[i−1]) 初始条件
-
dp[0] = nums[0]，因为第一个元素只能是自己。
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int ret = dp[0];
for(int i = 1;i < nums.length;i++) {
if(nums[i] +dp[i-1] > nums[i]) {
dp[i] = nums[i] +dp[i-1];
} else {
dp[i] = nums[i];
}
ret = Math.max(ret,dp[i]);
}
return ret;
}
}优化，使用prev记录当前dp[i]的值
public int maxSubArray(int[] nums) {
int prev = nums[0];
int ret = nums[0];
for (int i = 1; i < nums.length; i++) {
prev = Math.max(nums[i], nums[i] + prev); // 计算当前的最大值
ret = Math.max(ret, prev); // 更新全局最大值
}
return ret;
}合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
思路： 1 先进行排序 这样的话可以让小的区间在前 可以一次遍历所有的区间 Lambda 表达式
(x, y) -> x[0] - y[0]此时按照第一列升序排序。 如果按照第二列升序的话 就是(x, y) -> x[1] - y[1]如果为第一列降序排序。(x, y) -> y[0] - x[0]2 先指定最小的区间 定义它们的左端点和右端点
如图，进行遍历的时候从第二个数组开始 并且指定他们的首尾 a b 找到并集 就是要找到他们共同覆盖最大的一块区域 当 right <= a 的时候 ，此时说明他们一定有并集 ，所有将right 定义到他们俩个数组中最大的一个数上 right = max(right,b） 反之，当 a > right 的时候 这个时候它们一定不可能会有并集 所以直接将刚才的最终结果ret中 ，并且将最新的 left = a right = b 继续下一个寻找
细节： 当循环结束，再把最后一个nums(left,right)加到最终结果中
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(v1,v2) ->{
return v1[0] - v2[0];
});
int len = intervals.length;
List<int[]> ret = new ArrayList<>();
int left = intervals[0][0],right = intervals[0][1];
for(int i = 1 ;i < len ; i++) {
int a = intervals[i][0] , b = intervals[i][1];
if(a <= right) {
right = Math.max(right,b);
}else {
ret.add(new int[]{left,right});
left = a;
right = b;
}
}
ret.add(new int[]{left,right});
return ret.toArray(new int[0][]);
}
}缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
题目分析：.
这道题要我们找到没有出现的最小的正整数。假设1没出现 就直接返回1 依次下去
1)暴力解法：
1.将数组中的数字存放到哈希表中，并且记录一下最大的一个数字max 2.从第一个正数开始遍历 1--max 看看哪个在哈希表中不存在 因为是按顺序返回，如果第一次遍历到不存在的数字，直接返回即可 如果遍历完 说明 1---max中的数字都存在，直接返回max后的一个数字即可
class Solution {
public int firstMissingPositive(int[] nums) {
HashSet<Integer> hash = new HashSet<>();
int max = 0;
for(int i = 0;i< nums.length;i++) {
max = Math.max(max,nums[i]);
hash.add(nums[i]);
}
for(int i = 1 ;i <= max ;) {
if(hash.contains(i)) {
i++;
} else {
return i;
}
}
return max+1;
}
}2）因为不能使用额外的空间 并且要在O(N)时间内完成
参考力扣大佬 林小鹿 41. 缺失的第一个正数 - 力扣（LeetCode）
原地哈希： 1）假设数组长度是n，我们通过某种规律的交换恢复数组，使得,nums[0]=1, nums[1]=2 … nums[n−1]=n ，即恢复完的数组中的每个数都应满足nums[i]=i+1。如果某个nums[i]不满足，说明数组中缺失该i+1数。以[3,4,−1,1] 为例：恢复后的数组应当为 [1,−1,3,4]，其中nums[1]!=(1+1)我们就可以知道缺失的数为2。 2） 那么我们如何将数组进行恢复呢？我们发现数组的值num[i]和下标i有一定的关系，即nums[i]==nums[nums[i]−1]，下标i==nums[i]−1。 3）因此我们可以对数组进行一次遍历。对于处在[1,n]之间的数nums[i],如果其nums[i]！=nums[nums[i]−1]，我们就将nums[i], nums[nums[i]−1]不断进行交换，直到nums[i]==nums[nums[i]−1]。 4）若存在不在[1,n]区间的数时，则表示该数一定会在原数组占空间，且占到不能被对应的位置上，因此从小到大枚举，若nums[i]!=i+1，则表示i+1这个数是第一个缺失的正数，若都没有缺失，那么n+1就是第一个缺失的正数。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
// swap
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if ((i + 1) != nums[i]) {
return i + 1;
}
}
return n + 1;
}
}电话号码的字母组合
1）使用一个String数组先将每个数字对应的字符存储在数组对应的下标内，便于取元素 2）类似全排列的思路，可以迭代...
class Solution {
String[] digit = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> ret ;
StringBuffer path = new StringBuffer();
public List<String> letterCombinations(String digits) {
ret = new ArrayList<>();
if(digits.length() == 0) {
return ret;
}
dfs(digits,0);
return ret;
}
void dfs(String digits , int pos) {
if(pos == digits.length()) {
ret.add(path.toString());
return;
}
String cur = digit[digits.charAt(pos) - '0'];
for(int i = 0;i < cur.length();i++) {
char ch = cur.charAt(i);
path.append(ch);
dfs(digits,pos+1);
path.deleteCharAt(path.length()-1);
}
}
}腾讯云开发者
