本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。

前言

今天早上可能是浏览器出了点故障，一直没法打开力扣官网页面（但别的页面没问题）（别人都能进说明不是官网服务器的问题咯），错过了周赛（不过就算按时参加估计也是陪跑，就先这么安慰自己了），下午发现能进去了，赶紧找个时间补了一下题。

题目、代码、思路

找出中枢整数

给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

• 1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。

返回中枢整数 **x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

思路：
这个可以利用数学公式：对连续自然数a1到an相加的和=(a1+an)*项数n/2

对题目进行变形可得：(1+x)x=(x+n)(n-x+1)

代码如下：

class Solution {
    public int pivotInteger(int n) {
        for(int x=1;x<=n;x++){
            if((1+x)*x==(x+n)*(n-x+1)) return x;
        }
        return -1;
    }
}

追加字符以获得子序列

给你两个仅由小写英文字母组成的字符串  s 和  t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

思路：这是一个很典型的双指针问题，指针i j同时开始遍历s和t，i走得快些，j走得慢些，最后j停住不动了，剩下它走不完的就是要在s末尾补上去的字符。

class Solution {
    public int appendCharacters(String s, String t) {
        int cnt=0;
        int n=s.length(),m=t.length();
        int i=0,j=0;
        while(i<n&&j<m){
            if(s.charAt(i)==t.charAt(j)){
                i++;
                j++;
            }
            else i++;
        }
        cnt=m-j;
        return cnt;
    }
}

从链表中移除结点

给你一个链表的头节点  head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。

返回修改后链表的头节点 head 。

思路：这一题和传统的删除链表不一样的是：它移除的是当前的结点。

以往做的删除结点的常规思路都是：找到待删除结点的前一个结点，然后通过pre.next=pre.next.next的方式跳过当前结点。

这里题意变了，做法也相应变了。

可以采用递归的思路。注意三点：

• 递归结束条件：

if(head==null) return null;

• 如果选择不删除当前结点，也得把它的后续再接上一遍：
  head.next=nxt;
  因为有可能在前面递归时head后面的部分已经丢失了。

完整代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        if(head==null) return null;
        ListNode nxt=removeNodes(head.next);
        if(nxt!=null&&head.val<nxt.val){
            return nxt;
        }
        else{
            head.next=nxt;
            return head;
        }
    }
}

• 一点题外话：昨天做到了另外一道变形题，不提供头结点，要求你删除当前给定的结点。

6247 删除链表中的结点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

这道题的思路很有意思：如果想要A从世界上消失，只需要让它顶替B的位置：

class Solution {
    public void deleteNode(ListNode node) {
        int val=node.next.val;
        node.val=val;
        node.next=node.next.next;
    }
}

个人感觉这两题值得放在一起对比一下，别搞混了。

最后补一道今天做的打卡题，难度hard，个人感觉挺有意思，也较有实际意义

1203 项目管理

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

• 同一小组的项目，排序后在列表中彼此相邻。
• 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

思路解析已经很详细地体现在代码注释中了，这里就不多赘述了。

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        //数据预处理，给没有组号的编上新组号，免得后续全挤在一起
        for(int i=0;i<group.length;i++){
            if(group[i]==-1){
                group[i]=m;
                m++;
            }
        }

        //构建组和项目的邻接表
        List<Integer> [] itemList=new List [n];
        List<Integer> [] groupList=new List [m];
        for(int i=0;i<n;i++){
            itemList[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            groupList[i]=new ArrayList<>();
        }

        //建图 统计入度
        int [] itemDegree=new int [n];
        int [] groupDegree=new int [m];

        for(int i=0;i<group.length;i++){
            int curgroup=group[i];
            for(int preitem:beforeItems.get(i)){
                int pregroup=group[preitem];
                if(curgroup!=pregroup){
                    groupList[pregroup].add(curgroup);
                    groupDegree[curgroup]++;
                }
            }
        }

        for(int i=0;i<n;i++){
            for(int pre:beforeItems.get(i)){
                itemList[pre].add(i);
                itemDegree[i]++;
            }
        }

        //得到拓扑排序结果
        List<Integer> tuopuitem=tuopuSort(itemList,itemDegree,n);
        List<Integer> tuopugroup=tuopuSort(groupList,groupDegree,m);
        if(tuopuitem.size()==0||tuopugroup.size()==0) return new int [0];

        //建立组到项目的一对多关系
        Map<Integer,List<Integer>> groupToitems=new HashMap<>();
        for(Integer item:tuopuitem){
            groupToitems.computeIfAbsent(group[item],key->new ArrayList<>()).add(item);
        }

        //组的拓扑结构->项目的拓扑结构
        List<Integer> res=new ArrayList<>();
        for(Integer id:tuopugroup){
            List<Integer> items=groupToitems.getOrDefault(id,new ArrayList<>());
            res.addAll(items);
        }
        int len=res.size();
        int [] ans=new int [len];
        for(int i=0;i<len;i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

    public List<Integer> tuopuSort(List<Integer> [] list,int [] degree,int len){
        List<Integer> res=new ArrayList<>();
        //拓扑排序，使用队列做
        Queue<Integer> queue=new LinkedList<>();
        //将所有没有前驱结点的结点入队（入度为0）
        for(int i=0;i<len;i++){
            if(degree[i]==0) queue.offer(i);
        }

        /** 算法核心：
        将没有前驱节点的结点逐个出队并添加至结果中;
        逐个遍历这些节点的后继节点，并且标记已访问（取消它的度）
        当它没有入度时也将其归入没有前驱结点的阵列（入队）
        */
        while(!queue.isEmpty()){
            int top=queue.poll();
            res.add(top);
            for(int nxt:list[top]){
                degree[nxt]--;
                if(degree[nxt]==0){
                    queue.offer(nxt);
                }
            }
        }
        return res.size()==len?res:new ArrayList<>();
    }
}

以上就是本文的全部内容啦！喜欢的小伙伴们欢迎点个赞再走哦！