首页 > 其他分享 >[左神面试指南] 递归和动态规划[下]篇

[左神面试指南] 递归和动态规划[下]篇

时间：2023-11-14 21:11:16浏览次数：46  
标签：arr 递归 int 左神 面试 length str public dp

CD42 子数组异或和为 0 的最多划分⭐

/*⭐DP⭐*/
public class CD42_1
{
    public static int solution(int[] arr)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] dp = new int[arr.length];
        int temp = 0;
        dp[0] = arr[0] == 0 ? 1 : 0;
        temp ^= arr[0];
        map.put(arr[0], 0);
        map.put(0, -1);
        for (int i = 1; i < arr.length; i++)
        {
            temp ^= arr[i];
            if (map.containsKey(temp))
            {
                int idx = map.get(temp);
                dp[i] = idx == -1 ? 1 : dp[idx] + 1;
            }
            dp[i] = Math.max(dp[i], dp[i - 1]);
            map.put(temp, i);
        }
        return dp[arr.length - 1];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD43 最小编辑代价⭐

/* ⭐DP⭐
 * 令dp[i][j]的值代表s1[0..i-1]编辑成s2[0..j-1]的最小代价
 * 则dp[i][j]=min(dp[i-1][j-1], dp[i-1][j-1]+replace, dp[i-1][j]+delete, dp[i][j-1]+insert)
 */
public class CD43_1
{
    public static int solution(String s1, String s2, int insert, int delete, int replace)
    {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        dp[0][0] = 0;
        for (int i = 1; i < s1.length() + 1; i++)
            dp[i][0] = i * delete;
        for (int i = 1; i < s2.length() + 1; i++)
            dp[0][i] = i * insert;
        for (int i = 1; i < s1.length() + 1; i++)
            for (int j = 1; j < s2.length() + 1; j++)
            {
                dp[i][j] = Math.min(dp[i - 1][j] + delete, dp[i][j - 1] + insert);
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                else
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + replace);
            }
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s1, s2;
        int insert, delete, replace;
        s1 = in.nextLine();
        s2 = in.nextLine();
        insert = in.nextInt();
        delete = in.nextInt();
        replace = in.nextInt();
        System.out.println(solution(s1, s2, insert, delete, replace));
    }
}

CD44 字符串的交错组成⭐

/* ⭐DP⭐
 * dp[i][j]的值代表aim[0..i+j-1]能否被str1[0..i-1]和str2[0..j-1]交错组成
 */
public class CD44_1
{
    public static String solution(String s1, String s2, String aim)
    {
        if (aim.length() < s1.length() + s2.length()) return "NO";
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++)
        {
            if (aim.charAt(i - 1) != s1.charAt(i - 1))
                break;
            dp[i][0] = true;
        }
        for (int i = 1; i <= s2.length(); i++)
        {
            if (aim.charAt(i - 1) != s2.charAt(i - 1))
                break;
            dp[0][i] = true;
        }
        for (int i = 1; i <= s1.length(); i++)
            for (int j = 1; j <= s2.length(); j++)
                if ((dp[i - 1][j] && s1.charAt(i - 1) == aim.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == aim.charAt(i + j - 1)))
                    dp[i][j] = true;
        return dp[s1.length()][s2.length()] ? "YES" : "NO";
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s1, s2, s3;
        s1 = in.nextLine();
        s2 = in.nextLine();
        s3 = in.nextLine();
        System.out.println(solution(s1, s2, s3));
    }
}

CD45 龙与地下城游戏问题

/* DP
 * dp[i][j]表示为从[i,j]到[n-1,m-1]至少需要的血量
 */
public class CD45_1
{
    public static int solution(int[][] arr)
    {
        int n = arr.length, m = arr[0].length;
        int[][] dp = new int[n][m];
        for (int[] t : dp)
            Arrays.fill(t, Integer.MAX_VALUE);
        dp[n - 1][m - 1] = arr[n - 1][m - 1] < 0 ? -arr[n - 1][m - 1] + 1 : 1;
        for (int i = n - 2; i >= 0; i--)
            dp[i][m - 1] = Math.max(dp[i + 1][m - 1] - arr[i][m - 1], 1);
        for (int i = m - 2; i >= 0; i--)
            dp[n - 1][i] = Math.max(dp[n - 1][i + 1] - arr[n - 1][i], 1);
        for (int i = n - 2; i >= 0; i--)
            for (int j = m - 2; j >= 0; j--)
                dp[i][j] = Math.min(Math.max(dp[i + 1][j] - arr[i][j], 1), Math.max(dp[i][j + 1] - arr[i][j], 1));
        return dp[0][0];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, m;
        n = in.nextInt();
        m = in.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                arr[i][j] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD46 数字字符串转换为字母组合的种数

/* DP */
public class CD46_1
{
    public static int solution(String str)
    {
        int MOD = (int) (1E9 + 7);
        int[] dp = new int[str.length()];
        if (str.charAt(0) == '0') return 0;
        dp[0] = 1;
        dp[1] = (check(str.charAt(0), str.charAt(1)) ? 1 : 0) + (str.charAt(1) != '0' ? 1 : 0);
        for (int i = 2; i < str.length(); i++)
        {
            if (str.charAt(i) == '0')
            {
                if (str.charAt(i - 1) == '1' || str.charAt(i - 1) == '2')
                    dp[i] = dp[i - 2];
                else
                    return 0;
            }
            else
                dp[i] = (dp[i - 1] + (check(str.charAt(i - 1), str.charAt(i)) ? dp[i - 2] : 0)) % MOD;
        }
        return dp[str.length() - 1];
    }

    public static boolean check(char ch1, char ch2)
    {
        if (ch1 == '0') return false;
        else if (ch1 == '1') return true;
        else if (ch1 == '2') return (ch2 >= '0' && ch2 <= '6');
        else return false;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }
}

/* DP */
public class CD46_2
{
    // 暴力递归
    public static int solution1(String str)
    {
        return cal(str, 0);
    }

    public static int cal(String s, int idx)
    {
        int res = 0;
        if (idx == s.length()) return 1;
        if (idx < s.length() && s.charAt(idx) != '0')
            res = cal(s, idx + 1) % (int) (1E9 + 7);
        if (idx < s.length() - 1 && check(s.charAt(idx), s.charAt(idx + 1)))
            res = (res + cal(s, idx + 2)) % (int) (1E9 + 7);
        return res;
    }

    public static boolean check(char ch1, char ch2)
    {
        if (ch1 == '0') return false;
        else if (ch1 == '1') return true;
        else if (ch1 == '2') return (ch2 >= '0' && ch2 <= '6');
        else return false;
    }

    // 优化
    public static int solution2(String str)
    {
        int strLen = str.length();
        int[] dp = new int[strLen];
        dp[strLen - 1] = str.charAt(strLen - 1) == '0' ? 0 : 1;
        if (str.charAt(strLen - 2) == '0')
            dp[strLen - 2] = 0;
        else
            dp[strLen - 2] = (check(str.charAt(strLen - 2), str.charAt(strLen - 1)) ? 1 : 0) + (str.charAt(strLen - 1) != '0' ? 1 : 0);
        for (int i = strLen - 3; i >= 0; i--)
        {
            if (str.charAt(i) != '0')
                dp[i] = dp[i + 1];
            if (check(str.charAt(i), str.charAt(i + 1)))
                dp[i] = (dp[i] + dp[i + 2]) % (int) (1E9 + 7);
        }
        return dp[0];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution2(s));
    }
}

CD47 表达式得到期望结果的组成种数❗

/* ❗DP❗ */
public class CD47_1
{

    public static int solution(String str, boolean desired)
    {
        return cal(str, desired, 0, str.length() - 1);
    }

    public static int cal(String str, boolean desired, int l, int r)
    {
        if (l == r)
        {
            if (str.charAt(l) == '1')
                return desired ? 1 : 0;
            else
                return desired ? 0 : 1;
        }
        int res = 0;
        if (desired)
        {
            for (int i = l + 1; i < r; i += 2)
            {
                switch (str.charAt(i))
                {
                    case '&':
                        res = res + cal(str, true, l, i - 1) * cal(str, true, i + 1, r);
                        break;
                    case '^':
                        res = res + cal(str, true, l, i - 1) * cal(str, false, i + 1, r);
                        res = res + cal(str, false, l, i - 1) * cal(str, true, i + 1, r);
                        break;
                    case '|':
                        res = res + cal(str, true, l, i - 1) * cal(str, true, i + 1, r);
                        res = res + cal(str, false, l, i - 1) * cal(str, true, i + 1, r);
                        res = res + cal(str, true, l, i - 1) * cal(str, false, i + 1, r);
                        break;
                }
            }
        }
        else
        {
            for (int i = l + 1; i < r; i += 2)
            {
                switch (str.charAt(i))
                {
                    case '&':
                        res = res + cal(str, true, l, i - 1) * cal(str, true, i + 1, r);
                        res = res + cal(str, false, l, i - 1) * cal(str, true, i + 1, r);
                        res = res + cal(str, true, l, i - 1) * cal(str, false, i + 1, r);
                        break;
                    case '^':
                        res = res + cal(str, true, l, i - 1) * cal(str, true, i + 1, r);
                        res = res + cal(str, false, l, i - 1) * cal(str, false, i + 1, r);
                        break;
                    case '|':
                        res = res + cal(str, false, l, i - 1) * cal(str, false, i + 1, r);
                        break;
                }
            }
        }
        return res;
    }

    public static boolean isValid(char[] exp)
    {
        if ((exp.length & 1) == 0)
        {
            return false;
        }
        for (int i = 0; i < exp.length; i = i + 2)
        {
            if ((exp[i] != '1') && (exp[i] != '0'))
            {
                return false;
            }
        }
        for (int i = 1; i < exp.length; i = i + 2)
        {
            if ((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^'))
            {
                return false;
            }
        }
        return true;
    }

    public static long solution2(String express, boolean desired)
    {
        int MOD = (int) (1E9 + 7);
        char[] exp = express.toCharArray();
        if (!isValid(exp)) return 0;
        long[][] t = new long[exp.length][exp.length];
        long[][] f = new long[exp.length][exp.length];
        t[0][0] = exp[0] == '0' ? 0 : 1;
        f[0][0] = exp[0] == '1' ? 0 : 1;
        for (int i = 2; i < exp.length; i += 2)
        {
            t[i][i] = exp[i] == '0' ? 0 : 1;
            f[i][i] = exp[i] == '1' ? 0 : 1;
            for (int j = i - 2; j >= 0; j -= 2)
            {
                for (int k = j; k < i; k += 2)
                {
                    if (exp[k + 1] == '&')
                    {
                        t[j][i] = (t[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
                        f[j][i] = (f[j][i] + (((f[j][k] + t[j][k]) % MOD) * f[k + 2][i]) % MOD + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
                    }
                    else if (exp[k + 1] == '|')
                    {
                        t[j][i] = (t[j][i] + ((((f[j][k] + t[j][k]) % MOD) * t[k + 2][i]) % MOD + (t[j][k] * f[k + 2][i]) % MOD) % MOD) % MOD;
                        f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
                    }
                    else
                    {
                        t[j][i] = (t[j][i] + ((f[j][k] * t[k + 2][i]) % MOD + (t[j][k] * f[k + 2][i]) % MOD) % MOD) % MOD;
                        f[j][i] = (f[j][i] + ((f[j][k] * f[k + 2][i]) % MOD + (t[j][k] * t[k + 2][i]) % MOD) % MOD) % MOD;
                    }
                }
            }
        }
        return desired ? t[0][t.length - 1] : f[0][f.length - 1];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String str, desired;
        str = in.nextLine();
        desired = in.nextLine();
        System.out.println(solution2(str, !"false".equals(desired)));
    }

}

CD91 排成一条线的纸牌博弈问题❗

/*❗❗*/
public class CD91_1
{
    public static int solution1(int[] arr)
    {
        if (arr == null || arr.length == 0) return 0;
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    public static int f(int[] arr, int i, int j)
    {
        if (i == j) return arr[i];
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    public static int s(int[] arr, int i, int j)
    {
        if (i == j) return 0;
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

    public static int solution2(int[] arr)
    {
        if (arr == null || arr.length == 0) return 0;
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int j = 0; j < arr.length; j++)
        {
            f[j][j] = arr[j];
            for (int i = j - 1; i >= 0; i--)
            {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution2(arr));
    }
}

CD92 跳跃游戏

public class CD92_1
{

    public static int solution(int[] arr)
    {
        int cur = 0, next = 0, ans = 0;
        for (int i = 0; i < arr.length; i++)
        {
            if (cur < i)
            {
                ans++;
                cur = next;
            }
            next = Math.max(next, i + arr[i]);
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD93 数组中的最长连续序列⭐

public class CD93_1
{
    public static int solution(int[] arr)
    {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            if (!map.containsKey(arr[i]))
            {
                map.put(arr[i], 1);
                if (map.containsKey(arr[i] + 1))
                    ans = Math.max(ans, merge(arr[i], arr[i] + 1, map));
                if (map.containsKey(arr[i] - 1))
                    ans = Math.max(ans, merge(arr[i] - 1, arr[i], map));
            }
        }
        return ans;
    }

    public static int merge(int less, int more, HashMap<Integer, Integer> map)
    {
        int left = less - map.get(less) + 1;
        int right = more + map.get(more) - 1;
        int len = right - left + 1;
        map.put(left, len);
        map.put(right, len);
        return len;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD94 N 皇后问题

public class CD94_1
{
    // 递归
    public static int solution(int n)
    {
        int[] vis = new int[n];
        return cal(0, vis, n);
    }

    public static int cal(int row, int[] vis, int n)
    {
        if (row == n) return 1;
        int res = 0;
        for (int col = 0; col < n; col++)
        {
            if (!isValid(vis, row, col)) continue;
            vis[row] = col;
            res += cal(row + 1, vis, n);
        }
        return res;
    }

    public static boolean isValid(int[] vis, int row, int col)
    {
        for (int r = 0; r < row; r++)
            if (col == vis[r] || row + col == r + vis[r] || col - row == vis[r] - r)
                return false;
        return true;
    }

    // 二进制优化
    public static int solution2(int n)
    {
        if (n < 1 || n > 32) return 0;
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process2(upperLim, 0, 0, 0);
    }

    public static int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim)
    {
        if (colLim == upperLim) return 1;
        int pos = 0;
        int mostRightOne = 0;
        pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while (pos != 0)
        {
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(upperLim, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        System.out.println(solution2(n));
    }
}

标签：arr,递归,int,左神,面试,length,str,public,dp
From： https://www.cnblogs.com/VividBinGo/p/17832582.html

相关文章

  • 常见面试题-Spring的aop和ioc如何实现？
    Spring的aop和ioc怎么实现？Spring的IOC是如何实现的呢？Spring的IOC是通过工厂+反射去实现的，在IOC中，Spring会将创建的Bean都放在工厂中，我们可以通过@Configuration来定义配置类，在配置类中通过@Bean来将Bean创建在Bean工厂中，在对Bean进行实例化时，使用的......
  • Java多线程面试题
    目录0、请你说说线程和进程的区别1、请你说说多线程2、说说CAS的ABA问题3、说说你对AQS（抽象队列同步器）的理解4、Java哪些地方使用了CAS5、说说怎么保证线程安全5、说说你了解的线程同步方式6、说说synchronized的用法及原理7、synchronized和Lock有什么区别8、说说Java......
  • netcore net 递归查询示例
    ///<summary>///查询项目列表///</summary>///<paramname="userModel"></param>///<returns></returns>publicasyncTask<List<GetProjectListOutput>>GetProjectList......
  • Android并发编程高级面试题汇总（含详细解析 三）
    Android并发编程高级面试题汇总最全最细面试题讲解持续更新中......
  • SQLserver中的递归如何实现
    在SQLServer中，可以使用递归CTE（通用表达式）来实现递归查询。CTE（通用表达式）是一种临时命名结果集，它只存在于查询语句的执行过程中。CTE可以在一个SELECT，INSERT，UPDATE或DELETE语句中使用，并且可以在同一个查询中递归引用自身。这使得递归查询成为可能。下面是一个使用递归CTE的示例：......
  • [左神面试指南] 递归和动态规划[上]篇
    CD183斐波那契数列问题的递归和动态规划1/**矩阵快速幂*[f(n),f(n-1)]=[1,1]x[[1,1],[1,0]]^(n-2)*/publicclassCD183_1{publicstaticlongsolution(longn){if(n<1)return-1;if(n<=2)return1;long[][]......
  • 2023蚂蚁金服/理想/字节/快手面试笔试题——5个线程交叉打印1~100
    原题来自牛客网面经。类似这种多线程轮流打印的手撕题会出现很多次，比如以前就看过类似的3个线程轮流打印ABC。 关键点在于：怎么设计机制保证这个顺序，至于要打印的数字，肯定是要用互斥量保护起来。C++代码如下：#include<iostream>#include<mutex>#include<thread>#include......
  • 面试必刷TOP101：27、按之字形顺序打印二叉树
    题目题解importjava.util.*;/**publicclassTreeNode{*intval=0;*TreeNodeleft=null;*TreeNoderight=null;*publicTreeNode(intval){*this.val=val;*}*}*/publicclassSolution{/***代码中的类名、方......
  • 用函数递归打印数字的每位数字
    #include<stdio.h>voidprint(intj){  if(j>9)  {        print(j/10);      }  printf("%d",j%10);}intmain(){ inti; printf("请输入数字："); scanf_s("%d",&i);   print(i); ......
  • Delphi TNetHTTPClient使用递归方式取所有分页数据
    DelphiTNetHTTPClient使用递归方式取所有分页数据   业务系统提供的一个查询数据接口，可以通过分页方式取得数据，如果一次性取得所有数据，将页大小增大即可，但如果数据太多怕会造成内存溢出。   综合考虑每次只取一个分页，分页数据不要太大，用递归方式来获取是比较合理的解......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99