当前位置：首页 > news >正文

数组与贪心算法——409、621（1中1简）

news 来源：原创 2024/9/20 0:26:35

409. 最长回文串(简单)

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的 最长的

回文串的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

解法一、统计

class Solution {public int longestPalindrome(String s) {int[] alphabet = new int[52];boolean odd = false;int even = 0;for(int i = 0;i < s.length();i++){char c = s.charAt(i);if(Character.isUpperCase(c)){alphabet[c - 'A']++;}else{alphabet[c - 'a' + 26]++;}}for(int i = 0;i < 52;i++){even += alphabet[i] / 2 * 2;if(alphabet[i] % 2 == 1)odd = true;}return odd ? even + 1 : even;}
}

以下是两种改善的解法。解法一优化掉了一个布尔值，而且减少了数组的添加判断（空间换时间）。解法二的ans<s.length非常巧妙。

class Solution {public int longestPalindrome(String s) {int[] count = new int[128];int length = s.length();for (int i = 0; i < length; ++i) {char c = s.charAt(i);count[c]++;}int ans = 0;for (int v: count) {ans += v / 2 * 2;if (v % 2 == 1 && ans % 2 == 0) {ans++;}}return ans;}
}

public int longestPalindrome(String s) {char[] occurs = new char[128];int ans = 0;for (int i = 0; i < s.length(); ++i) {char c = s.charAt(i);occurs[c]++;if (occurs[c] == 2) {ans += 2;occurs[c] = 0;}}if (ans < s.length()) ans++;return ans;}

621. 任务调度器（中等）

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

解法一、标记模拟

每次都找到一个可以调用的，然后把里面数量最大的那个取出来怼上去。。

class Solution {public static int leastInterval(char[] tasks, int n) {int complete = 0,taskNum = tasks.length,count = 0;int[][] num = new int[26][2];for(char task : tasks){num[task - 'A'][0]++;num[task-'A'][1] = -n-1;}for(;complete < taskNum;count++){int max = 0,maxIndex = -1;for(int i = 0;i < 26;i++)if(num[i][0] > max && count - num[i][1] > n){max = num[i][0];maxIndex = i;}if(maxIndex != -1){complete++;num[maxIndex][0]--;num[maxIndex][1] = count;}}return count;}
}

解法二、贪心

 public int leastInterval(char[] tasks, int n) {//统计每个任务出现的次数，找到出现次数最多的任务int[] hash = new int[26];for(int i = 0; i < tasks.length; ++i) {hash[tasks[i] - 'A'] += 1;}Arrays.sort(hash);//因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列（X看作预占位置）//该序列长度为int minLen = (n+1) *  (hash[25] - 1) + 1;//此时为了尽量利用X所预占的空间（贪心）使得整个执行序列长度尽量小，将剩余任务往X预占的空间插入//剩余的任务次数有两种情况：//1.与A出现次数相同，比如B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1//2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列//直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为nfor(int i = 24; i >= 0; --i){if(hash[i] == hash[25]) ++ minLen;}//当所有X预占的位置插满了怎么办？//在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件//因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度return Math.max(minLen, tasks.length);}