【题解】leetcode_biweek_52_problems 题解

leetcode_biweek_52_problems

results:
  1. problem1: AC
  2. problem2: AC
  3. problem3:AC + 3 failed-try
  4. problem4:not try


1. 1859. Sorting the Sentence:
// AC:
// Runtime: 5 ms, faster than 100.00% of Java online submissions for Sorting the Sentence.
// Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Sorting the Sentence.
// Using tree map to sort key.
// T:O(n), S:O(n), n = len(s)
//
class Solution {
   public String sortSentence(String s) {
       TreeMap<Integer, String> record = new TreeMap<>();
       String[] sArr = s.split(" ");
       for (String item: sArr) {
           Integer index = Integer.parseInt(String.valueOf(item.charAt(item.length() - 1)));
           record.put(index, item.substring(0, item.length() - 1));
       }
       StringBuilder ret = new StringBuilder();
       for (Integer i: record.keySet()) {
           ret.append(record.get(i));
           ret.append(" ");
       }
       return ret.substring(0, ret.length() - 1);
   }
}


2. 1860. Incremental Memory Leak
// AC:
// Runtime: 8 ms, faster than 100.00% of Java online submissions for Incremental Memory Leak.
// Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Incremental Memory Leak.
// simulation... it seems that brute-force can pass. Any way I haven't thought out better solution...
// complexity:  T: O(sqrt(max(m1, m2))), S: O(1)
//
class Solution {
   public int[] memLeak(int memory1, int memory2) {
       int second = 1;
       while (memory1 >= second || memory2 >= second) {
           if (memory1 >= memory2) {
               if (memory1 >= second) {
                   memory1 -= second;
               } else {
                   break;
               }
           } else {
               if (memory2 >= second) {
                   memory2 -= second;
               } else {
                   break;
               }
           }
           second++;
       }
       int[] ret = new int[]{second, memory1, memory2};
       return ret;
   }
}


3.1861. Rotating the Box
// AC:
// Runtime: 2056 ms, faster than 50.00% of Java online submissions for Rotating the Box.
// Memory Usage: 64.7 MB, less than 100.00% of Java online submissions for Rotating the Box.
// my thought: using string split(obstacle), and combine every part to make stone fall down.
// complexity: T:O(m * n), S:O(m * n)
//
class Solution {
   public char[][] rotateTheBox(char[][] box) {
       int row = box.length, col = box[0].length;
       char[][] ret = new char[col][row];
       List<List<Character>> record = new LinkedList<>();
       for (int i = 0; i < row; i++) {
           // 逐行下落
           List<Character> temp = new LinkedList<>();
           StringBuilder tempStr = new StringBuilder();
           for (int j = 0; j <= col - 1; j++) {
               tempStr.append(box[i][j]);
           }
           tempStr.append("#");
           String[] tempArr = tempStr.toString().split("\\*");
           if (tempArr.length == 0) {
               for (int t = 0; t < tempStr.length(); t++) {
                   temp.add('*');
               }
           } else {
               for (String part : tempArr) {
                   if (part.isEmpty()) {
                       temp.add('*');
                       continue;
                   }
                   int countEmpty = 0, countStone = 0;
                   for (char item : part.toCharArray()) {
                       if (item == '#') {
                           countStone++;
                       }
                       if (item == '.') {
                           countEmpty++;
                       }
                   }
                   for (int k = 0; k < countEmpty; k++) {
                       temp.add('.');
                   }
                   for (int k = 0; k < countStone; k++) {
                       temp.add('#');
                   }

                   temp.add('*');
               }
               // 去除末尾 *
               if (temp.get(temp.size() - 1) == '*') {
                   temp.remove(temp.size() - 1);
               }
           }
           temp.remove(temp.size() - 1);
           record.add(temp);
       }
       // rotate
       for (int i = 0; i < col; i++) {
           for (int j = 0; j < row; j++) {
               ret[i][j] = record.get(row - 1 - j).get(i);
           }
       }

       return ret;
   }
}


4. 1862. Sum of Floored Pairs:



发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

«   2021年6月   »
123456
78910111213
14151617181920
21222324252627
282930
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接

    Powered By Z-BlogPHP 1.5.2 Zero

    Copyright liuyang1.com. 转载文章,请注明出处。谢谢!