leetcode之模拟刷题总结3

leetcode之模拟刷题总结3

1-转置矩阵
题目链接:题目链接戳这里!!!

思路:对应行的值放到对应列即可,easy题一道,先做一道easy题,自我安慰安慰。

class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length ;
        int n = matrix[0].length ;
        int [][] ans = new int [n][m] ;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                ans[j][i] = matrix[i][j] ;
            }
        }
        return ans ;
    }
}

leetcode之模拟刷题总结3
2-输出比赛匹配对
题目链接:题目链接戳这里!!!

思路:team[i-1]表示每个队伍的初始情况,一共需要经过第一层循环次数的配对,每轮配对,依次将第一个和最后一个配对,第二个和倒数第二个配对,依次类推。

class Solution {
    public String findContestMatch(int n) {
        String [] team = new String[n] ;
        for(int i=1; i<=n; i++){
            team[i-1] = i + "" ;
        }
        for(;n>1;n/=2){
            for(int i=0; i<n/2; i++){
                team[i] = "(" + team[i] + "," + team[n-i-1] + ")" ;
            }
        }
        return team[0] ;
    }
}

leetcode之模拟刷题总结3
3-翻转图像
题目链接:题目链接戳这里!!!

思路:image[i][j] != image[i][-1-j],如:0, 1,先交换变成1, 0,再取非又变回0, 1,故什么都不做。
image[i][j] == image[i][n-1-j],同时取非。

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int m = image.length;
        int n = image[0].length ;
   
        for(int i=0; i<m; i++){
            for(int j=0; j<(n%2==0 ? n/2 : n/2+1); j++){
                if(image[i][j]==image[i][n-j-1]){
                    if(j!=n-j-1){
                        image[i][j] = 1 - image[i][j] ;
                        image[i][n-j-1] = 1 - image[i][n-j-1] ;
                    }else{
                        image[i][j] = 1 - image[i][j] ;
                    }
                }
            }
        }
        return image ;
    }
}

leetcode之模拟刷题总结3
4-困于环中的机器人
题目链接:题目链接戳这里!!!

思路:(x,y)模拟当前坐标,face模拟当前面朝方向,一轮指令下来,只有不在原点并且面朝方向未改变的才最终回不到原点。

class Solution {
    public boolean isRobotBounded(String instructions) {
        int x = 0, y = 0 ; 
        int face = 0 ;
        int [] dx = {-1,0,1,0} ;
        int [] dy = {0,1,0,-1} ;
        char [] c = instructions.toCharArray() ;
        for(char ch : c){
            switch(ch){
                case 'R' : face = (face+1)%4 ; break ;
                case 'L' : face = (face+3)%4 ; break ;
                case 'G' : x += dx[face] ; y += dy[face]; break ;    
            }
        }
        return (x==0 && y==0) || (face % 4 != 0) ;
    }
}

leetcode之模拟刷题总结3
5-分糖果II
题目链接:题目链接戳这里!!!

思路:模拟分糖果的过程就可以,只要有糖果就可以继续分,每次糖果数大于等于应分的数量n,就分n,否则,分掉剩余全部糖果。

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int [] ans = new int [num_people] ;
        int n = 1 ;
        int i = 0 ;
        while(candies>0){
            if(candies-n>=0){
            ans[i] += n ;
            candies -= n ; 
            n++ ;
            i = (i+1)%num_people ;
        }else{
            ans[i] += candies ;
            break ;
        }
        }
        return ans ;
    }
}

leetcode之模拟刷题总结3
6-查询带键的排列
题目链接:题目链接戳这里!!!

思路:使用List集合模拟数组p的元素变动情况,每次将相应的元素从List集合删除并插入List集合头部。

class Solution {

    public int[] processQueries(int[] queries, int m) {
        List<Integer> p = new ArrayList<>() ;
        for(int i=0; i<m; i++){
            p.add(i+1) ;
        }
        int [] ans = new int [queries.length] ;
        for(int i=0; i<queries.length; i++){
            int x = f(queries[i],p) ;
            ans[i] = x ;
            p.remove(x) ;
            p.add(0,queries[i]) ;
        } 
        return ans ;
    }
    public int f(int value, List<Integer> p){
        for(int i=0; i<p.size(); i++){
            if(value==p.get(i)){
                return i ;
            }
        }
        return 0  ;
    }
}

leetcode之模拟刷题总结3
7-奇数值单元格的数目
题目链接:题目链接戳这里!!!

思路:使用两个数组row和column分别标记行和列是否是奇数。

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        boolean [] row = new boolean[m] ;
        boolean [] column = new boolean[n] ;
        int r = 0, c = 0 ;
        for(int i=0; i<indices.length; i++){
            row[indices[i][0]] = !row[indices[i][0]] ;
            column[indices[i][1]] = !column[indices[i][1]] ;
        }
        for(int i=0; i<m; i++){
          if(row[i]){
              r ++ ;
          }
        }
        for(int i=0; i<n; i++){
            if(column[i]){
                c ++ ;
            }
        }
        return r*n + c*m - 2*r*c ;

    }
}

leetcode之模拟刷题总结3
8-用栈操作构建数组
题目链接:题目链接戳这里!!!

思路:模拟整个过程就可以,从1到n,每次值等于target时候,将Push加入list集合,每次值小于target则需要进行target-i的Push和Pop。

class Solution {
    public List<String> buildArray(int[] target, int n) {
       List<String> ans = new ArrayList<>() ;
       int j = 0 ;
       for(int i=1; i<=n; i++){
           if(j > target.length-1 || target[j]<i){
               break ;
           }
           if(target[j]==i){
               ans.add("Push") ;
               j ++ ;
           }else if(target[j]>i){
               for(int k=0; k<target[j]-i; k++){
                   ans.add("Push") ;
                   ans.add("Pop") ;
               }
               i += (target[j]-i-1) ;
           }
           
       } 
       return ans ;
    }
}

leetcode之模拟刷题总结3
9-换酒问题
题目链接:题目链接戳这里!!!

思路:模拟换酒过程就可以,只要当前的酒瓶数大于兑换数,则循环,每轮循环求出喝掉的酒数res。同时更新酒瓶数numBottles。

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int res = 0 ;
        int temp = numBottles ;
        while(numBottles>=numExchange){
            int n = numBottles / numExchange ;
            res += (numBottles / numExchange) ;
            numBottles = (numBottles%numExchange) + n ;
        }
        return res+temp ;
    }
}

leetcode之模拟刷题总结3
10-找出数组游戏的玩家
题目链接:题目链接戳这里!!!

思路1:用list集合模拟整个过程,尽管也能AC,但是效率较低。

class Solution {
    public int getWinner(int[] arr, int k) {
        int [] res = new int [1000000] ;
        int max = 0 ;
        List<Integer> list = new ArrayList<>() ;
        for(int i=0; i<arr.length; i++){
            list.add(arr[i]) ;
            max = Math.max(max,arr[i]) ;
        }
        while(true){
            if(list.get(0)==max || list.get(1)==max){
                return max ;
            }
            if(list.get(0)>list.get(1)){
                int t = list.get(0) ;
                res[t] ++ ;
                int temp = list.get(1) ;
                list.remove(1) ;
                list.add(temp) ;
                if( res[t]==k){
                    return t ;
                }
            }else{
                int t = list.get(1) ;
                res[t] ++ ;
                int temp = list.get(0) ;
                list.remove(0) ;
                list.add(temp) ;
                if(res[t]==k){
                    return t ;
                }
            }
        }  
    }
}

leetcode之模拟刷题总结3
11-按既定顺序创建目标数组
题目链接:题目链接戳这里!!!

思路:先更新index数组,在更新结果数组ans。

class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
       int len = nums.length ;
       int [] ans = new int [len] ;
       for(int i=0; i<len; i++){
           for(int j=0; j<i; j++){
               index[j] += (index[j]>=index[i]) ? 1 : 0 ;
           }
       }
       for(int i=0; i<ans.length; i++){
           ans[index[i]] = nums[i] ;
       }
       return ans ;
    }
}

leetcode之模拟刷题总结3
12-可以攻击国王的王后
题目链接:题目链接戳这里!!!

思路:模拟过程,是用国王去攻击王后,沿着8个方向攻击,每次只要能攻击到一个就结束当前方向的攻击,如果超过边界仍攻击不到则结束当前方向的攻击。

class Solution {
     int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
     int dy[] = {-1,  0,  1, 1, 1, 0,-1,-1};
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> list = new ArrayList<>() ;
        int [][] grid = new int [8][8] ; 
        for(int i=0; i<queens.length; i++){
            grid[queens[i][0]][queens[i][1]] = 1 ;
        }
        for(int i=0; i<8; i++){
            int tx = king[0] + dx[i] ;
            int ty = king[1] + dy[i] ;
            while(tx>=0 && ty>=0 && tx<8 && ty<8){
                if(grid[tx][ty]==1){
                List<Integer> temp = new ArrayList<>() ;
                temp.add(tx) ;
                temp.add(ty) ;
                list.add(temp) ;
                 break ;
                }
                tx += dx[i] ;
                ty += dy[i] ;
            }
        }
        return list ;
    }
}

leetcode之模拟刷题总结3

上一篇:LeetCode 有效括号


下一篇:[leetcode] 344. Reverse String