[LeetCode周赛]第 270 场周赛

一.介绍

  周赛链接: LeetCode第270场周赛
  结果这样,还算可以接受

  A了三题,还算OK,但是第三题做的真的太烂了,这题做了半个小时是我没想到的,第四题可惜了.第一题的罚时……,无话可说,赛前十分钟才起床,脑子还不大清醒,做题还是再细心点吧.

二.分析

2.1 找出3位偶数(Easy)

  题目链接: LeetCode-5942

题目内容:
	给你一个整数数组 digits ,其中每个元素是一个数字(0 - 9)。数组中可能存在重复元素。
	你需要找出 所有 满足下述条件且 互不相同 的整数:
	该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
		-该整数不含 前导零
		-该整数是一个 偶数
	例如,给定的 digits 是 [1, 2, 3] ,整数 132 和 312 满足上面列出的全部条件。
	将找出的所有互不相同的整数按递增顺序排列,并以数组形式返回。


示例:
	输入:digits = [2,1,3,0]
	输出:[102,120,130,132,210,230,302,310,312,320]
	解释:
		所有满足题目条件的整数都在输出数组中列出。
		注意,答案数组中不含有 奇数 或带 前导零 的整数。

提示:
	3 <= digits.length <= 100
	0 <= digits[i] <= 9

  我的解答如下:

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        Set<Integer> set=new HashSet<>();
        int n=digits.length;
        for(int i=0;i<n;i++)
        {
            if(digits[i]==0) continue;
            for(int j=0;j<n;j++)
            {
                if(j==i) continue;
                for(int k=0;k<n;k++)
                {
                    if(k==i||k==j) continue;
                    if(digits[k]%2==0)
						set.add(100*digits[i]+10*digits[j]+digits[k]);
                }
            }
        }
        if(set.size()==0) return new int[]{};
        int[]res=new int[set.size()];
        int index=0;
        for(int num:set)
            res[index++]=num;
        Arrays.sort(res);
        return res;
    }
}

  简单题没啥好说的,数组长100,因此最暴力的方法也ok,这个题为啥被罚时了呢,因为我没看到递增返回结果……挺无语的
  此种解法,时间复杂度为O(n3),空间复杂度为O(1)(不计算答案所用空间)
  本题也可以用数组存储每个数字个数,遍历100-999即可,代码如下:

class Solution
{
    public int[] findEvenNumbers(int[] digits)
    {
        int [] digit_freq = new int [10];
        for (int x : digits)
        {
            digit_freq[x] ++;
        }

        List<Integer> nums = new ArrayList<>();
        for (int num = 100; num < 1000; num += 2)
        {
            int [] cur_digit_freq = new int [10];
            boolean ok = true;
            int x = num;
			//除法统计每位数个数
            while (x > 0)
            {
                int cur = x % 10;
                cur_digit_freq[cur] ++;
                if (cur_digit_freq[cur] > digit_freq[cur]) ok = false;
                x /= 10;
            }
            if (ok) nums.add(num);
        }
        int len = nums.size();
        int [] res = new int [len];
        for (int i = 0; i < len; i ++)
        {
            res[i] = nums.get(i);
        }
        return res;
    }
}

2.2 删除链表的中间节点(Medium)

  题目链接: LeetCode-5943

题目内容:
	给你一个链表的头节点 head 。删除链表的中间节点,并返回修改后的链表的头节点head。
	长度为n链表的中间节点是从头数起第⌊n / 2⌋个节点(下标从0开始),
	其中 ⌊x⌋ 表示小于或等于x的最大整数。
	对于 n = 1、2、3、4 和 5 的情况,中间节点的下标分别是 0、1、1、2 和 2


示例:
	输入:head = [1,3,4,7,1,2,6]
	输出:[1,3,4,1,2,6]
	解释:
		上图表示给出的链表。节点的下标分别标注在每个节点的下方。
		由于 n = 7 ,值为 7 的节点 3 是中间节点,用红色标注。
		返回结果为移除节点后的新链表。


提示:
	链表中节点的数目在范围 [1, 105] 内
	1 <= Node.val <= 10^5

  我的解答如下:

/**
 * 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 {
	//获得链表长度
    int getlen(ListNode head)
    {
        if(head==null) return 0;
        int res=0;
        while(head!=null)
        {
            res++;
            head=head.next;
        }
        return res;
    }
    public ListNode deleteMiddle(ListNode head) {
        int len=getlen(head);
        if(len==1) return null;
        int index=0;
        ListNode p=head,q=head.next;
        while(index<len/2-1)
        {
            p=p.next;
            q=q.next;
            index++;
        }
        p.next=q.next;
        return head;
    }
}

  这应该算是中等里最简单的题了吧,竞赛的时候本着最快的方法,就直接两遍遍历实现了,没什么好说的
  时间复杂度为O(n),空间复杂度为O(1)
  当然这题用快慢指针可以只遍历一次,代码如下:

class Solution {
   public ListNode deleteMiddle(ListNode head) {
		if(head.next==null) return null;
		ListNode slow=head;
		ListNode fast=head;
		//寻找要删除的结点
		while (fast!=null && fast.next!=null) {
			slow=slow.next;
			fast=fast.next;
            //System.out.println(slow.val);
			if(fast!=null){
                fast=fast.next;
            }
		}
		//删除结点,直接让删除结点的前一个结点的next指向删除结点的next
		ListNode cur=head;
		while (cur.next!=slow) {
			cur=cur.next;
		}
		cur.next=slow.next;
		return head;
    }
}

  时间复杂度为O(n),空间复杂度为O(1)

2.3 从二叉树一个节点到另一个节点每一步的方向(Medium)

  题目链接: LeetCode-5944

题目内容:
	给你一棵 二叉树 的根节点 root ,这棵二叉树总共有 n 个节点。
	每个节点的值为 1 到 n 中的一个整数,且互不相同。
	给你一个整数 startValue ,表示起点节点 s 的值,
	和另一个不同的整数 destValue ,表示终点节点 t 的值。

	请找到从节点 s 到节点 t 的 最短路径 ,并以字符串的形式返回每一步的方向。
	每一步用 大写 字母 'L' ,'R' 和 'U' 分别表示一种方向:

	'L' 表示从一个节点前往它的 左孩子 节点。
	'R' 表示从一个节点前往它的 右孩子 节点。
	'U' 表示从一个节点前往它的 父 节点。
	请你返回从 s 到 t 最短路径 每一步的方向。

示例:
	输入:root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
				5
			  /   \
			1		2
		  /		   /  \
		3		  6	   4
	输出:"UURL"
	解释:最短路径为:3 → 1 → 5 → 2 → 6 。

提示:
	树中节点数目为 n 。
	2 <= n <= 10^5
	1 <= Node.val <= n
	树中所有节点的值 互不相同 。
	1 <= startValue, destValue <= n
	startValue != destValue

  我的解答如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
		StringBuilder left=new StringBuilder();
   		StringBuilder right=new StringBuilder();
        getRoute(root,startValue,left);
        getRoute(root,destValue,right);
        int index=0;
        while(index<Math.min(left.length(),right.length()))
        {
            if(left.charAt(index)==right.charAt(index)) index++;
            else break;
        }
        StringBuilder res=new StringBuilder();
        for(int i=index;i<left.length();i++)
            res.append("U");
        res.append(right.substring(index));
        return res.toString();

    }
    public Boolean getRoute(TreeNode root, int Value, StringBuilder sb )
    {
        if(root==null) return false;
        if(root.val==Value) return true;
        sb.append("L");
        if(getRoute(root.left,Value,sb)) return true;
        sb.deleteCharAt(sb.length()-1);
        sb.append("R");
        if(getRoute(root.right,Value,sb)) return true;
        sb.deleteCharAt(sb.length()-1);
        return false;
    }
}

  这个题难度不算特别高,算是比较基本的回溯法,所以这题做了半个多小时真的挺不应该的,做的时候在回溯时绕了很多弯子,一度还想用并查集做这题,挺不应该的,这个题注意不要用String存储答案就可以了,那样很有可能超时,用StringBuilder会好很多,别的就没啥了,起点和终点的路径找到后,先把前面相同路径排除掉,走到最近公共祖先,起点剩余的路径转换为U,到终点的剩余路径保持不变就可以了
  这种方法时间复杂度是O(n),即最坏情况遍历所有结点一遍,空间复杂度为O(1)
  此题也可用最近公共祖先方法做,但我感觉两种方法差的不多,就不在这儿写了:

2.4 合法重新排列数对(Hard)

  题目链接: LeetCode-5932

题目内容:
	给你一个下标从 0 开始的二维整数数组 pairs ,其中 pairs[i] = [start(i), end(i)] 。
	如果 pairs 的一个重新排列,满足对每一个下标i(1<=i< pairs.length)都有end(i-1)==start(i)
	那么我们就认为这个重新排列是 pairs 的一个合法重新排列 。
	请你返回任意一个 pairs 的合法重新排列。
	注意:数据保证至少存在一个 pairs 的合法重新排列。

示例:
	输入:pairs = [[5,1],[4,5],[11,9],[9,4]]
	输出:[[11,9],[9,4],[4,5],[5,1]]
	解释:
		输出的是一个合法重新排列,因为每一个 endi-1 都等于 start(i) 。
		end(0) = 9 == 9 = start(1)
		end(1) = 4 == 4 = start(2)
		end(2) = 5 == 5 = start(3)

提示:
	1 <= pairs.length <= 10^5
	pairs[i].length == 2
	0 <= starti, endi <= 10^9
	start(i) != end(i)
	pairs 中不存在一模一样的数对。
	至少存在一个合法的 pairs 重新排列。

  很明显的一道欧拉路径的题,但我当时竟然没想起来……,最后也就卡在了这儿,挺可惜的
  本题标准的欧拉路径解法,先找起点,逐一找到接下来的点,代码如下:

class Solution {
    Map<Integer,List<Integer>>map=new HashMap<>();
    List<Integer> res=new ArrayList<>();
    public int[][] validArrangement(int[][] pairs) {
        int len=pairs.length;
        Map<Integer,Integer> in=new HashMap<>();
        Map<Integer,Integer> out=new HashMap<>();
        for(int []pair:pairs)
        {
            map.putIfAbsent(pair[0],new ArrayList<>());
            map.get(pair[0]).add(pair[1]);
            in.put(pair[1],in.getOrDefault(pair[1],0)+1);
            out.put(pair[0],out.getOrDefault(pair[0],0)+1);
        }
        int start=-1;
        for(int key:out.keySet())
        {
            //当入度比出度小1时,一定是起点,本题一定有欧拉路径,不用考虑不存在的情况
            if(out.get(key)-in.getOrDefault(key,0)==1)
            {
                start=key;
                break;
            }
        }
        // 若start==-1代表存在欧拉回路,任意一个点均可以当起点
        if(start==-1) start=pairs[0][0];
        //采用dfs遍历的方式,获得一条路径
        dfs(start);
        int[][] ans = new int[len][2];
        //从倒数第二个点开始,每个点既是后一个点的起点,也是当前点的终点
        for(int i = len ; i > 0 ; i--){
            ans[len-i][0] = res.get(i);
            ans[len-i][1] = res.get(i-1);
        }
        return ans;
    }
    public void dfs(int start)
    {
        List<Integer> list = map.getOrDefault(start , new ArrayList<>());
        while(list.size() > 0){
            int x = list.remove(list.size()-1);
            dfs(x);
        }
        //后添加,确保终点会第一个被添加进去
        res.add(start);
    }
}

  找到起点后,用dfs确定路径就可以了,注意结点一定要反向添加,如果正向加的话会先碰到终点,反向可以确保终点第一个被添加

end
  • 作者:Yuan(联系作者)
  • 发表时间:2021-12-05 19:37
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请联系作者
  • 评论

    测试
    测试
    1  @ 测试
    测试