编程珠玑

计算机编程充满乐趣。有时候,它是一门优雅的科学,有时候,它要去开发和使用新的软件工具。编程与人息息相关:客户实际想解决什么问题?

解题模板

双指针解题模板

我们通过迭代数组来解决一些问题。通常,我们只需要一个指针进行迭代,即从数组中的第一个元素开始,最后一个元素结束。然而,有时我们会使用两个指针进行迭代。

示例
让我们从一个经典问题开始:

反转数组中的元素。比如数组为 [‘l’, ‘e’, ‘e’, ‘t’, ‘c’, ‘o’, ‘d’, ‘e’],反转之后变为 [‘e’, ‘d’, ‘o’, ‘c’, ‘t’, ‘e’, ‘e’, ‘l’]。

使用双指针技巧,其思想是分别将两个指针分别指向数组的开头及末尾,然后将其指向的元素进行交换,再将指针向中间移动一步,继续交换,直到这两个指针相遇。

原地哈希(哈希表)

滑动窗口

二分法

每日一题

561. 数组拆分 I

//给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得
//从 1 到 n 的 min(ai, bi) 总和最大。 
// 返回该 最大总和 。
//
// 示例 1: 
//输入:nums = [1,4,3,2]
//输出:4
//解释:所有可能的分法(忽略元素顺序)为:
//1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
//2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
//3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
//所以最大总和为 4 
//
// 示例 2: 
//输入:nums = [6,2,6,5,1,2]
//输出:9
//解释:最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 
//6 = 9
// 

// 提示: 
// 1 <= n <= 104 
// nums.length == 2 * n 
// -104 <= nums[i] <= 104 
// Related Topics 数组 
// 👍 240 👎 0

class Solution {
    public int arrayPairSum(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(i%2 == 0){
               res = res + nums[i];
            }
        }
        return res;
    }
}

解题思路分析:

我们先对数组进行排序。

由于每两个数,我们只能选择当前小的一个进行累加。

因此我们猜想应该从第一个位置进行选择,然后隔一步选择下一个数。这样形成的序列的求和值最大

566. 重塑矩阵

//在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。 
// 给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。 
// 重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。 
// 如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。 
// 示例 1: 
//输入: 
//nums = 
//[[1,2],
// [3,4]]
//r = 1, c = 4
//输出: 
//[[1,2,3,4]]
//解释:
//行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
// 示例 2: 
//输入: 
//nums = 
//[[1,2],
// [3,4]]
//r = 2, c = 4
//输出: 
//[[1,2],
// [3,4]]
//解释:
//没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
// 注意: 
// 给定矩阵的宽和高范围在 [1, 100]。 
// 给定的 r 和 c 都是正数。 
// 
// Related Topics 数组 
// 👍 183 👎 0
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
      int m = nums.length;
      int n = nums[0].length;
      if(m*n != r*c){
          return nums;
      }
      int[][] ans = new int[r][c];
      for(int x=0;x<m*n;x++){
           ans[x / c][x % c] = nums[x / n][x % n];
      }
      return ans;
    }
}

1004. 最大连续1的个数 III

//给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。 
// 返回仅包含 1 的最长(连续)子数组的长度。 
// 示例 1: 
//
// 输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//输出:6
//解释: 
//[1,1,1,0,0,1,1,1,1,1,1]
//粗体数字从 0 翻转到 1,最长的子数组长度为 6。 
//
// 示例 2: 
// 输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//输出:10
//解释:
//[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
//粗体数字从 0 翻转到 1,最长的子数组长度为 10。 
// 提示: 
// 1 <= A.length <= 20000 
// 0 <= K <= A.length 
// A[i] 为 0 或 1 
// 
// Related Topics 双指针 Sliding Window 
// 👍 218 👎 0

class Solution {
    public int longestOnes(int[] A, int K) {

    }
}

解题思路:滑动窗口法,//TODO

数组的遍历

485. 最大连续1的个数
//给定一个二进制数组, 计算其中最大连续1的个数。 
//示例 1: 
//输入: [1,1,0,1,1,1]
//输出: 3
//解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.
// 
// 注意: 
// 输入的数组只包含 0 和1。 
// 输入数组的长度是正整数,且不超过 10,000。 
// 
// Related Topics 数组 
// 👍 165 👎 0

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
     int count = 0;
     int maxCount = 0;
     for(int i=0;i<nums.length;i++){
         if(nums[i] == 1){
             count++;
         }
         if(nums[i] == 0){
             if(count>maxCount){
                 maxCount = count;
             }
             count = 0;
         }
     }
     return count>maxCount?count:maxCount;
    }
}

思路:遍历数组,用一个计数器(count)记录1的数量,用另一个计数器记录当前1的最大出行次数,如果遇到0 ,比较count与maxCount ,maxCount 记录较大值,同时将count置为0;

495. 提莫攻击

//在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击时间序列和提莫攻击
//的中毒持续时间,你需要输出艾希的中毒状态总时长。 
//
// 你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。 
// 示例1: 
//
// 输入: [1,4], 2
//输出: 4
//原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
//第 4 秒初,提莫再次攻击艾希,使得艾希获得另外 2 秒中毒时间。
//所以最终输出 4 秒。
// 
// 示例2: 
//
// 输入: [1,2], 2
//输出: 3
//原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
//但是第 2 秒初,提莫再次攻击了已经处于中毒状态的艾希。
//由于中毒状态不可叠加,提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
//所以最终输出 3 。
// 
// 提示: 
// 你可以假定时间序列数组的总长度不超过 10000。 
// 你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数,并且不超过 10,000,000。 

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
     int res = 0;
     if(timeSeries.length == 0){
         return 0;
     }
     if(timeSeries.length == 1){
         return duration;
     }
     for(int i=1;i<timeSeries.length;i++){
         if(timeSeries[i]-timeSeries[i-1]<duration){
             res = res + timeSeries[i] - timeSeries[i-1];
         }
         else{
             res= res + duration;
         }
     }
     return res+duration;
    }
}

思路:按照时间序列的话,数组一定是递增的如果第二个时间点和前一个时间之差大于了中毒时间,明显总中毒时间加duration
否则,则有重叠,总中毒时间加上第二个时间点和前一个时间之差。

414. 第三大的数

//给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。 
// 示例 1: 
//输入:[3, 2, 1]
//输出:1
//解释:第三大的数是 1 。 
//
// 示例 2: 
//输入:[1, 2]
//输出:2
//解释:第三大的数不存在, 所以返回最大的数 2 。
// 
// 示例 3: 
//输入:[2, 2, 3, 1]
//输出:1
//解释:注意,要求返回第三大的数,是指第三大且唯一出现的数。
//存在两个值为2的数,它们都排第二。
// 
// 提示: 
// 1 <= nums.length <= 104 
// -231 <= nums[i] <= 231 - 1 
// 
// 进阶:你能设计一个时间复杂度 O(n) 的解决方案吗? 
// Related Topics 数组 
// 👍 201 👎 0
class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
            if(set.size() > 3){
                set.remove(set.first());
            }
        }
        return set.size() <3?set.last():set.first();
    }
}


思路:维护一个只有3个元素的TreeSet,如果大于三个元素就就把Set中的最小最小值remove掉。
最后如果Set中元素小于3就返回Set最大值,否则返回最小值。

628. 三个数的最大乘积

//给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。 
//
// 示例 1: 
//输入:nums = [1,2,3]
//输出:6
// 
// 示例 2: 
// 
//输入:nums = [1,2,3,4]
//输出:24
// 
// 示例 3: 
//
//输入:nums = [-1,-2,-3]
//输出:-6
// 提示: 
//
// 3 <= nums.length <= 104 
// -1000 <= nums[i] <= 1000 
// 
// Related Topics 数组 数学 
// 👍 278 👎 0
class Solution {
    public int maximumProduct(int[] nums) {
     Arrays.sort(nums);
     int max1 = nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3];
     int max2 = nums[0]*nums[1]*nums[nums.length-1];
     return Math.max(max1,max2); 
    }
}

思路:首先将数组排序。

如果数组中全是非负数,则排序后最大的三个数相乘即为最大乘积;如果全是非正数,则最大的三个数相乘同样也为最大乘积。

如果数组中有正数有负数,则最大乘积既可能是三个最大正数的乘积,也可能是两个最小负数(即绝对值最大)与最大正数的乘积。

综上,我们在给数组排序后,分别求出三个最大正数的乘积,以及两个最小负数与最大正数的乘积,二者之间的最大值即为所求答案。

统计数组中的元素

645. 错误的集合

//集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有
//一个数字重复 。 
// 给定一个数组 nums 代表了集合 S 发生错误后的结果。 
// 请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。 
//
// 示例 1: 
//输入:nums = [1,2,2,4]
//输出:[2,3]
// 
// 示例 2: 
//输入:nums = [1,1]
//输出:[1,2]
// 
// 提示: 
// 2 <= nums.length <= 104 
// 1 <= nums[i] <= 104 
// Related Topics 哈希表 数学 
// 👍 150 👎 0

class Solution {
    public int[] findErrorNums(int[] nums) {

    }
}

448. 找到所有数组中消失的数字

//给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
// 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
//
// 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
//
// 示例:
//输入:
//[4,3,2,7,8,2,3,1]
//
//输出:
//[5,6]
// Related Topics 数组
// 👍 641 👎 0
//暴力解法,超出时间限制
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> resp = new ArrayList<>();
        List<Integer> map = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            map.add(nums[i]);
        }
        for(int j=1;j<nums.length+1;j++){
            if(!list.contains(j)){
              resp.add(j);
            }
        }
        return resp;
    }
}
//思路二 通过

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
     List<Integer> resp = new ArrayList<>();
     for(int i=1;i<nums.length+1;i++){
       int index = Math.abs(nums[i-1]);
       if(nums[index-1] > 0){
         nums[index-1] = - nums[index-1];  
       }
     }
     for(int i=0;i<nums.length;i++){
         if(nums[i] > 0){
             resp.add(i+1);
         }
     }
    return resp;
    }
}

解题思路:

使用数组的下标来标记数字的出现于否,通过一遍遍历即可标记出全部已经出现的数组

[4,3,2,7,8,2,3,1] 初始数据

[4,3,2,-7,8,2,3,1] 第一个数据 4 出现,将数组的第四个也就是下标 3 的数据修改为负数。-7 计算时,通过绝对值处理一下即可不影响数据的计算

[4,3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,-3,1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[-4,-3,-2,-7,8,2,-3,-1]

442. 数组中重复的数据

//给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。 
// 找到所有出现两次的元素。 
// 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗? 
// 示例: 
//输入:
//[4,3,2,7,8,2,3,1]
//输出:
//[2,3] 
// Related Topics 数组 
// 👍 337 👎 0
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<>();
     Arrays.sort(nums);
     for(int i=1;i<nums.length;i++){
        if(nums[i] == nums[i-1]){
            res.add(nums[i]);
        }
     }
     return res;
    }
}
//解法二

解题思路:

对数组进行排序,如果相邻两数相等,则为重复元素。

41. 缺失的第一个正数

//给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 
// 进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗? 
// 示例 1: 
//输入:nums = [1,2,0]
//输出:3
// 示例 2: 
//输入:nums = [3,4,-1,1]
//输出:2
// 示例 3: 
//输入:nums = [7,8,9,11,12]
//输出:1
// 提示: 
// 0 <= nums.length <= 300 
// -231 <= nums[i] <= 231 - 1 
// 
// Related Topics 数组 
// 👍 954 👎 0
//哈希表解法
class Solution {
    public int firstMissingPositive(int[] nums) {
     Set<Integer> set = new HashSet<>();
     for(int i=0;i<nums.length;i++){
         set.add(nums[i]);
     }
     for(int i=1;i<nums.length+1;i++){
         if(!set.contains(i)){
             return i;
         }
     }
     return nums.length +1;
    }
}
//暴力破解
class Solution {
    public int firstMissingPositive(int[] nums) {
     int min = 1;
     Arrays.sort(nums);
     for(int i=0;i<nums.length;i++){
        if(nums[i] == min){
            min++;
        }
     }
     return min;
    }
}
//原地哈希法


解题思路:

1、哈希表 我们可以将数组所有的数放入哈希表,随后从 11 开始依次枚举正整数,并判断其是否在哈希表中。

2、原地哈希:我们对数组进行遍历,对于遍历到的数 x,如果它在 [1, N][1,N] 的范围内,那么就将数组中的第 x-1 个位置(注意:数组下标从 0 开始)打上「标记」。在遍历结束之后,如果所有的位置都被打上了标记,那么答案是 N+1,否则答案是最小的没有打上标记的位置加 1。

274. H 指数

//给定一位研究者论文被引用次数的数组(被引用次数是非负整数)。编写一个方法,计算出研究者的 h 指数。 
// h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)总共有 h 篇论文分别被引
//用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。 
// 例如:某人的 h 指数是 20,这表示他已发表的论文中,每篇被引用了至少 20 次的论文总共有 20 篇。 
// 示例:  
//输入:citations = [3,0,6,1,5]
//输出:3 
//解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
//     由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。 
// 提示:如果 h 有多种可能的值,h 指数是其中最大的那个。 
// Related Topics 排序 哈希表 
// 👍 129 👎 0

class Solution {
    public int hIndex(int[] citations) {

    }
}

453. 最小操作次数使数组元素相等

//给定一个长度为 n 的 非空 整数数组,每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。 
// 示例: 
//输入:
//[1,2,3]
//输出:
//3
//解释:
//只需要3次操作(注意每次操作会增加两个元素的值):
//[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
// 
// Related Topics 数学 
// 👍 190 👎 0
//排序解法
class Solution {
    public int minMoves(int[] nums) {
     Arrays.sort(nums);
     int res = 0;
     for(int i=0;i<nums.length;i++){
       res = res + nums[i] - nums[0];
     }
     return res;
    }
}

//数学解法:

解题思路:先找出数组中的最小值,然后让数组中的每一个值减去最小值,代表着这个数要移动的次数。然后把所有次数累加求和即是结果。

665. 非递减数列

//给你一个长度为 n 的整数数组,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。 
// 我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]。 
// 示例 1: 
//输入: nums = [4,2,3]
//输出: true
//解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
// 示例 2:  
//输入: nums = [4,2,1]
//输出: false
//解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
// 提示: 
// 1 <= n <= 10 ^ 4 
// - 10 ^ 5 <= nums[i] <= 10 ^ 5 
// 
// Related Topics 数组 
// 👍 532 👎 0

class Solution {
    public boolean checkPossibility(int[] nums) {
      int count = 0;
      for(int i=1;i<nums.length;i++){
          //出现递减
         if(nums[i] <nums[i-1]){
          if(i==1 || nums[i] >= nums[i-2]){
              nums[i-1] = nums[i];
              count++;
          }
          else{
              nums[i] = nums[i-1];
               count++;
          }
          if(count >1){
              return false;
          }
         }
      }
      return count<=1;
    }
}

解题思路:贪心算法,遍历数组,查看是哪个数遍历数组,如果遇到递减:

  • 还能修改:
    • 修改方案1:将nums[i]缩小至nums[i 1 1];
    • 修改方案2:将nums[i - 1]放大至nums[i];

283. 移动零

//给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 
// 示例: 
// 输入: [0,1,0,3,12]
//输出: [1,3,12,0,0] 
// 说明: 
// 必须在原数组上操作,不能拷贝额外的数组。 
// 尽量减少操作次数。 
// 
// Related Topics 数组 双指针 
// 👍 955 👎 0
//暴力解法 使用了额外数组,定义一个新数组,不等于0的放前面,后面的都是0了
class Solution {
    public void moveZeroes(int[] nums) {
    if(nums == null || nums.length == 0){
         return;
     } 
     int[] temp = new int[nums.length];
     int j=0;
     for(int i=0;i<nums.length;i++){
         if(nums[i]!=0){
             temp[j] = nums[i];
             j++;
         }
     }
     for(int i=0;i<nums.length;i++){
         nums[i] = temp[i];
     }
    }
}
//双指针交换
class Solution {
    public void moveZeroes(int[] nums) {
     int start = 0;
     for(int i=0;i<nums.length;i++){
         if(nums[i] != 0){
             int temp = nums[i];
             nums[i] = nums[start];
             nums[start] = temp;
             start++;   
         }
     }
    }
}
//双指针解法(快慢指针) 优化上面交换方法,减少操作次数
class Solution {
    public void moveZeroes(int[] nums) {
    if(nums == null || nums.length == 0){
        return;
     } 
     int start = 0;
     for(int i=0;i<nums.length;i++){
         if(nums[i] != 0){
             nums[start] = nums[i];
             start++;
         }
     }
     for(int i=start;i<nums.length;i++){
         nums[i] = 0;
     }
    }
}

解题思路:

11. 盛最多水的容器

//给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i,
//ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
// 说明:你不能倾斜容器。
// 示例 1:
//输出:49
//解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
// 示例 2:
//输入:height = [1,1]
//输出:1
// 示例 3:
//输入:height = [4,3,2,1,4]
//输出:16
// 示例 4:
//输入:height = [1,2,1]
//输出:2
// 提示:
// n = height.length
// 2 <= n <= 3 * 104
// 0 <= height[i] <= 3 * 104
//
// Related Topics 数组 双指针
// 👍 2215 👎 0
//暴力破解,双层循环找出最大值
class Solution {
    public int maxArea(int[] height) {
     int maxCount = 0;
     for(int i=0;i<height.length;i++){
         for(int j=i+1;j<height.length;j++){
             maxCount = Math.max(Math.min(height[i], height[j]) * (j - i), maxCount);
         }
     }
     return maxCount;
    }
}
//双指针解法
class Solution {
    public int maxArea(int[] height) {
        int maxCount = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            maxCount = Math.max(Math.min(height[left], height[right]) * (right - left), maxCount);
            if (height[left] <= height[right]) {
                ++left;
            }
            else {
                --right;
            }
        }
        return maxCount;
    }
}

70. 爬楼梯

二维数组及滚动数组

118. 杨辉三角

//给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。 
// 在杨辉三角中,每个数是它左上方和右上方的数的和。 
// 示例: 
// 输入: 5
//输出:
//[
//     [1],
//    [1,1],
//   [1,2,1],
//  [1,3,3,1],
// [1,4,6,4,1]
//] 
// Related Topics 数组 
// 👍 454 👎 0
//数学解法
class Solution {
    public List<List<Integer>> generate(int numRows) {
      List<List<Integer>>  res = new ArrayList<>(); 
      for(int i=0;i<numRows;i++){
          List<Integer> list = new ArrayList<>();
          for(int j=0;j<=i;j++){
              if(j==0 || j==i){
                  list.add(1);
              }
              else{
                 list.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
              }
          }
          res.add(list);
      }
      return res;
    }
}

119. 杨辉三角 II

//给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。 
// 在杨辉三角中,每个数是它左上方和右上方的数的和。 
// 示例: 
// 输入: 3
//输出: [1,3,3,1]
// 进阶: 
// 你可以优化你的算法到 O(k) 空间复杂度吗? 
// Related Topics 数组 
// 👍 263 👎 0

class Solution {
    public List<Integer> getRow(int rowIndex) {
       List<List<Integer>>  res = new ArrayList<>(); 
       for(int i=0;i<=rowIndex;i++){
          List<Integer> list = new ArrayList<>();
          for(int j=0;j<=i;j++){
              if(j==0 || j==i){
                  list.add(1);
              }
              else{
                 list.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
              }
          }
          res.add(list);
      }
     return res.get(rowIndex);
    }
}

数组的旋转

189. 旋转数组

//给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 
// 进阶: 
// 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。 
// 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗? 
// 示例 1: 
//输入: nums = [1,2,3,4,5,6,7], k = 3
//输出: [5,6,7,1,2,3,4]
//解释:
//向右旋转 1 步: [7,1,2,3,4,5,6]
//向右旋转 2 步: [6,7,1,2,3,4,5]
//向右旋转 3 步: [5,6,7,1,2,3,4]
// 示例 2: 
//输入:nums = [-1,-100,3,99], k = 2
//输出:[3,99,-1,-100]
//解释: 
//向右旋转 1 步: [99,-1,-100,3]
//向右旋转 2 步: [3,99,-1,-100] 
// 提示: 
// 1 <= nums.length <= 2 * 104 
// -231 <= nums[i] <= 231 - 1 
// 0 <= k <= 105 
// Related Topics 数组 
// 👍 880 👎 0
class Solution {
    public void rotate(int[] nums, int k) {

    }
}

字符串

520. 检测大写字母

//给定一个单词,你需要判断单词的大写使用是否正确。 
// 我们定义,在以下情况时,单词的大写用法是正确的: 
// 全部字母都是大写,比如"USA"。 
// 单词中所有字母都不是大写,比如"leetcode"。 
// 如果单词不只含有一个字母,只有首字母大写, 比如 "Google"。 
// 否则,我们定义这个单词没有正确使用大写字母。 
// 示例 1: 
//输入: "USA"
//输出: True
// 示例 2: 
//输入: "FlaG"
//输出: False
// 注意: 输入是由大写和小写拉丁字母组成的非空单词。 
// Related Topics 字符串 
// 👍 123 👎 0
//解题思路:字符串转字符串数组,判断大写个数,全大写,全小写校验通过,第一个字符大写,校验通过
class Solution {
    public boolean detectCapitalUse(String word) {
        int count = 0;
        char[] chars = word.toCharArray();
        for(int i=0;i<chars.length;i++){
            if(chars[i]>='A' && chars[i] <= 'Z'){
                count++;
            }
        }
        return count==0 || count==chars.length || (count==1 && chars[0]>='A' && chars[0]<='Z');
    }
}

125. 验证回文串

//给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 
// 说明:本题中,我们将空字符串定义为有效的回文串。 
// 示例 1: 
// 输入: "A man, a plan, a canal: Panama"
//输出: true
// 示例 2: 
// 输入: "race a car"
//输出: false
// Related Topics 双指针 字符串 
// 👍 330 👎 0
//双指针解法
class Solution {
    public boolean isPalindrome(String s) {
        String s1 = s.toLowerCase().trim();
        char[] chars = s1.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<chars.length;i++){
            if((chars[i] >='a' && chars[i] <='z') || (chars[i]>='0' && chars[i]<='9')){
                sb.append(chars[i]);
            }
        }
        int j = sb.length()-1;
        for(int i=0;i<sb.length();i++){
            if(sb.charAt(i) != sb.charAt(j)){
                return false;
            }
            j--;
        }
        return true;
    }
}

14. 最长公共前缀

//编写一个函数来查找字符串数组中的最长公共前缀。 
// 如果不存在公共前缀,返回空字符串 ""。 
// 示例 1: 
//输入:strs = ["flower","flow","flight"]
//输出:"fl"
// 示例 2:  
//输入:strs = ["dog","racecar","car"]
//输出:""
//解释:输入不存在公共前缀。 
// 提示: 
// 0 <= strs.length <= 200 
// 0 <= strs[i].length <= 200 
// strs[i] 仅由小写英文字母组成 
// Related Topics 字符串 
// 👍 1466 👎 0
//解题思路:纵向比较字符串的位置值是否相等
//flower
//flow
//flight
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(null == strs || strs.length==0){
            return "";
        }
        for(int i=0;i<strs[0].length();i++){
            char c = strs[0].charAt(i);
            for(int j=1;j<strs.length;j++){
                if(i== strs[j].length() || strs[j].charAt(i) != c){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }
}

434. 字符串中的单词数

//统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。 
// 请注意,你可以假定字符串里不包括任何不可打印的字符。 
// 示例: 
// 输入: "Hello, my name is John"
//输出: 5
//解释: 这里的单词是指连续的不是空格的字符,所以 "Hello," 算作 1 个单词。
// Related Topics 字符串 
// 👍 77 👎 0
class Solution {
    public int countSegments(String s) {
        int count = 0;
        if(s.length()==0 || s.equals("")){
            return 0;
        }
        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != '') {
                count++;
            }
        }
        return count;
    }
}

解题思路:计算单词的数量,就等同于计数单词开始的下标个数。因此,只需要定义好下标的条件,就可以遍历整个字符串,检测每个下标。定义如下:若该下标前为空格(或者为初始下标),且自身不为空格,则其为单词开始的下标。该条件可以以常数时间检测。最后,返回满足条件的下标个数。

58. 最后一个单词的长度

//给你一个字符串 s,由若干单词组成,单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词,请返回 0 。 
// 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 
// 示例 1: 
//输入:s = "Hello World"
//输出:5
// 示例 2: 
//输入:s = " "
//输出:0
// 提示: 
// 1 <= s.length <= 104 
// s 仅有英文字母和空格 ' ' 组成 
// 
// Related Topics 字符串 
// 👍 280 👎 0
//字符串分割法
class Solution {
    public int lengthOfLastWord(String s) {
        if(s==null || s=="" || s.length()==0){
            return 0;
        }
        String[] s1 = s.split(" ");
        if(s1.length ==0){
            return 0;
        }
        return s1[s1.length-1].length();
    }
}
//从尾部开始遍历字符串
class Solution {
    public int lengthOfLastWord(String s) {
        int count = 0;
        if(s==null || s=="" || s.length()==0){
            return 0;
        }
        for(int i=0;i<s.length();i++){
           char k = s.charAt(s.length()-1-i);
           if(k != ' '){
               count++;
           }
           if(count>0 && k == ' '){
               break;
           }
        }
        return count;
    }
}

344. 反转字符串

//编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 
// 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 
// 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。 
// 示例 1: 
// 输入:["h","e","l","l","o"]
//输出:["o","l","l","e","h"]
// 示例 2: 
// 输入:["H","a","n","n","a","h"]
//输出:["h","a","n","n","a","H"] 
// Related Topics 双指针 字符串 
// 👍 358 👎 0
//暴力破解,双层循环交换
class Solution {
    public void reverseString(char[] s) {
        if(s==null || s.length==0){
            return;
        }
        for (int i = 0; i < s.length; i++) {
            for (int j = i + 1;j<s.length; j++) {
                char temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }
}
//双指针解法
class Solution {
    public void reverseString(char[] s) {
        if(s==null || s.length==0){
            return;
        }
        int left = 0;
        int right = s.length-1;
        while (left<right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

541. 反转字符串 II

//给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。 
// 如果剩余字符少于 k 个,则将剩余字符全部反转。 
// 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。 
// 示例: 
// 输入: s = "abcdefg", k = 2
//输出: "bacdfeg"
// 提示: 
// 该字符串只包含小写英文字母。 
// 给定字符串的长度和 k 在 [1, 10000] 范围内。 
// Related Topics 字符串 
// 👍 116 👎 0
class Solution {
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        for(int start = 0;start<chars.length;start = start+(2*k)){
            int i= start;
            int j= Math.min(start+k-1,chars.length-1);
            while (i<j){
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
                i++;
                j--;
            }
        }
        return new String(chars);
    }
}

557. 反转字符串中的单词 III

//给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 
// 示例: 
// 输入:"Let's take LeetCode contest"
//输出:"s'teL ekat edoCteeL tsetnoc"
// 提示: 
// 在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。 
// Related Topics 字符串 
// 👍 274 👎 0
//暴力破解
class Solution {
    public String reverseWords(String s) {
        if(s==null || s.length()==0 || s==""){
            return "";
        }
        String[] ans = s.split(" ");
        StringBuilder result = new StringBuilder();
        for(int i=0;i<ans.length;i++){
           String s1 = ans[i];
           for(int j=0;j<s1.length();j++){
               result.append(s1.charAt(s1.length()-1-j));
           }
           if(i !=ans.length-1){
               result.append(" ");
           }
        }
        return result.toString();
    }
}

151. 翻转字符串里的单词

//给定一个字符串,逐个翻转字符串中的每个单词。 
// 说明: 
// 无空格字符构成一个 单词 。 
// 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。 
// 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。 
// 示例 1: 
// 输入:"the sky is blue"
//输出:"blue is sky the"
// 示例 2: 
// 输入:"  hello world!  "
//输出:"world! hello"
//解释:输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
// 示例 3: 
// 输入:"a good   example"
//输出:"example good a"
//解释:如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
// 示例 4: 
// 输入:s = "  Bob    Loves  Alice   "
//输出:"Alice Loves Bob"
// 示例 5: 
// 输入:s = "Alice does not even like bob"
//输出:"bob like even not does Alice"
// 提示: 
// 1 <= s.length <= 104 
// s 包含英文大小写字母、数字和空格 ' ' 
// s 中 至少存在一个 单词 
// 进阶: 
// 请尝试使用 O(1) 额外空间复杂度的原地解法。 
// Related Topics 字符串 
// 👍 281 👎 0
class Solution {
    public String reverseWords(String s) {
     if(s == null || s.length() == 0){
         return null;
     }
     StringBuilder result = new StringBuilder();
     String[] s1 = s.split(" ");
     for(int i=s1.length-1;i>=0;i--){
         if(s1[i] == null || s1[i].length() == 0){
             continue;
         }
         result.append(s1[i]).append(" ");
     }
     return result.toString().trim();
    }
}

387. 字符串中的第一个唯一字符

//给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 
// 示例: 
// s = "leetcode"
//返回 0
//s = "loveleetcode"
//返回 2
// 提示:你可以假定该字符串只包含小写字母。 
// Related Topics 哈希表 字符串 
// 👍 351 👎 0
//暴露解法 超时
class Solution {
    public int firstUniqChar(String s) {
     for(int i=0;i<s.length();i++){
         int count = 0;
         char ans = s.charAt(i);
         for(int j=0;j<s.length();j++){
           if(s.charAt(j) == ans){
               count++;
           }
         }
         if(count == 1){
             return i;
         }
     }
     return -1;
    }
}
//HashMap 计数
class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Integer integer = map.get(s.charAt(i));
            if (null == integer || integer == 0) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), integer + 1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

389. 找不同

//给定两个字符串 s 和 t,它们只包含小写字母。 
// 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。 
// 请找出在 t 中被添加的字母。 
// 示例 1: 
// 输入:s = "abcd", t = "abcde"
//输出:"e"
//解释:'e' 是那个被添加的字母。
// 示例 2: 
// 输入:s = "", t = "y"
//输出:"y"
// 示例 3: 
// 输入:s = "a", t = "aa"
//输出:"a"
// 示例 4: 
// 输入:s = "ae", t = "aea"
//输出:"a"
// 提示: 
// 0 <= s.length <= 1000 
// t.length == s.length + 1 
// s 和 t 只包含小写字母 
// Related Topics 位运算 哈希表 
// 👍 235 👎 0
//解题思路1:HashMap 分别统计s、t字母个数,遍历t,如果字母个数不相等,则返回字母。
class Solution {
    public char findTheDifference(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            Integer integer = map.get(s.charAt(i));
            if (null == integer || integer == 0) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), integer + 1);
            }
        }

        Map<Character,Integer> map1 = new HashMap<>();
        for(int i=0;i<t.length();i++){
            Integer integer = map1.get(t.charAt(i));
            if (null == integer || integer == 0) {
                map1.put(t.charAt(i), 1);
            } else {
                map1.put(t.charAt(i), integer + 1);
            }
        }

        for(int i=0;i<t.length();i++){
            if(map.get(t.charAt(i)) != map1.get(t.charAt(i))){
                return t.charAt(i);
            }
        }
        return ' ';
    }
}

//解法2:将字符串 *s* 中每个字符的 ASCII 码的值求和,得到 *A_s*;对字符串 *t* 同样的方法得到 *A_t*。两者的差值 *A_t-A_s* 即代表了被添加的字符。
class Solution {
    public char findTheDifference(String s, String t) {
      int anst = 0; int anss = 0;
      for(int i=0;i<s.length();i++){
          anss = anss + s.charAt(i);
      }
      for(int i=0;i<t.length();i++){
          anst = anst+t.charAt(i);
      }
      return (char)(anst - anss);
    }
}
//把字符串s和t合并,然后遍历合并的每个字符,判断集合set中是否有这个字符,如果有就移除,否则就加入到集合set中。最后集合set中只有一个字符,这个字符就是我们要求的。
class Solution {
    public char findTheDifference(String s, String t) {
        Set<Character> set = new HashSet<>();
        char[] charArr = s.concat(t).toCharArray();
        for (int i = 0; i < charArr.length; i++) {
            if (set.contains(charArr[i]))
                set.remove(charArr[i]);
            else
                set.add(charArr[i]);
        }
        return (char) set.toArray()[0];
    }
}    

383. 赎金信

//给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面
//的字符构成。如果可以构成,返回 true ;否则返回 false。 
// (题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 
// 注意: 
// 你可以假设两个字符串均只含有小写字母。 
// canConstruct("a", "b") -> false
//canConstruct("aa", "ab") -> false
//canConstruct("aa", "aab") -> true
// Related Topics 字符串 
// 👍 135 👎 0
//HashMap 分别统计赎金与杂志里的字符个数,如果杂志里没有赎金里的字符或者赎金里的字符个数大于杂志里的字符个数,返回false,不然返回true
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> mMap = new HashMap<>();
        HashMap<Character, Integer> rMap = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            Integer count = mMap.get(magazine.charAt(i));
            if (count == null || count == 0) {
                mMap.put(magazine.charAt(i), 1);
            } else {
                mMap.put(magazine.charAt(i), count + 1);
            }
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            Integer count = rMap.get(ransomNote.charAt(i));
            if (count == null || count == 0) {
                rMap.put(ransomNote.charAt(i), 1);
            } else {
                rMap.put(ransomNote.charAt(i), count + 1);
            }
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char ans = ransomNote.charAt(i);
            if (mMap.get(ans) == null) {
                return false;
            }
            if (mMap.get(ans) != null && rMap.get(ans) != null) {
                if (rMap.get(ans) > mMap.get(ans)) {
                    return false;
                }
            }
        }
        return true;
    }
}

242. 有效的字母异位词

//给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 
// 示例 1: 
// 输入: s = "anagram", t = "nagaram"
//输出: true
// 示例 2: 
// 输入: s = "rat", t = "car"
//输出: false 
// 说明: 
//你可以假设字符串只包含小写字母。 
// 进阶: 
//如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况? 
// Related Topics 排序 哈希表 
// 👍 345 👎 0
//HashMap 统计单次个数
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        Map<Character,Integer> sMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
             sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        }  
        for(int i=0;i<t.length();i++){
          Integer nums =  sMap.get(t.charAt(i));
          if(nums != null){
              sMap.put(t.charAt(i),nums-1);
        }  
        for(int i=0;i<s.length();i++){
            if(sMap.get(s.charAt(i)) != 0){
                return false;
            }
        }
        return true;
    }
}
//解法2 使用数组保存字母个数,由于内存是连续的,-'a' 表示对应字母索引个数
class Solution {
    public boolean isAnagram(String s, String t) {
     int[] ans = new int[26];  
     if (s.length() != t.length()) {
        return false;
    }
     for(int i=0;i<s.length();i++){
      ans[s.charAt(i)-'a'] = ans[s.charAt(i)-'a'] +1;
     }
     for(int i=0;i<t.length();i++){
       ans[t.charAt(i)-'a'] = ans[t.charAt(i)-'a'] -1;
       if(ans[t.charAt(i)-'a'] <0){
           return false;
       }   
     }
     return true;
    }
}  

49. 字母异位词分组

//给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 
// 示例: 
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
// 说明: 
// 所有输入均为小写字母。 
// 不考虑答案输出的顺序。 
// Related Topics 哈希表 字符串 
// 👍 668 👎 0
//HashMap 解法
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
       Map<String,List<String>> map = new HashMap<>();
       for(int i=0;i<strs.length;i++){
           char[] chars = strs[i].toCharArray();
           Arrays.sort(chars);
           String key = new String(chars);
           List<String> list = map.get(key);
           if(list == null || list.size() == 0){
             list = new ArrayList<>();
           }
           list.add(strs[i]);
           map.put(key,list);
       }
       return new ArrayList<>(map.values());
    }
}

//Java8写法
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str -> {
                // 返回 str 排序后的结果。
                // 按排序后的结果来grouping by,算子类似于 sql 里的 group by。
                char[] array = str.toCharArray();
                Arrays.sort(array);
                return new String(array);
            })).values());
    }
}
//一行代码
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());
    }
}

451. 根据字符出现频率排序

//给定一个字符串,请将字符串里的字符按照出现的频率降序排列。 
// 示例 1: 
//输入:
//"tree"
//输出:
//"eert"
//解释:
//'e'出现两次,'r'和't'都只出现一次。
//因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
// 示例 2: 
//输入:
//"cccaaa"
//输出:
//"cccaaa"
//解释:
//'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
//注意"cacaca"是不正确的,因为相同的字母必须放在一起。
// 示例 3: 
//输入:
//"Aabb"
//输出:
//"bbAa"
//解释:
//此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
//注意'A'和'a'被认为是两种不同的字符。
// Related Topics 堆 哈希表 
// 👍 220 👎 0
class Solution {
    public String frequencySort(String s) {
     Map<Character,Integer> map = new HashMap<>();
     int[] ans = new int[s.length()];
     StringBuilder sb = new StringBuilder();
     for(int i=0;i<s.length();i++){
         map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
     }
     for(int i=0;i<s.length();i++){
       Integer num =  map.get(s.charAt(i));
       ans[i] = num;
     }
     Arrays.sort(ans);
     for(int i=ans.length;i>0;i--){
      for(int j=0;j<s.length();j++){
          if(map.get(s.charAt(j)) == i){
              sb.append(s.charAt(j));
          }
      }
     }
     return sb.toString();
    }
}

423. 从英文中重建数字

//给定一个非空字符串,其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。 
// 注意: 
// 输入只包含小写英文字母。 
// 输入保证合法并可以转换为原始的数字,这意味着像 "abc" 或 "zerone" 的输入是不允许的。 
// 输入字符串的长度小于 50,000。 
// 示例 1: 
//输入: "owoztneoer"
//输出: "012" (zeroonetwo)
// 示例 2: 
//输入: "fviefuro"
//输出: "45" (fourfive)
// Related Topics 数学 
// 👍 56 👎 0
class Solution {
    public String originalDigits(String s) {

    }
}

657. 机器人能否返回原点

//在二维平面上,有一个机器人从原点 (0, 0) 开始。给出它的移动顺序,判断这个机器人在完成移动后是否在 (0, 0) 处结束。 
// 移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。如果机器人在完成所有动作后
//返回原点,则返回 true。否则,返回 false。 
// 注意:机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次,“L” 将始终向左移动等。此外,假设每次移动机器人的移动幅度相同。 
// 示例 1: 
// 输入: "UD"
//输出: true
//解释:机器人向上移动一次,然后向下移动一次。所有动作都具有相同的幅度,因此它最终回到它开始的原点。因此,我们返回 true。 
// 示例 2: 
// 输入: "LL"
//输出: false
//解释:机器人向左移动两次。它最终位于原点的左侧,距原点有两次 “移动” 的距离。我们返回 false,因为它在移动结束时没有返回原点。 
// Related Topics 字符串 
// 👍 189 👎 0

class Solution {
    public boolean judgeCircle(String moves) {
     int x =0;
     int y=0;
     for(int i=0;i<moves.length();i++){
        if(moves.charAt(i) == 'L'){
            x--;
        }
        if(moves.charAt(i) == 'R'){
            x++;
        }
        if(moves.charAt(i) == 'U'){
            y--;
        }
        if(moves.charAt(i) == 'D'){
           y++;
        }
     }
     return x==0 && y==0;
    }
}

551. 学生出勤记录 I

//给定一个字符串来代表一个学生的出勤记录,这个记录仅包含以下三个字符: 
// 'A' : Absent,缺勤 
// 'L' : Late,迟到 
// 'P' : Present,到场 
// 如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。 
// 你需要根据这个学生的出勤记录判断他是否会被奖赏。 
// 示例 1: 
// 输入: "PPALLP"
//输出: True
// 示例 2: 
// 输入: "PPALLL"
//输出: False
// Related Topics 字符串 
// 👍 69 👎 0
class Solution {
    public boolean checkRecord(String s) {
     Map<Character,Integer> map = new HashMap<>();
     for(int i=0;i<s.length();i++){
         map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
     }
     if(map.get('A') == null || map.get('A')<=1){
         if(map.get('L') ==null || map.get('L') <=2){
           return true;
         }
         for(int i=2;i<s.length();i++){
             if(s.charAt(i) == 'L' && s.charAt(i-1) == 'L' && s.charAt(i-2) == 'L'){
              return false;
             }
         }
         return true;
     }
     return false;
    }
}
//优化时间复杂度
class Solution {
    public boolean checkRecord(String s) {
      int aCount = 0;
      int lCount = 0;
      for(int i=0;i<s.length();i++){
        if(s.charAt(i) == 'A'){
            lCount = 0;
            aCount++;
            if(aCount>1){
                return false;
            }
        }
        else if(s.charAt(i) == 'L'){
            lCount++;
            if(lCount>2){
                return false;
            }
        }
        else{
            lCount = 0;
        }
      }
      return true;
    }
}
//一行代码解决
class Solution {
    public boolean checkRecord(String s) {
    return s.indexOf("A") == s.lastIndexOf("A") && !s.contains("LLL");
    }
}

696. 计数二进制子串

//给定一个字符串 s,计算具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是连续的。 
// 重复出现的子串要计算它们出现的次数。 
// 示例 1 : 
//输入: "00110011"
//输出: 6
//解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。
//请注意,一些重复出现的子串要计算它们出现的次数。
//另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。
// 示例 2 : 
//输入: "10101"
//输出: 4
//解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。
// 提示: 
// s.length 在1到50,000之间。 
// s 只包含“0”或“1”字符。 
// Related Topics 字符串 
// 👍 336 👎 0
class Solution {
    public int countBinarySubstrings(String s) {

    }
}

535. TinyURL 的加密与解密

//TinyURL是一种URL简化服务, 比如:当你输入一个URL https://leetcode.com/problems/design-tinyurl 时
//,它将返回一个简化的URL http://tinyurl.com/4e9iAk. 
// 要求:设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的,你只需要保证一个URL可
//以被加密成一个TinyURL,并且这个TinyURL可以用解密方法恢复成原本的URL。 
// Related Topics 哈希表 数学 
// 👍 113 👎 0
public class Codec {

    Map<String,String> map = new HashMap<>();
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
      map.put(Integer.toHexString(longUrl.hashCode()),longUrl);
     return Integer.toHexString(longUrl.hashCode());
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
      return map.get(shortUrl);
    }
}

299. 猜数字游戏

//你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 
// 你写出一个秘密数字,并请朋友猜这个数字是多少。 
// 朋友每猜测一次,你就会给他一个提示,告诉他的猜测数字中有多少位属于数字和确切位置都猜对了(称为“Bulls”, 公牛),有多少位属于数字猜对了但是位置不对
//(称为“Cows”, 奶牛)。 
// 朋友根据提示继续猜,直到猜出秘密数字。 
// 请写出一个根据秘密数字和朋友的猜测数返回提示的函数,返回字符串的格式为 xAyB ,x 和 y 都是数字,A 表示公牛,用 B 表示奶牛。 
// xA 表示有 x 位数字出现在秘密数字中,且位置都与秘密数字一致。 
// yB 表示有 y 位数字出现在秘密数字中,但位置与秘密数字不一致。 
// 请注意秘密数字和朋友的猜测数都可能含有重复数字,每位数字只能统计一次。 
// 示例 1: 
// 输入: secret = "1807", guess = "7810"
//输出: "1A3B"
//解释: 1 公牛和 3 奶牛。公牛是 8,奶牛是 0, 1 和 7。 
// 示例 2: 
// 输入: secret = "1123", guess = "0111"
//输出: "1A1B"
//解释: 朋友猜测数中的第一个 1 是公牛,第二个或第三个 1 可被视为奶牛。 
// 说明: 你可以假设秘密数字和朋友的猜测数都只包含数字,并且它们的长度永远相等。 
// Related Topics 哈希表 
// 👍 119 👎 0

class Solution {
    public String getHint(String secret, String guess) {
        int[] nums = new int[10];
        int countA = 0, countB = 0;
        for (int i = 0; i < secret.length(); i++) {
            if(secret.charAt(i) == guess.charAt(i)) countA++;
            else{
                if (nums[guess.charAt(i) - '0']-- > 0) countB++;
                if(nums[secret.charAt(i) - '0']++ < 0) countB++;
            }
        }
        return countA + "A" + countB + "B";
    }
}

412. Fizz Buzz

//写一个程序,输出从 1 到 n 数字的字符串表示。
// 1. 如果 n 是3的倍数,输出“Fizz”;
// 2. 如果 n 是5的倍数,输出“Buzz”;
// 3.如果 n 同时是3和5的倍数,输出 “FizzBuzz”。
// 示例:
// n = 15,
//返回:
//[
//    "1",
//    "2",
//    "Fizz",
//    "4",
//    "Buzz",
//    "Fizz",
//    "7",
//    "8",
//    "Fizz",
//    "Buzz",
//    "11",
//    "Fizz",
//    "13",
//    "14",
//    "FizzBuzz"
//]
//
// 👍 85 👎 0
class Solution {
    public List<String> fizzBuzz(int n) {
        String[] res = new String[n];
        for (int i = 1; i < n; i++) {
            if (i % 3 == 0 && i % 5 != 0) {
                res[i] = "Fizz";
            } else if (i % 5 == 0 && !i % 3 != 0) {
                res[i] = "Buzz";
            } else if (i % 5 == 0 && i % 3 == 0) {
                res[i] = "FizzBuzz";
            } else {
                res[i] = String.valueOf(i);
            }
        }
        return res;
    }
}

  转载请注明: Hi 高虎 编程珠玑

 本篇
编程珠玑 编程珠玑
计算机编程充满乐趣。有时候,它是一门优雅的科学,有时候,它要去开发和使用新的软件工具。编程与人息息相关:客户实际想解决什么问题? 解题模板双指针解题模板我们通过迭代数组来解决一些问题。通常,我们只需要一个指针进行迭代,即从数组中的第一个
下一篇 
LeetCode刷题指南 LeetCode刷题指南
刷题提升自身数据结构与算法的能力,提升思考问题,解决问题的能力。
  目录