public static void main(String[] args) {

//4, 寻找两数组的中位数

//34. 在排序数组中查找元素的第一个和最后一个位置

//40，只可以取一次

//-------------------------------------------------------------------------

//-------------------------------------------------------------------------

//238. 除自身以外数组的乘积

//42,接雨水

Solution42 solution42 = new Solution42();

System.out.println(solution42.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));

//字符串相乘

//49，生成旋转数组

}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode resultHead = null;

ListNode cur = null;

int carry = 0;

while (l1 != null || l2 != null) {

int x = (l1 == null ? 0 : l1.val);

int y = (l2 == null ? 0 : l2.val);

int sum = x + y + carry;

carry = sum / 10;

sum = sum % 10;

ListNode newListNode = new ListNode(sum);

if (null == resultHead) {

resultHead = newListNode;

cur = newListNode;

} else {

cur.next = newListNode;

cur = cur.next; //指向尾节点

}

if (null != l1) l1 = l1.next;

if (null != l2) l2 = l2.next;

}

//注意退出的时候要特别考虑

if (carry == 1) {

cur.next = new ListNode(1);

}

return resultHead;

}

int val;

ListNode next;

ListNode(int x) {

val = x;

}

@Override

public String toString() {

return "ListNode{" +

"val=" + val +

", next=" + next +

'}';

}

public int lengthOfLongestSubstringBySet(String s) {

//滑动窗口法：左边进行滑动，检查右边

Set<Character> set = new HashSet<>(); //易错Character，不是int！1

int len = s.length(); //易错2！

int result = 0, i = 0, j = 0; //result将被进行前后大小判断以迭代

while (i < len && j < len) {

if (!set.contains(s.charAt(j))) {

set.add(s.charAt(j++)); //添加完成之后才i++;

result = Math.max(result, j - i);

} else {

set.remove(i++);

}

}

return result;

}

public int lengthOfLongestSubstringByMap(String s) {

//滑动窗口法：左边进行滑动，检查右边

Map<Character, Integer> map = new HashMap<>(); //易错Character，不是int！1

int len = s.length(); //易错2！

int result = 0, i = 0, j = 0; //result将被进行前后大小判断以迭代

while (j < len) {

//map添加前判断，更新i

if (map.containsKey(s.charAt(j))) {

i = Math.max(map.get(s.charAt(j)), i); //易错！难点！形如abba时，当j轮到a时，避免i返回去取第一个a的值1

}

//一定添加

map.put(s.charAt(j++), j); //易错，这个地方将更新值，而键不变！“键数值位”

result = Math.max(result, j - i);

}

return result;

}

//获取最大子串

public String subOfLongestSubstringBySet(String s) {

//滑动窗口法：左边进行滑动，检查右边

Set<Character> set = new HashSet<>();

int[] indexs = new int[]{0, 0};

int len = s.length();

int difMax = 0, i = 0, j = 0;

while (i < len && j < len) {

if (!set.contains(s.charAt(j))) { //这里要等到i走到重复的字母前面才会停止。难点！

set.add(s.charAt(j++));

if ((j - i) > difMax) { //对当前的j进行操作，避免j++的影响

indexs[0] = i;

indexs[1] = j; //正好j+1，即在被截取的字符的后面

difMax = j - i;

}

} else {

set.remove(s.charAt(i++)); //为什么删除的是i++？因为要使得i的左边不包括在集合里

}

}

return s.substring(indexs[0], indexs[1]); //易错，substring含头不含尾（避开区间）

}

public String subOfLongestSubstringByMap(String s) {

//滑动窗口法：左边进行滑动，检查右边

Map<Character, Integer> map = new HashMap<>();

int[] indexs = new int[]{0, 0};

int len = s.length();

int difMax = 0, i = 0, j = 0;

while (j < len) {

if (map.containsKey(s.charAt(j))) {

i = Math.max(s.charAt(j), i);

}

map.put(s.charAt(j++), j);

if (j - i > difMax) {

difMax = j - i;

indexs[0] = i;

indexs[1] = j;

}

}

return s.substring(indexs[0], indexs[1]); //易错，substring含头不含尾（避开区间）

}

//方法1：暴力法

public String longestPalindromeByForce(String s) {

int len = s.length();

String sSub = "";

String huiWenMax = "";

for (int i = 0; i < len; i++) {

for (int j = i + 1; j < len + 1; j++) {

sSub = s.substring(i, j);

if (isHuiWenString(sSub)) {

huiWenMax = sSub.length() > huiWenMax.length() ? sSub : huiWenMax;

}

}

}

return huiWenMax;

}

private boolean isHuiWenString(String s) {

int len = s.length();

for (int i = 0; i < len / 2; i++) {

if (s.charAt(i) != s.charAt(len - i - 1)) {

return false;

}

}

return true;

}

//方法2：动态规划法

public String longestPalindromeByDp1(String s) {

//动态规划2

//定义一个结构保存所有字串，存的是下标

class Str {

int i;

int j;

Str(int i, int j) {

this.i = i;

this.j = j;

}

}

//针对特殊情况进行处理

if (s.equals("") || s.length() == 1) {

return s;

}

//存储元回文串

ArrayList<Str> al = new ArrayList<>();

for (int i = 0; i < s.length(); i++) {

Str str = new Str(i, i);

al.add(str);

if (i != s.length() - 1) { //如果不是最后1个字符

//如果当前字符等于后一个字符，那么也要将该重复子串添加到单元数组中

if (s.charAt(i) == s.charAt(i + 1)) {

Str str2 = new Str(i, i + 1);

al.add(str2);

}

}

}

Str largeStr = new Str(0, 0); //存储最大

for (Str str : al) {

//向两边扩展

while (str.i != 0 && str.j != s.length() - 1) {

if (s.charAt(str.i - 1) == s.charAt(str.j + 1)) {

str.i--;

str.j++;

} else {

break;

}

}

//更新最大子串

if ((str.j - str.i) >= (largeStr.j - largeStr.i)) {

largeStr = str;

}

}

return s.substring(largeStr.i, largeStr.j + 1);

}

public String convert(String s, int numRows) {

if (numRows < 2) {

return s;

}

List<StringBuilder> rows = new ArrayList<StringBuilder>();

//先放n个SB对象

for (int i = 0; i < numRows; i++) {

rows.add(new StringBuilder());

}

int i = 0, flag = -1;

//遍历字符串字符

for (char c : s.toCharArray()) {

rows.get(i).append(c);

if (i == 0 || i == numRows - 1) { //每一行的首位或者末位

flag = -flag;

}

i += flag;

}

StringBuilder res = new StringBuilder();

for (StringBuilder row : rows) {

res.append(row);

}

return res.toString();

}

public int reverse(int x) {

int result = 0, a = 0;

while (x != 0) {

a = x % 10; // 得到最低位（除去低，百得低）

if (result > Integer.MAX_VALUE / 10 || ((Integer.MAX_VALUE / 10) == result && Integer.MAX_VALUE % 10 < a)) {

return 0; // 考虑溢出问题 数值范围 [-2^31, 2^31 - 1],Integer.MAX_VALUE % 10 < a 最后一位大于最大数的最后一位

}

if (result < Integer.MIN_VALUE / 10 || ((Integer.MAX_VALUE / 10) == result && Integer.MIN_VALUE % 10 > a)) {

return 0;

}

result = result * 10 + a;

x = x / 10;

}

return result;

}

public int myAtoi(String str) {

if (str == null) {

return 0;

}

// 偷懒做法，去掉空格，也可以用while循环来做

String temp = str.trim();

if (temp.equals("") || temp.length() == 0) {

return 0;

}

//正数标记

boolean flag = true;

char[] bits = temp.toCharArray();

int i = 0;

int res = 0;

int bit = 0;

//负数标记

if (bits[0] == '-') {

flag = false;

}

//如果是符号位，那么就将i往后移一位

if (bits[0] == '+' || bits[0] == '-') {

i++;

}

for (; i < bits.length; i++) {

if (bits[i] >= '0' && bits[i] <= '9') { //如果是数字

bit = bits[i] - '0';

} else {

break; //如果为非数字，那么直接退出

}

// 这里巧妙的应用了如果溢出就取最大值 Integer.MAX_VALUE 或 Integer.MIN_VALUE，[-2147483648，2147483647]

if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && bit > 7)) {

return flag ? Integer.MAX_VALUE : Integer.MIN_VALUE;

}

res = res * 10 + bit;

}

return flag ? res : -res;

}

public boolean isPalindrome(int x) {

// 特殊情况：

// 如上所述，当 x < 0 时，x 不是回文数。

// 同样地，如果数字的最后一位是 0，为了使该数字为回文，

// 则其第一位数字也应该是 0

// 只有 0 满足这一属性

if (x < 0 || (x % 10 == 0 && x != 0)) {

return false;

}

int revertedNumber = 0;

while (x > revertedNumber) { //只循环到中位

revertedNumber = revertedNumber * 10 + x % 10;

x /= 10;

}

// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。

// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，

// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。

return x == revertedNumber || x == revertedNumber / 10;

}

public int maxArea(int[] height) {

int maxarea = 0, l = 0, r = height.length - 1;

while (l < r) {

maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));

//谁的板子小则跳过谁

if (height[l] < height[r]) {

l++;

} else {

r--;

}

}

return maxarea;

}

public String intToRoman(int num) {

// 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中

// 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想

int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

StringBuilder stringBuilder = new StringBuilder();

int index = 0;

while (index < 13) {

// 特别注意：这里是等号

while (num >= nums[index]) {

// 注意：这里是等于号，表示尽量使用大的"面值"

stringBuilder.append(romans[index]);

num -= nums[index];

}

index++;

}

return stringBuilder.toString();

}

public int romanToInt(String s) {

Map<String, Integer> map = new HashMap<>();

map.put("I", 1);

map.put("IV", 4);

map.put("V", 5);

map.put("IX", 9);

map.put("X", 10);

map.put("XL", 40);

map.put("L", 50);

map.put("XC", 90);

map.put("C", 100);

map.put("CD", 400);

map.put("D", 500);

map.put("CM", 900);

map.put("M", 1000);

int ans = 0;

for (int i = 0; i < s.length(); ) {

if (i + 1 < s.length() && map.containsKey(s.substring(i, i + 2))) { //包含两个字符

ans += map.get(s.substring(i, i + 2));

i += 2;

} else { //只包含一个字符

ans += map.get(s.substring(i, i + 1));

i++;

}

}

return ans;

}

public String longestCommonPrefix(String[] strs) {

if (strs.length == 0)

return "";

String ans = strs[0]; //首先将第一个字符串进行初始化

for (int i = 1; i < strs.length; i++) { //遍历除了第一个字符串之后的所有剩余字符串

int j = 0;

//找到不相等的j值

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;

}

public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> ans = new ArrayList();

int len = nums.length;

if (nums == null || len < 3) {

return ans;

}

Arrays.sort(nums); // 排序

for (int i = 0; i < len; i++) {

if (nums[i] > 0) {

break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环

}

if (i > 0 && nums[i] == nums[i - 1]) {

continue; // 去重

}

int L = i + 1;

int R = len - 1;

while (L < R) {

int sum = nums[i] + nums[L] + nums[R];

if (sum == 0) {

ans.add(Arrays.asList(nums[i], nums[L], nums[R]));

while (L < R && nums[L] == nums[L + 1]) {

L++; // 去重

}

while (L < R && nums[R] == nums[R - 1]) {

R--; // 去重

}

L++;

R--;

} else if (sum < 0) {

L++;

} else {

R--;

}

}

}

return ans;

}

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums); //排序

int ans = nums[0] + nums[1] + nums[2];

for (int i = 0; i < nums.length; i++) {

int start = i + 1, end = nums.length - 1;

while (start < end) {

int sum = nums[start] + nums[end] + nums[i];

if (Math.abs(target - sum) < Math.abs(target - ans)) {

ans = sum;

}

//组目标是将sum变小，因数组有序，当sum > target时，说明sum很多，应将end--；反之，则将start++

if (sum > target) {

end--;

} else if (sum < target)

start++;

else {

return ans; //如果循环到最后，如果等于0，那么就将结果返回

}

}

}

return ans;

}

Map<String, String> phone = new HashMap<String, String>() {{

put("2", "abc");

put("3", "def");

put("4", "ghi");

put("5", "jkl");

put("6", "mno");

put("7", "pqrs");

put("8", "tuv");

put("9", "wxyz");

}};

List<String> output = new ArrayList<String>();

public List<String> letterCombinations(String digits) {

if (digits.length() != 0)

backtrack("", digits);

return output;

}

private void backtrack(String combination, String next_digits) {

//回溯组合

if (next_digits.length() == 0) {

output.add(combination);

} else {

String digit = next_digits.substring(0, 1);

String letters = phone.get(digit);

for (int i = 0; i < letters.length(); i++) {

String letter = phone.get(digit).substring(i, i + 1); //分别取每一个字符

//next_digits.substring(1)。递归到最后一位数字，然后再回溯组合在一起

backtrack(combination + letter, next_digits.substring(1));

}

}

}

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode first = head;

ListNode second = head;

//移动n位

for (int i = 0; i < n; i++) {

second = second.next;

}

if (null == second) { //如果是null == second，说明删除的是头结点，特殊处理

head = head.next;

return head; //注意要返回

} else {

while (second.next != null) {

first = first.next;

second = second.next;

}

first.next = first.next.next; //是first.next = ...，而不是first = ...

return head;

}

}

//内部类

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

}

}

private final Map<Character, Character> map = new HashMap<Character, Character>() {{

put('{', '}');

put('[', ']');

put('(', ')');

put('?', '?');

}};

public boolean isValid(String s) {

if (s.length() > 0 && !map.containsKey(s.charAt(0))) {

return false;

}

Stack<Character> stack = new Stack<>();

stack.add('?');

//策略，进来一个弹出一个进行判断，最后如果只剩下一个？，那么就是真括号

for (Character c : s.toCharArray()) { //最后不会进来？

if (map.containsKey(c)) {

stack.add(c);

} else if (map.get(stack.pop()) != c) {

return false;

}

}

return stack.size() == 1;

}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode head1 = l1;

ListNode head2 = l2;

ListNode newHead = null;

ListNode cur = null;

if (null == l1 && null == l2) {

return null;

}

if (null == l1) {

return l2;

}

if (null == l2) {

return l1;

}

//将头节点指向最小的那个链表

if (head1.val < head2.val) {

newHead = head1;

cur = head1;

head1 = head1.next;

} else {

newHead = head2;

cur = head2;

head2 = head2.next;

}

while (head1 != null && head2 != null) {

if (head1.val < head2.val) {

cur.next = head1;

cur = cur.next;

head1 = head1.next;

} else {

cur.next = head2;

cur = cur.next;

head2 = head2.next;

}

}

cur.next = head1 == null ? head2 : head1;

return newHead;

}

public ListNode swapPairs(ListNode head) {

ListNode pre = new ListNode(0);

pre.next = head;

ListNode temp = pre;

while (temp.next != null && temp.next.next != null) {

ListNode start = temp.next; //要交换的前节点

ListNode end = temp.next.next; //要交换的后节点

temp.next = end;

start.next = end.next;

end.next = start;

temp = start;

}

return pre.next;

}

public int removeDuplicates(int[] nums) {

if (nums.length == 0) {

return 0;

}

int first = 0;

//不重复就放左边

for (int second = 1; second < nums.length; second++) {

//如果不相等，就更新慢指针，同时在慢指针处插入新值，慢指针同时还起到计数的作用

if (nums[second] != nums[first]) {

first++;

nums[first] = nums[second]; //因为前几个元素存储不重复的数字

}

}

return first + 1;

}

public int removeElement(int[] nums, int val) {

if (nums.length == 0) {

return 0;

}

int left = 0;

//不等就放左边

for (int right = 0; right < nums.length; right++) {

if (nums[right] != val) {

nums[left] = nums[right];

left++;

}

}

return left;

}

public int strStr(String haystack, String needle) {

int lenH = haystack.length();

int lenN = needle.length();

for (int i = 0; i < lenH - lenN + 1; i++) {

if (haystack.substring(i, i + lenN).equals(needle)) {

return i;

}

}

return -1;

}

public int search(int[] nums, int target) {

if (nums == null || nums.length == 0) {

return -1;

}

int start = 0;

int end = nums.length - 1;

int mid;

while (start <= end) {

mid = (start + end) / 2;

if (nums[mid] == target) {

return mid;

}

//前半部分有序,注意此处用小于等于

if (nums[start] <= nums[mid]) {

//target在前半部分

if (target >= nums[start] && target < nums[mid]) {

end = mid - 1;

} else {

start = mid + 1;

}

} else {

if (target <= nums[end] && target > nums[mid]) {