每日一题

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. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] 仅为 012
思路

模拟一遍这个过程,但是每次烂掉的橘子记为-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^9
  • 1 <= 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 res

07 面试题59 - II. 队列的最大值

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_valuepush_backpop_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 <= 1000
  • 1 <= str2.length <= 1000
  • str1[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 <= 1000
  • 1 <= 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 <= 10000
  • 0 <= 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,那么可以进行以下操作:

    1. 往 y 壶倒水;
    2. 把 y 壶的水倒入 x 壶;
    3. 如果 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 操作是不能让数组的每个值唯一的。

提示:

  1. 0 <= A.length <= 40000
  2. 0 <= 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,我们返回第二个结点。

提示:

  • 给定链表的结点数介于 1100 之间。
思路

经典的快慢指针用法。

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 <= 50
  • 0 <= 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
解释:
在本例中,车能够捕获所有的卒。

提示:

  1. board.length == board[i].length == 8
  2. board[i][j] 可以是 'R','.','B' 'p'
  3. 只有一个格子上存在 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. 1 <= deck.length <= 10000
  2. 0 <= 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. 1 <= words.length <= 2000
  2. 1 <= words[i].length <= 7
  3. 每个单词都是小写字母 。
思路

很烂的思路,先对单词进行按长度排序。然后遍历判断是否以其他单词结尾的,如果有单词被别的单词包含就不计算,最后的结果就是没有被包含的单词的长度+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,上面的每个「区域」(单元格)都用 01 标记好了。其中 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. 1 <= grid.length == grid[0].length <= 100
  2. grid[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^5
  • 1 <= 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+10
k+21
......
n-1n-k-2
0n-k-1
......
k-1n-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. 1 <= nums.length <= 50000
  2. -50000 <= nums[i] <= 50000
思路

各种排序~

code
class Solution {
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
}
文章目录