剑指offer

剑指offer

面试题13： 机器人的运动范围

面试题13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

• 1 <= n,m <= 100
• 0 <= k <= 20

解答

//测试能通过  提交就报错  离谱
class Solution {
    public static int res=0;
    public int movingCount(int m, int n, int k) {
         int  [][]nums=new int[m][n];
         dfs(i,j,m,n,k,nums);
        return res;

    }
     private static void dfs(int i,int j,int m, int n, int k,int  [][]nums) {
        if(i<0 || i>=m || j<0 || j>=n ||  !canWalk(i,j,k) || nums[i][j]==-1){
            return;
        }
        res++;
        nums[i][j]=-1;
        dfs(i+1,j,m,n,k,nums);
        dfs(i-1,j,m,n,k,nums);
        dfs(i,j-1,m,n,k,nums);
        dfs(i,j+1,m,n,k,nums);


    }

    private static boolean canWalk(int i, int j,int k) {
        String s = String.valueOf(i);
        String s1 = String.valueOf(j);
        StringBuilder builder=new StringBuilder();
        builder.append(s);
        builder.append(s1);
        int add=0;
        String temp=builder.toString();
        for (int l = 0; l <temp.length() ; l++) {
            add+=temp.charAt(l)-'0';
            if(add>k){
                return false;
            }
        }
        return true;
    }
}

解答2

class Solution {
    public int movingCount(int m, int n, int k) {
         int  [][]nums=new int[m][n];
         return  dfs(0,0,m,n,k,nums);  

    }
     private static int dfs(int i,int j,int m, int n, int k,int  [][]nums) {
        if(i<0 || i>=m || j<0 || j>=n ||   (i/10 + i%10 + j/10 + j%10) > k || nums[i][j]==-1){
            return 0;
        }
    
        nums[i][j]=-1;
      return  dfs(i+1,j,m,n,k,nums)+
                dfs(i-1,j,m,n,k,nums)+
                dfs(i,j-1,m,n,k,nums)+
                dfs(i,j+1,m,n,k,nums)+1;
    }   
}

剑指 Offer II 119. 最长连续序列

剑指 Offer II 119. 最长连续序列

难度中等40收藏分享切换为英文接收动态反馈

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 104
• -109 <= nums[i] <= 109

解答

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<=1){
          return nums.length;
        }
         int []dp=new int[nums.length];
         int max=1;
         Arrays.sort(nums);
         dp[0]=1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==nums[i-1]+1){
                dp[i]=dp[i-1]+1;
                max=Math.max(dp[i],max);
            }else if(nums[i]==nums[i-1]){
                dp[i]=dp[i-1];
            }
            else{
                dp[i]=1;
            }
        }
        return max;

    }
}

剑指 Offer II 098. 路径的数目

剑指 Offer II 098. 路径的数目

难度中等24收藏分享切换为英文接收动态反馈

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

解答

// ps  做过很多遍了
class Solution {
    public int uniquePaths(int m, int n) {
        int [][]dp=new int[m][n];
        for (int i = 0; i <m ; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i <n ; i++) {
            dp[0][i]=1;
        }
  
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <n ; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];

    }
}

剑指offerII 099. 最小路径之和

剑指 Offer II 099. 最小路径之和

难度中等26收藏分享切换为英文接收动态反馈

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

解答

class Solution {
    public int minPathSum(int[][] grid) {
        int [][]dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for (int i = 1; i <grid.length ; i++) {
           dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i <grid[0].length ; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i <grid.length ; i++) {
            for (int j = 1; j <grid[0].length ; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];

    }
}

剑指 Offer II 080. 含有 k 个元素的组合

剑指 Offer II 080. 含有 k 个元素的组合

难度中等27收藏分享切换为英文接收动态反馈

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例 1:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

提示:

• 1 <= n <= 20
• 1 <= k <= n

解答

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        int index=1;
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new LinkedList<>();
        backTrack(res,path,index,n,k);
        return res;

    }
     private static void backTrack(List<List<Integer>> res, Deque<Integer> path, int index, int n, int k) {
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i <=n; i++) {
            path.add(i);
            backTrack(res,path,i+1,n,k);
            path.removeLast();
        }
    }
}

剑指 Offer II 081. 允许重复选择元素的组合

剑指 Offer II 081. 允许重复选择元素的组合

难度中等29收藏分享切换为英文接收动态反馈

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

示例 4：

输入: candidates = [1], target = 1
输出: [[1]]

示例 5：

输入: candidates = [1], target = 2
输出: [[1,1]]

解答

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
         List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new LinkedList<>();
        Arrays.sort(candidates);
        int begin=0;
        int sum=0;
        backTrack(res,path,candidates,begin,target,sum);
        return res;

    }
     private static void backTrack(List<List<Integer>> res, Deque<Integer> path, int[] candidates, int begin, int target,int sum) {
          if(sum>target) {
              return;
          }
          if(sum==target){
              res.add(new ArrayList<>(path));
              return;
            }
        for (int i = begin; i <candidates.length ; i++) {
            path.add(candidates[i]);
            backTrack(res,path,candidates,i,target,sum+candidates[i]);
            path.removeLast();
        }
    }
}

剑指 Offer II 082. 含有重复元素集合的组合

剑指 Offer II 082. 含有重复元素集合的组合

难度中等25收藏分享切换为英文接收动态反馈

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

解答

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new LinkedList<>();
        Arrays.sort(candidates);
        boolean []used=new boolean[candidates.length];
        int begin=0;
        int sum=0;
        backTrack(res,path,used,candidates,begin,target,sum);
        return res;

    }

    private static void backTrack(List<List<Integer>> res, Deque<Integer> path,  boolean []used,int[] candidates, int begin, int target, int sum) {
        if(sum>target) {
            return;
        }
        if(sum==target && !res.contains(path)){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i <candidates.length ; i++) {
            if(used[i]){
                continue;
            }
            used[i]=true;
            path.add(candidates[i]);
            backTrack(res,path,used,candidates,i,target,sum+candidates[i]);
            path.removeLast();
            used[i]=false;
        }
    }

}

剑指 Offer II 006. 排序数组中两个数字之和

剑指 Offer II 006. 排序数组中两个数字之和

难度简单43收藏分享切换为英文接收动态反馈

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[0,1]

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 递增顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

解答

class Solution {
    public int[] twoSum(int[] numbers, int target) {
         int []res=new int[2];
      int left=0;
      int right=numbers.length-1;
      int nums1=0,nums2=0;

          while (left<=right){
              nums1=numbers[left];
              nums2=numbers[right];
              if(nums1+nums2==target){
                  res[0]=left;
                  res[1]=right;
                  break;
              }else if(nums1+nums2>target){
                  right--;
              }else{
                  left++;
              }


          }
          return res;

    }
}

剑指 Offer II 091. 粉刷房子

剑指 Offer II 091. 粉刷房子

难度中等124

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]
输出: 2

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

解答

/**

**/
 
class Solution {
    public int minCost(int[][] costs) {
        int [][]dp=new int[costs.length][3];
        dp[0][0]=costs[0][0];
        dp[0][1]=costs[0][1];
        dp[0][2]=costs[0][2];
        for (int i = 1; i <costs.length ; i++) {
            dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i][0];
            dp[i][1]=Math.min(dp[i-1][2],dp[i-1][0])+costs[i][1];
            dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i][2];
        }

        return Math.min(Math.min(dp[costs.length-1][1],dp[costs.length-1][0]),dp[costs.length-1][2]);

    }
}

剑指 Offer II 092. 翻转字符

剑指 Offer II 092. 翻转字符

难度中等42收藏分享切换为英文接收动态反馈

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

解答

class Solution {
    public int minFlipsMonoIncr(String s) {
        // dp[i][0] 表示前i为 为0的最小翻转次数
       // dp[i][1] 表示前i为 为1的最小翻转次数
        int [][]dp=new int[s.length()][2];
        dp[0][0]=s.charAt(0)=='0'? 0:1;
        dp[0][1]=s.charAt(0)=='1'? 0:1;
        for(int i=1;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='0'){
              dp[i][0]=dp[i-1][0];
              dp[i][1]=dp[i-1][1]+1;
            }else{
                //注意  这里要跟dp[i-1][1],dp[i-1][0]比较  因为如果为1的情况下前一位既可以为0 也可以为1  所以获取一个较小的
                dp[i][1]=Math.min(dp[i-1][1],dp[i-1][0]);
                dp[i][0]=dp[i-1][0]+1;
            }
        }

          return Math.min(dp[s.length()-1][1], dp[s.length()-1][0]);
    }
}

剑指 Offer II 073. 狒狒吃香蕉

剑指 Offer II 073. 狒狒吃香蕉

难度中等36收藏分享切换为英文接收动态反馈

狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23

提示：

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

解答

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left=1;
        int max=-1;
        for (int pile : piles) {
            max=Math.max(max,pile);
        }
        int right=max;

        while (left<right){
            int mid=left+(right-left)/2;
            if(calTime(piles,mid)>h){
                left=mid+1;
            }else{
                right=mid;
            }

        }
        return left;

    }

    public static int calTime(int []piles,int mid){
        int res=0;
        for (int i = 0; i <piles.length ; i++) {
            if(piles[i]<=mid){
                res++;
            }else{
                res=res+(piles[i]/mid);
                int temp=piles[i]%mid;
                if(temp!=0){
                    res++;
                }
            }
        }
        return res;

    }
}

剑指 Offer II 066. 单词之和

剑指 Offer II 066. 单词之和

难度中等21收藏分享切换为英文接收动态反馈

实现一个 MapSum 类，支持两个方法，insert 和 sum：

• MapSum() 初始化 MapSum 对象
• void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
• int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

示例：

输入：
inputs = ["MapSum", "insert", "sum", "insert", "sum"]
inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]

解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

提示：

• 1 <= key.length, prefix.length <= 50
• key 和 prefix 仅由小写英文字母组成
• 1 <= val <= 1000
• 最多调用 50 次 insert 和 sum

解答

class MapSum {
    private Map map;

    /** Initialize your data structure here. */
    public MapSum() {
       this.map=new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        Set keySet = map.keySet();
        int len=prefix.length();
        int res=0;
        Iterator iterator = keySet.iterator();
        while (iterator.hasNext()){
            String  next = (String) iterator.next();
             if(next.length()<prefix.length()){
                continue;
            }
            String substring = next.substring(0, len);
            if(substring.equals(prefix)) {
                res = res + (int) map.get(next);
            }
        }
        return  res;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

347 前k个高频元素

剑指 Offer II 060. 出现频率最高的 k 个数字（https://leetcode.cn/problems/g5c51o/）

347. 前 K 个高频元素

难度中等1291收藏分享切换为英文接收动态反馈

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

解答

//小根堆
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int []res=new int[k];
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i <nums.length ; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
        }
        for (int i = 0; i < k ; i++) {
            res[i]=queue.poll().getKey();
        }
        return res;

    }
}

剑指 Offer II 063. 替换单词

剑指 Offer II 063. 替换单词

难度中等25收藏分享切换为英文接收动态反馈

在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"

示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"

解答

//可以使用前缀树
class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] strings = sentence.split(" ");
        StringBuilder builder=new StringBuilder();
        dictionary.sort(new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o1.length()-o2.length();
            }
        });

        for (int i = 0; i < strings.length; i++) {
            for (String s : dictionary) {
                if(strings[i].startsWith(s)){
                    strings[i]=s;

                }
            }
           if(i<strings.length-1) {
                builder.append(strings[i] + " ");
            }else{
                builder.append(strings[i]);
            }
        }

        return builder.toString();

    }
}

剑指 Offer II 062. 实现前缀树

剑指 Offer II 062. 实现前缀树

难度中等29收藏分享切换为英文接收动态反馈

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
inputs = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
inputs = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

解答

class  TrieNode{
    boolean isEnd;
    TrieNode[] next;

    public TrieNode() {
        next = new TrieNode[26];
    }
}

class Trie {

    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root=new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur=root;
        
        for(char ch:word.toCharArray()){
            if(cur.next[ch-'a']==null){
                cur.next[ch-'a']=new TrieNode();
            }
           cur=cur.next[ch-'a'];
        }
        cur.isEnd=true;

    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur=root;
        for(char ch:word.toCharArray()){
            if(cur.next[ch-'a']==null){
                return false;
            }
            cur=cur.next[ch-'a'];
        }
        return cur.isEnd;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur=root;
        for(char ch:prefix.toCharArray()){
            if(cur.next[ch-'a']==null){
                return false;
            }
            cur=cur.next[ch-'a'];
        }
        return true;

    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

剑指offer II 068. 查找插入位置

剑指 Offer II 068. 查找插入位置

难度简单31收藏分享切换为英文接收动态反馈

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

解答

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

        }
        return left;

    }
}

剑指 Offer II 070. 排序数组中只出现一次的数字

剑指 Offer II 070. 排序数组中只出现一次的数字

难度中等40

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

解答

package SwordFingerOffer;

/**
 * 剑指 Offer II 070. 排序数组中只出现一次的数字
 * 给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
 *
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 * 示例 1:
 *
 * 输入: nums = [1,1,2,3,3,4,4,8,8]
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums =  [3,3,7,7,10,11,11]
 * 输出: 10
 */
public class leetcode21 {
    public static void main(String[] args) {
        int []nums=new int[]{1,1,2,3,3,4,4,8,8};
        System.out.println(singleNonDuplicate(nums));

    }
      //异或
    public static int singleNonDuplicate(int[] nums) {
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            res=res ^ nums[i];
        }
        return res;

    }
}

剑指 Offer II 035. 最小时间差

剑指 Offer II 035. 最小时间差

难度中等25收藏分享切换为英文接收动态反馈

给定一个 24 小时制（小时:分钟 **”HH:MM”**）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

• 2 <= timePoints <= 2 * 104
• timePoints[i] 格式为 “HH:MM

解答

 public  int findMinDifference(List<String> timePoints) {
        int []times=new int[timePoints.size()+1];
        int h=0;
        int minutes=0;
        int res=Integer.MAX_VALUE;
        for (int i=0;i<timePoints.size();i++) {
            if(timePoints.get(i).equals("00:00")){
                times[i]=24*60;
                continue;
            }
            String hour = timePoints.get(i).substring(0, 2);
            String min =  timePoints.get(i).substring(3, 5);

            h=Integer.valueOf(hour);
            minutes=Integer.valueOf(min);
            times[i]=h*60+minutes;
        }
        //数组最后添加一个元素  用于判断最小值 与最大值之间差值  比如00:35  和23：59
        times[timePoints.size()]=Integer.MAX_VALUE;
        Arrays.sort(times);
        times[timePoints.size()]=times[0]+24*60;
        for (int i = 1; i < times.length ; i++) {
            res=Math.min(res,times[i]-times[i-1]);
        }
        return res;

    }

剑指 Offer II 103. 最少的硬币数目

剑指 Offer II 103. 最少的硬币数目

难度中等46收藏分享切换为英文接收动态反馈

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

解答

class Solution {
    public int coinChange(int[] coins, int amount) {
        int []dp=new int[amount+1];
        int max=amount+1;
        for (int i = 0; i < dp.length; i++) {
            dp[i]=max;
        }
        dp[0]=0;
        for (int i = 1; i <=amount ; i++) {
            for (int j = 0; j <coins.length ; j++) {
                if(coins[j]<=i ){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }

            }
        }
        return dp[amount] >amount ? -1 : dp[amount];
    }
}

剑指 Offer II 025. 链表中的两数相加

剑指 Offer II 025. 链表中的两数相加

难度中等62收藏分享切换为英文接收动态反馈

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

解答

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> s1=new ArrayDeque<>();
        Deque<Integer> s2=new ArrayDeque<>();
        ListNode n1=l1;
        ListNode n2=l2;
        ListNode res=null;
        while(n1!=null){
            s1.push(n1.val);
            n1=n1.next;
        }
        while(n2!=null){
            s2.push(n2.val);
            n2=n2.next;
        }
        int carry=0;
        while(!s1.isEmpty()||!s2.isEmpty()||carry!=0){
            int num1=s1.isEmpty()?0:s1.pop();
            int num2=s2.isEmpty()?0:s2.pop();
            int cur=num1+num2+carry;
            carry=cur/10;
            cur=cur%10;
            ListNode tmp=new ListNode(cur);
            tmp.next=res;
            res=tmp;
        }
        return res;
    }
}

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer 48. 最长不含重复字符的子字符串

难度中等490

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答

//双指针
class Solution {
    public int lengthOfLongestSubstring(String s) {
     Map<Character,Integer> map=new HashMap<>();
        int i=-1;   //左指针
        int res=0;
        for (int j = 0; j < s.length(); j++) {
            char c=s.charAt(j);
            //如果包含重复元素 就移动左指针位置  左指针位置为 Math.max(i,map.get(c))
            if(map.containsKey(c)){
                i=Math.max(i,map.get(c));
            }
            //更新数据及索引
            map.put(s.charAt(j),j);
           //得出结果
            res=Math.max(res,j-i);
        }
        return res;

    }
}

解答2 滑动窗口

public  int lengthOfLongestSubstring(String s) {
    Set<Character> set=new HashSet<>();
    //记录结果
    int res=0;
    for (int l = 0,r=0; r < s.length();r++) {
        char c = s.charAt(r);
        //如果set集合包含重复的  就让l++  如果l++后 还是包含 就继续remove  比如 p w  时遇到w  首先移除p  然后w依然包含  继续remove w
        while (set.contains(c)){
            set.remove(s.charAt(l++));
        }
        set.add(c);
        res=Math.max(res,r-l+1);

    }
    return res;
}

剑指 Offer 57 - II. 和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列

难度简单473

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

解答

class Solution {
    public int[][] findContinuousSequence(int target) {
         List<int []> res=new ArrayList<>();
        int left=1;
        int right=2;
        while(left < right){
            int temp=(right-left+1)*(left+right)/2;
            if(temp==target){
                int []arr=new int[right-left+1];
                for (int i = 0; i <right-left+1 ; i++) {
                    arr[i]=left+i;
                }
                res.add(arr);
                left++;
            }else if(target> temp){
                right++;
            }else{
                left++;
            }
        }
        return res.toArray(new int[res.size()][]);

    }
}

剑指 Offer 52. 两个链表的第一个公共节点

剑指 Offer 52. 两个链表的第一个公共节点

难度简单546

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          Set<ListNode> set=new HashSet<>();
        while(headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while(headB!=null){
            if(set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
        
    }
}

剑指 Offer II 020. 回文子字符串的个数

剑指 Offer II 020. 回文子字符串的个数

难度中等64

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解答

class Solution {
    public int countSubstrings(String s) {
        if(s.length()==1){
            return 1;
        }
      //dp[i][j] 表示从i到j 构成的子串是否回文
        boolean [][]dp=new boolean[s.length()][s.length()];
        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = i; j < s.length() ; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }else{
                    dp[i][j]=false;
                }
            }
        }

        int res=0;
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length ;j++) {
                if(dp[i][j]){
                    res++;
                }
            }
        }
        return res;

    }
}

剑指 Offer II 007. 数组中和为 0 的三个数

剑指 Offer II 007. 数组中和为 0 的三个数

难度中等78收藏分享切换为英文接收动态反馈

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

解答

//回溯  超时了
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if(nums.length<3){
            return res;
        }
        Arrays.sort(nums);
        List<Integer> path=new ArrayList<>();
        dfs(res,path,0,nums);

        return res;

    }
      

    private static void dfs(List<List<Integer>> res,List<Integer> path, int index, int[] nums) {
        if(path.size()==3){
            if(getSum(path)==0) {
                res.add(new ArrayList<>(path));
                return;
            }else{
                return;
            }
        }
        for (int i = index; i < nums.length ; i++) {
            if(i>index && nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            dfs(res,path,i+1,nums);
            path.remove(path.size()-1);
        }

    }

    public static  int getSum(List<Integer> path){
        int res=0;
        for (Integer integer : path) {
            res+=integer;
        }
        return res;
    }

}

解答2 排序加双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        if(nums.length<3){
            return res;
        }
        for (int i = 0; i <nums.length; i++) {
            if(i>=1 &&  nums[i]==nums[i-1]){
                continue;
            }
            int target=-nums[i];
            int third=nums.length-1;

            for (int j = i+1; j <nums.length ; j++) {
                if(j > i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                while(j<third && nums[j]+nums[third] >target){
                    --third;
                }
                if(third==j){
                    break;
                }

                if(nums[j]+nums[third]==target){
                    List<Integer> path=new ArrayList<>();
                    path.add(nums[i]);
                    path.add(nums[j]);
                    path.add(nums[third]);
                    res.add(path);

                }

            }
        }
        return res;
    }

}

剑指 Offer 63. 股票的最大利润

剑指 Offer 63. 股票的最大利润

难度中等282

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 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。

解答

class Solution {
    public int maxProfit(int[] prices) {
       if(prices.length==1){
            return 0;
        }
        int res=0;
        int lowPrice=Integer.MAX_VALUE;
        for (int i = 1; i <prices.length ; i++) {
            lowPrice=Math.min(lowPrice,prices[i-1]);
            res=Math.max(res,prices[i]-lowPrice);
        }
        return res;
    
    }
}

剑指Offer 61.扑克牌中的顺子

剑指 Offer 61. 扑克牌中的顺子

难度简单269

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

解答

class Solution {
    public boolean isStraight(int[] nums) {
       int ZeroNumber=0;  //记录大小王数目
        Arrays.sort(nums);
        for (int i = 0; i < 4; i++) {
            if(nums[i]==0){
                ZeroNumber++;
            }else  if(nums[i]==nums[i+1]){
                return  false;
            }
        }
        return nums[4]-nums[ZeroNumber]<5;
    }
}

剑指 Offer II 011. 0 和 1 个数相同的子数组

剑指 Offer II 011. 0 和 1 个数相同的子数组

难度中等94

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

解答

class Solution {
    public int findMaxLength(int[] nums) {
          for (int i = 0; i < nums.length; i++) {
            if(nums[i]==0){
                nums[i]=-1;
            }
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,-1);
        int maxLen=0,sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            if(map.containsKey(sum)){
                maxLen=Math.max(maxLen,i-map.get(sum));
            }else{
                map.put(sum,i);
            }

        }
        return maxLen;

    }
}

剑指 Offer II 014. 字符串中的变位词

剑指 Offer II 014. 字符串中的变位词

难度中等61

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

解答

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        for (int i = 0; i <=s2.length()-s1.length() ; i++) {
            String substring = s2.substring(i, i + s1.length());
            if(isSame(substring,s1)){
                return true;
            }
        }
        return false;

    }
     private static boolean isSame(String substring,String s1) {
        int []count=new int[26];
        for (int i = 0; i <s1.length() ; i++) {
            count[s1.charAt(i)-'a']++;
        }
        for (int i = 0; i <substring.length() ; i++) {
            count[substring.charAt(i)-'a']--;
        }
        for (int i = 0; i < count.length; i++) {
            if(count[i]!=0){
                return false;
            }
        }
        return true;

    }
}