头像

Fant.J




离线:2020-03-19 10:59


活动打卡代码 AcWing 51. 数字排列

Fant.J
2019-10-23 07:19
class Solution {
    public List<List<Integer>> permutation(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int length = nums.length;
        boolean [] visited = new boolean[length];
        dfs(res, nums, visited, new ArrayList<>());
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] nums, boolean[] visited, List<Integer> temp){
        // 如果长度够nums.length 则添加到res中并return
        if(temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        // 遍历nums 
        for(int i = 0; i< nums.length; i++){
            // 如果当前数字已读, 则跳到下一个, 如果重复的话
            if(visited[i] || i>0 &&  nums[i] == nums[i-1] && visited[i-1]){
                continue;
            }
            // 设置已读, temp存储
            visited[i] = true;
            temp.add(nums[i]);
            //System.out.println(temp);
            dfs(res, nums, visited, temp);
            visited[i] = false;
            temp.remove(temp.size()-1);
        }
    }
}


活动打卡代码 AcWing 77. 翻转单词顺序

Fant.J
2019-09-30 03:05
class Solution {
    public String reverseWords(String s) {
        // 反转整个字符串
        char[] chars = s.toCharArray();
        reverse(chars,0, chars.length-1);
        // 反转每个单词
        int index = 0;
        for(int i = 0; i< chars.length; i++){
            // 检测到' '就执行翻转
            if(chars[i] == ' '){
                reverse(chars, index, i-1);
                index = i+1;
            }
            // 处理最后一个字符
            if(i == chars.length-1){
                reverse(chars, index, i);
            }
        }
        return new String(chars);

    }
    public void reverse(char[] chars, int start, int end){
        for(int i = start; i< end; i++){
            char temp = chars[i];
            chars[i] = chars[end];
            chars[end] = temp;
            end--;
        }
        //System.out.println(Arrays.toString(chars));
    }
}



Fant.J
2019-09-30 02:45
class Solution {
    public List<List<Integer> > findContinuousSequence(int sum) {
       // 前后指针法
       // int i = 1;
       int j = 1;
       int count = 1; // 计数器
       List<List<Integer>> res = new ArrayList<>();
       // 这里的i就是前指针
       for(int i = 1; i<= sum/2; i++){

           // 如果计数值小鱼sum, 则j往后移动
            while(count < sum){
               count += ++j;
            }
            if(count == sum && i<j){
                List<Integer> temp = new ArrayList<>();
                // 将i-j之间的数放进去
                for(int k = i; k <= j; k++){
                    temp.add(k);
                }
                res.add(temp);
            }
            // 每次遍历完都要将当前的i去掉, 即i往后移动
            count -= i;
       }
       return res;
    }
}



Fant.J
2019-09-30 02:27
class Solution {
    public int[] findNumbersWithSum(int[] nums, int target) {
        // 存值Set
        Set<Integer> map = new HashSet<>();
        for(int i = 0; i< nums.length; i++){
            // 边放边比较,返回符合的结果
            map.add(nums[i]);
            int diff = target - nums[i];
            if(map.contains(diff)){
                return new int[]{nums[i],diff};
            }
        }
        return null;

    }
}


活动打卡代码 AcWing 80. 骰子的点数

Fant.J
2019-09-29 10:14
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {

    public int[] numberOfDice(int n) {
        // n~6n 一共有6n-n+1个数
        int[] res = new int[6 * n - n + 1];
        int[][]f=new int[n+1][6*n+1];
        f[0][0] = 1;
        // 次数
        for(int i = 1; i <= n ; i++){
            // 点数
            for(int j = 1; j <= i*6; j ++){
                // 点数从1开始减,一直
                for(int k = 1; k <=Math.min(j, 6); k ++)
                    f[i][j] += f[i-1][j - k];
            }
        }
        for (int i = n,j=0; i <= 6 * n; i++,j++) {
            res[j] = f[n][i];
        }
        return res;
    }


}



Fant.J
2019-09-28 15:30
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public int getMaxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int res[] = new int[cols];
        for(int i = 0; i< rows; i++){
            for(int j = 0; j< cols; j++){
                int up = 0;
                int left = 0;
                if(i > 0){
                    // 把res的当前元素赋值
                    up = res[j];
                }
                if( j > 0){
                    // 把res的上一个元素赋值
                    left = res[j-1];
                }
                res[j] = Math.max(up,left) + grid[i][j];
            }
        }
        return res[cols-1];
    }
}



Fant.J
2019-09-21 14:41
class Solution {
    public int[] printMatrix(int[][] matrix) {
        if(matrix == null|| matrix.length == 0){return new int[0];}
        int startX = 0;
        int endX = matrix.length;
        int startY = 0;
        int endY = matrix[0].length;
        //System.out.println(startX + " " + endX + " " + startY + " " + endY);
        int res[] = new int[endX * endY ];
        while((startX <= endX) && (startY<=endY)){
            printMatrix(res, matrix, startX, endX-1, startY, endY-1);
            startX++;
            startY++;
            endX--;
            endY--;
        }
        return res;
    }
    public int index = 0;
    public void printMatrix(int res[], int[][] matrix, int startX, int endX, int startY, int endY){
        // 向右 ➡
        if(startX == endX){
            // 说明只能竖着来了, 为什么要等于, 因为怕拉下最后一个元素了
            for(int i = startY; i <= endY; i++){
                res[index++] = matrix[startX][i];
            }
            return;
        }

        // 向下 ⬇
        if(startY == endY){
            // 说明只能竖着来了
            for(int i = startX; i <= endX; i++){
                res[index++] = matrix[i][startY];
            }
            return;
        }
        // 向右 ➡
        for(int i = startY; i < endY; i++){
            res[index++] = matrix[startX][i];
        }        
        // 向下 ⬇
        for(int i = startX; i < endX; i++){
            res[index++] = matrix[i][endY];
        }        
        // 向左 ⬅
        for(int i = endY; i > startY; i--){
            res[index++] = matrix[endX][i];
        }
        // 向上 ⬆  y不变x变
        for(int i = endX; i > startX; i--){
            res[index++] = matrix[i][startY];
        }

    }
}



Fant.J
2019-09-20 10:12
class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        // 如果两个数组为空, 直接返回true, 两个数组长度不等, 返回false
        if(pushV == null && popV == null){
            return true;
        }
        if(pushV.length != popV.length){
            return false;
        }
        // 新建一个栈, 将push一个一个放入, 并判断
        // 如果元素与popV的top元素相等, 则弹出popV, 否则继续在stack里放元素
        // 如果顺序正确的话, PopV应该会为空值
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i = 0; i< popV.length; i++){
            stack.push(pushV[i]);
            while(!stack.isEmpty() && stack.peek() == popV[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}



Fant.J
2019-09-20 10:11
class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        // 如果两个数组为空, 直接返回true, 两个数组长度不等, 返回false
        if(pushV == null && popV == null){
            return true;
        }
        if(pushV.length != popV.length){
            return false;
        }
        // 新建一个栈, 将push一个一个放入, 并判断
        // 如果元素与popV的top元素相等, 则弹出popV, 否则继续在stack里放元素
        // 如果顺序正确的话, PopV应该会为空值
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i = 0; i< popV.length; i++){
            stack.push(pushV[i]);
            while(!stack.isEmpty() && stack.peek() == popV[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}


活动打卡代码 AcWing 23. 矩阵中的路径

Fant.J
2019-09-18 13:25
class Solution {

    public boolean hasPath(char[][] matrix, String str) {
        if(matrix == null || str == "" || matrix.length == 0){
            return false;
        }
        int length = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        // 对元素进行打标
        boolean[][] visited = new boolean[rows][cols];

        for(int i = 0; i< rows; i++){
            for(int j = 0; j < cols; j++){
                // 遍历调用方法
                if(findPath(matrix, str, rows, cols, i, j, visited, length)){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean findPath(char[][] matrix, String str, int rows, int cols, int row, int col, boolean[][] visited, int length){
        int strLen = str.length();
        boolean flag = false;
        // System.out.println(str + " " + row +" " + col + " " + length+ " "+ visited[row][col] + " " + str.charAt(length));
        // 如果行号和列号合法, 并且打标为未路过
        if(row>=0 && row<rows && col>=0 && col<cols && visited[row][col] == false
                             && matrix[row][col] == str.charAt(length)){
            // 路长+1
            length++;
            visited[row][col] = true;
            if(length == strLen){
                return true;
            }
            flag = findPath(matrix, str, rows, cols, row+1, col, visited, length)||
                   findPath(matrix, str, rows, cols, row, col+1, visited, length)||
                   findPath(matrix, str, rows, cols, row-1, col, visited, length)||
                   findPath(matrix, str, rows, cols, row, col-1, visited, length);
            if(!flag){
                length--;
                visited[row][col] = false;
            }

        }
        return flag;
    }
}