每日力扣1

【前言】：写给无意中点进来的你

（主要是因为博客好久没更新了，打算重新利用起来）代码有一部分是借鉴评论区和官方题解的，所以在力扣写题解就难免不太合适，然而记笔记的需求是确切存在的，博客的tag查找也很方便，就打算在博客写笔记了，也方便我快速回忆起知识点省得再去CSDN（垃圾堆）里找，尽量每日一更，之前积攒下来的题也会慢慢加更上来。

今日题目

雇佣K名工人的最低成本
计算右侧小于当前元素的个数
分割回文串
单词搜索II
修剪二叉搜索树

---

雇佣K名工人的最低成本（优先级队列，lambda排序）

题目链接
这道题的核心在于根据什么去挑工人。我们定义“价性比”=期望工资/工作量，即每单位工作量对应的工资。
我们再看题目的两个关键要求：
1.工资要按工作量占比分配
2.每个工人得到的工资应大于等于其期望工资
我们将所有工人按价性比从低往高排列，如果按第k个人的价性比付工资，则能满足以上两个条件。
那么如何满足成本最低呢？
我们易知成本=价性比*工作总量，如果成本要最低的，那么工作总量也要尽量小。我们使用优先级队列，先将前k-1个人的工作量入队，从第k个人开始，我们将当前遍历到的工人的工作量加入k-1个工人的工作量中得到总工作量，再乘以当前工人对应的效费比，将结果与最小值进行比较以更新结果，最后返回。
来看代码：

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k) {//雇佣K名工人的最低成本
         int l = quality.Length;
         int[] q = new int[l];
         double res =1e9,totalq=0.0;
         for(int i = 0;i<l;i++){//这个数组是用来存储按效费比排列后工人的序号，以获取对应工作量和工资
             q[i]=i;
         }
         Array.Sort(q,(a,b)=>{return wage[a]*quality[b]-wage[b]*quality[a];});//将数组通过lambda表达式按升序排列，前者比后者大则调转，即升序
         PriorityQueue<int,int> PQ = new PriorityQueue<int,int>();//通过优先级队列实现最大堆，优先级队列中维护的是最小的k个工作量
         for(int i =0;i<k-1;i++){//先获取前k-1个工人的工作量之和，并将他们的工作量入队
             totalq+=quality[q[i]];
             PQ.Enqueue(quality[q[i]],-quality[q[i]]);//C#的最大堆优先级是根据第二个参数的大小升序排列的，要想让工作量从大到小排，就让工作量的相反数从小到大排
         }      
         for(int i =k-1;i<l;i++){
             totalq+=quality[q[i]];//得到当前k个工人的工作量
             double cur = ((double)wage[q[i]]/quality[q[i]])*totalq;//得到结果
             res = Math.Min(res,cur);//取较小值
             PQ.Enqueue(quality[q[i]],-quality[q[i]]);//将当前工人的工作量入队进行比较
             totalq-=PQ.Dequeue(); //将最大的工作量出队，此时totalq是最小的k-1个工作量之和  
         }
         return res;
    }
}

---

计算右侧小于当前元素的个数（二分查找）

题目链接
从右往左遍历数组，单独用一个List存入，每次存入前先通过二分查找获取该数在List中的位置（按升序排列），设该类数的最小索引为k，即有k个数在该数右侧且比该数小。
由于是从右往左遍历数组，每次遍历得到的结果也是从右往左加入作为结果的List，故需要对List进行翻转后再返回。
来看代码：

public class Solution {
    public IList<int> CountSmaller(int[] nums) {//计算右侧小于当前元素的个数-二分查找
          IList<int> res = new List<int>();
          List<int> sortedList = new List<int>();
          int[] resTemp = new int[nums.Length];
          for(int i = nums.Length-1;i>-1;i--){
              int location = bFind(sortedList,nums[i]);
              resTemp[i]=location;
              sortedList.Insert(location,nums[i]);
          }
        res = resTemp.ToList();
        return res;
    }
    public int bFind(List<int> sortedList,int num){
        if(sortedList.Count==0)
            return 0;
        int left = 0,right = sortedList.Count-1;
        while(left<=right){
            int mid = (left+right)>>1;
            if(num>sortedList[mid]){
                left=mid+1;
             }else{
                right = mid-1;
                //num=sortedList[mid]或num<sortedList[mid]都得right=mid-1，后者的原因显而易见，而前者的原因是这道题要求的是当前元素右侧小于（划重点）该元素的元素个数，如果是小于等于则可直接返回mid，但为了排除相等的元素，我们则要去找这段连续的相同数字的左边界
            }
        }
        return left;
    }
    // public void Reverse(IList<int> res){//由于力扣的C#版本中Reverse存在问题，然而重写Reverse会导致超时，最后用数组和ToList方法取代。
    //     Stack<int> stack = new Stack<int>();
    //     int l  = res.Count;
    //     for(int i  = 0;i<l;i++){
    //         stack.Push(res[0]);
    //         res.RemoveAt(0);
    //     }
    //     for(int i = 0;i<l;i++){
    //         res.Add(stack.Pop());
    //     }
    //     return ;
    // }
}

---

分割回文串（回溯、DFS）

题目链接
题目的要求是返回一个List，List里是这个字符串分成多个回文串组合的所有分法。这是一个考察枚举的题
我们先用一个bool类型的二维数组record记录i和j为左右端点的回文串是否存在，如果存在即为true，类似于动态规划，我们通过上一个回文串来判断当前的子串是否是回文串
设字符串为s,i为左端点，j为右端点，则record[i,j]的递推式如下：
record[i,j]= i>=j? true: (record[i+1,j-1]==true&&s[i]==s[j]?true:false) 意会，不严谨，首先判断i是否大于等于j，即当前串是否为空串或长度为1的串，如果不是，则需要查询该子串的上一个状态s[i+1]-s是否是回文串，如果是回文串且当前指向的两个字符相等，才返回为true。
通过以上步骤，我们获取了字符串所有的回文串，接下来解决怎么分的问题。
由于是枚举，我们可以通过DFS+回溯的方式来枚举。设一个指针i，0~i的子串被枚举完了，又设一个指针j，j在i和最后一个字符间枚举当前分法的下一个回文子串两端，i再指向j。
来看代码：

public class Solution {
    bool[,] record;
    int l ;
    IList<IList<string>> res = new List<IList<string>>();
    IList<string> ans = new List<string>();
    public IList<IList<string>> Partition(string s) {//分割回文串
            l = s.Length;
           record = new bool[l,l];
           for(int i =0;i<l;i++){
               for(int j = 0;j<l;j++){
                   record[i,j]=true;
               }
           }
           for(int i = l-1;i>-1;--i){
               for(int j = i+1;j<l;j++){
                   record[i,j]=(s[i]==s[j]&&record[i+1,j-1]);
               }
           }
           DFS(s,0);
           return res;
    }
    public void DFS(string s,int i){
        if(i==l){
           res.Add(new List<string>(ans));
           return;
        }
        for(int j = i;j<l;j++){
            if(record[i,j]){
                ans.Add(s.Substring(i,j-i+1));
                DFS(s,j+1);
                ans.RemoveAt(ans.Count-1);
            }
        }
    }
}

---

单词搜索II（字典树，回溯）

题目链接
字典树是一种用于快速查找单词的数据结构，它基于字典实现，每个结点的孩子结点值（即字符）和所属字典树的对应关系都用字典存储。将单词插入到字典树中的步骤是遍历单词的字符，若当前字典树/字典子树不存在与该字符相等的键（即不存在以当前字符为首字母的单词），则将该字符与新字典树组成的键值对加入字典，当遍历到当前单词的最后一个字符时，将该单词存入字典树结点的word属性。在遍历时，我们以board中的每个格为起点做DFS，在该格子对应的DFS结束后进行回溯，再以下一个格子为起点进行DFS。查找时，若当前字典树结点为叶结点或不匹配（字典不存在当前字符对应的键，当前字符不在路径上）则返回，若存在对应键且该键对应的值（字典树）的word属性为单词，说明找到了一个单词，将单词存入ISet，ISet是C#提供的用于集的抽象的基接口，用HashSet实现时，其Add方法保证最后结果的元素互不相同，使用ISet存储结果完美避免了重复的问题。
来看代码：

public class Solution {
    int[][] direction = new int[][]{
        new int[]{1,0},
        new int[]{-1,0},
        new int[]{0,-1},
        new int[]{0,1}
    };
    public IList<string> FindWords(char[][] board, string[] words) {//单词搜索II
           Trie trie = new Trie();
           foreach(string word in words){//构造字典树
               trie.Insert(word);
           }
           ISet<string> ans = new HashSet<string>();//用于集的抽象基接口ISet，可以用HashSet或SortedSet实现
           //使用HashSet的一个重要原因是HashSet中的元素互不相同，和哈希表类似（键互不相同）
           for(int i = 0;i<board.Length;i++){
               for(int j = 0;j<board[0].Length;j++){
                   DFS(board,trie,i,j,ans);
               }
           }
        return new List<string>(ans);
    }
    public void DFS(char[][] board,Trie now,int i1,int j1, ISet<string> ans){
        if(!now.children.ContainsKey(board[i1][j1])){
            return;//没有以当前字母为前缀的单词、当前结点为叶结点或不匹配
        }
        char ch = board[i1][j1];
        now=now.children[ch];
        if(!"".Equals(now.word)){//如果词不为空
            ans.Add(now.word);//这里不return的原因是可能存在以当前词为前缀的词语
        }
        board[i1][j1]='#';
        foreach(int[] dir in direction){
            int i2=i1+dir[0],j2=j1+dir[1];
            if(i2>=0&&i2<board.Length&&j2>=0&&j2<board[0].Length){
               DFS(board,now,i2,j2,ans);
            }
        }
        board[i1][j1]=ch;
    }
}
public class Trie{//字典树模板
    public string word;
    public Dictionary<char,Trie> children;
    public Trie(){
        this.word = "";
        this.children = new Dictionary<char,Trie>();
    }
    public void Insert(string word){
        Trie cur = this;
        foreach(char c in word){
            if(!cur.children.ContainsKey(c)){
                cur.children.Add(c,new Trie());
            }
            cur = cur.children[c];
        }
        cur.word=word;//当遍历结束时，cur指向的是以单词最后一个字母为根结点的字典树，让该字典树的word等于存入的word，当DFS遍历到该结点时，如果该结点的word为单词，就说明找到了这个词
    }
}

ISet C#文档链接
HashSet C#文档链接
SortedSet C#文档链接

---

修剪二叉搜索树（二叉树、前序遍历、递归）

题目链接
对出范围的结点做如下处理：
结束递归条件：结点为空
出左边界：返回遍历其右子树的结果
出右边界：返回遍历其左子树的结果
对在范围内的结点，对其左右子树均进行同样的遍历
来看代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode TrimBST(TreeNode root, int low, int high) {//修剪二叉搜索树
          if(root==null)
             return root;
          if(root.val<low)//如果当前结点出左边界，就在该结点的右子树去找
             return TrimBST(root.right,low,high);
          if(root.val>high)//如果当前结点出右边界，就在该结点的左子树去找
             return TrimBST(root.left,low,high);//处理正常的结点
          root.left=TrimBST(root.left,low,high);
          root.right=TrimBST(root.right,low,high);
          return root;
    }
}

Donate