编程导航会员会员
登录/注册

力扣刷题Hot100

HOT 回溯章节，这个部分基本就是默写了，推荐去看b站的灵神的算法精讲视频，我很多思路或者题解都是从那 里学会的。睡觉，今天就到这了....祝好梦

  1. 78. 子集 - 力扣（LeetCode）
  2. 46. 全排列 - 力扣（LeetCode）
  3. 17. 电话号码的字母组合 - 力扣（LeetCode）
  4. 39. 组合总和 - 力扣（LeetCode）
  5. 22. 括号生成 - 力扣（LeetCode）
  6. 79. 单词搜索 - 力扣（LeetCode）
  7. 131. 分割回文串 - 力扣（LeetCode）
  8. 51. N 皇后 - 力扣（LeetCode）

子集

板子题

▼
java
复制代码
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int n;
    private int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        dfs(0);
        return ans;
    }
    private void dfs(int i ){
        ans.add(new ArrayList<>(path));
        for (int j = i ; j < n; j++){
            path.add(nums[j]);
            dfs(j + 1);
            path.remove(path.size()-1);
        }
    }
}

全排列

板子题

▼
java
复制代码
class Solution {
    private int n;
    private int[] nums;
    private boolean[] onPath;
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        this.n = n;
        this.nums = nums;
        this.onPath = new boolean[n];
        dfs(0);
        return ans;
    }

    private void dfs(int i){
        if (i == n){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = 0; j < n ; j++){
            if (!onPath[j]){
                path.add(nums[j]);
                onPath[j] = true;
                dfs(i + 1);
                path.remove(path.size()-1);
                onPath[j] = false;
            }
        }
    }
}

电话号码字母组合

组合变形题

▼
java
复制代码
class Solution {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    private List<String> ans = new ArrayList<>();
    private char[] digits;
    private char[] path;
    private int n;

    public List<String> letterCombinations(String digits) {
        this.digits = digits.toCharArray();        
        this.n = digits.length();
        this.path = new char[n];
        if (n == 0){
            return List.of();
        }
        dfs(0);
        return ans;
    }

    private void dfs(int i ){
        if (i == n){
            ans.add(new String(path));
            return;
        }
        for (char c : MAPPING[digits[i] - '0'].toCharArray()){
            path[i] = c;
            dfs(i + 1);
        }
    }
}

组合总和

有点像二叉树路径和

▼
java
复制代码
class Solution {

    private List<List<Integer>> ans = new ArrayList<>();
    private int[] candidates;
    private int n;
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.n = candidates.length;
        this.candidates = candidates;
        dfs(0,target);
        return ans;
    }

    private void dfs(int i , int target){
        if (target == 0){
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i == n || target < candidates[i]){
            return;
        }
        dfs(i + 1, target);
        path.add(candidates[i]);
        dfs(i , target - candidates[i]);
        path.remove(path.size()-1);
    }
}

括号生成

选或不选的思路

推荐去看灵神的这部分的算法精讲

▼
java
复制代码
class Solution {
    private int n ;
    private List<String> ans = new ArrayList<>();
    private char[] path;
         
    public List<String> generateParenthesis(int n) {

        this.n = n;
        path = new char[n * 2];
        dfs(0 ,0);
        return ans;    
    }


    private void dfs(int i , int open){
        if (i == n * 2){
            ans.add(new String(path));
            return;
        }
        if (open < n){
            path[i] = '(';
            dfs(i + 1,open + 1);
        }
        if (i - open < open){
            path[i] = ')';
            dfs(i + 1,open);
        }
    } 
}

单词搜索

经典广度优先算法

▼
java
复制代码
class Solution {

    private static final int[][] DIRS = {{0,-1},{0,1},{-1,0},{1,0}};
    private char[][] board;
    private char[] word;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word.toCharArray();
        for (int i  = 0 ; i < board.length; i++){
            for (int j = 0; j < board[i].length; j ++){
                if (dfs(i , j ,0)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i , int j , int k){
        if (board[i][j] != word[k]){
            return false;
        }
        if (k == word.length - 1){
            return true;
        }

        board[i][j] = 0;
        for (int[] d : DIRS){
            int x = i + d[0];
            int y = j + d[1];
            if (0 <=  x && x < board.length && 0 <= y && y < board[x].length && board[x][y] != 0 && dfs(x, y, k +1)){
                return true;
            }
        }
        board[i][j] = word[k];
        return false;
    }
}

分割回文串

使用选或者不选的思路，也可以直接回溯模板

▼
java
复制代码
class Solution {

    private List<List<String>> ans = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    private String s;
    private int n;
    public List<List<String>> partition(String s) {
        this.s = s;
        this.n = s.length();
        dfs(0,0);
        return ans;
    }

    private void dfs(int i , int start){
        if (i == n){
            ans.add(new ArrayList<>(path));
            return ;
        }
        if (i < n - 1){
            dfs(i + 1, start);
        }
        if (check(start , i)){
            path.add(s.substring(start,i + 1));
            dfs(i + 1, i + 1);
            path.remove(path.size()-1);
        }
    }

    private boolean check(int l , int r){
        while (l < r){
            if (s.charAt(l ++)  != s.charAt(r --)){
                return false;
            }
        }
        return true;
    }
}

N皇后

经典排列了，默写

▼
java
复制代码
class Solution {

    private char[][] queens;
    private boolean[] onPath;
    private boolean[] dig1;
    private boolean[] dig2;
    private int n;
    private List<List<String>> ans = new ArrayList<>();


    public List<List<String>> solveNQueens(int n) {

        this.n = n;
        this.queens = new char[n][n];
        for (int i = 0 ; i < n; i++){
            for (int j  =0; j < n; j++){
                queens[i][j] = '.';
            }
        }

        this.onPath  = new boolean[n];
        this.dig1 = new boolean[n * 2];
        this.dig2 = new boolean[n  *2];
        dfs(0);
        return ans;
    }


    private void dfs(int i){
        if (i == n){
            List<String> temp = new ArrayList<>();
            for (int j  =0 ; j < n; j++){
                temp.add(new String(queens[j]));
            }
            ans.add(temp);
        }
        for (int j  = 0; j < n; j++){
            if (!onPath[j] && !dig1[i + j]  && !dig2[i - j + n -1]){
                queens[i][j] = 'Q';
                onPath[j] = dig1[i + j] = dig2[i- j + n - 1] = true;
                dfs(i + 1);
                queens[i][j] = '.';
                onPath[j] = dig1[i + j] = dig2[i- j + n - 1] = false;
            }
        }
    }
}
算法
Java
春招
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
quan
quan
等级
内容推荐
更多
LEO 卫星星座管理平台
4
新手SpringSecurity6.0源码流程总结
3
🛰️ dtSpaceMap - 实时卫星追踪 3D 可视化平台
5
Spring Boot 如何处理跨域请求（CORS）：深度调研报告
3
#字节内推# 实习、校招、社招均有岗位
4
作者分享
更多
来上海啦，有没有租房的推荐哇，在徐汇区上班，酒店太贵了🤑。
4
好久没冒泡了，力扣热题100题分享也停更好久了。 但是也没浪费这段时间，这段时间总体是玩+面试+毕设。结果总体毕设差不多了，以及拿到了游族网络的实习offer，年后入职，java和kotlin，说是有转正机会。说实话还是有点犹豫的，因为后面有春招，我怕实习冲突，毕竟也不可能说把机会全压在这一个公司。然后又想去试试，毕竟也算是个国内比较大的游戏公司了，再刷个实习经历简历试试。 唉，这个就业形势，双非仔真的很难哦，我都开始做两手准备，测开，真的我这段时间也在看这方面的知识，我后面投大厂春招的话，真的会all in测开了碰碰运气了，java做第二手中厂或者游戏公司的准备。 我不喜欢说大话（社恐bushi）也没啥大目标，毕竟自己的实力和背景在这，所以我认为这也是我看的很开的原因，有份工作就不错了。。。说实话我还是这一届学院第一个有正儿八经的符合专业方向的应届生，然后总共也没几个有实习经历，有不少都去了学校合作的培训机构学游戏和嵌入式了，然后放弃秋招，直接春招，我看不懂。我玩的好的室友也是学游戏，然后让他年后来上海游族网络投递找我玩，哈哈哈。 不知不觉又写了怎么多，大家觉得我的年后安排合理吗（边实习边春招），大家可以分享一下自己的经历让我参考参考。😜 tips:上海租房好贵哦，公司在徐汇区，有推荐的嘛？
3
泛微网络深圳三面结束，挂了。。。。麻了，聊的挺好的啊，可能是我薪资要高了？？？不会吧，我问过朋友的，也有可能是我说我比较介意二开，更喜欢做新项目，太操蛋了，挂了，直接拉黑，没一点反馈。。。。 算了，反正也没什么意愿，因为做的业务不喜欢。 卧槽，成都的MOKA刚刚来电话了，周三面试，实习转正岗位（这又是什么时候投的？🤣） 转正9k * 15。 兄弟们这薪资怎么说？？？ 我先接面试试试我的技术水平吧。
2
力扣刷题Hot100
2
泛微网络实习面经
3
下载 APP