Question7 种花问题
/**
* 假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。
* 可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
* <p>
* 给定一个花坛(表示为一个数组包含0和1,其中0表示没种植花,1表示种植了花),
* 和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False。
* <p>
* 思路:
* 先把第一个和最后一个给种上
* 然后再循环找能种上的花盆,种上之后改成1
*/
public class Question7 {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
// n=0判断
if (n == 0) {
return true;
}
// 判断花盆数量只有一个的话
if(flowerbed.length==1){
if(flowerbed[0]==0&&n==1){
return true;
}
return false;
}
// 先排除掉第一和最后一盆
if(flowerbed[0]==0&&flowerbed[1]==0){
flowerbed[0]=1;
n--;
}
if (flowerbed[flowerbed.length - 1] == 0 && flowerbed[flowerbed.length-2]==0) {
flowerbed[flowerbed.length-1]=1;
n--;
}
// 遍历花盆
for (int i = 1; i < flowerbed.length - 1; i++) {
if (flowerbed[i] == 1) {
continue;
} else if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
n--;
flowerbed[i] = 1;
}
}
return n <= 0 ? true : false;
}
}
Question 8 判断子序列
/**
* 给定字符串 s 和 t ,判断 s 是否为 t 的子序列
*
* 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
* 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。
* (例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
*
* 解题思路:
* 直接遍历目标数组,应用一个指针size
*
*/
public class Question8 {
public boolean isSubsequence(String s, String t) {
int size = 0;
for(int i = 0;i<t.length()&&size<s.length();i++){
if(s.charAt(size)==t.charAt(i)){
// 一样了,size++
size++;
}
}
return s.length()==size?true:false;
}
}
Question 9 非递减数列
/**
* 给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
* 我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
* <p>
* 解题思路:
* 见注释
*/
public class Question9 {
public boolean checkPossibility(int[] nums) {
// 非空判断
if (nums.length == 0 || nums == null || nums.length == 1) {
return true;
}
// 定义删除次数
int index = 0;
// 第一个数特殊处理
if (nums[0] > nums[1]) {
index++;
nums[0] = nums[1];
}
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
// 找到非递增的数
index++;
// 修改数字 最大能承受的修改的数字
// 注意这里需要进行贪心判断
if (nums[i - 1] <= nums[i + 1]) {
// 此时上一个比下一个还小,那么就没必要直接改下一个了,直接修改nums[i]
nums[i] = nums[i - 1];
} else {
// 上一个比下一个要大,说明要实现递增就只能够修改nums[i+1]了
nums[i + 1] = nums[i];
}
}
}
return index <= 1 ? true : false;
}
}
Question 10 最大子序和
/**
* 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
* 例如:
* 输入: [-2,1,-3,4,-1,2,1,-5,4],
* 输出: 6
* 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
* 运用到动态规划的小知识
*/
public class Question10 {
public int maxSubArray(int[] nums) {
// 非空判断
if (nums.length == 0 || nums == null) {
return 0;
}
// 定义初始化最大值
int max = nums[0];
// 初始化sum
int sum = 0;
for (int num : nums) {
if (sum > 0) {
// 有所增益
sum += num;
} else {
// 没有增益 舍弃前者
sum = num;
}
// 前一个最大值已经存储好了 ,与新的最大值进行比对
max = Math.max(sum, max);
}
return max;
}
}
/**
* 字符串 S 由小写字母组成。
* 我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。
* 返回一个表示每个字符串片段的长度的列表。
*/
public class Question11 {
public List<Integer> partitionLabels(String S) {
// 非空判断
if (S == null || S.length() == 0) {
return new ArrayList<Integer>();
}
// 统计每个字母最后出现的位置
int[] last = new int[26];
for (int i = 0; i < S.length(); i++) {
last[S.charAt(i) - 'a'] = i;
}
// 统计结果
List<Integer> list = new ArrayList<>();
// 记录当前最大的目标字母出现的最后位置
int maxIndex = 0;
// 记录当前目标字母出现的最后位置,初始化不能为0,防止第一个字母为a
int index = -1;
// 记录最后i的值
int lastI = -1;
// 遍历S
for (int i = 0; i < S.length(); i++) {
// 获取当前字母的最后出现位置
index = last[S.charAt(i) - 'a'];
// 判断是否是比maxIndex还要大
if (index > maxIndex) {
// 修改maxIndex 继续找
maxIndex = index;
} else if (index < maxIndex) {
// 直接继续,说明该字母在范围内
continue;
} else if (index == maxIndex&& maxIndex==i) {
// 找到一个范围了,记录 初始化数据
list.add(maxIndex-lastI);
// 初始化
lastI = maxIndex;
// maxIndex不能初始化为0,需要初始化为max++ 防止出现最后只剩下一个字母的情况
maxIndex++;
index = -1;
}
}
return list;
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于