leetcode刷题记录-1

towsum

public int[] twoSum(int[] nums, int target) {
       int[] index = new int[2];
       for (int i = 0; i < nums.length; i++) {
           for (int j = 0; j < nums.length; j++) {
               if (nums[i] + nums[j] == target && i != j) {
                   index[0] = i;
                   index[1] = j;
               }
           }
       }
       return index;
   }

• hashMap

  上面的方法在时间复杂堵上为O(n*n)，在数据过大时十分暴力，可以采用哈希表来检索

reverse

看到别人的做法才感觉好厉害，思路非常灵活。

这种根据原理判断整数是否溢出虽然比较科学，但感觉没有榜一大哥那么有灵性

public int reverse(int x) {
        int ret = 0;
        while(x != 0){
            // 先判断倒序数字是否满足条件
            if(ret>Integer.MAX_VALUE/10 || (ret==Integer.MAX_VALUE/10 && x>7)){
                return 0;
            }
            if(ret<Integer.MIN_VALUE/10 || (ret==Integer.MIN_VALUE/10 && x<-8)){
                return 0;
            }
            ret = ret*10+x%10;
            x /= 10;

        }
        return ret;
    }

isPalindrome

这道题和上面将数字倒序的思想是一样的

public boolean isPalindrome(int x){
     // 判断负数
     if(x<0){
         return false;
     }else {
         int temp = x, cmpNum=0;
         while (temp != 0){
             cmpNum = cmpNum*10 + temp%10;
             temp /= 10;
         }
         if(cmpNum==x){
             return true;
         }
         return  false;
     }
    }

romanToInt

这道题也可以用打表的思路，将不能单个字符表示的罗马数字全部穷举出来，这里只有6组，然后上哈希表

4, 9, 40, 90, 400, 900
IV IX XL  XC  CD   CM

从右到左来切割判断

public int romanToInt(String s) {
        int ret = 0;
        String[] strArr = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
        int[] num = {1,4,5,9,10,40,50,90,100,400,500,900,1000};

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < strArr.length; i++) {
            map.put(strArr[i],num[i]);
        }

        for (int i = 0; i < s.length();) {
            if (i+2<=s.length() && (map.containsKey(s.substring(i,i+2)))){
                ret += map.get(s.substring(i,i+2));
                i += 2;
                continue;
            }
            ret += map.get(s.substring(i,i+1));
            i += 1;
        }
        return ret;
    }

largestNumber

这道题折磨了一天，需要用到别人感觉并不复杂但是我看不懂的数学证明，所以数学证明是不可能证明的，用字符串解决

public String largestNumber(int[] nums){
        /// 不能用顺序排列
    	/// 数字排序和字符串排序思路都不同
        int n = nums.length;
        String[] numStr = new String[n];
        for (int i = 0; i < n; i++) {
            numStr[i] = String.valueOf(nums[i]);
        }

        /// compareTo返回前字符串比较字符ASCII与后字符串比较字母ASCII的差值
        Arrays.sort(numStr,(a, b)->{     // 使用lambda重写sort函数，使其字符串逆序排序
            return (b+a).compareTo(a+b); // 如果后面加起来比前面大的话，返回1
                                         // 否则返回0
        });
        System.out.println(Arrays.toString(numStr));

        if(numStr[0].equals("0")){
            return "0";
        }

        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < numStr.length; i++) {
            ret.append(numStr[i]);
        }
        return ret.toString();
    }

黑白方格画

一道纯考排列组合的数学题，两年没有碰过这些考智商的东西，脑袋没转过弯来，虽然里面包含的数学知识也不是很复杂，

public int factorial(int a){
       if(a == 1 || a == 0)
           return 1;
       return factorial(a-1)*a;
   }
   public int combine(int n, int a){
       return factorial(n)/(factorial(a)*factorial(n-a));
   }

   public int paintingPlan(int n, int k) {
       if (n*n == k){
           return 1;
       }else if(n > k){
           return 0;
       }
       int ret = 0;
       for(int a=0; a<=n; a++){
           for(int b=0; b<=n; b++){
               if(k == n*(a+b)-a*b){
                   ret += combine(n, a)*combine(n, b);
               }
           }
       }
       return ret;
   }

跳水板 && 青蛙跳台阶

这道题如果用纯递归的方法去做属实不行，时间复杂度太高了<O(2^n)>，斐波那契数列的性质是一样的，前面两个数决定后一个数，动态规划

• 递归方法

public int divingBoard(int shorter, int longer, int k){
        if (k < 0)return 0;
        if (k == 0)return 1;
        return climb(shorter, longer, k - 1) + climb(shorter, longer, k - 2);
    }

• 非递归方法

public int[] divingBoard(int shorter, int longer, int k) {
        if(k == 0){
            return new int[0];
        } else if (shorter == longer){
            int[] ret = {shorter * k};
            return ret;
        }
        int[] board = new int[k + 1];
        int shortest = k * shorter;
        for (int i = 0; i < k + 1; i++) {
            board[i] = shortest + i * (longer - shorter);
        }
        return board;
    }

重要的员工

public int retSubImp(Employee pre, List<Employee> employees){
        if (pre.subordinates.isEmpty()){
            return 0;
        }
        int imp = 0;
        for (Integer sub :
                pre.subordinates) {
            for (Employee employee :
                   employees ) {
                if (sub == employee.id){
                    imp += employee.importance;
                    imp += retSubImp(employee, employees);
                }
            }
        }
        return imp;
    }

    public int getImportance(List<Employee> employees, int id) {
        int imp = 0;
        for (Employee staff :
                employees) {
            if (staff.id == id){
                imp += staff.importance;
                for (Integer subid :
                        staff.subordinates) {
                    imp += retSubImp(staff, employees);
                    break;
                }
            }
        }
        return imp;
    }

扫雷

这道题有点好玩😛，dfs搜索一共三个步骤

• 判断该坐标是否为雷，如果是雷就直接结束游戏
• 如果不是雷，判断坐标周围雷的个数，如果个数不为0，则标记雷的个数，结束游戏
• 如果周围没有雷，则递归检索周围没有越界的坐标

int width;
int height;
int countBomb = 0;
int[][] step = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
                {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
char[] dic = {'0', '1','2','3','4','5','6','7','8'};

public void updateBoardDfs(char[][] board, int x, int y, int[][] sign){
    if (x >= height || x < 0 || y >= width || y < 0 || sign[x][y] == 1){
        return;
    }
    // 首先判断周围8个方向是否有雷
    getCountBomb(board, x, y);
    if (countBomb != 0){
        board[x][y] = dic[countBomb];
        countBomb = 0;
        return;
    }
    // 八个方向
    for (int i = 0; i < 8; i++) {
        int post_x = x + step[i][0];
        int post_y = y + step[i][1];
        board[x][y] = 'B';
        sign[x][y] = 1;
        updateBoardDfs(board, post_x, post_y, sign);
    }
}

public void getCountBomb(char[][] board, int x, int y){
    for (int i = 0; i < 8; i++) {
        int post_x = x + step[i][0];
        int post_y = y + step[i][1];
        if (post_x >= height || post_x < 0 || post_y >= width || post_y < 0) continue;
        if (board[post_x][post_y] == 'M')
            countBomb++;
    }
}

/*
 * 判断点击是否为雷
 * 检索周围8个方向是否有雷，无雷标记为B
 * 有雷标检索有雷个数，然后标记数字
 * */
public char[][] updateBoard(char[][] board, int[] click){
    width = board[0].length;
    height = board.length;
    int[][] sign = new int[height][width];
    // 玩家点击矩阵坐标
    char playerClickPot = board[click[0]][click[1]];
    if (playerClickPot == 'M'){
        board[click[0]][click[1]] = 'X';
    }else {
        updateBoardDfs(board, click[0], click[1],  sign);
    }
    return board;
}

在D天内送达包裹的能力

看题解打卡下班

class Solution {
     public int shipWithinDays(int[] weights, int D) {
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        while (left < right){
            int middle = (left+right) >> 1;
            int needDay = 1;
            int sum = 0;
            for (int goodWeight : weights){
                if (sum + goodWeight > middle){
                    needDay++;
                    sum = 0;
                }
                sum += goodWeight;
            }
            if (needDay <= D){
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return right;
    }

}