[toc]
16.17：程序员面试金典 连续数列
describe
给定一个整数数组，找出总和最大的连续数列，并返回总和。 示例： 输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
code
import javax.xml.parsers.SAXParser;public class InterView16_17 {//mainpublic static void main(String[] args) {Solution s = new Solution();System.out.println(s.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); //6}static class Solution {//使用动态规划方式public int maxSubArray(int[] nums) {if(nums == null || nums.length == 0){return 0;}if (nums.length == 1) {return nums[0];}int[] dp = new int[nums.length];dp[0] = nums[0];int max = dp[0];//使用动态规划方式处理for (int i = 1; i <nums.length ; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);max = Math.max(max, dp[i]);}return max;}}}
17.16：程序员面试金典 按摩师
describe
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
示例 1：输入： [1,2,3,1]输出： 4解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：输入： [2,7,9,3,1]输出： 12解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：输入： [2,1,4,5,3,1,1,3]输出： 12解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
code
public class InterView17_16 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.massage(new int[]{1, 2, 3, 1})); //4
}
/**
* 每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
*
* 使用动态规划方式：
* 创建dp[]
*/
static class Solution {
public int massage(int[] nums){
if (nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
}else{ // 有两个数字以上
//创建dp 动态数组
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
int max = dp[1];
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}
}
}
}
3.无重复字符的最长子串
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2: 输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
code
package bytedance;
import java.util.HashSet;
import java.util.Set;
public class LeetCode01 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lengthOfLongestSubstring("pwwkew"));
}
static class Solution {
/**
* 无重复字符的最长子串
*
* @param s
* @return
*/
//pwwkew
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); i++) {
//进行判断
int j = i;
//判断如果重复, 就一直向右查找
while (j < s.length() && !isDuplicated(s, i, j, s.charAt(j))) {
j++;
}
//判断是否最长
if (j - i > max) {
max = j-i;
}
}
return max;
}
//判断是否重复的方法
public boolean isDuplicated(String s, int start, int end, char ch) {
//从起点到终点，如果存在相同的就直接返回true
for (int i = start; i < end; i++) {
if (s.charAt(i) == ch) return true;
}
return false;
}
}
}
14. 最长公共子串
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
code:
public class ByteDance02 {
//main
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
}
private static class Solution {
//判断最长公共前缀
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String ans = strs[0];
for (int i = 1; i < strs.length; i++) { //从第二个开始进行遍历
int j = 0;
for (; j < ans.length() && j < strs[i].length(); j++) { //进行内部遍历
if(ans.charAt(j) != strs[i].charAt(j)){
break;
}
}
ans = ans.substring(0, j); //
//处理这种特殊情况，如果确实没有匹配的最长子串，就直接返回空子串即可
if (ans.equals("")) {
return ans;
}
}
return ans;
}
}
}
39. 组合总数
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
code
public class LeetCode39 {
public static void main(String[] args) {
Solution s = new Solution();
for (List<Integer> list : s.combinationSum(new int[]{2, 3, 6, 7}, 7)) {
for (Integer integer : list) {
System.out.print(integer);
}
System.out.println();
}
}
static class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
combo(res, candidates, target, new ArrayList<Integer>(), 0);
return res;
}
private void combo(List<List<Integer>> res, int[] candidates, int target, ArrayList<Integer> tempList, int index) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(tempList));
}else{
for (int i = index; i < candidates.length; i++) {
tempList.add(candidates[i]);
combo(res, candidates, target - candidates[i], tempList, i);
tempList.remove(tempList.size() - 1);
while (i< candidates.length-1 && candidates[i] == candidates[i+1]) i++;
}
}
}
}
}
40. 组合总数2
题目描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
code
package com.wangyg.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LeetCode40 {
public static void main(String[] args) {
Solution s = new Solution();
// System.out.println(s.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
System.out.println(s.combinationSum2(new int[]{2,5,2,1,2}, 5));
}
/**
* 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
*
* candidates 中的每个数字在每个组合中只能使用一次。
*
* 说明：
*
* 所有数字（包括目标数）都是正整数。
* 解集不能包含重复的组合。
* 示例 1:
*
* 输入: candidates = [10,1,2,7,6,1,5], target = 8,
* 所求解集为:
* [
* [1, 7],
* [1, 2, 5],
* [2, 6],
* [1, 1, 6]
* ]
* 示例 2:
*
* 输入: candidates = [2,5,2,1,2], target = 5,
* 所求解集为:
* [
* [1,2,2],
* [5]
* ]
* 1 2 2 2 5
*/
static class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//套路题
List<List<Integer>> res = new ArrayList<>();
//进行排序
Arrays.sort(candidates); //1 2 2 2 5
//target要找寻的目标
combo(res, candidates,target, new ArrayList<Integer>(), 0);
return res;
}
private void combo(List<List<Integer>> res, int[] candidates, int target, ArrayList<Integer> tempList, int index) {
//如果target<0了，就表示找的不对，所以递归结束
if (target < 0) {
return;
}
if (target == 0) { //等于0 ，表示正好完全找到一个合适的组合, 将templist中的一个临时结果放入到res中
res.add(new ArrayList<>(tempList));
}else {
for (int i = index; i < candidates.length; i++) {
tempList.add(candidates[i]);
//递归
combo(res, candidates, target - candidates[i], tempList, i + 1); //如果可以有重复使用数字，把 +1去掉即可
tempList.remove(tempList.size() - 1);
//去重，不能有重复的
while (i< candidates.length-1 && candidates[i] == candidates[i+1]) i++;
}
}
}
}
}
42. 剑指offer42.连续子数组的最大和(动态规划)
describe
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
code
package com.wangyg.leetcode;
public class LeetCode42 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
}
/**
* 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
*
* 要求时间复杂度为O(n)。
*
* 示例1:
* 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
* 输出: 6
* 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
*
* 提示：
* 1 <= arr.length <= 10^5
* -100 <= arr[i] <= 100
*/
static class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i <nums.length; i++) {
//这里为什么不用nums[i] 而是dp[i] 因为即便是nums[i]>0 ，前一个dp[i-1]如果是负的，结果也有可能是负的
if (dp[i-1] > 0) {
dp[i] = dp[i-1] + nums[i];
}else { // <0
dp[i] = nums[i];
}
max = Math.max(max, dp[i]);
}
return max;
}
}
}
121. Best Time to Buy and Sell Stock
describe
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
code
package com.wangyg.leetcode;
/**
* 小米面试题， 买卖股票的最佳时机
* 买卖股票的最好时机
*/
public class LeetCode121 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
}
//一维的动态规划
static class Solution {
public int maxProfit(int[] prices) {
//定义最大的收益变量
int maxProfit = 0;
//定义较小值，买入的点
int min = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
if (min > prices[i]) {//更新较小值
min = prices[i];
}
//计算较大的利益
if(maxProfit < prices[i] - min){ //如果当前值获取的收益比maxProfit大，就更新
maxProfit = prices[i]-min;
}
}
return maxProfit;
}
}
}
方式二： 使用动态规划数组存储中间过程值
class Solution {
public int maxProfit(int[] prices){
if(prices.length==0) return 0;
int n = prices.length;
int[] dp = new int[n];
int minPrice = prices[0];
for (int i = 1; i < prices.length; i++) {
minPrice = Math.min(minPrice, prices[i]);
dp[i] = Math.max(dp[i - 1], prices[i] - minPrice); //使用dp数组动态保存获取的最大收益值
}
return dp[n - 1];
}
}
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4.
code
package com.wangyg.leetcode;
public class Leetcode300 {
public static void main(String[] args) {
Solution s = new Solution();
//输出
System.out.println(s.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
}
/**
* 给定一个无序的整数数组，找到其中最长上升子序列的长度。
* <p>
* 示例:
* <p>
* 输入: [10,9,2,5,3,7,101,18]
* 输出: 4
* 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
* 说明:
* <p>
* 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
* 你算法的时间复杂度应该为 O(n2) 。
* 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
* <p>
* 维持顺序不变，
* 最暴力的做法： 从10 开始，然后进行 双层for循环进行遍历，然后重复进行查找，只要符合条件即可， 每个数字都向后找一遍，
* 然后看最长的子序列， 但是这样会有大量的重复计算，对于每个数字来说，后面的数字都要进行重复的遍历，所以是浪费性能
* <p>
* 改进方法： 从末尾进行查找
* 18： 1
* 101 : 1
* 7 : 2 (1->101 / 7-> 18都是2)
* 3： 3
* 5： 3
* 2： 4(2_> 5 / 2->3)
* 9: 2
* 10: 2
* <p>
* 最终结果： 所有中做大的是 4 ，所以最大的list 是4
*/
static class Solution {
/**
* 方式一： O(n2) 时间复杂度
*
* @param nums
* @return
*/
public int lengthOfLIS(int[] nums) {
//获取长度
int len = nums.length;
//0 1情况
if (len < 2) return len;
int[] record = new int[len + 1];
record[len - 1] = 1; //最后一个位置
int ans = -1;
for(int i = len-2; i>= 0; i--){ //从倒数第二个元素位置开始，进行倒叙计算
int cur = nums[i];//获取当前值
int max = 0;
//内循环，向后进行遍历
for (int j = i + 1; j < len; j++) {
//判断如果cur 比 后面值小 && max < record[j]
if (cur < nums[j] && max < record[j]) {
max = record[j]; // 获取最大的max
}
}
//当前位置的record[i] = max +1
record[i] = max+1;
//比较获取最大值 ，赋值给ans
if(record[i] > ans) ans = record[i];
}
return ans;
}
}
}
474. 一和零
题目描述
计算机世界中，我们总是追求有限的资源获取最大的收益，现在有m个
0和 n个1， 另外，还有一个仅包含0 和1 字符串的数组 你的任务是使用给定的 m 个0和 n 个1，找到能拼出存在于数组中的字符串的最大数量。每个0和1至多被使用一次。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
code
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//如果strs中没有字符串则直接返回0
if (strs == null || strs.length == 0) {
return 0;
}
//如果没有0 和1 ，则拼不出任何字符串
if (m == 0 && n == 0) {
return 0;
}
//创建动态规划数组, 计算最大收益
int[][] dp = new int[m+1][n+1];
for (String s : strs) {
char[] arr = s.toCharArray();
//zeros, ones 变量分别保存arr里面的 0 和 1 的个数
int zeros = 0;
int ones = 0;
for (char c : arr) {
if (c == '0') {
zeros ++;
}else{
ones ++;
}
}
//进行计算
for (int i = m ; i >= zeros ; i--) {
for (int j = n; j >= ones; j--) {
//进行计算， 可以选择装与不装这个字符串
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}
参考链接: https://blog.csdn.net/sinat_41917109/article/details/88891011
第二种做法:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if(strs == null || strs.length == 0)
return 0;
int[][] dp = new int[m+1][n+1];
for(int i = 0; i < strs.length; i++){
int zero = 0;int one = 0;
for(char c : strs[i].toCharArray()){
if(c == '0')
zero++;
else
one++;
}
for(int j = m;j >= zero; j--){
for(int k = n; k >= one; k--){
dp[j][k] = Math.max(dp[j][k],dp[j-zero][k-one]+1);
}
}
}
return dp[m][n];
}
}
557. 反转字符串中的单词 III
题目描述
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
code
package com.wangyg.leetcode;
public class LeetCode557 {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.reverseWords("Let's take LeetCode contest"));
}
/*
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
*/
static class Solution {
//
public String reverseWords(String s) {
StringBuffer stringBuffer = new StringBuffer();
String[] split = s.split(" ");
for (String tmp : split) {
String reverseTmp = new StringBuffer(tmp).reverse().toString();
stringBuffer.append(reverseTmp).append(" ");
}
return stringBuffer.toString().trim();
}
}
}
字符串翻转： new StringBuffer(tmp).reverse().toString()
567. 字符串的排列
题目描述
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
思路:
最直接是思路是暴力法，穷举字符串s1的所有可能，然后比较是否是s2的子串，但是这样的时间复杂度严重依赖于s1的子串长度，如果长度为10， 有10的阶乘种排列组合 优化思路： 使用数组获取每个字符出现的长度，然后使用滑动窗口的方式进行遍历，遍历过程中，比较s1map 和s2map两个是否相同，即可。
/**
*
*/
public class ByteDance03 {
public static void main(String[] args) {
String s1 = "ab";
String s2 = "eidbaooo";
//输出: False
System.out.println(checkInclusion(s1, s2));
}
//可能现需要找到一个位置，然后在根据这个位置，找到其他的连续的字母
//使用hash_table记录字母出现的长度
public static boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length())
return false;
int[] s1map = new int[26];//创建一个数组
int[] s2map = new int[26];//创建一个数组
for (int i = 0; i < s1.length(); i++)
s1map[s1.charAt(i) - 'a']++; //首先记录字符出现的个数
for (int i = 0; i <s2.length(); i++) { //滑动窗口的方式进行遍历类似， 滑动窗口前面的去掉， 后面的加上，然后进行比较长度是否相同
if (i >= s1.length()) {
--s2map[s2.charAt(i-s1.length()) -'a']; //将s2前面的元素移除， 效果同等于滑动窗口的方式
}
++s2map[s2.charAt(i) - 'a']; //将对应的元素添加到数组中
//对比数组元素是否相同
if (matches(s1map, s2map))
return true;
}
return false;
}
public static boolean matches(int[] s1map, int[] s2map) {
for (int i = 0; i < 26; i++) {
if (s1map[i] != s2map[i])
return false;
}
return true;
}
}
643. 子数组最大平均数I
题目描述
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例 1:
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
code
package com.wangyg.leetcode;
public class LeetCode643 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findMaxAverage(new int[]{1, 12, -5, -6, 50, 3}, 4)); //12.75
System.out.println(s.findMaxAverage(new int[]{5}, 1)); //5
System.out.println(s.findMaxAverage(new int[]{9, 7, 3, 5, 6, 2, 0, 8, 1, 9}, 6)); //5.33333333333
}
/**
* 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
* <p>
* 示例 1:
* <p>
* 输入: [1,12,-5,-6,50,3], k = 4
* 输出: 12.75
* 解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
*
* <p>
* 注意:
* <p>
* 1 <= k <= n <= 30,000。
* 所给数据范围 [-10,000，10,000]。
*/
static class Solution {
public double findMaxAverage(int[] nums, int k) {
//创建数组
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
double res = sum[k - 1] * 1.0 / k;
for (int i = k; i < nums.length; i++) {
res = Math.max(res, (sum[i] - sum[i - k]) * 1.0 / k);
}
return res;
}
}
}
674. 最长连续递增序列
题目描述
给定一个未经排序的整数数组，找到最长且连续的的递增序列，并返回该序列的长度。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
code
package com.wangyg.leetcode;
public class LeetCode674 {
public static void main(String[] args) {
Solution s = new Solution();
// System.out.println(s.findLengthOfLCIS(new int[]{1, 3, 5, 4, 7}));
System.out.println(s.findLengthOfLCIS(new int[]{2,2,2,2,2,}));
}
/**
* 最长连续递增序列
* 给定一个未经排序的整数数组，找到最长且连续的滴滴增序列，并返回该序列的长度
*/
static class Solution {
public int findLengthOfLCIS(int[] nums) {
//防御性编程，如果数组长度《1 直接返回0
if (nums.length < 1) {
return 0;
}
int d = 0;
int max = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i]> nums[i-1]){
max = Math.max(max, i-d+1);
}else{
//变换d 的位置，重新进行计算
d= i;
}
}
return max;
}
}
}
1144. 递减元素使数组呈锯齿状
题目描述
给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。
如果符合下列情况之一，则数组 A 就是 锯齿数组：
- 每个偶数索引对应的元素都大于相邻的元素，即
A[0] > A[1] < A[2] > A[3] < A[4] > ... - 或者，每个奇数索引对应的元素都大于相邻的元素，即
A[0] < A[1] > A[2] < A[3] > A[4] < ...
返回将数组 nums 转换为锯齿数组所需的最小操作次数。
示例 1：
输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。
示例 2：
输入：nums = [9,6,1,6,2]
输出：4
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1000
code
package com.wangyg.leetcode;
/**
* 锯齿操作，递减元素使数据成锯齿状
*/
public class LeetCode1144 {
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = new int[]{9, 6, 1, 6, 2};
System.out.println(s.movesToMakeZigzag(nums));
}
}
/**
* 步骤： [9,6,1,6,2]
* 第一步： d1 不处理 之比较右侧 d2=
*/
class Solution {
public int movesToMakeZigzag(int[] nums) {
int n = nums.length;
int ans1 = 0, ans2 = 0;
for (int i = 0; i < n; i++) {
// i>0 是边界条件， nums[i] >= nums[i-1] 是 右边>左边 否则结果为0
int d1 = (i > 0 && nums[i] >= nums[i - 1]) ? (nums[i] - nums[i - 1] + 1) : 0;
//把该位置变成比后一个小需要d2步 左边> 右边 结果d2 = nums[i]-nums[i+1]
int d2 = (i < n - 1 && nums[i] >= nums[i + 1]) ? (nums[i] - nums[i + 1] + 1) : 0;
if (i % 2 == 0) { //偶数为ans1
ans1 += Math.max(d1, d2);
} else { //奇数为ans2
ans2 += Math.max(d1, d2);
}
System.out.println(i+":"+ ans1);
System.out.println(i+":"+ ans2);
}
return Math.min(ans1, ans2);
}
}
若有收获，就点个赞吧
0 人点赞
