int result = 0;

/*

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

//key:值 value:数组下标

HashMap<Integer, Integer> numberIndex = new HashMap();

int[] result = new int[2];

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

//判断与当前值和为target的值是否存在

int index = numberIndex.getOrDefault(target - nums[i], -1);

if (index != -1) {

result[0] = index;

result[1] = i;

break;

}

numberIndex.put(nums[i], i);

}

return result;

}

/*

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

//记录初始node的地址,用来return

ListNode head = new ListNode(0);

//游标

ListNode cursor = head;

int carry = 0;

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

int val1 = 0, val2 = 0;

if (l1 != null) {

val1 = l1.val;

l1 = l1.next;

}

if (l2 != null) {

val2 = l2.val;

l2 = l2.next;

}

int result = val1 + val2 + carry;

carry = result / 10;

cursor.next = new ListNode(result % 10);

cursor = cursor.next;

}

return head.next;

}

/*

public int lengthOfLongestSubstring(String s) {

int maxLength = 0;

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

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

i = Math.max(charIndex.getOrDefault(s.charAt(j), -1), i);

maxLength = Math.max(maxLength, j - i + 1);

charIndex.put(s.charAt(j), j + 1);

}

return maxLength;

}

/*

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int length = nums1.length + nums2.length;

//奇数情况,取中间的一个数即可

if ((length & 1) == 1) {

return getTopK(nums1, 0, nums2, 0, length / 2 + 1) / 1.0;

}

//偶数情况,取中间2位数求平均值

return (getTopK(nums1, 0, nums2, 0, length / 2) + getTopK(nums1, 0, nums2, 0, length / 2 + 1)) / 2.0;

}

/*

private int getTopK(int[] nums1, int index1, int[] nums2, int index2, int k) {

if (index1 >= nums1.length) {

return nums2[index2 + k - 1];

}

if (index2 >= nums2.length) {

return nums1[index1 + k - 1];

}

if (k == 1) {

return Math.min(nums1[index1], nums2[index2]);

} else {

int tmpK = k / 2 - 1;

int position1 = Math.min((index1 + tmpK), nums1.length - 1);

int position2 = Math.min((index2 + tmpK), nums2.length - 1);

if (nums1[position1] >= nums2[position2]) {

position2 = position2 + 1;

k = k - (position2 - index2);

return getTopK(nums1, index1, nums2, position2, k);

} else {

position1 = position1 + 1;

k = k - (position1 - index1);

return getTopK(nums1, position1, nums2, index2, k);

}

}

}

/*

public String longestPalindrome(String s) {

if (s == null || s.length() == 1) {

return s;

}

int n = s.length();

//dp[i][j]即为s(i,j)是否为回文字串

boolean[][] dp = new boolean[n][n];

int start = 0;

int end = 0;

//最外层为字符串长度

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

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

int j = i + l;

if (l == 0) {

dp[i][j] = true;

} else if (s.charAt(i) == s.charAt(j)) {

dp[i][j] = l == 1 || dp[i + 1][j - 1];

}

if (dp[i][j] && l + 1 > (end - start)) {

start = i;

end = i + 1 + l;

}

}

}

return s.substring(start, end);

}

/*

public String convert(String s, int numRows) {

if (numRows == 1) {

return s;

}

StringBuilder[] result = new StringBuilder[numRows];

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

result[i] = new StringBuilder();

}

int count = 0;

boolean addFlag = true;

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

result[count].append(s.charAt(i));

if (addFlag) count++;

else count--;

if (count == numRows) {

addFlag = !addFlag;

count = count - 2;

}

if (count == -1) {

addFlag = !addFlag;

count = count + 2;

}

}

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

result[0].append(result[i]);

}

return result[0].toString();

}

/*

public int reverse(int x) {

int result = 0;

int tmpResult = 0;

int bit;

while (x != 0) {

bit = x % 10;

x = x / 10;

tmpResult = tmpResult * 10 + bit;

if (result != 0 && tmpResult / result < 10)

return 0;

result = tmpResult;

}

return result;

}

/*

public int myAtoi(String str) {

int result = 0;

int tmpResult = 0;

int invalidResult = 0;

int positive = 1;

int start = 0;

int l = str.length();

//首先去除空格

for (; start < l; start++) {

if (str.charAt(start) != ' ')

break;

}

if (start == l) {

return invalidResult;

}

//判断首位是不是符号

int firstChar = str.charAt(start);

if (firstChar == '+') {

start++;

positive = 1;

} else if (firstChar == '-') {

start++;

positive = -1;

} else if (firstChar < '0' || firstChar > '9') {

return invalidResult;

}

for (; start < l; start++) {

char c = str.charAt(start);

//有效字符串

if (c >= '0' && c <= '9') {

tmpResult = tmpResult * 10 + (c - 48);//ascii码

//溢出情况

if (result != 0 && tmpResult / result < 10) {

if (positive == 1) {

return Integer.MAX_VALUE;

} else {

return Integer.MIN_VALUE;

}

}

result = tmpResult;

} else {

//无效字符串

break;

}

}

return positive * result;

}

/*

public boolean isPalindrome(int x) {

if (x == 0) {

return true;

}

//负数不可能为回文数

if (x < 0) {

return false;

}

//最后一位不能是0,例如10,100不可能是回文数

if (x % 10 == 0) {

return false;

}

int bit;

int result = 0;

while (x > 0) {

bit = x % 10;

result = result * 10 + bit;

if (result > x)

return false;

if (result == x)

return true;

x = x / 10;

if (result == x)

return true;

}

return true;

}

/*

public boolean isMatch(String s, String p) {

if (p.isEmpty()) return s.isEmpty();

boolean firstCharMatch = (!s.isEmpty() &&

(p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

//存在*时

if (p.length() >= 2 && p.charAt(1) == '*') {

//两种情况

//1 x*匹配空字符串

//2 x*匹配一个字符串

return (isMatch(s, p.substring(2)) ||

(firstCharMatch && isMatch(s.substring(1), p)));

} else {

//不存在*时

return firstCharMatch && isMatch(s.substring(1), p.substring(1));

}

}

/*

public int maxArea(int[] height) {

int left = 0, right = height.length - 1;

//初始面积

int max = Math.min(height[left], height[right]) * (right - left);

while (left < right) {

if (height[left] < height[right]) {

left++;

} else {

right--;

}

int tmpArea = Math.min(height[left], height[right]) * (right - left);

max = Math.max(max, tmpArea);

}

return max;

}

/*

public String intToRoman(int num) {

String[] thousands = new String[]{"", "M", "MM", "MMM"};

//0,100,...,900

String[] hundreds = new String[]{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};

//0,10,...,90

String[] tens = new String[]{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};

//0,1,...,9

String[] ones = new String[]{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

//千位

int thousand = num / 1000;

int hundred = num % 1000 / 100;

int ten = num % 100 / 10;

int one = num % 10;

String result =

thousands[thousand] +

hundreds[hundred] +

tens[ten] +

ones[one];

return result;

}

/*

public int romanToInt(String s) {

Map<Character, Integer> romanMap = initMap();

int result = 0;

int pre = 0;

for (int i = s.length() - 1; i >= 0; i--) {

int num = romanMap.get(s.charAt(i));

if (num >= pre) {

result += num;

} else {

result -= num;

}

pre = num;

}

return result;

}

/*

private Map<Character, Integer> initMap() {

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

romanMap.put('I', 1);

romanMap.put('V', 5);

romanMap.put('X', 10);

romanMap.put('L', 50);

romanMap.put('C', 100);

romanMap.put('D', 500);

romanMap.put('M', 1000);

return romanMap;

}

/*

public String longestCommonPrefix(String[] strs) {

if (strs.length == 0) {

return "";

}

if (strs.length == 1) {

return strs[0];

}

//找出字符串最短长度

int minLength = Integer.MAX_VALUE;

for (String str : strs) {

minLength = Math.min(minLength, str.length());

}

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

char c = strs[0].charAt(i);

for (int j = 1, l = strs.length; j < l; j++) {

if (strs[j].charAt(i) != c)

return strs[0].substring(0, i);

}

}

return strs[0].substring(0, minLength);

}

/*

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

//三数之和可以转化为两数字之和,例如[-1, 0, 1, 2, -1, -4]只需要依次找到两个和为[1,0,-1,-2,1,4]即可

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

//对数组进行排序

Arrays.sort(nums);

int length = nums.length;

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

//若a已经大于0,由于排序过b,c肯定大于0

if (nums[i] > 0) {

break;

}

//相同的a直接跳过

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

continue;

}

int l = i + 1, r = length - 1;

while (l < r) {

int sum = nums[i] + nums[l] + nums[r];

//满足条件

if (sum == 0) {

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

list.add(nums[i]);

list.add(nums[l]);

list.add(nums[r]);

result.add(list);

while (l < r && (nums[l + 1] == nums[l])) l++;

while (l < r && (nums[r - 1] == nums[r])) r--;

l++;

r--;

}

//加大l

if (sum < 0) {

l++;

}

//减小r

if (sum > 0) {

r--;

}

}

}

return result;

}

/*

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

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

if (nums.length < 3) {

return result;

}

Arrays.sort(nums);

threeSum2(nums, 0, 0, new ArrayList<>(3), result);

return result;

}

public void threeSum2(int[] nums, int start, int sum, List<Integer> current, List<List<Integer>> result) {

if (current.size() == 3) {

if (sum == 0) {

result.add(new ArrayList<>(current));

}

return;

}

for (int i = start, l = nums.length; i < l; i++) {

//剪枝

//1.若a>0,b和c都大于0,不存在a+b+c=0

if (current.isEmpty() && nums[i] > 0)

break;

//1.若a+b>0,c大于0,不存在a+b+c=0

if (current.size() == 1 && (sum + nums[i]) > 0)

break;

//去重

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

continue;

current.add(nums[i]);

threeSum2(nums, i + 1, sum + nums[i], current, result);

current.remove(current.size() - 1);

}

}

/*

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

//排序

Arrays.sort(nums);

int length = nums.length;

int result = Integer.MAX_VALUE;

int minGap = Integer.MAX_VALUE;

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

int l = i + 1, r = length - 1;

while (l < r) {

int sum = nums[i] + nums[l] + nums[r];

//相等时最接近,直接返回

if (sum == target) {

return target;

}

if (sum > target) {

r--;

}

if (sum < target) {

l++;

}

int gap = Math.abs(sum - target);

if (gap < minGap) {

result = sum;

minGap = gap;

}

}

}

return result;

}

/*

public List<String> letterCombinations(String digits) {

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

List<List<String>> letterList = getList();

for (int i = 0, l = digits.length(); i < l; i++) {

List<String> charList = letterList.get(digits.charAt(i) - '0');

result = multiply(result, charList);

}

return result;

}

/*

private List<List<String>> getList() {

//0-9对应的九宫格

String[] letters = {

"", "", "abc",

"def", "ghi", "jkl",

"mno", "pqrs", "tuv",

"wxyz"

};

List<List<String>> letterList = new ArrayList(letters.length);

for (String letter : letters) {

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

for (int j = 0, dl = letter.length(); j < dl; j++) {

charList.add(letter.charAt(j) + "");

}

letterList.add(charList);

}

return letterList;

}

/*

private List<String> multiply(List<String> l1, List<String> l2) {

if (l1.isEmpty() || l2.isEmpty()) {

return l1.isEmpty() ? l2 : l1;

}

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

for (int i = 0; i < l1.size(); i++)

for (int j = 0; j < l2.size(); j++) {

result.add(l1.get(i) + l2.get(j));

}

return result;

}

/*

public List<List<Integer>> fourSum(int[] nums, int target) {

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

//对数组进行排序

Arrays.sort(nums);

int length = nums.length;

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

if (nums[i] > target) {

break;

}

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

continue;

}

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

if (nums[i] + nums[j] > target) {

break;

}

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

continue;

}

int l = j + 1, r = length - 1;

while (l < r) {

int sum = nums[i] + nums[j] + nums[l] + nums[r];

if (sum == target) {

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

list.add(nums[i]);

list.add(nums[j]);

list.add(nums[l]);

list.add(nums[r]);

result.add(list);

while (l < r && (nums[l + 1] == nums[l])) l++;

while (l < r && (nums[r - 1] == nums[r])) r--;

l++;

r--;

}

//加大l

if ((target - sum) > 0) {

l++;

}

//减小r

if ((target - sum) < 0) {

r--;

}

}

}

}

return result;

}

/*

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode cursor = head;

//计算链表长度

int length = 0;

while (cursor != null) {

length++;

cursor = cursor.next;

}

//转换倒数为正数

int index = length - n;

//如果删除的是第一个,直接删除

if (index == 0) {

ListNode next = head.next;

head.next = null;

return next;

}

cursor = head;

ListNode pre = null;

while (index > 0) {

pre = cursor;

cursor = cursor.next;

index--;

}

pre.next = cursor.next;

return head;

}

/*

public ListNode removeNthFromEnd2(ListNode head, int n) {

ListNode newHead = new ListNode(0);

newHead.next = head;

ListNode fast = newHead;

ListNode slow = newHead;

while (n >= 0) {

fast = fast.next;

n--;

}

//第一个指针到达终点停止遍历

while (fast != null) {

fast = fast.next;

slow = slow.next;

}

slow.next = slow.next.next;

return newHead.next;

}

/*

public boolean isValid(String s) {

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

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

char c = s.charAt(i);

if (stack.isEmpty() || isLeft(c)) {

stack.push(c);

} else {

if (stack.peek() == getRight(c)) {

stack.pop();

} else {

break;

}

}

}

return stack.isEmpty();

}

private boolean isLeft(char c) {

return c == '(' || c == '[' || c == '{';

}

private char getRight(char c) {

if (c == ')')

return '(';

if (c == ']')

return '[';

return '{';

}

/*

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode head = new ListNode(0);

ListNode cursor = head;

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

if (l1 == null) {

cursor.next = new ListNode(l2.val);

l2 = l2.next;

} else if (l2 == null) {

cursor.next = new ListNode(l1.val);

l1 = l1.next;

} else {

if (l1.val < l2.val) {

cursor.next = new ListNode(l1.val);

l1 = l1.next;

} else {

cursor.next = new ListNode(l2.val);

l2 = l2.next;

}

}

cursor = cursor.next;

}

return head.next;

}

/*

public List<String> generateParenthesis(int n) {

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

generateParenthesis(n, 0, 0, "", result);

return result;

}

/*

private void generateParenthesis(int n, int l, int r, String s, List<String> result) {

if (l == n && r == n) {

result.add(s);

}

if (l < n) {

generateParenthesis(n, l + 1, r, s + "(", result);

}

if (r < l) {

generateParenthesis(n, l, r + 1, s + ")", result);

}

}

/*

public ListNode mergeKLists(ListNode[] lists) {

if (lists.length == 0) {

return null;

}

if (lists.length == 1) {

return lists[0];

}

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

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

ListNode head = lists[i];

while (head != null) {

nodeList.add(head.val);

head = head.next;

}

}

Collections.sort(nodeList);

ListNode head = new ListNode(0);

ListNode current = head;

for (int i = 0; i < nodeList.size(); i++) {

ListNode node = new ListNode(nodeList.get(i));

current.next = node;

current = node;

}

return head.next;

}

/*

public ListNode mergeKLists2(ListNode[] lists) {

if (lists.length == 0) {

return null;

}

if (lists.length == 1) {

return lists[0];

}

return merge(lists, 0, lists.length - 1);

}

private ListNode merge(ListNode[] lists, int l, int r) {

if (l == r) {

return lists[l];

}

if (l + 1 == r) {

return mergeTwoLists(lists[l], lists[r]);

}

int mid = (l + r) / 2;

ListNode l1 = merge(lists, l, mid);

ListNode l2 = merge(lists, mid + 1, r);

return mergeTwoLists(l1, l2);

}

/*

public ListNode swapPairs(ListNode head) {

//链表只有0个或1个结点时,无法交换

if (head == null || head.next == null) {

return head;

}

ListNode next = head.next;

head.next = swapPairs(next.next);

next.next = head;

return next;

}

/*

public ListNode swapPairs2(ListNode head) {

//链表只有0个或1个结点时,无法交换

if (head == null || head.next == null) {

return head;

}

ListNode next = head.next;

head.next = swapPairs(next.next);

next.next = head;

return next;

}

/*

public ListNode reverseKGroup(ListNode head, int k) {

if (head == null || head.next == null || k == 0) {

return head;

}

ListNode index = head;

int i = k;

while (i - 1 > 0) {

index = index.next;

if (index == null) {

return head;

}

i--;

}

ListNode temp = index.next;

index.next = null;

ListNode newHead = reverse(head);

head.next = reverseKGroup(temp, k);

return newHead;

}

/*

private ListNode reverse(ListNode head) {

ListNode newHead = head;

while (head.next != null) {

ListNode next = head.next;

head.next = next.next;

next.next = newHead;

newHead = next;

}

return newHead;

}

/*

public int removeDuplicates(int[] nums) {

if (nums.length < 2) {

return nums.length;

}

int slow = 0;

for (int fast = 1, l = nums.length; fast < l; fast++) {

if (nums[fast] != nums[slow]) {

slow++;

if (fast != slow) {

nums[slow] = nums[fast];

}

}

}

//slow是下标,数量应该再加1

return slow + 1;

}

/*

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

int slow = 0;

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

if (nums[i] != val) {

if (i != slow) {

int temp = nums[slow];

nums[slow] = nums[i];

nums[i] = temp;

}

slow++;

}

}

return slow;

}

//todo 28

/*

public int divide(int dividend, int divisor) {

int ans = -1;

int sign = 1;

if (dividend > 0) {

sign = opposite(sign);

dividend = opposite(dividend);

}

if (divisor > 0) {

sign = opposite(sign);

divisor = opposite(divisor);

}

//由于被除数和除数都是负数,如果dividend>divisor

//说明|dividend|<|divisor|

//即|dividend|/|divisor| < 1,结果就是0