算法基础九

2023-12-14 20:39:08

螺旋矩阵2

给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。

示例 1:
输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]]
示例 2:
输入:n = 1 输出:[[1]]

解题思路:里面元素是1 - n*n,并且数组是顺序螺旋排列。


    public int[][] generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;

        int[][] matrix = new int[n][n];
        int row = 0;
        int column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        while(curNum <= maxNum) {
            matrix[row][column] = curNum;
            curNum++;
            int nextRow = row + directions[directionIndex][0];
            int nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
                directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向
            }

            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }

        return matrix;
    }

排列序列

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。

示例 1:
输入:n = 3, k = 3 输出:“213”
示例 2:
输入:n = 4, k = 9 输出:“2314”
示例 3:
输入:n = 3, k = 1 输出:“123”

解题思路:DFS

 public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        --k;
        StringBuffer ans = new StringBuffer();
        int[] valid = new int[n + 1];
        Arrays.fill(valid, 1);
        for (int i = 1; i <= n; ++i) {
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; ++j) {
                order -= valid[j];
                if (order == 0) {
                    ans.append(j);
                    valid[j] = 0;
                    break;
                }
            }
            k %= factorial[n - i];
        }
        return ans.toString();
    }

旋转链表

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1:
输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3]
示例 2:
输入:head = [0,1,2], k = 4 输出:[2,0,1]

public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }

不同路径

一个机器人位于一个 m * n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,问总共有多少条不同的路径?

示例 1:
输入:m = 3, n = 7 输出:28
示例 2:
输入:m = 3, n = 2 输出:3
示例 3:
输入:m = 7, n = 3 输出:28
示例 4:
输入:m = 3, n = 3 输出:6

解题思路:动态规划


 public int uniquePaths(int m, int n) {
     int[][] dp = new int[m][n];
     for (int i = 0; i < n; i++) {
         dp[0][i] = 1;
     }
     for (int i = 0; i < m; i++) {
         dp[i][0] = 1;
     }
     for (int i = 1; i < m; i++) {
         for (int j = 1; j < n; j++) {
             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
         }
     }
     return dp[m - 1][n - 1];  
 }

不同路径2

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1


 public int uniquePathsWithObstacles(int[][] obstacleGrid) {
     int len = obstacleGrid.length;
     int m = obstacleGrid[0].length;

     int[] f = new int[m];

     f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
     for (int i = 0; i < len; ++i) {
         for (int j = 0; j < m; ++j) {
             if (obstacleGrid[i][j] == 1) {
                 f[j] = 0;
                 continue;
             }
             if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                 f[j] += f[j - 1];
             }
         }
     }

     return f[m - 1];
 }

文章来源:https://blog.csdn.net/javaJasonjava/article/details/134912343
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。