class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res=new int[2];
for(int i=0,j=numbers.length-1;i<j;)
{
int temp=numbers[i]+numbers[j];
if(temp==target)
{
res[0]=i+1;
res[1]=j+1;
break;
}
else
if(temp<target)
i++;
else
j--;
}
return res;
}
}

class Solution {
public boolean judgeSquareSum(int c) {
int left=0;
int right=(int)Math.sqrt(c);
for(;left<=right;)
{
int temp=left*left+right*right;
if(temp==c)
return true;
else
if(temp>c)
right--;

else
left++;
}
return false;
}
}

class Solution {
public String reverseVowels(String s) {
if (s!=null && s.length()!=0)
{
char[] ch=new char[s.length()];
String letter="aieouAIEOU";
for(int i=0,j=s.length()-1;i<=j;)
{
char left=s.charAt(i);
char right=s.charAt(j);
int flagleft=0;
int flagright=0;
if(i==j)
{
ch[i]=left;
i++;
j--;
continue;
}
if(letter.indexOf(left)==-1)
{
ch[i]=left;
i++;
}
else
flagleft=1;
if((letter.indexOf(right)==-1)&&(i<j))
{
ch[j]=right;
j--;
}
else
flagright=1;
if(flagleft==1&&flagright==1)
{
ch[i]=right;
ch[j]=left;
i++;
j--;
}
}
s=String.valueOf(ch);
}
return s;
}
}

class Solution {
public boolean validPalindrome(String s) {
char[] chars = s.toCharArray();
int i = 0, j = chars.length - 1;
while (i < j) {
if (chars[i] != chars[j]) {
return validPalindrome(chars, i, j - 1) || validPalindrome(chars, i + 1, j);
}
i++;
j--;
}
return true;
}

private boolean validPalindrome(char[] chars, int l, int r) {
while (l < r) {
if (chars[l] != chars[r]) {
return false;
}
l++;
r--;
}
return true;
}
}

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p = m-- + n-- - 1;
while (m >= 0 && n >= 0) {
nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n >= 0) {
nums1[p--] = nums2[n--];
}
}
}

//快慢指针版
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
return true;
}
return false;
}
}
//别人写的骚套路，复制过来记一下
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode>node = new HashSet<>();
while(head!=null)
{
if(node.contains(head))
return true;
else
node.add(head);
head = head.next;
}
return false;
}
}

class Solution {
public String findLongestWord(String s, List<String> d) {
String res="";
for(int i=0;i<d.size();i++)
{
String temp=d.get(i);
if(issubstring(s,temp))
{
if(res.length()<temp.length())
res=temp;
else
if((temp.length()==res.length())&&(temp.compareTo(res)<0))
res=temp;
}
}
return res;
}
public boolean issubstring(String s,String target)
{
int i=0,j=0;
for(;i<s.length()&&j<target.length();)
{
if(s.charAt(i)==target.charAt(j))
{
i++;
j++;
}
else
{
i++;
}
}
if(j==target.length())
return true;
return false;
}
}

//时间复杂度 O(NlogK)，空间复杂度 O(K)。
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0;i<nums.length;i++)
{
pq.add(nums[i]);
if (pq.size() > k)
pq.poll();
}
return pq.peek();
}
}

class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> m = new HashMap<>();
for (int num : nums) {
m.put(num, m.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b)
{
return m.get(a)-m.get(b);
}
});
for (int key : m.keySet()) {
pq.add(key);
if(pq.size()>k)
pq.poll();
}
List<Integer> res=new ArrayList<Integer>();
while(!pq.isEmpty())
{
res.add(pq.remove());
}
Collections.reverse(res);
return res;
}
}

class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map=new HashMap<>();
for(int i=0;i<s.length();i++)
{
char c=s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
}
PriorityQueue<Character> pq=new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character a,Character b)
{
return map.get(b)-map.get(a);
}
});
for(Character key : map.keySet())
{
pq.add(key);
}
char[] res=new char[s.length()];
int j=0;
while(!pq.isEmpty())
{
char ch=pq.remove();
int times=map.get(ch);
for(int i=0;i<times;i++)
{
res[j++]=ch;
}
}
return String.valueOf(res);
}
}

class Solution {
public void sortColors(int[] nums) {
int left=-1,mid=0,right=nums.length;
while(mid<right)
{
if(nums[mid]==0)
{
swap(nums,++left,mid++);
}
else
if(nums[mid]==2)
{
swap(nums,mid,--right);
}
else
mid++;
}
}
public void swap(int[] nums,int i,int j)
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}

class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count=0;
for(int gi=0,si=0;gi<g.length&&si<s.length;)
{
if(s[si]>=g[gi])
{
count++;
si++;
gi++;
}
else
{
si++;
}

}
return count;
}
}

class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length==0)
return 0;
Arrays.sort(intervals,Comparator.comparingInt(o->o[1]));
int total=1;
int right=intervals[0][1];
for(int i=1;i<intervals.length;i++)
{
if(intervals[i][0]<right)
continue;
right=intervals[i][1];
total++;
}
return intervals.length-total;
}
}

class Solution {
public int findMinArrowShots(int[][] points) {
if(points.length==0)
return 0;
Arrays.sort(points,Comparator.comparingInt(o->o[1]));
int total=1;
int right=points[0][1];
for(int i=1;i<points.length;i++)
{
if(points[i][0]<=right)
continue;
right=points[i][1];
total++;
}
return total;
}
}

class Solution {
public int[][] reconstructQueue(int[][] people) {
if(people==null||people.length==0||people[0].length==0)
return new int[0][0];
Arrays.sort(people,(a,b)->(a[0]==b[0]?a[1]-b[1]:b[0]-a[0]));
List<int[]> res=new ArrayList<int[]>();
for(int i=0;i<people.length;i++)
{
res.add(people[i][1],people[i]);
}
return res.toArray(new int[people.length][1]);
}
}

class Solution {
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0)
return 0;
int max=0;
int curmin=prices[0];
for(int i=1;i<prices.length;i++)
{
if(curmin>prices[i])
curmin=prices[i];
if(prices[i]-curmin>max)
max=prices[i]-curmin;
}
return max;
}
}

class Solution {
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0)
return 0;
int res=0;
for(int i=1;i<prices.length;i++)
{
if(prices[i]-prices[i-1]>0)
res+=prices[i]-prices[i-1];
}
return res;
}
}

class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count=0;
if(flowerbed==null||flowerbed.length==0)
return n==0?true:false;
for(int i=0;i<flowerbed.length;i++)
{
if(flowerbed[i]==1)
continue;
int pre=i==0?0:flowerbed[i-1];
int next=i==flowerbed.length-1?0:flowerbed[i+1];
if(pre==0&&next==0)
{
count++;
i++;
//flowerbed[i] = 1;往后移一位或者改为1
}
}
if(count>=n)
return true;
return false;
}
}

//手动实现的慢版本
class Solution {
public boolean isSubsequence(String s, String t) {
int si=0,ti=0;
for(;si<s.length()&&ti<t.length();)
{
if(s.charAt(si)==t.charAt(ti))
{
si++;
ti++;
}
else
{
ti++;
}
}
if(si!=s.length())
return false;
return true;
}
}
//借助indexOf实现的快版本
class Solution {
public boolean isSubsequence(String s, String t) {
int index=-1;
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
index=t.indexOf(ch,index+1);
if(index==-1)
return false;
}
return true;
}
}

class Solution {
public boolean checkPossibility(int[] nums) {
int flag=0;
if(nums.length<3)
return true;
if(nums[0]>nums[1])
{
nums[0]=nums[1];
flag=1;
}
for(int i=1;i<nums.length-1;i++)
{
if(nums[i]>nums[i+1])
{
if(flag==1)
{
return false;
}
if(nums[i-1]<nums[i+1])
{
nums[i]=nums[i+1];
flag=1;
}
else
{
nums[i+1]=nums[i];
flag=1;
}
}
}
return true;
}
}

class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int cursum=nums[0];
for(int i=1;i<nums.length;i++)
{
if(cursum<=0)
cursum=nums[i];
else
cursum+=nums[i];
if(cursum>max)
max=cursum;
}
return max;
}
}

class Solution {
public List<Integer> partitionLabels(String S) {
if (S == null || S.length() == 0) {
return null;
}
int start=0;
List<Integer> res=new ArrayList<>();
for(int i=0;i<S.length();)
{
char ch=S.charAt(i);
int lastindex=S.lastIndexOf(ch);
if(lastindex!=-1)
{
for(i++;i<=lastindex;i++)
{
char ch2=S.charAt(i);
int lastindex2=S.lastIndexOf(ch2);
if(lastindex2>lastindex)
lastindex=lastindex2;
}
res.add(i-start);
start=i;
}
else
i++;
}
return res;
}
}

class Solution {
public int mySqrt(int x) {
if(x<=1)
return x;
int left=1,right=x;
while(left<right)
{
int mid=left+(right-left)/2;
if(x/mid==mid)
return mid;
else
if(x/mid>mid)
left=mid+1;
else
right=mid-1;
}
if(x/left<left)
return left-1;
else
return left;
}
}

class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int n = letters.length;
int l = 0, h = n - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (letters[m] <= target) {
l = m + 1;
} else {
h = m - 1;
}
}
return l < n ? letters[l] : letters[0];
}
}

class Solution {
public int singleNonDuplicate(int[] nums) {
int left=0,right=nums.length-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]==nums[mid-1])
{
if((mid-left)%2==0)
right=mid-2;
else
left=mid+1;
}
else
if(nums[mid]==nums[mid+1])
{
if((right-mid)%2==0)
left=mid+2;
else
right=mid-1;
}
else
return nums[mid];
}
return nums[right];
}
}

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left=0,right=n;
while(left<right)
{
int mid=left+(right-left)/2;
if(isBadVersion(mid))
{
right=mid;
}
else
left=mid+1;
}
return right;
}
}

class Solution {
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h]) {
h = m;
} else {
l = m + 1;
}
}
return nums[l];
}
}

class Solution {
public int[] searchRange(int[] nums, int target) {
int first = binarySearch(nums, target);
int last = binarySearch(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}
public int binarySearch(int[] nums, int target) {
int l = 0, h = nums.length;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= target) {
h = m;
} else {
l = m + 1;
}
}
return l;
}
}

class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res=new ArrayList<>();
for(int i=0;i<input.length();i++)
{
char ch=input.charAt(i);
if(ch=='+'||ch=='-'||ch=='*')
{
List<Integer> left=diffWaysToCompute(input.substring(0,i));
List<Integer> right=diffWaysToCompute(input.substring(i+1));
for(int li=0;li<left.size();li++)
for(int ri=0;ri<right.size();ri++)
{
if(ch=='+')
res.add(left.get(li)+right.get(ri));
if(ch=='-')
res.add(left.get(li)-right.get(ri));
if(ch=='*')
res.add(left.get(li)*right.get(ri));
}
}
}
if(res.size()==0)
res.add(Integer.parseInt(input));
return res;
}
}

class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res=new LinkedList<TreeNode>();
if(n<1)
return res;
return generateSubtrees(1,n);
}
public List<TreeNode> generateSubtrees(int s, int e) {
List<TreeNode> res = new LinkedList<TreeNode>();
if (s > e) {
res.add(null);
return res;
}
for (int i = s; i <= e; i++) {
List<TreeNode> left = generateSubtrees(s, i - 1);
List<TreeNode> right = generateSubtrees(i + 1, e);
for(int li=0;li<left.size();li++)
for(int ri=0;ri<right.size();ri++)
{
TreeNode root=new TreeNode(i);
root.left=left.get(li);
root.right=right.get(ri);
res.add(root);
}
}
return res;
}
}

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// Since all words are of same length.
int L = beginWord.length();
// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
HashMap<String, ArrayList<String>> allComboDict = new HashMap<String, ArrayList<String>>();

wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
ArrayList<String> transformations =
allComboDict.getOrDefault(newWord, new ArrayList<String>());
transformations.add(word);
allComboDict.put(newWord, transformations);
}
});

// Queue for BFS
Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();
Q.add(new Pair(beginWord, 1));

// Visited to make sure we don't repeat processing same word.
HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
visited.put(beginWord, true);

while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {

// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

// Next states are all the words which share the same intermediate state.
for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<String>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (adjacentWord.equals(endWord)) {
return level + 1;
}
// Otherwise, add it to the BFS Queue. Also mark it visited
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
}

return 0;
}
}

class Solution {
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}

private int dfs(int[][] grid, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int area = 1;
for (int[] d : direction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}
}

class Solution {
private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '0') {
dfs(grid, i, j);
islandsNum++;
}
}
}
return islandsNum;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
for (int[] d : direction) {
dfs(grid, i + d[0], j + d[1]);
}
}
}

class Solution {
public int findCircleNum(int[][] M) {
boolean[] visited = new boolean[M.length];
int ret = 0;
for(int i = 0; i < M.length; ++i) {
if(!visited[i]) {
dfs(M, visited, i);
ret++;
}
}
return ret;
}
private void dfs(int[][] m, boolean[] visited, int i) {
for(int j = 0; j < m.length; ++j) {
if(m[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(m, visited, j);
}
}
}
}

class Solution {
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return ;
}
m = board.length;
n = board[0].length;
for(int i=0;i<m;i++)
{
dfs(board,i,0);
dfs(board,i,n-1);
}
for(int i=0;i<n;i++)
{
dfs(board,0,i);
dfs(board,m-1,i);
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'N')
{
board[i][j] = 'O';
}
else
{
if (board[i][j] == 'O')
{
board[i][j] = 'X';
}
}
}
}
}
private void dfs(char[][] board, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
return;
}
board[i][j] = 'N';
for (int[] d : direction) {
dfs(board, i + d[0], j + d[1]);
}
}
}

class Solution {
private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res=new ArrayList<>();
List<int[]> ret = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return res;
}
m = matrix.length;
n = matrix[0].length;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];

for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
List<Integer> temp=new ArrayList<>();
temp.add(i);
temp.add(j);
res.add(temp);
}
}
}

return res;
}
private void dfs(int r, int c, boolean[][] canReach) {
if (canReach[r][c]) {
return;
}
canReach[r][c] = true;
for (int[] d : direction) {
int nextR = d[0] + r;
int nextC = d[1] + c;
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
|| matrix[r][c] > matrix[nextR][nextC]) {

continue;
}
dfs(nextR, nextC, canReach);
}
}
}

class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}

class Solution {
public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}

class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return Math.max(rob(nums,0,nums.length-1),rob(nums,1,nums.length));
}
public int rob(int[] nums,int start,int end) {
int pre2 = 0, pre1 = 0;
for (int i = start; i < end; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}

//普通版本
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp=new int[grid.length][grid[0].length];
dp[0][0]=grid[0][0];
for(int i=0;i<grid.length;i++)
{
for(int j=0;j<grid[0].length;j++)
{
if(i==0&&j==0)
continue;
if(j==0)
dp[i][j]=dp[i-1][j]+grid[i][j];
else
if(i==0)
dp[i][j]=dp[i][j-1]+grid[i][j];
else
dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
//空间优化版本，一维dp数组
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
dp[j] = dp[j]; // 只能从上侧走到该位置
} else if (i == 0) {
dp[j] = dp[j - 1]; // 只能从左侧走到该位置
} else {
dp[j] = Math.min(dp[j - 1], dp[j]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}
}

class Solution {
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(i==0||j==0)
dp[i][j]=1;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
return dp[m-1][n-1];
}
}

class NumArray {

private int[] sums;

public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}

public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}

class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int n = A.length;
int[] dp = new int[n];
for (int i = 2; i < n; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
}
int total = 0;
for (int cnt : dp) {
total += cnt;
}
return total;
}
}

class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}
}

//DP版本
class Solution {
public int numSquares(int n) {
int [] res = new int[n+1];
for (int i = 1; i <= n; i++){
int min = Integer.MAX_VALUE;
for (int j = 1; j*j <= i; j++){
min = Math.min(min, res[i-j*j]);
}
res[i] = min + 1;
}
return res[n];
}
}
//数学定理版
// 由定理可知，结果只有 “1、2、3、4” 四种可能。依次判断下列情况：
// （1）ans = 4 ，判断是否满足推论；（在此过程中，以 4 的倍数缩小 n ，并不影响最后结果）
// （2）ans = 1 ，判断缩小后的 n 是否为平方数；
// （3）ans = 2 ，判断缩小后的 n 是否可以由两个平方数构成；
// （4）ans = 3， 以上都不满足，则结果为 3。
class Solution {
public int numSquares(int n) {
while(n%4==0)
n/=4;
if(n%8==7)
return 4;
for(int i=0;i*i<n;i++)
{
int j=(int)Math.sqrt(n-i*i);
if(j*j+i*i==n)
if(i!=0&&j!=0)
return 2;
else
return 1;
}
return 3;
}
}

class Solution {
public int numDecodings(String s) {
if(s.length()==0||(s.length()==1&&s.charAt(0)=='0'))
return 0;
if(s.length()==1)
return 1;
int[] dp=new int[s.length()+1];
dp[0]=1;
dp[1]=s.charAt(0) == '0' ? 0 : 1;
for(int i=2;i<=s.length();i++)
{
int onestep=s.charAt(i-1)=='0'?0:dp[i-1];
int twostep=Integer.valueOf(s.substring(i - 2, i));
if(s.charAt(i-2)=='0')
twostep=0;
else
twostep=twostep>26?0:dp[i-2];
dp[i]=onestep+twostep;
}
return dp[s.length()];
}
}

class Solution {
public int lengthOfLIS(int[] nums) {
if(nums==null||nums.length==0)
return 0;
int[] dp=new int[nums.length];
dp[0]=1;
int max=1;
for(int i=1;i<nums.length;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
dp[i]=Math.max(dp[i],dp[j]+1);
}
if(max<dp[i])
max=dp[i];
}
return max;
}
}

class Solution {
public int findLongestChain(int[][] pairs) {
if(pairs==null||pairs.length==0)
return 0;
Arrays.sort(pairs,(a,b)->(a[0]-b[0]));
int[] dp=new int[pairs.length];
dp[0]=1;
int max=1;
for(int i=1;i<pairs.length;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(pairs[j][1]<pairs[i][0])
dp[i]=Math.max(dp[i],dp[j]+1);
}
if(max<dp[i])
max=dp[i];
}
return max;
}
}

class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}

class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++)
sum+=nums[i];
if(sum%2!=0)
return false;
sum/=2;
boolean[] dp = new boolean[sum+1];
dp[0] = true;
for(int i=0;i<nums.length;i++)
{
for(int j=sum;j>=nums[i];j--)
{
dp[j]=dp[j]||dp[j-nums[i]];
}
}
return dp[sum];
}
}

class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for(int i=0;i<nums.length;i++)
sum+=nums[i];
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int W = (sum + S) / 2;
int[] dp = new int[W + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = W; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[W];
}
}

class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if (strs.length == 0) {
return 0;
}
int[][] dp =new int[m+1][n+1];
for(String s :strs) {
int zeros = 0,ones = 0;
for(char c:s.toCharArray()) {
if (c == '0') {
zeros++;
}else {
ones++;
}
}
for (int i = m; i >=zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeros][j-ones]);
}
}
}
return dp[m][n];
}
}

class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0 || coins == null || coins.length == 0) {
return 0;
}
int[] dp = new int[amount + 1];
for(int i=0;i<coins.length;i++)
{
for(int j=coins[i];j<=amount;j++)
{
if(j==coins[i])
dp[j]=1;
else
if(dp[j]==0&&dp[j-coins[i]]!=0)
dp[j]=dp[j-coins[i]]+1;
else
if(dp[j-coins[i]]!=0)
dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}

class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++)
{
int coin=coins[i];
for(int j=coin;j<=amount;j++)
{
dp[j]+=dp[j-coin];
}
}
return dp[amount];
}
}

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) { // 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}

class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int n=nums.length;
int[] dp=new int[target+1];
dp[0]=1;
for(int i=1;i<=target;i++)
{
for(int j=0;j<nums.length&&i>=nums[j];j++)
{
dp[i]+=dp[i-nums[j]];
}
}
return dp[target];
}
}

for(int i=0;i<nums.length;i++)
for(int j=target;j>=V[i];j--)

for(int i=0;i<nums.length;i++)
for(int j=V[i];j<=target;j++)

for(int i=1;i<=target;i++)
for(int j=0;j<V.length&&j>=V[i];j++)

class Solution {
public int maxProfit(int[] prices) {
int[] sell=new int[prices.length];
int[] buy=new int[prices.length];
int[] cool=new int[prices.length];
if(prices==null||prices.length<2)
return 0;
buy[0]=-prices[0];
for(int i=1;i<prices.length;i++)
{
sell[i]=Math.max(buy[i-1]+prices[i],sell[i-1]);
buy[i]=Math.max(cool[i-1]-prices[i],buy[i-1]);
cool[i]=Math.max(sell[i-1], cool[i-1]);
}
return sell[prices.length-1];
}
}

class Solution {
public int maxProfit(int[] prices, int fee) {
int[] sell=new int[prices.length];
int[] buy=new int[prices.length];
if(prices==null||prices.length<2)
return 0;
buy[0]=-prices[0];
for(int i=1;i<prices.length;i++)
{
sell[i]=Math.max(buy[i-1]+prices[i]-fee,sell[i-1]);
buy[i]=Math.max(sell[i-1]-prices[i],buy[i-1]);
}
return sell[prices.length-1];
}
}

class Solution {
public int maxProfit(int[] prices) {
int fstBuy = Integer.MIN_VALUE, fstSell = 0;
int secBuy = Integer.MIN_VALUE, secSell = 0;
for(int i=0;i<prices.length;i++)
{
int p=prices[i];
fstBuy = Math.max(fstBuy, -p);
fstSell = Math.max(fstSell, fstBuy + p);
secBuy = Math.max(secBuy, fstSell - p);
secSell = Math.max(secSell, secBuy + p);
}
return secSell;
}
}

class Solution {
public int maxProfit(int k, int[] prices) {
if(k < 1) return 0;
if(k >= prices.length/2) return greedy(prices);
int[][] t = new int[k][2];
for(int i = 0; i < k; i++)
t[i][0] = Integer.MIN_VALUE;
for(int i=0;i<prices.length;i++)
{
int p=prices[i];
t[0][0] = Math.max(t[0][0], -p);
t[0][1] = Math.max(t[0][1], t[0][0] + p);
for(int j=1;j<k;j++)
{
t[j][0]=Math.max(t[j][0],t[j-1][1]-p);
t[j][1]=Math.max(t[j][1],t[j][0]+p);
}
}
return t[k-1][1];
}
private int greedy(int[] prices) {
int max = 0;
for(int i = 1; i < prices.length; ++i) {
if(prices[i] > prices[i-1])
max += prices[i] - prices[i-1];
}
return max;
}
}

class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return m + n - 2 * dp[m][n];
}
}

class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}
}

//DP版本
class Solution {
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j <= h; j++) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}
}
//递归版本
class Solution {
public int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return i + minSteps(n / i);
}
return n;
}
}

class Solution {
public int countPrimes(int n) {
boolean[] notPrimes = new boolean[n + 1];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrimes[i]) {
continue;
}
count++;
for (long j = (long) (i) * i; j < n; j += i) {
notPrimes[(int) j] = true;
}
}
return count;
}
}

class Solution {
public String convertToBase7(int num) {
if (num == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean isNegative = num < 0;
if (isNegative) {
num = -num;
}
while (num > 0) {
sb.append(num % 7);
num /= 7;
}
String ret = sb.reverse().toString();
return isNegative ? "-" + ret : ret;
}
}
//Java 中 static String toString(int num, int radix) 可以将一个整数转换为 radix 进制表示的字符串。

public String convertToBase7(int num) {
return Integer.toString(num, 7);
}

class Solution {
public String toHex(int num) {
char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
while (num != 0) {
sb.append(map[num & 0b1111]);
num >>>= 4;
}
return sb.reverse().toString();
}
}

class Solution {
public String convertToTitle(int n) {
if (n <= 0) {
return "";
}
StringBuilder sb = new StringBuilder();
while (n > 0) {
n--;
sb.append((char) (n % 26 + 'A'));
n =n / 26;
}
return sb.reverse().toString();
}
}

class Solution {
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
}

class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
carry++;
}
if (j >= 0 && b.charAt(j--) == '1') {
carry++;
}
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}
}

class Solution {
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
while (carry == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
str.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return str.reverse().toString();
}
}

class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int i=0,j=nums.length-1;
int res=0;
while(i<j)
{
res+=nums[j--]-nums[i++];
}
return res;
}
}

class Solution {
public int majorityElement(int[] nums) {
if(nums==null||nums.length==0)
return 0;
int flag=nums[0],count=1;
for(int i=1;i<nums.length;i++)
{
if(flag==nums[i])
count++;
else
{
count--;
if(count==0)
{
flag=nums[i];
count=1;
}
}
}
return flag;
}
}

class Solution {
public boolean isPerfectSquare(int num) {
for(int i=1;num>=0;i+=2)
{
if(num==0)
return true;
num-=i;
}
return false;
}
}

//通用方法
class Solution {
public boolean isPowerOfThree(int n) {
if(n<=0)
return false;
if(n==1)
return true;
while(n%3==0)
{
if(n/3==1)
return true;
n/=3;
}
return false;
}
}
//数学思想
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
}

class Solution {
public int[] productExceptSelf(int[] nums) {
if(nums==null||nums.length==0)
return null;
int[] output=new int[nums.length];
int left=1,right=1;
for(int i=0;i<nums.length;i++)
{
output[i]=1;
}
for(int i=0;i<nums.length;i++)
{
output[i]=left;
left*=nums[i];
}
for(int i=nums.length-1;i>=0;i--)
{
output[i]*=right;
right*=nums[i];
}
return output;
}
}

class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int n=nums.length;
return Math.max(nums[n-1]*nums[n-2]*nums[n-3],nums[0]*nums[1]*nums[n-1]);
}
}

public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int Alength=0;
int Blength=0;
ListNode temp=null;
temp=headA;
while(temp!=null)
{
Alength++;
temp=temp.next;
}
temp=headB;
while(temp!=null)
{
Blength++;
temp=temp.next;
}
int diff=Alength-Blength;
while(diff>0)
{
headA=headA.next;
diff--;
}
while(diff<0)
{
headB=headB.next;
diff++;
}
while(headA!=headB)
{
headA=headA.next;
headB=headB.next;
}
return headA;
}

}
//CYC
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while (l1 != l2) {
l1 = (l1 == null) ? headB : l1.next;
l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}

class Solution {
public ListNode reverseList(ListNode head) {
ListNode tail=null;
while(head!=null)
{
ListNode temp=head;
head=head.next;
temp.next=tail;
tail=temp;
}
return tail;
}
}

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head=new ListNode(0);
ListNode newlink=head;
while(l1!=null||l2!=null)
{
if(l1==null)
{
newlink.next=l2;
return head.next;
}
else
if(l2==null)
{
newlink.next=l1;
return head.next;
}
else
{
if(l1.val>l2.val)
{
newlink.next=l2;
newlink=newlink.next;
l2=l2.next;
}
else
{
newlink.next=l1;
newlink=newlink.next;
l1=l1.next;
}
}
}
return head.next;
}
}

class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode res=head;
while(res!=null&&res.next!=null)
{
if(res.val==res.next.val)
res.next=res.next.next;
else
res=res.next;
}
return head;
}
}

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null||head.next==null)
return null;
ListNode fast=head;
for(int i=0;i<n;i++)
{
fast=fast.next;
}
ListNode slow=head;
if(fast==null)
return head.next;
while(fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return head;
}
}

class Solution {
public ListNode swapPairs(ListNode head) {
ListNode beforehead=new ListNode(0);
beforehead.next=head;
ListNode temp=null;
int count=0;
ListNode p=beforehead;
while(p.next!=null&&p.next.next!=null)
{
if(count==1)
{
count=0;
p=p.next.next;
}
else
{
count++;
temp=p.next.next;
p.next.next=p.next.next.next;
temp.next=p.next;
p.next=temp;
}
}
return beforehead.next;
}
}