想上岸 找上岸

No.1

Check if the Sentence Is Pangram

解题思路

简单遍历字符串判断

非英文字母字符直接返回false

否则记录不同字符的个数是否满足26个

代码展示

public boolean checkIfPangram(String sentence) { 
   if (sentence == null || sentence.length() == 0) { 
       return false; 
   } 
   Set<Character> set = new HashSet<>(); 
   for (char c : sentence.toCharArray()) { 
       if (c - 'a' < 0 || c - 'a' >= 26) { 
           return false; 
       } 
       set.add(c); 
   } 
   return set.size() == 26; 
}

No.2 Maximum Ice Cream Bars

解题思路

贪心的去买雪糕

无需看成背包问题，TLE or MLE

代码展示

public int maxIceCream(int[] costs, int coins) { 
   if (costs == null || costs.length == 0) { 
       return 0; 
   } 
   int n = costs.length; 
   int res = 0; 
   // 排序从小到大买即可 
   Arrays.sort(costs); 
   for (int cost : costs) { 
       if (coins > cost) { 
           res += 1; 
           coins -= cost; 
       } 
       else { 
           return res; 
       } 
   } 
   return res; 
}

No.3 Single-Threaded CPU

解题思路

堆 + 扫描线结合

添加第三位信息，构建自己的 task model

按时间起始时间从小打到排序

minHeap的操作

代码展示

public int[] getOrder(int[][] tasks) { 
   int n = tasks.length; 
   // 添加第三维度信息index 
   int[][] newTasks = new int[n][3]; 
   for (int i = 0; i < tasks.length; i++) { 
       newTasks[i][0] = tasks[i][0]; 
       newTasks[i][1] = tasks[i][1]; 
       newTasks[i][2] = i; 
   } 
   // 按照时间先后排序 
   Arrays.sort(newTasks, Comparator.comparingInt(x -> x[0])); 
   PriorityQueue<Integer> minHeap = new PriorityQueue<>((x, y) -> { 
       if (newTasks[x][1] == newTasks[y][1]) { 
           return newTasks[x][2] - newTasks[y][2]; 
       } 
       return newTasks[x][1] - newTasks[y][1]; 
   }); 
   int curTime = 1; 
   int[] res = new int[n]; 
   // task index offer to heap 
   int i = 0; 
   // task index add to result 
   int j = 0; 
   while (i < n) { 
       while (i < n && (minHeap.isEmpty() || curTime >= newTasks[i][0])) { 
           curTime = Math.max(curTime, newTasks[i][0]); 
           minHeap.offer(i++); 
       } 
       // 从heap中拿出执行 
       if (!minHeap.isEmpty()) { 
           int[] task = newTasks[minHeap.poll()]; 
           res[j++] = task[2]; 
           curTime += task[1]; 
       } 
   } 
   while (!minHeap.isEmpty()) { 
       res[j++] = newTasks[minHeap.poll()][2]; 
   } 
   return res; 
}

No.4 Find XOR Sum of All Pairs Bitwise AND

解题思路

位运算推导，纯数学题

前置技能：a ⊕ b = (~a & b) | (a & ~b)

因此：(a & b1) ⊕ (a & b2) = [(~a | ~b1) & (a | b2 )] | [[(~a | ~b2) & (a | b1 )]

因此：(a & b1) ⊕ (a & b2) = a & (b1 ⊕ b2)

原题：(a & b1) ⊕ (a1 & b2) (a1 & b3) ⊕(a1 & bm) .......⊕(an & bm)

等同于：[a1 & (b1⊕  b2 ⊕.....bm)] ⊕ [a2 & (b1⊕  b2 ⊕.....bm)] ⊕......⊕ [an & (b1⊕  b2 ⊕.....bm)] 

位运算学习欢迎咨询上岸算法一对一定制辅导

代码展示

public int getXORSum(int[] arr1, int[] arr2) { 
   int sumArray2 = 0; 
   int res = 0; 
   for (int i : arr2) { 
       sumArray2 ^= i; 
   } 
   for (int i : arr1) { 
       res ^= (i & sumArray2); 
   } 
   return res; 
}