题目表述：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点?(i,?ai) 。在坐标内画 n 条垂直线，垂直线 i?的两个端点分别为?(i,?ai) 和 (i, 0)。找出其中的两条线，使得它们与?x?轴共同构成的容器可以容纳最多的水。eg. 输入[1,8,6,2,5,4,8,3,7]，输出49。
思路：
预处理数组：省去多余查询的时间成本
双指针：最优解时间复杂度O(n)，空间复杂度O(1)
算法实现（python）
class Solution:
def maxArea(self, height: List[int]) -> int:
left,right=0,len(height)-1
edge_num,edge=[left,right],[height[left],height[right]]
e_max,wide,high=max(edge),right-left,min(edge)
max_size=high*wide
for i in range(len(height)):
if e_max==edge[0]: #如果左边大
right-=1
edge_num,edge=[left,right],[height[left],height[right]]
e_max,wide,high=max(edge),right-left,min(edge)
max_size=max(max_size,high*wide)
else: #如果右边大
left+=1
edge_num,edge=[left,right],[height[left],height[right]]
e_max,wide,high=max(edge),right-left,min(edge)
max_size=max(max_size,high*wide)
return max_size
题目表述：给定一个数组arr，返回所有子数组的累加和中，最大的累加和
思路：
public static int maxSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i != arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
题目表述：给定给两个字符串str1，str2，判断str2是不是str1循环右移得到的。
思路：
public static boolean isRotation(String a, String b) {
if (a == null || b == null || a.length() != b.length()) {
return false;
}
String b2 = b + b;
return getIndexOf(b2, a) != -1;
}
// KMP Algorithm
public static int getIndexOf(String s, String m) {
if (s.length() < m.length()) {
return -1;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int si = 0;
int mi = 0;
int[] next = getNextArray(ms);
while (si < ss.length && mi < ms.length) {
if (ss[si] == ms[mi]) {
si++;
mi++;
} else if (next[mi] == -1) {
si++;
} else {
mi = next[mi];
}
}
return mi == ms.length ? si - mi : -1;
}
public static int[] getNextArray(char[] ms) {
if (ms.length == 1) {
return new int[] { -1 };
}
int[] next = new int[ms.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < next.length) {
if (ms[pos - 1] == ms[cn]) {
next[pos++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[pos++] = 0;
}
}
return next;
}
public static void main(String[] args) {
String str1 = "yunzuocheng";
String str2 = "zuochengyun";
System.out.println(isRotation(str1, str2));
}
题目表述：给定一个字符串str和数字k，输出str循环右移k位后的字符串
思路：
public static void rotateWord(char[] chas) { //间隔子序列交换问题
if (chas == null || chas.length == 0) {
return;
}
reverse(chas, 0, chas.length - 1);
int l = -1;
int r = -1;
for (int i = 0; i < chas.length; i++) {
if (chas[i] != ‘ ‘) {
l = i == 0 || chas[i - 1] == ‘ ‘ ? i : l;
r = i == chas.length - 1 || chas[i + 1] == ‘ ‘ ? i : r;
}
if (l != -1 && r != -1) {
reverse(chas, l, r);
l = -1;
r = -1;
}
}
}
public static void reverse(char[] chas, int start, int end) { //逆序
char tmp = 0;
while (start < end) {
tmp = chas[start];
chas[start] = chas[end];
chas[end] = tmp;
start++;
end--;
}
}
public static void rotate1(char[] chas, int size) { //右移k位后的字符串
if (chas == null || size <= 0 || size >= chas.length) {
return;
}
reverse(chas, 0, size - 1);
reverse(chas, size, chas.length - 1);
reverse(chas, 0, chas.length - 1);
}
public static void rotate2(char[] chas, int size) { //右移k位后的字符串 - 第二种
if (chas == null || size <= 0 || size >= chas.length) {
return;
}
int start = 0;
int end = chas.length - 1;
int lpart = size;
int rpart = chas.length - size;
int s = Math.min(lpart, rpart);
int d = lpart - rpart;
while (true) {
exchange(chas, start, end, s);
if (d == 0) {
break;
} else if (d > 0) {
start += s;
lpart = d;
} else {
end -= s;
rpart = -d;
}
s = Math.min(lpart, rpart);
d = lpart - rpart;
}
}
public static void exchange(char[] chas, int start, int end, int size) {
int i = end - size + 1;
char tmp = 0;
while (size-- != 0) {
tmp = chas[start];
chas[start] = chas[i];
chas[i] = tmp;
start++;
i++;
}
}
public static void main(String[] args) {
char[] chas1 = { ‘d‘, ‘o‘, ‘g‘, ‘ ‘, ‘l‘, ‘o‘, ‘v‘, ‘e‘, ‘s‘, ‘ ‘, ‘p‘,
‘i‘, ‘g‘ };
System.out.println(String.valueOf(chas1));
rotateWord(chas1);
System.out.println(String.valueOf(chas1));
char[] chas2 = { ‘1‘, ‘2‘, ‘3‘, ‘4‘, ‘5‘, ‘A‘, ‘B‘, ‘C‘ };
System.out.println(String.valueOf(chas2));
rotate1(chas2, 5);
System.out.println(String.valueOf(chas2));
rotate2(chas2, 3);
System.out.println(String.valueOf(chas2));
}
题目表述：有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向最右边滑一个位置。如果数组长度为n，窗口大小为w，则一共会产生n-w+1个窗口最大值。实现一个函数返回数组res[]，即所有的窗口最大值。
思路：
窗口最大/最小值结构：①L,R指针，都只会往右走 ②L永远不会超过R - 就是数网里的滑动窗口，使用双端队列实现
更新规则：L往右减数，R往右加数，双端队列维持严格左大右小的排序；
算法实现（java）
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
LinkedList<Integer> qmax = new LinkedList<Integer>();
int[] res = new int[arr.length - w + 1];
int index = 0;
for (int i = 0; i < arr.length; i++) {
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
qmax.pollLast();
}
qmax.addLast(i);
if (qmax.peekFirst() == i - w) {
qmax.pollFirst();
}
if (i >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
int w = 3;
printArray(getMaxWindow(arr, w));
}
题目表述：给定一个字符串类型的数组strs，找到一种拼接方式，使得所有字符串拼起来之后形成的字符粗换具有最低的字典序。
思路：
字典序：同长度比较从左到右逐位k进制；不同长度，短字符串补0再同前。
错误的贪心策略：单个str字典序小的排前面 - eg. b和ba，如果按照这种排序就是bba，但是实际上最低的是bab
正确的贪心策略：str1+str2的字典序大于str2+str1，则str1在前面。（把这种贪心策略作为比较器的比较方法，然后作为排序的比较器）
str1/str2 + str2/str3 -> str1/str3算法实现（java）
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
public static String lowestString(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
public static void main(String[] args) {
String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };
System.out.println(lowestString(strs1));
String[] strs2 = { "ba", "b" };
System.out.println(lowestString(strs2));
}
题目表述：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给予项目开始与结束时间数组，求进行宣讲场次最多的次数。（算法导论上的贪心也有该题）
思路：
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
public static int bestArrange(Program[] programs, int start) {
Arrays.sort(programs, new ProgramComparator());
int result = 0;
for (int i = 0; i < programs.length; i++) {
if (start <= programs[i].start) {
result++;
start = programs[i].end;
}
}
return result;
}
算法<初级> - 第六章 从原始问题出发的技巧 / 贪心（完结）
原文：https://www.cnblogs.com/ymjun/p/12733745.html