首页 > 编程语言 >算法问题——动态规划和回溯算法问题

算法问题——动态规划和回溯算法问题

时间：2023-04-04 19:40:16浏览次数：53  
标签：index return int ArrayList list 问题 算法 回溯 new


回溯算法

树形问题

排列问题

组合问题

二位平面的回溯算法

回溯递归问题

树形问题

17. 电话号码的字母组合(全排列的问题)

/**
 * Copyright (C), 2018-2020
 * FileName: letterCombinations
 * Author:   xjl
 * Date:     2020/3/20 15:30
 * Description: 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 */
package Leetcode_Medium_difficulty;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 这里是一个递归问题的概念
 */
public class letterCombinations2 {
    Map<Character, String> map = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};
    //用于存储结构的list
    List<String> output = new ArrayList<String>();

    public void findCombination(String str, int index, String s) {
        //递归终止的条件
        if (index == str.length()) {
            output.add(s);
            return;
        }
        //递归
        char c = str.charAt(index);
        if (c >= '0' && c <= '9') {
            String letter = map.get(c);
            for (int i = 0; i < letter.length(); i++) {
                findCombination(str, index + 1, s + letter.charAt(i));
            }
        }
        return;
    }

    public List<String> letterCombinations(String digits) {
        if (digits .equals("")) {
            return output;
        }
        findCombination(digits, 0, "");
        return output;
    }

    @Test
    public void test() {
        System.out.println(letterCombinations("9").toString());
    }

}

93. 复原IP地址

131. 分割回文串

46. 全排列

这个是不需要的处重复的

@Test
    public void test2(){
        ArrayList<ArrayList<Integer>> lists = permute(new int[]{1, 2, 3});
        for (List<Integer> list : lists) {
            for (int i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] vis = new boolean[num.length];
        test11(num, 0, vis, list, lists);
        return lists;
    }

    private void test11(int[] num, int index, boolean[] vis, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> lists) {
        if (index == num.length) {
            lists.add(new ArrayList<>(list));
            return;
        } else {
            for (int i = 0; i < num.length; i++) {
                if (!vis[i]) {
                    vis[i]=true;
                    list.add(num[i]);
                    test11(num,index+1,vis,list,lists);
                    list.remove(list.size()-1);
                    vis[i]=false;
                } else {
                    continue;
                }
            }
        }
    }
/**
 * Copyright (C), 2018-2020
 * FileName: Permutation46
 * Author:   xjl
 * Date:     2020/4/23 14:53
 * Description: 全排列的组合
 */
package Leetcode_Medium_difficulty;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Permutation46 {
    List<List<Integer>> lists = new ArrayList<>();
    Boolean[] used;

    public void generatepermuation(int[] nums, int index, List<Integer> list) {
        //递归的终止
        if (index == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        //递归
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                generatepermuation(nums, index + 1, list);
                list.remove(list.size()-1);
                used[i] = false;
            }
        }
        return;
    }

    public List<List<Integer>> permute(int[] nums) {
        System.out.println(nums.length);
        if (nums.length == 0) {
            return lists;
        }
        List<Integer> list = new ArrayList();
        used = new Boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            used[i] = false;
        }
        generatepermuation(nums, 0, list);
        return lists;
    }

    @Test
    public void test() {
        int[] numbers={1,2,3};
        System.out.println(permute(numbers).toString());
    }
}

排列问题

47. 全排列 II

/**
     * 采用的是结果去重的方法
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] vis = new boolean[nums.length];
        test2(nums, 0, vis, list, lists);
        lists = new ArrayList<>(new HashSet<>(lists));
        return lists;
    }

    private void test2(int[] nums, int index, boolean[] vis, List<Integer> list, List<List<Integer>> lists) {
        if (index == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!vis[i]) {
                    list.add(nums[i]);
                    vis[i] = true;
                    test2(nums, index + 1, vis, list, lists);
                    list.remove(list.size() - 1);
                    vis[i] = false;
                } else {
                    continue;
                }
            }
        }
    }
/**
 * Copyright (C), 2018-2020
 * FileName: Permutation2
 * Author:   xjl
 * Date:     2020/7/15 16:21
 * Description: quanpailie
 */
package DFS_BFS;

import org.junit.Test;

import java.util.ArrayList;

public class Permutation2 {

    public ArrayList<String> Permutation(String str) {
        char[] array = str.toCharArray();
        ArrayList<String> result = new ArrayList<>();
        slove(array, result, 0, str.length());
        return result;
    }

    private void slove(char[] array, ArrayList<String> result, int index, int length) {
        if (index == length - 1) {
            String res = chage(array);
            result.add(res);
        } else {
            //说明要去确定indxd的位置
            for (int i = index; i < length; i++) {
                char temp = array[i];
                array[i] = array[index];
                array[index] = temp;
                //那么就是递归的调用到洗衣歌位置的字符
                slove(array, result, index + 1, length);
                //为了消除递归的时候的进行的交换的字符的影响
                temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
        }
    }

    private String chage(char[] array) {
        StringBuilder res = new StringBuilder();
        for (char value : array) {
            res.append(value);
        }
        return res.toString();
    }

    public int reletive_7 (int[] digit) {
       String Str="";
       for (int i=0;i<digit.length;i++){
           Str+=String.valueOf(digit[i]);
       }
        ArrayList<String> list = Permutation(Str);
        int[] result=new int[list.size()];
        for (int i=0;i<result.length;i++){
            result[i]=Integer.valueOf(list.get(i));
        }
        int count=0;
        for (int i=0;i<result.length;i++){
            if (result[i]%7==0){
                count++;
            }
        }
        return count;
    }
    @Test
    public void test(){
        int[] arr={1,1,2};
        int result = reletive_7(arr);
        System.out.println(result);
    }
}

组合问题

77. 组合

/**
 * Copyright (C), 2018-2020
 * FileName: combine
 * Author:   xjl
 * Date:     2020/4/23 18:29
 * Description: 组合
 */
package Leetcode_Medium_difficulty;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class combine {
    List<List<Integer>> lists = new ArrayList<>();

    public void generCombinations(int n, int k, int start, List<Integer> list) {
        //递归的结束的条件
        if (list.size() == k) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i <= n; i++) {
            list.add(i);
            generCombinations(n, k, i + 1, list);
            //回溯的过程
            list.remove(list.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k <= 0 || k > n) {
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        generCombinations(n, k, 1, list);
        return lists;
    }

    @Test
    public void test() {
        System.out.println(combine(4, 2).toString());
    }
}

39. 组合总和

40. 组合总和 II

216. 组合总和 III

78. 子集

90. 子集 II

401. 二进制手表

二位平面的回溯算法

79. 单词搜索

/**
 * Copyright (C), 2018-2020
 * FileName: exist
 * Author:   xjl
 * Date:     2020/4/24 8:48
 * Description: 回溯算法的二维平面
 */
package Leetcode_Medium_difficulty;

import org.junit.Test;

public class exist {
    //四个方向
    int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int m, n;
    boolean[][] visit = new boolean[m][n];

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        //赋值没有访问过
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = false;
            }
        }
        //开始遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (searchword(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean searchword(char[][] board, String word, int index, int startx, int starty) {
        //递归的终止条件
        if (index == word.length() - 1) {
            return board[startx][starty] == word.charAt(index);
        }
        //递归的流程
        if (board[startx][starty] == word.charAt(index)) {
            visit[startx][starty] = true;
            //从四个方向开始往下寻找
            for (int i = 0; i < 4; i++) {
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if (inArea(newx, newy) && !visit[newx][newy]) {
                    if (searchword(board, word, index + 1, newx, newy)) {
                        return true;
                    }
                }
            }
            visit[startx][starty] = false;
        }
        return false;
    }

    //判断是否在矩阵中
    private boolean inArea(int newx, int newy) {
        return newx >= 0 && newx < m && newy >= 0 && newy < n;
    }

    @Test
    public void test() {

    }
}

回溯递归问题

public class exist79 {
    //四个方向
    int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int m, n;
    boolean[][] visit;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        //赋值没有访问过
        visit=new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = false;
            }
        }
        //开始遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (searchword(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean searchword(char[][] board, String word, int index, int startx, int starty) {
        //递归的终止条件
        if (index == word.length() - 1) {
            return board[startx][starty] == word.charAt(index);
        }
        //递归的流程
        if (board[startx][starty] == word.charAt(index)) {
            visit[startx][starty] = true;
            //从四个方向开始往下寻找
            for (int i = 0; i < 4; i++) {
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if (inArea(newx, newy) && !visit[newx][newy]) {
                    if (searchword(board, word, index + 1, newx, newy)) {
                        return true;
                    }
                }
            }
            visit[startx][starty] = false;
        }
        return false;
    }

    //判断是否在矩阵中
    private boolean inArea(int newx, int newy) {
        return newx >= 0 && newx < m && newy >= 0 && newy <n;
    }
}

标签：index,return,int,ArrayList,list,问题,算法,回溯,new
From： https://blog.51cto.com/u_13643065/6169258

相关文章

  • Redis——面试问题集合
    那你能说说Redis是单线程的？Redis完全基于内存，绝大部分请求是纯粹的内存操作，非常迅速，数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度是O(1)。数据结构简单，对数据操作也简单。采用单线程，避免了不必要的上下文切换和竞争条件，不存在多线程导致的CPU切换......
  • 大数据云计算——hadoop的面试问题总结
    1.讲述HDFS上传⽂件和读⽂件的流程？HDFS上传流程，举例说明⼀个256M的⽂件上传过程(1)由客户端Client向NameNode节点发出请求;(2)NameNode向Client返回可以存数据的DataNode列表，遵循机架感应原则(把副本分别放在不同的机架，甚⾄不同的数据中⼼);(3)客户端⾸先根据返回的信息先将⽂......
  • 算法训练——剑指offer(动态规划算法)摘要
    摘要一、动态规划原理与解题方法二、动态规划算法练习题目2.1跳台阶问题package动态规划算法;importorg.junit.Test;/***@ClassnameJZ69跳台阶问题*@DescriptionTODO*@Date2022/2/1118:54*@Createdbyxjl*/publicclassJZ69跳台阶问题{/**......
  • 并发编程——JUC并发大厂面试问题
    摘要现如今，不管是应届毕业生还是工作了三五年之内的工程师，在面试招聘的时候JUC并发编程的是必须掌握的一个技能，否者你将会被面试官玩弄。本博文将整理有关于的JUC的大厂面试问题和答案。帮助大家在面试过程中能够回答面试官问题的一二。同时本人也总结相关的面试问题的在相关文档中......
  • LeetCode——贪心算法总结
    贪心算法的主要的解题目的思路是： 860.柠檬水找零这道题算是生活中很常见的一道题，对于每一个顾客如果我们都有足够的零钱给他找零，那么就返回true，只要有一个顾客没有足够的零钱找给他就返回false。顾客只能有3种纸币，5元，10元，20元。我们要统计5元和10元的数量，20元的不需要统计，因为20......
  • Kafka——kafka的面试问题和解答
    摘要主要的是的针对于的kafka的面试的问题进行分析和总结PartitionRebalance分区再均衡1）消费者组中新添加消费者读取到原本是其他消费者读取的消息,（2）消费者关闭或崩溃之后离开群组，原本由他读取的partition将由群组里其他消费者读取,（3）当向一个Topic添加新的partition，会发生partitio......
  • pytorch中bin模型文件转onnx遇到的问题
    pytorch中bin模型文件转onnx遇到的问题1常规做法importosimportnumpyasnpfromtransformersimportGPT2LMHeadModelimporttorchlocalfile=r"C:\Users\min_ppl_model"model=GPT2LMHeadModel.from_pretrained(localfile)#输入shape为1，50其中1为bs50为固......
  • 最全综述 | 图像分割算法
    图像分割是计算机视觉研究中的一个经典难题，已经成为图像理解领域关注的一个热点，图像分割是图像分析的第一步，是计算机视觉的基础，是图像理解的重要组成部分，同时也是图像处理中最困难的问题之一。所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相......
  • 部署项目遇到的问题汇总
    部署项目遇到的问题汇总问题一：nginx部署完成后，访问后端的接口返回CORS跨域请求思考：我部署的前后端都在同一个宿主机上，访问的ip都是相同的，不应出现跨域才对。解决：当你的nginx有如下配置（该配置通常用于本地开发环境）server{listen80;server_namexxx.aliyun.......
  • 如何基于AI算法实现智慧工厂视频大数据智能预警平台搭建？
    当前我国正处于数字经济高速发展的时代，企业正面临着数字化“转型升级”的需求。那么，工厂该如何实现智能化转型目标呢？EasyCVR视频融合平台与AI智能分析网关，融合了边缘AI智能识别技术，部署了多种AI算法，能实现人脸、人体、车辆、物体、行为等智能检测，在工厂的智慧转型场景中发挥着重要......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99