求职Leetcode题目（11）
1.最长连续序列
解题思路:
方法一：
- • 首先对数组进行排序，这样我们可以直接比较相邻的元素是否连续。
- • 使用一个变量 cur_cnt 来记录当前的连续序列长度。
- • 遍历排序后的数组：
- 如果当前元素与前一个元素相等，则跳过（因为相等的元素不会影响连续性）。
- 如果当前元素与前一个元素相差 1，则当前元素是连续序列的一部分，增加计数器 cur_cnt。
- 如果当前元素与前一个元素不连续，说明当前连续序列结束，更新最长连续序列 max，并重置 cur_cnt 为 1，准备重新计数。
- • 在遍历结束后，返回最长的连续序列长度。
这种方法思维就就比较简单，而且最后的效率也很不错！
class Solution {
public int longestConsecutive(int[] nums) {
Arrays.sort(nums);
int max =0;
for(int i =0;i<nums.length;i++){
int cur_cnt=1;
while((i+1<nums.length&&nums[i+1]==nums[i]+1)||(i+1<nums.length&&nums[i+1]==nums[i])){
if(nums[i+1]==nums[i]){
i++;
continue;
}
cur_cnt++;
i++;
}
max=Math.max(max,cur_cnt);
}
return max;
}
}方法二：
对于数组中存在的连续序列，为了统计每个连续序列的长度，我们希望直接定位到每个连续序列的起点，从起点开始遍历每个连续序列，从而获得长度。
那么如何获取到每个连续序列的起点呢，或者说什么样的数才是一个连续序列的起点？
答案是这个数的前一个数不存在于数组中，因为我们需要能够快速判断当前数num的前一个数num - 1是否存在于数组中。
同时当我们定位到起点后，我们就要遍历这个连续序列，什么时候是终点呢？
答案是当前数num的后一个数nunm + 1不存在于数组中，因此我们需要能够快速判断当前数num的后一个数num + 1是否存在于数组中。
为了实现上述需求，我们使用哈希表来记录数组中的所有数，以实现对数值的快速查找。
class Solution {
public int longestConsecutive(int[] nums) {
int res =0;//记录最长序列的长度
Set<Integer> numSet =new HashSet<>();//记录所有的数值
for(int num:nums){
numSet.add(num);//将数组中的值加入到hash表中
}
int seqLen;//连续序列的长度
for(int num:numSet){
//如果当前的书是一个连续序列的起点，统计这个连续序列的长度
if(!numSet.contains(num-1)){
seqLen =1;
while(numSet.contains(++num)) seqLen++;//不断查找连续序列，直到num的下一个数不存在数组中
res =Math.max(res,seqLen);//更新最长连续序列长度
}
}
return res;
}
2.单词拆分
- 将字符串 s 长度记为 n，wordDict 长度记为 m。为了方便，我们调整字符串 s 以及将要用到的动规数组的下标从 1 开始。
- 定义 f[i] 为考虑前 i 个字符，能否使用 wordDict 拼凑出来：当 f[i]=true 代表 s[1...i] 能够使用 wordDict 所拼凑，反之则不能。
- 不失一般性考虑 f[i] 该如何转移：由于 f[i] 需要考虑 s[1...i] 范围内的字符，若 f[i] 为 True 说明整个 s[1...i] 都能够使用 wordDict 拼凑，自然也包括最后一个字符 s[i] 所在字符串 sub。
- 我们可以枚举最后一个字符所在字符串的左端点 j，若 sub=s[j...i] 在 wordDict 中出现过，并且 f[j−1]=True，说明 s[0...(j−1)] 能够被拼凑，并且子串 sub 也在 wordDict，可得 f[i] = True。
- 为了快速判断某个字符是否在 wordDict 中出现，我们可以使用 Set 结构对 wordDict[i] 进行转存。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set =new HashSet<>();
for(String word:wordDict) set.add(word);
int n =s.length();
boolean[] f =new boolean[n+10];
f[0]=true;
for(int i =1;i<=n;i++){
for(int j =1;j<=i&&!f[i];j++){
String sub =s.substring(j-1,i);
if(set.contains(sub))f[i]=f[j-1];
}
}
return f[n];
}
}3.买卖股票的最佳时机III
class Solution {
public int maxProfit(int[] prices) {
int f1 =-prices[0],f2=0,f3=-prices[0],f4=0;
for(int i =1;i<prices.length;i++){
f1=Math.max(f1,-prices[i]);
f2=Math.max(f2,f1+prices[i]);
f3=Math.max(f3,f2-prices[i]);
f4=Math.max(f4,f3+prices[i]);
}
return f4;
}
}