package com.dengzm.lib;
/**
* @Description 057 和为s的数字
* 题目一：和为s的两个数
* 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
* 题目二：和为s的连续正数序列
* 输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）
*
* Created by deng on 2019/10/31.
*/
public class Jianzhi057 {
public static void main(String[] args) {
int[] data1 = new int[] {1,3,5,6,8,9,12,15,17,20};
findNumbersWithSum(data1, 20);
findNumbersWithSum(data1, 17);
findNumbersWithSum(data1, 18);
System.out.println();
findContinuousSequence(15);
System.out.println();
findContinuousSequence(25);
System.out.println();
findContinuousSequence(35);
System.out.println();
}
/**
* 题目一
* 两个下标，从数组的头尾开始遍历，如果和大于s，左边的下标增加；如果下雨，则右边的增加，直到和为s 或 下标相等
*
* @param data data
* @param s sum
*/
private static void findNumbersWithSum(int[] data, int s) {
if (data == null || data.length < 2 || s < data[0]) {
System.out.println("sth is wrong in data or sum is too big");
return;
}
int leftIndex = 0;
int rightIndex = data.length - 1;
while (leftIndex != rightIndex) {
int sum = data[leftIndex] + data[rightIndex];
if (sum == s) {
System.out.println("sum is " + s + " and the numbers are " + data[leftIndex] + " and " + data[rightIndex]);
return;
} else if (sum > s) {
rightIndex --;
} else {
leftIndex ++;
}
}
System.out.println("no such numbers in data");
}
/**
* 题目二
* 与题目一类似，在计算和时，如果小于sum，右边增加；如果大于，左边增加，相当于整体向右移动
*
* @param sum sum
*/
private static void findContinuousSequence(int sum) {
if (sum < 2) {
System.out.println("sum cannot be less than 2");
return;
}
int leftIndex = 1;
int rightIndex = 2;
while (leftIndex < (sum + 1) / 2 && leftIndex < rightIndex) {
float tempSum = ((float)(leftIndex + rightIndex)) * (rightIndex - leftIndex + 1) / 2;
if (tempSum == sum) {
System.out.println("sum is " + sum + ", sequence is " + leftIndex + " to " + rightIndex);
leftIndex ++;
} else if (tempSum > sum) {
leftIndex ++;
} else {
rightIndex ++;
}
}
}
}
package com.dengzm.lib;
/**
* @Description 058 翻转字符串
* 题目一：翻转单词顺序
* 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，标点和普通字符一样处理
* 例如：I am a student. -> student. a am I
* 题目二：左旋转字符串
* 把字符串前面的若干字符转移到字符串的尾部
*
* Created by deng on 2019/10/31.
*/
public class Jianzhi058 {
public static void main(String[] args) {
String s1 = "I am a student.";
String s2 = " I am a student. ";
String s3 = "asdfghjkl";
System.out.println(reverseSentence(s1));
System.out.println(reverseSentence(s2));
System.out.println(leftRotateString(s3, 0));
System.out.println(leftRotateString(s3, 1));
System.out.println(leftRotateString(s3, 5));
System.out.println(leftRotateString(s3, 9));
}
/**
* 题目一
* 先将整个句子翻转，再将每个单词翻转
*
* @param target target
* @return reversed target
*/
private static String reverseSentence(String target) {
if (target == null || target.length() == 0) {
return "";
}
char[] targetChars = target.toCharArray();
// 整体翻转
reverse(targetChars, 0, targetChars.length - 1);
int start = 0;
int end = 0;
// 单词翻转，判断条件为，空格分隔的为单词
while (start < targetChars.length - 1) {
while (targetChars[end] != ' ') {
end ++;
}
reverse(targetChars, start, end - 1);
end ++;
start = end;
}
return String.valueOf(targetChars);
}
/**
* 题目二
* 与题目一类似，利用n分段后，各自翻转，最后整体翻转即可
*
* @param target target
* @param n left rotate num
* @return left rotated target
*/
private static String leftRotateString(String target, int n) {
if (target == null || target.length() == 0 || n < 0 || n > target.length()) {
return "";
}
char[] targetChars = target.toCharArray();
int firstStart = 0;
int firstEnd = n - 1;
int secondStart = n;
int secondEnd = targetChars.length - 1;
// 各自翻转
reverse(targetChars, firstStart, firstEnd);
reverse(targetChars, secondStart, secondEnd);
// 整体翻转
reverse(targetChars, 0, targetChars.length - 1);
return String.valueOf(targetChars);
}
/**
* reverse
*
* @param target target
* @param start start
* @param end end
*/
private static void reverse(char[] target, int start, int end) {
if (target == null || target.length == 0 || start >= end || end >= target.length) {
return;
}
while (start < end) {
char temp = target[start];
target[start] = target[end];
target[end] = temp;
start ++;
end --;
}
}
}
package com.dengzm.lib;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @Description 059 队列最大值
* 题目一：滑动窗口的最大值
* 例如：数组[2,3,4,2,6,2,5]，窗口大小为3，得到的最大值为[4,4,6,6,6,5]
* 题目二：队列的最大值
* 请定义一个队列，实现函数max得到队列的最大值，max、push_back、pop_front的时间复杂度为O(1)
*
*
* Created by deng on 2019/10/31.
*/
public class Jianzhi059 {
public static void main(String[] args) {
int[] data1 = new int[] {2,3,4,2,6,2,5,1};
System.out.println(maxValuesInWindow(data1, 3).toString());
QueueWithMax<Integer> queue = new QueueWithMax<>();
queue.push_back(6);
queue.push_back(6);
queue.push_back(6);
queue.push_back(2);
queue.push_back(3);
queue.push_back(5);
queue.push_back(4);
queue.push_back(2);
queue.push_back(2);
queue.push_back(1);
for (int i = 0; i < 10; i ++) {
System.out.println("Max is " + queue.max());
queue.pop_front();
}
}
/**
* 题目一
* 使用链表，保存当前窗口中最大值的下标
* 保存最大值的同时，也保存后续添加进入的值中，小于最大值的值，当最大值滑出窗口后，第二大值自动变为最大值
*
* @param data data
* @param size window size
* @return max values
*/
private static ArrayList<Integer> maxValuesInWindow(int[] data, int size) {
ArrayList<Integer> maxValuesInWindow = new ArrayList<>();
if (data == null || data.length == 0 || size < 1) {
return maxValuesInWindow;
}
// 保存最大值的下标
LinkedList<Integer> indexQueue = new LinkedList<>();
// 初始化，在前size个数中，找到最大的数，并记录下标
for (int i = 0; i < size; i ++) {
while (!indexQueue.isEmpty() && data[i] >= data[indexQueue.getFirst()]) {
indexQueue.removeLast();
}
indexQueue.addLast(i);
}
// 边界判断
if (size >= data.length - 1) {
maxValuesInWindow.add(data[indexQueue.getFirst()]);
return maxValuesInWindow;
}
// 滑动窗口
for (int i = size; i < data.length; i ++) {
// 结果中保存最大值
maxValuesInWindow.add(data[indexQueue.getFirst()]);
// 滑动窗口，获得的新数字，需要与之前的数字进行对比
// 如果大于之前的数字，要把之前的去掉
while (!indexQueue.isEmpty() && data[i] >= data[indexQueue.getLast()]) {
indexQueue.removeLast();
}
// 判断当前最大的数字，是否已经被滑出了窗口
if (!indexQueue.isEmpty() && indexQueue.getFirst() <= (i - size)) {
indexQueue.removeFirst();
}
indexQueue.addLast(i);
}
maxValuesInWindow.add(data[indexQueue.getFirst()]);
return maxValuesInWindow;
}
/**
* 题目二
*
* 与题目一类似，利用一个额外的队列保存最大值
*/
public static class QueueWithMax<T extends Comparable> {
private LinkedList<InternalData> data;
private LinkedList<InternalData> maxMembers;
private int currentIndeX;
public QueueWithMax() {
currentIndeX = 0;
data = new LinkedList<>();
maxMembers = new LinkedList<>();
}
public void push_back(T number) {
// 此处的边界判断与书上不同，应该为大于，不是大于等于
while (!maxMembers.isEmpty() && number.compareTo(maxMembers.getLast().value) > 0) {
maxMembers.removeLast();
}
InternalData internalData = new InternalData(number, currentIndeX);
data.addLast(internalData);
maxMembers.addLast(internalData);
currentIndeX ++;
}
public InternalData pop_front() {
if (maxMembers.isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
if (maxMembers.getFirst().value == data.getFirst().value) {
maxMembers.removeFirst();
}
return data.removeFirst();
}
public T max() {
if (maxMembers.isEmpty()) {
throw new RuntimeException("Queue is empty.");
}
return maxMembers.peekFirst().value;
}
private class InternalData {
T value;
int index;
InternalData(T value, int index) {
this.value = value;
this.index = index;
}
}
}
}
