Xhofe's BlogLeetcode 3月份每日一题
1-10
01 225. 用队列实现栈
题目
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
注意: - 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
思路
没啥好说的，就是一个队列存数据，一个队列辅助入栈，入栈时交换两个队列。
code
class MyStack {
private Queue<Integer> queue1,queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1=new ArrayDeque<>();
queue2=new ArrayDeque<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue1.add(x);
while (!queue2.isEmpty())queue1.add(queue2.poll());
Queue tmp=queue1;queue1=queue2;queue2=tmp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue2.poll();
}
/** Get the top element. */
public int top() {
return queue2.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue2.isEmpty();
}
}02 206. 反转链表
题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路
老题目了，上数据结构的时候就说过，遍历链表，遍历到结点链接到上一个节点并记录该结点。
code
class Solution {
public ListNode reverseList(ListNode head) {
if (head==null||head.next==null)return head;
ListNode last=null;
ListNode cur=head;
ListNode next=null;
while (cur!=null){
next=cur.next;
cur.next=last;
last=cur;
cur=next;
}
return last;
}
}03 面试题 10.01. 合并排序的数组
题目
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3输出: [1,2,2,3,5,6]
说明:
A.length == n + m
思路
双指针。
code
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int i=A.length-1;
m-=1;n-=1;
while (m>=0&&n>=0){
if (A[m]>B[n]){
A[i--]=A[m];m--;
}else {
A[i--]=B[n];n--;
}
}
while (n>=0){
A[i--]=B[n];n--;
}
}
}04 994. 腐烂的橘子
题目
在给定的网格中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
- 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4示例 2：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。提示：
1 <= grid.length <= 101 <= grid[0].length <= 10grid[i][j]仅为0、1或2
思路
模拟一遍这个过程，但是每次烂掉的橘子记为-1，之后再统一标记为2，避免一次中的腐烂传播。
code
class Solution {
public int orangesRotting(int[][] grid) {
int count =0;
while(lan(grid)){
count++;
}
for (int[] ints : grid) {
for (int j = 0; j < grid[0].length; j++) {
if (ints[j] == 1) {
return -1;
}
}
}
return count;
}
public static boolean lan(int [][] grid){
boolean lan=false;
for(int i=0;i<=grid.length-1;i++){
for (int j = 0; j < grid[0].length; j++) {
if(grid[i][j]==2){
if(i-1>=0&&grid[i-1][j]==1){
grid[i-1][j]=-1;
lan=true;
}
if(i+1<grid.length&&grid[i+1][j]==1){
grid[i+1][j]=-1;
lan=true;
}
if(j-1>=0&&grid[i][j-1]==1){
grid[i][j-1]=-1;
lan=true;
}
if(j+1<grid[0].length&&grid[i][j+1]==1){
grid[i][j+1]=-1;
lan=true;
}
}
}
}
for(int i=0;i<=grid.length-1;i++){
for (int j = 0; j < grid[0].length; j++) {
if(grid[i][j]==-1){
grid[i][j]=2;
}
}
}
return lan;
}
}05 1103. 分糖果 II
题目
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。示例 2：
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。提示：
1 <= candies <= 10^91 <= num_people <= 1000
思路
纯数学计算，先计算出把所有小朋友发全可以发多少次，然后剩下的糖果模拟发完为止。
code
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] res=new int[num_people];
int tmp=candies;
int count=-1;
while (tmp>0){
candies=tmp;++count;
tmp-=num_people*((2*count+1)*num_people+1)/2;
}
for (int i = 0; i < num_people; i++) {
res[i]=count*(2*(i+1)+(count-1)*num_people)/2;
tmp=count*num_people+i+1;
if (candies<=0)continue;
if (candies>=tmp){
res[i]+=tmp;
candies-=tmp;
}else {
res[i]+=candies;
candies=0;
}
}
return res;
}
}06 面试题57 - II. 和为s的连续正数序列
题目
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
- 1 <= target <= 10^5
思路
滑动窗口，因为都是正数，要往目标和靠近，小的时候右边界右移，大的时候左边界右移。
code
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
i = 1 # 滑动窗口的左边界
j = 1 # 滑动窗口的右边界
sum = 0 # 滑动窗口中数字的和
res = []
while i <= target // 2:
if sum < target:
sum += j
j += 1
elif sum > target:
sum -= i
i += 1
else:
arr = list(range(i, j))
res.append(arr)
sum -= i
i += 1
return res07 面试题59 - II. 队列的最大值
题目
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
限制：
- 1 <= push_back,pop_front,max_value的总操作数 <= 10000
- 1 <= value <= 10^5
思路
当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响。所以我们只需要维护一个单调队列即可，在放入元素的时候，将单调队列里所有比该元素小的值poll，输出元素的时候，如果这个元素是当时的最大值，则将单调队列也进行poll。
code
class MaxQueue {
private Queue<Integer> queue;
private Deque<Integer> max;
public MaxQueue() {
queue=new LinkedList<>();
max=new LinkedList<>();
}
public int max_value() {
if (max.isEmpty())return -1;
return max.getFirst();
}
public void push_back(int value) {
queue.add(value);
while (!max.isEmpty()&&max.getLast()<value)max.pollLast();
max.add(value);
}
public int pop_front() {
if (queue.isEmpty())return -1;
int value=queue.poll();
if (max.getFirst()==value)max.pollFirst();
return value;
}
}08 322. 零钱兑换
题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3
输出: -1说明:
你可以认为每种硬币的数量是无限的。
思路
动态规划，属于背包问题。dp[i][j]记录当只用前i种硬币组合j时的最少硬币个数，则有$dp[i][j]=\min(dp[i-1][j],dp[i][j-coins[i]]+1)$.如果dp[i][j-coins[i]]存在的话。因为只使用了上一次的状态，所以可以用滚动数组进行优化。
code
class Solution {
public int coinChange(int[] coins, int amount) {
int len=coins.length;
int[] dp=new int[amount+1];
dp[0]=0;
for (int i=1;i<amount+1;i++){
dp[i]=Integer.MAX_VALUE/2;
}
for (int i=0;i<len;i++){
for (int j=coins[i];j<amount+1;j++){
dp[j]=Integer.min(dp[j],dp[j-coins[i]]+1);
}
}
if (dp[amount]>=amount+1){
return -1;
}
return dp[amount];
}
}09 121. 买卖股票的最佳时机
题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
从前往后遍历，记录当前最小值与当前值减去最小值的差的最大值。
code
class Solution {
public int maxProfit(int[] prices) {
int res=0;
int min=Integer.MAX_VALUE;
for (int price : prices) {
min=Math.min(min,price);
res=Math.max(res,price-min);
}
return res;
}
}10 543. 二叉树的直径
题目
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路
递归，其实最大直径就是左子树的深度+右子树的深度。
code
class Solution {
private int res=0;
public int diameterOfBinaryTree(TreeNode root) {
deep(root);
return res;
}
public int deep(TreeNode node){
if (node==null)return -1;
int left=deep(node.left)+1;
int right=deep(node.right)+1;
res=Math.max(res,left+right);
return Math.max(left,right);
}
}11-20
11 1013. 将数组分成和相等的三个部分
题目
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
示例 1：
输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4思路
先计算出总和，看能不能被3整除，然后模拟一下即可。
code
class Solution{
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
for (int num: A) {
sum += num;
}
if (sum % 3 != 0) {
return false;
}
sum /= 3;
int curSum = 0, cnt = 0;
for (int i = 0; i < A.length; i++) {
curSum += A[i];
if (curSum == sum) {
cnt++;
curSum = 0;
}
}
// 最后判断是否找到了3段（注意如果目标值是0的话可以大于3段）
return cnt == 3 || (cnt > 3 && sum == 0);
}
}12 1071. 字符串的最大公因子
题目
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""提示：
1 <= str1.length <= 10001 <= str2.length <= 1000str1[i]和str2[i]为大写英文字母
思路
如果两个字符串有公因子串，则必有str1+str2=str2+str1，用辗转相除法计算出长度的最大公因数，截取其中一段即为最大公因子串了。
code
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1+str2).equals(str2+str1))return "";
return str1.substring(0,gcd(str1.length(),str2.length()));
}
private int gcd(int a, int b){
return b==0?a:gcd(b,a%b);
}
}13 169. 多数元素
题目
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2思路
从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，因为最多的数出现的次数大于一半，所以最后总会找到这个数。
code
class Solution {
public int majorityElement(int[] nums) {
int cur=nums[0];
int count=0;
for (int num : nums) {
if (num==cur)count++;
else if (count==0){
cur=num;
count=1;
}else count--;
}
return cur;
}
}14 300. 最长上升子序列
题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 $O(n^2)$ 。
思路
常规dp就可以$O(n^2)$，这里参考官方题解的贪心+二分。
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 ii 的最长上升子序列的末尾元素的最小值，用 $len$ 记录目前最长上升子序列的长度，起始时 $len$ 为 11，$d[1]=nums[0]$。
同时我们可以注意到 d[i]d[i] 是关于 ii 单调递增的。因为如果 $d[j] \geq d[i]$且$ j < i$，我们考虑从长度为 ii 的最长上升子序列的末尾删除 $i-j$ 个元素，那么这个序列长度变为 j，且第 j个元素 xx（末尾元素）必然小于 d[i]，也就小于 d[j]。那么我们就找到了一个长度为 j的最长上升子序列，并且末尾元素比 d[j] 小，从而产生了矛盾。因此数组 d[] 的单调性得证。
我们依次遍历数组 $nums[] $中的每个元素，并更新数组 d[]d[] 和 $len$ 的值。如果$ \textit{nums}[i] > d[\textit{len}] $则更新 $len = len + 1$，否则在 $d[1 \ldots len]$中找满足$ d[i−1]<nums[j]<d[i] $的下标 ii，并更新 $d[i]=nums[j]$。
根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。
最后整个算法流程为：
设当前已求出的最长上升子序列的长度为$ len$（初始时为 11），从前往后遍历数组 $nums$，在遍历到 $nums[i] $时：
如果$nums[i]>d[len] $，则直接加入到 d 数组末尾，并更新 $len=len+1$；
否则，在 d 数组中二分查找，找到第一个比$nums[i] $小的数 d[k] ，并更新 $d[k+1]=nums[i]$。
作者：
LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
code
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = (int)nums.length;
if (n == 0) return 0;
int[] d=new int[n+1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) d[++len] = nums[i];
else{
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
d[pos + 1] = nums[i];
}
}
return len;
}
}15 695. 岛屿的最大面积
题目
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。（如果没有岛屿，则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]对于上面这个给定的矩阵, 返回 0。
思路
对于每个1进行dfs。下面的代码其实可以不必使用cur标记是否访问，直接对访问过进行置0即可。
code
class Solution {
private int[][]conditions={{-1,0},{1,0},{0,-1},{0,1}};
private boolean[][] cur;
private int res=0;
public int maxAreaOfIsland(int[][] grid) {
if (grid.length==0||grid[0].length==0)return 0;
cur=new boolean[grid.length][grid[0].length];
int cur_res=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]==1&&!cur[i][j]){
cur_res=maxAreaOfIsland(grid,i,j);
res=Math.max(res,cur_res);
}
}
}
return res;
}
public int maxAreaOfIsland(int[][] grid,int i,int j){
int cur_res=0;
if (i<0||i==grid.length||j<0||j==grid[0].length||cur[i][j]||grid[i][j]!=1)return cur_res;
cur_res++;
cur[i][j]=true;
for (int k = 0; k < 4; k++) {
cur_res+=maxAreaOfIsland(grid,i+conditions[k][0],j+conditions[k][1]);
}
return cur_res;
}
}16 面试题 01.06. 字符串压缩
题目
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
输入："aabcccccaaa"
输出："a2b1c5a3"示例2:
输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。提示：
- 字符串长度在[0, 50000]范围内。
思路
直接模拟这个过程即可。
code
class Solution {
public String compressString(String S) {
if (S.length()<3)return S;
StringBuilder sb=new StringBuilder();
char c=S.charAt(0);
int count=1;
for (int i = 1; i < S.length(); i++) {
if (S.charAt(i)==c){
count++;
}else {
sb.append(c).append(count);
if (sb.length()>=S.length()){
return S;
}
c=S.charAt(i);
count=1;
}
}
sb.append(c).append(count);
if (sb.length()>=S.length()){
return S;
}
return sb.toString();
}
}17 1160. 拼写单词
题目
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1：
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。示例 2：
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。提示：
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100- 所有字符串中都仅包含小写英文字母
思路
只有26个字母，直接数组哈希。逐个测试即可。
code
class Solution {
public int countCharacters(String[] words, String chars) {
int[] hash = new int[26];
for(char ch : chars.toCharArray()){
hash[ch - 'a'] += 1;
}
int[] map = new int[26];
int len = 0;
for(String word : words){
Arrays.fill(map, 0);
boolean flag = true;
for(char ch : word.toCharArray()){
map[ch - 'a']++;
if(map[ch - 'a'] > hash[ch - 'a']) flag = false;
}
len += flag ? word.length() : 0;
}
return len;
}
}18 836. 矩形重叠
题目
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false提示：
- 两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
- 矩形中的所有坐标都处于 -10^9 和 10^9 之间。
- x 轴默认指向右，y 轴默认指向上。
- 你可以仅考虑矩形是正放的情况。
思路
矩形如果不重叠，从x轴和y轴上看两个矩形就变成了两条线段，这两条线段肯定是不相交的，也就是说左边的矩形的最右边小于右边矩形的最左边，也就是rec1[2] < rec2[0] || rec2[2] < rec1[0]；y轴同理，下面的矩形的最上边小于上面矩形的最下边，也就是rec1[3] < rec2[1] || rec2[3] < rec1[1]。因为题目要求重叠算相离，所以加上=，最后取反就行啦~
code
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return !(rec1[0] >= rec2[2] || rec1[2] <= rec2[0] || rec1[1] >= rec2[3] || rec1[3] <= rec2[1]);
}
}19 409. 最长回文串
题目
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。思路
直接统计每个字符的个数。只要是复数出现的即可，最后还可以加上一个正中间的。
code
class Solution {
public int longestPalindrome(String s) {
int[] cnts = new int[58];
for (int i = 0; i < s.length(); i++) {
cnts[s.charAt(i) - 'A']++;
}
int palindrome = 0;
for (int cnt : cnts) {
palindrome += (cnt / 2) * 2;
}
if (palindrome < s.length()) {
palindrome++;
}
return palindrome;
}
}20 面试题40. 最小的k个数
题目
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
思路
二分法，每次取mid，将数组分为两个部分，如果小的那部分>k，则继续再这部分进行二分，如果<k，则这些数都是结果，再在大的部分继续取剩下的数，如果刚好等于要取的数，则结束。
code
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res=new int[k];
int len=arr.length;
int leftL,rightL;
int[] left=new int[len];
int[] right=new int[len];
int index=0;
int mid;
int[] midA=new int[len];
int midL;
while (index<k){
leftL=0;rightL=0;midL=0;
mid=arr[len/2];
for (int i = 0; i < len; i++) {
if (arr[i]<mid){
left[leftL++]=arr[i];
}else if (arr[i]==mid)midA[midL++]=arr[i];
else right[rightL++]=arr[i];
}
if (leftL>(k-index)){
arr=left;
len=leftL;
}else {
for (int i = 0; i < leftL; i++) {
res[index++]=left[i];
}
int tmp=0;
while (index<k&&tmp<midL){
res[index++]=midA[tmp++];
}
arr=right;
len=rightL;
}
}
return res;
}
}21-31
21 365. 水壶问题
题目
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True示例 2:
输入: x = 2, y = 6, z = 5
输出: False思路
预备知识：贝祖定理
我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。
你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？接下来我们来解释这一点：
首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；
其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。
因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a,b，使得
$$ax+by=z$$
而只要满足z≤x+y，且这样的 a,b 存在，那么我们的目标就是可以达成的。这是因为：
- 若a≥0,b≥0，那么显然可以达成目标。
若a<0，那么可以进行以下操作：
- 往 y 壶倒水；
- 把 y 壶的水倒入 x 壶；
- 如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
- 若 b<0，方法同上，x 与 y 互换。
而贝祖定理告诉我们，ax+by=z 有解当且仅当 z 是 x,y 的最大公约数的倍数。因此我们只需要找到x,y 的最大公约数并判断 z 是否是它的倍数即可。
code
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x+y<z)return false;
if (x+y==z||x==z||y==z||x==1||y==1)return true;
if (x==y||x==0||y==0)return false;
if(z==0)return true;
int gcd=getGCD(x,y);
if (gcd==1)return true;
return gcd<z&&z%gcd==0;
}
private int getGCD(int a, int b) {
if (a < 0 || b < 0) {
return -1; // 数学上不考虑负数的约数
}
if (b == 0) {
return a;
}
while (a % b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return b;
}
}22 945. 使数组唯一的最小增量
题目
给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。
示例 1:
输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。示例 2:
输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。提示：
0 <= A.length <= 400000 <= A[i] < 40000
思路
首先模拟也可以做，但是很慢，所以可以利用空间换时间的方法，记录下所有的数出现的次数，遍历这些数，对于每个数出现次数>1的数进行次数-1的move操作，所以该数+1要的次数要加上该数的次数-1，结果加上move的次数即可。
code
class Solution {
public int minIncrementForUnique(int[] A) {
// Arrays.sort(A);
// int res=0;
// for (int i = 1; i < A.length; i++) {
// while (A[i]<=A[i-1]){
// A[i]++;
// res++;
// }
// }
// return res;
//空间换时间
int[] arr=new int[50000];
int res=0;
for(int i:A){
arr[i]++;
}
for (int i = 0; i < 50000; i++) {
if (arr[i]>1){
arr[i+1]+=arr[i]-1;
res+=arr[i]-1;
}
}
return res;
}
}23 876. 链表的中间结点
题目
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。提示：
- 给定链表的结点数介于
1和100之间。
思路
经典的快慢指针用法。
code
class Solution {
public ListNode middleNode(ListNode head) {
// 快慢指针
ListNode low = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
}
return low;
}
}24 面试题 17.16. 按摩师
题目
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。思路
动态规划：$dp[i]=\max(dp[i-1],dp[i-2]+nums[i])$
code
class Solution {
public int massage(int[] nums) {
if (nums.length==0)return 0;
if (nums.length==1)return nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];
dp[1]= Math.max(nums[1], nums[0]);
for (int i = 2; i < nums.length; i++) {
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
}25 892. 三维形体的表面积
题目
在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
示例 1：
输入：[[2]]
输出：10示例 2：
输入：[[1,2],[3,4]]
输出：34示例 3：
输入：[[1,0],[0,2]]
输出：16示例 4：
输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32示例 5：
输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46提示：
1 <= N <= 500 <= grid[i][j] <= 50
思路
对于每个格子里的正方体，首先是上下两个面，然后是每个有四个侧面，最后减去重复计算的侧面即可。
code
class Solution {
public int surfaceArea(int[][] grid) {
if (grid.length==0||grid[0].length==0)return 0;
int res=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j]!=0){
res+=2;
res+=grid[i][j]<<2;
if (i>0)res-=Math.min(grid[i][j],grid[i-1][j])<<1;
if (j>0)res-=Math.min(grid[i][j],grid[i][j-1])<<1;
// if (i<grid.length-1)res-=Math.min(grid[i][j],grid[i+1][j]);
// if (j<grid[0].length-1)res-=Math.min(grid[i][j],grid[i][j+1]);
}
}
}
return res;
}
}26 999. 可以被一步捕获的棋子数
题目
在一个 8 x 8 的棋盘上，有一个白色的车（Rook），用字符 'R' 表示。棋盘上还可能存在空方块，白色的象（Bishop）以及黑色的卒（pawn），分别用字符 '.'，'B' 和 'p' 表示。不难看出，大写字符表示的是白棋，小写字符表示的是黑棋。
车按国际象棋中的规则移动。东，西，南，北四个基本方向任选其一，然后一直向选定的方向移动，直到满足下列四个条件之一：
- 棋手选择主动停下来。
- 棋子因到达棋盘的边缘而停下。
- 棋子移动到某一方格来捕获位于该方格上敌方（黑色）的卒，停在该方格内。
- 车不能进入/越过已经放有其他友方棋子（白色的象）的方格，停在友方棋子前。
你现在可以控制车移动一次，请你统计有多少敌方的卒处于你的捕获范围内（即，可以被一步捕获的棋子数）。
示例 1：
输入：
[[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".","R",".",".",".","p"],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".","p",".",".",".","."],
[".",".",".",".",".",".",".","."],
[".",".",".",".",".",".",".","."]]
输出：3
解释：
在本例中，车能够捕获所有的卒。提示：
board.length == board[i].length == 8board[i][j]可以是'R'，'.'，'B'或'p'- 只有一个格子上存在
board[i][j] == 'R'
思路
很没意思的一道题。。。。
code
class Solution {
public int numRookCaptures(char[][] board) {
int res=0;
int row=0,col=0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j]=='R'){
row=i;col=j;break;
}
}
}
int tmp=row-1;
while (tmp>=0){
char c=board[tmp][col];
if (c=='B')break;
if (c=='p'){res++;break;}
tmp--;
}
tmp=row+1;
while (tmp<board.length){
char c=board[tmp][col];
if (c=='B')break;
if (c=='p'){res++;break;}
tmp++;
}
tmp=col-1;
while (tmp>=0){
char c=board[row][tmp];
if (c=='B')break;
if (c=='p'){res++;break;}
tmp--;
}
tmp=col+1;
while (tmp<board[0].length){
char c=board[row][tmp];
if (c=='B')break;
if (c=='p'){res++;break;}
tmp++;
}
return res;
}
}27 914. 卡牌分组
题目
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
- 每组都有
X张牌。 - 组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
示例 1：
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。示例 3：
输入：[1]
输出：false
解释：没有满足要求的分组。示例 4：
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]示例 5：
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]提示：
1 <= deck.length <= 100000 <= deck[i] < 10000
思路
先给这些牌排个序。
然后记录所有牌的张数。以及最少的张数。
然后从2...最少的张数进行测试可否分组。
下面的代码写成hash会更好一点，懒得写了。。
code
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Arrays.sort(deck);
List<Integer> list=new ArrayList<>();
int min=Integer.MAX_VALUE;
int tmp=1;
for (int i = 1; i < deck.length; i++) {
if (deck[i]==deck[i-1])tmp++;
else {
if (tmp==1)return false;
min=Math.min(min,tmp);
list.add(tmp);
tmp=1;
}
}
if (tmp==1)return false;
min=Math.min(min,tmp);
list.add(tmp);
tmp=min;
boolean flag=true;
for (int i = 2; i <= min; i++) {
flag=true;
if (min%i==0){
for (Integer ii:list){
if (ii % i != 0) {
flag = false;
break;
}
}
if (flag)return true;
}
}
return false;
}
}28 820. 单词的压缩编码
题目
给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
示例：
输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。提示：
1 <= words.length <= 20001 <= words[i].length <= 7- 每个单词都是小写字母 。
思路
很烂的思路，先对单词进行按长度排序。然后遍历判断是否以其他单词结尾的，如果有单词被别的单词包含就不计算，最后的结果就是没有被包含的单词的长度+1的和。
最好的做法是用字典树（前缀树），奈何不会~待学。。
这道题将字符串倒过来就是判断前缀是否包含单词了。
code
class Solution {
public int minimumLengthEncoding(String[] words) {
Arrays.sort(words,(a,b)->(Integer.compare(b.length(), a.length())));
boolean[] flags=new boolean[words.length];
for (int i = 0; i < words.length; i++) {
String tmp=words[i];
for (int j = i+1; j < words.length; j++) {
if (!flags[j]&&tmp.endsWith(words[j])){
flags[j]=true;
}
}
}
int res=0;
for (int i = 0; i < words.length; i++) {
if (!flags[i])res+=words[i].length()+1;
}
return res;
}
}class Solution {
public int minimumLengthEncoding(String[] words) {
int len = 0;
Trie trie = new Trie();
// 先对单词列表根据单词长度由长到短排序
Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
// 单词插入trie，返回该单词增加的编码长度
for (String word: words) {
len += trie.insert(word);
}
return len;
}
}
// 定义tire
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public int insert(String word) {
TrieNode cur = root;
boolean isNew = false;
// 倒着插入单词
for (int i = word.length() - 1; i >= 0; i--) {
int c = word.charAt(i) - 'a';
if (cur.children[c] == null) {
isNew = true; // 是新单词
cur.children[c] = new TrieNode();
}
cur = cur.children[c];
}
// 如果是新单词的话编码长度增加新单词的长度+1，否则不变。
return isNew? word.length() + 1: 0;
}
}
class TrieNode {
char val;
TrieNode[] children = new TrieNode[26];
public TrieNode() {}
}29 1162. 地图分析
题目
你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例 1：
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。示例 2：
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。提示：
1 <= grid.length == grid[0].length <= 100grid[i][j]不是0就是1
思路
先找出所有的陆地，再从陆地开始进行分层的BFS，遍历的最大深度即为解。
code
class Solution {
private int[][]conditions={{-1,0},{1,0},{0,-1},{0,1}};
public int maxDistance(int[][] grid) {
// BFS
int N=grid.length;
Queue<int[]> queue=new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j]==1){
queue.add(new int[]{i,j});
}
}
}
if (queue.size()==N*N||queue.size()==0)return -1;
int res=-1;
while (!queue.isEmpty()){
res++;
int tmp=queue.size();
for (int k = 0; k < tmp; k++) {
int[] poi=queue.poll();
int i=poi[0],j=poi[1];
for (int l = 0; l < 4; l++) {
int newi=i+conditions[l][0];
int newj=j+conditions[l][1];
if (newi<0||newj<0||newi==N||newj==N)continue;
if (grid[newi][newj]==0){
grid[newi][newj]=-1;
queue.add(new int[]{newi,newj});
}
}
}
}
return res;
}
}30 面试题62. 圆圈中最后剩下的数字
题目
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3示例 2：
输入: n = 10, m = 17
输出: 2限制：
1 <= n <= 10^51 <= m <= 10^6
思路
首先是模拟这个过程，但是会超时，官方给出数学法：
【思路】
n个数字的圆圈，不断删除第m个数字，我们把最后剩下的数字记为f(n,m)
n个数字中第一个被删除的数字是(m-1)%n (取余的原因是m可能比n大)， 我们记作k，k=(m-1)%n
那么剩下的n-1个数字就变成了：0,1,……k-1,k+1,……,n-1，我们把下一轮第一个数字排在最前面，并且将这个长度为n-1的数组映射到0~n-2。
原始数组 映射数字 k+1 0 k+2 1 ... ... n-1 n-k-2 0 n-k-1 ... ... k-1 n-2 把映射数字记为x，原始数字记为y，那么映射数字变回原始数字的公式为
$$y=(x+k+1)\mod n$$在映射数字中，n-1个数字，不断删除第m个数字，由定义可以知道，最后剩下的数字为f(n-1,m)。我们把它变回原始数字，由上一个公式可以得到最后剩下的原始数字是（f(n-1,m)+k+1)%n，而这个数字也就是一开始我们标记的f(n,m)，所以可以推得递归公式为
$$f(n,m) =(f(n-1,m)+k+1)\mod n$$将k=(m-1)%n代入，化简得到：
$$f(n,m) =(f(n-1,m)+m)\mod n， 且f(1,m) = 0$$代码中可以采用迭代或者递归的方法实现该递归公式。时间复杂度为O(n)，空间复杂度为O(1)
注意公式中的mod就等同于%，为取模运算。值得注意的是，在数学中，下式成立：(a%n+b)%n=(a+b)%n
code
class Solution {
public int lastRemaining(int n, int m) {
// 模拟法
// boolean[] flag=new boolean[n];
// int index=-1;
// int tmp;
// for (int i = 0; i < n-1; i++) {
// tmp=m;
// while (tmp!=0){
// if (++index==n)index=0;
// if (!flag[index]){
// --tmp;
// }
// }
// flag[index]=true;
// }
// for (int i = 0; i < n; i++) {
// if (!flag[i])return i;
// }
// return 0;
// 数学法tql
int res = 0;
for (int i = 2; i <= n; i++) {
res = (res + m) % i;
}
return res;
}
}31 912. 排序数组
题目
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]提示：
1 <= nums.length <= 50000-50000 <= nums[i] <= 50000
思路
各种排序~
code
class Solution {
public int[] sortArray(int[] nums) {
Arrays.sort(nums);
return nums;
}
}本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。