讨论/题目交流/🏆 第 190 场力扣周赛/
🏆 第 190 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 检查单词是否为句中其他单词的前缀
4 分 - 定长子串中元音的最大数目
5 分 - 二叉树中的伪回文路径
6 分 - 两个子序列的最大点积

展开讨论
力扣 (LeetCode)发起于 2020-05-24

第3题:
题解:看数据范围,每个节点值才[1,...,9],这就很好办了。

  • 用dfs遍历路径,直到叶子节点,同时用个数组统计一下经过路径的所有数字的个数
  • 回文只有3种情况,1. 所有数字的个数是偶数 2. 一个数字的个数是奇数,一个数字的个数是偶数 3. 一个数字的个数是奇数
  • 每次遍历路径后回溯
import java.lang.reflect.Array;
import java.util.Arrays;

public class test5
{

  public static 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;
      }
  }

    private int ans;
    private int N = 10;
    private int[] num = new int[N];

    public void dfs(TreeNode root)
    {
        num[root.val] ++;

        // 到达一个路径
        if(root.left == null && root.right == null)
        {
            int ou = 0;
            int ji = 0;

            for (int i = 1; i < N; i++)
            {
                if(num[i] == 0) continue;

                if(num[i] % 2 == 0)
                {
                    ou++;
                }
                else
                {
                    ji++;
                }
            }

            if(ji == 1 && ou > 0)
            {
                ans++;
            }
            else if(ji == 0 && ou > 0)
            {
                ans++;
            }
            else if(ji == 1 && ou ==0)
            {
                ans++;
            }

            num[root.val]--;
            return;
        }


        if(root.left != null) dfs(root.left);
        if(root.right != null) dfs(root.right);

        num[root.val]--;
        return;
    }

    public int pseudoPalindromicPaths (TreeNode root)
    {
        ans = 0;
        if(root == null) return ans;

        Arrays.fill(num,0);

        dfs(root);

        return ans;
    }


    public static void main(String[] args)
    {
        TreeNode node01 = new TreeNode(2);
        TreeNode node02 = new TreeNode(3);
        TreeNode node03 = new TreeNode(1);
        TreeNode node04 = new TreeNode(3);
        TreeNode node05 = new TreeNode(1);
        TreeNode node06 = new TreeNode(1);

//        node01.left = node02;
//        node01.right = node03;
//        node02.left = node04;
//        node02.right = node05;
//        node03.right = node06;


        test5 of = new test5();
        System.out.println(of.pseudoPalindromicPaths(node01));
    }
}

第4题:
题解:一看题目,就是dp

  • 我用dfs来递归求解的,用dp来记忆化
  • 其中dp[i][j]表示为,剩下x=[i,...,n1] in nums1[x]y=[j,...,n2] in nums2[y]时,最大值是多少
  • 假设nums1的长度为length1num2的长度为length2
  • 所以所有的dp开始初始化为Integer.MIN_VALUE,表示记忆无效
  • 假如我是根据nums1来进行dfs,假设当前选择的数字是i,对于这个位置的数字有选择不选择的两项
  • 如果我不选这个数字,那么继续dp[i][j]=dfs(i+1,j);
  • 如果我选择这个数字的话,dp[i][j] = Math.max(dp[i][j],nums1[i] * nums[k] + dfs(i+1,k + 1)) k in [j,length2],其中假如k = t,那么[j,t-1] in num2这些数字是忽略掉,不要了,[t+1,length2],用于下一次选择
  • 要注意,必须在nums1选择一个数字,如果没选择数字,是空数组,肯定不合法,返回Integer.MIN_VALUE,所以用sum来记录
public class test6
{

    int n1,n2;
    int[][] dp;

    /**
     *
     * @param nums1
     * @param nums2
     * @param sum 总共选择了数字的个数
     */
    private int dfs(int i1,int i2,int[] nums1,int[] nums2,int sum)
    {
        if(i1 == n1 || i2 == n2)
        {
            if(sum == 0)
            {
                return Integer.MIN_VALUE;
            }

            return 0;
        }

        if(dp[i1][i2] != Integer.MIN_VALUE) return dp[i1][i2];

        // 不要这个数字
        dp[i1][i2] = dfs(i1 + 1,i2,nums1,nums2,sum + 0);

        for (int j = i2; j < n2; j++)
        {
            dp[i1][i2] = Math.max(dp[i1][i2],nums1[i1] * nums2[j] + dfs(i1+1,j+1,nums1,nums2,sum + 1));
        }

        return dp[i1][i2];
    }

    public int maxDotProduct(int[] nums1, int[] nums2)
    {
        if(nums1 == null|| nums1.length == 0 || nums2 == null || nums2.length == 0) return 0;

        n1 = nums1.length;
        n2 = nums2.length;
        dp = new int[n1 + 1][n2 + 1];

        for (int i = 0; i <= n1; i++)
        {
            for (int j = 0; j <= n2; j++)
            {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }


        return dfs(0,0,nums1,nums2,0);
    }

    public static void main(String[] args)
    {
        int[] nums1 = {-1,-1};
        int[] nums2 = {1,1};

        test6 of = new test6();
        System.out.println(of.maxDotProduct(nums1,nums2));
    }
}
展开全部 31 讨论