每日力扣2

今日题目

最大交换
课程表I
二叉树最近公共祖先
二叉树中的最大路径和
删除无效的括号

---

最大交换(lambda排序)

题目链接
思路是将整数先通过ToString转换为string，再通过ToCharArray转换为可以进行单数位交换操作的字符数组ans，借助lambda表达式和Array.Sort对其进行降序排列得到temp，再与原数字进行逐位比较，找到第一个不相等的位置i，由于需要返回一次转换能产生的最大值，故要在后面的数位里去找值为temp[i]的最小一位，得到该位置后进行转换，最后将ans通过string的构造方法的重载转换为string，再由int.Parse()转换为最终值。
来看代码：

public class Solution {
    public int MaximumSwap(int num) {//最大交换
        if(num<=9)
           return num;
        string s = num.ToString();
        char[] temp = s.ToCharArray();
        char[] ans = s.ToCharArray();
        int res = 0;
        Array.Sort(temp,(a,b)=>{return b-a;});
        for(int i = 0;i<temp.Length;i++){//temp将所有数字降序排列，s存储的是原数字
            if(temp[i]!=ans[i]){
                int lastlocation = i+1;
                for(int j = i+1;j<temp.Length;j++){
                     if(ans[j]==temp[i]){
                         lastlocation=j;
                     }
                }
                ans[lastlocation]=ans[i];
                ans[i]=temp[i];
                break;
            }
        }
        string s2=new string(ans);
        res = int.Parse(s2);
        return res;
    }
}

---

课程表I（有向图生成、环检测、回溯、DFS）

题目链接
该题要求验证是否能找到一个排课顺序，按照这个顺序，所有课在开课前都能修完需要提前修的课程，那么，我们根据这种前趋关系建立一个有向图，只用检查有向图中是否存在环即可，如果存在环，说明不存在该顺序。对于出度为0的点，其顺序可任意安排，故不影响结果。
我们首先建立存储有向图各结点有向边信息的List类型数组graph，对其进行初始化遍历存储前趋关系的交错数组prerequisites，prerequisites[i][0]为有向边终点，prerequisites[i][1]为起点，按照prerequisites[i][1]找到graph对应List将有向边终点存入，完成图的建立。
对于环的检测，我们使用！bool类型数组onPath[] 和visited[]，前者用于判断当前检查的路径是否存在环（即该点是否已经存在于路径上）如果存在环， onPath[0]就置为true，后者用于记录已经在其他路径上遍历过的结点，防止超时（比如“灯笼”型有向图，多个路径指向同一个结点，而这个结点在DFS中已经被在第一条路径中注册了，到遍历其他路径时就不必重复，然而这种情况又要和onPath区分开，不能被误认为环）。以当前结点出发的子路径均检查完毕后，按照回溯，应当将当前结点的onPath置回false，再进行其他路径的检查
来看代码：

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {//课程表：有向图的环检测
          List<int>[] graph = BuildGraph(numCourses,prerequisites);//课程总数，课程对
          bool[] visited = new bool[numCourses];
          bool[] onPath = new bool[numCourses+1];
          for(int i = 0;i<numCourses;i++){
              DFS(graph,i,visited,onPath);
          }
          return !onPath[0];//onPath[0]记录是否有环，有就是false，没有就是true，所以要置反
    }
    public List<int>[] BuildGraph(int numCourses,int[][] prerequisites){
        List<int>[] graph = new List<int>[numCourses];//用List<int>数组建立图，每个List都存着从该点出发的下一个点
        for(int i = 0;i<numCourses;i++){
            graph[i] = new List<int>();
        }
        for(int i = 0;i<prerequisites.Length;i++){
            int from =prerequisites[i][1];//先修课程为有向边起点，课程为有向边终点
            int to = prerequisites[i][0];
            graph[from].Add(to);
        }
        return graph;//graph
    }
    public void DFS(List<int>[] graph,int s,bool[] visited,bool[] onPath){
        if(onPath[s+1]){//如果这个地方已经在路径上了，说明有环
              onPath[0]=true;
        }
        if(visited[s]||onPath[0]){//如果已经访问过了（由于是DFS，所以可能这个结点已经在已知的路径里了）或者已经证明有环了，那就返回。onPath判断在后用时最短（因为能通过的例子里onPath都是负，还要再判断visited[s]是不是true）
            return;
        }
        visited[s]=true;
        onPath[s+1]=true;
        List<int> temp=graph[s];
        for(int i = 0;i < temp.Count;i++){
            DFS(graph,temp[i],visited,onPath);
        }
        onPath[s+1]=false;//这个回溯至关重要，如果没有这个回溯，就会出现因为visied[s]==true（即在前面遍历过）而导致onPath[0]=true
    }
}

---

二叉树的最近公共祖先（二叉树、DFS）

题目链接
这道题的一个重要条件就是两个值均在二叉树中，所以对于p和q而言，只会有以下三种情况：
p和q都不是对方的最近公共祖先
p或q是最近公共祖先（两种）
如果遇到p或q，直接返回该结点，若其他子树返回的是null（即到了叶结点也没找到p或q，那就只能在返回不为null的子树里），就说明该结点是最近公共祖先
如果p和q分别在该结点的左右子树找到了（返回不为null），就说明当前结点是最近公共祖先，返回该结点
如果p和q都没找到，自己也不是p或q，就返回null
来看代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//二叉树最近公共祖先
        if(root==q||root==p||root==null)
         return root;
        TreeNode left=LowestCommonAncestor(root.left,p,q);
        TreeNode right=LowestCommonAncestor(root.right,p,q);
        TreeNode res=new TreeNode();
        if(left==null&&right==null){
            res= null;
        }else if(left!=null&&right!=null){
            res= root;
        }else if(left!=null&&right==null){
            res= left;
        }else if(right!=null&&left==null){
            res= right;
        }
        return res;
    }
}

---

二叉树中的最大路径和（二叉树，DFS）

题目链接
这种情况适合DFS，从叶结点开始向祖先结点返回其子树的最大路径和，同时每个结点应先比较以下四个值，取最大值：
当前最大值
左右子树最大路径和较大者+自身值
自身值
自身值+左右子树的最大路径
向上返回时，比较自身值和自身+左右子树最大路径和较大者，返回较大的。
来看代码：

/**
 * 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 {
private int res = Int32.MinValue;
    public int MaxPathSum(TreeNode root) {//二叉树中的最大路径和
        DFS(root);
        return res;
    }
    public int DFS(TreeNode root){//算是DFS吧，前序遍历
        if(root==null)
           return 0;
        int left = DFS(root.left);
        int right = DFS(root.right);
        int max = Math.Max(left,right);
        int[] arr = {res,root.val+left+right,root.val,root.val+max};
        Array.Sort(arr);
        res = arr[3]; //将当前最大值、当前子树和、根值、根与最大子路径和进行比较
        return Math.Max(root.val,root.val+max);//要么返回根结点，要么返回根结点与最大子路径和
    }
}

---

删除无效的括号（BFS）

题目链接
我们使用HashSet来存储每层进行删除一个括号后所产生的所有结果以避免重复，针对相连左右括号和字符串首的括号进行删除操作。由于题目要求返回删除次数最小的有效字符串，故一旦当前步数（层数）产生了有效字符串（HashSet.Count>0)，就返回结果。
检查当前字符串是否有效的逻辑是遍历该字符串，记录需要右括号的左括号个数，若左括号小于0则说明当前字符串无效，若遍历后左括号个数大于0说明缺少右括号，即当前字符串无效。
来看代码：

public class Solution {
    public IList<string> RemoveInvalidParentheses(string s) {//删除无效的括号-BFS
         List<string> res = new List<string>();
         ISet<string> cur = new HashSet<string>();
         cur.Add(s);
         while(true){
            foreach(string str in cur){
                if(IsValid(str)){
                    res.Add(str);
                }
            }
            if(res.Count>0){
                return res;
            }
             ISet<string> next = new HashSet<string>();
            foreach(string str in cur){
                for(int i = 0;i<str.Length;i++){
                    if(i>0&&str[i]==str[i-1]){
                        continue;
                    }if(str[i]=='('||str[i]==')')
                       next.Add(str.Substring(0,i)+str.Substring(i+1)); //SubString的两种重载用法：前者返回以0位起点的i长度子串，后者截取以i+1为起点的字符串剩余部分，这两个重载结合起来的用法就是生成删除了当前位字符的字符串。             
                }
            }
            cur = next;
         }
    }
    public bool IsValid(string s){
        int left=0;
        for(int i = 0;i<s.Length;i++){
             if(s[i]=='('){
                  left++;
             }else if(s[i]==')'){
                 left--;
             }
             if(left<0)
                return false;
         }
         return left==0;
    }
}

Donate