Цена за 48 часов в ленте | 2650,00 |
Цена за 1 час закрепления | — |
Взаимопиар | Нет |
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
public class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = 0, right = 0;
for (int weight : weights) {
left = Math.max(left, weight);
right += weight;
}
while (left < right) {
int mid = (left + right) / 2;
if (canShipInDays(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canShipInDays(int[] weights, int D, int capacity) {
int days = 1, total = 0;
for (int weight : weights) {
if (total + weight > capacity) {
days++;
total = 0;
}
total += weight;
}
return days <= D;
}
}
Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
class Solution {
public int findComplement(int num) {
int bitmask = num;
bitmask |= (bitmask >> 1);
bitmask |= (bitmask >> 2);
bitmask |= (bitmask >> 4);
bitmask |= (bitmask >> 8);
bitmask |= (bitmask >> 16);
return bitmask ^ num;
}
}
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]
Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
import java.util.ArrayList;
import java.util.List;
class CombinationIterator {
private List combinations;
public CombinationIterator(String characters, int combinationLength) {
combinations = new ArrayList<>();
int n = characters.length();
int k = combinationLength;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
if (Integer.bitCount(bitmask) == k) {
StringBuilder curr = new StringBuilder();
for (int j = 0; j < n; ++j) {
if ((bitmask & (1 << (n - j - 1))) != 0) {
curr.append(characters.charAt(j));
}
}
combinations.add(curr.toString());
}
}
}
public String next() {
return combinations.remove(combinations.size() - 1);
}
public boolean hasNext() {
return !combinations.isEmpty();
}
}
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
class Solution {
protected void backtrack(
int remain,
LinkedList comb,
int start,
int[] candidates,
List> results
) {
if (remain == 0) {
results.add(new ArrayList(comb));
return;
} else if (remain < 0) {
return;
}
for (int i = start; i < candidates.length; ++i) {
comb.add(candidates[i]);
this.backtrack(
remain - candidates[i],
comb,
i,
candidates,
results
);
comb.removeLast();
}
}
public List> combinationSum(int[] candidates, int target) {
List> results = new ArrayList>();
LinkedList comb = new LinkedList();
this.backtrack(target, comb, 0, candidates, results);
return results;
}
}
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
public class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if (i == grid.length - 1 && j != grid[0].length - 1) dp[i][j] =
grid[i][j] + dp[i][j + 1];
else if (
j == grid[0].length - 1 && i != grid.length - 1
) dp[i][j] = grid[i][j] + dp[i + 1][j];
else if (
j != grid[0].length - 1 && i != grid.length - 1
) dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
else dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
}
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue q1 = new LinkedList<>();
private Queue q2 = new LinkedList<>();
private int top;
public void push(int x) {
q2.add(x);
top = x;
while (!q1.isEmpty()) {
q2.add(q1.remove());
}
Queue temp = q1;
q1 = q2;
q2 = temp;
}
public void pop() {
q1.remove();
if (!q1.isEmpty()) {
top = q1.peek();
}
}
public boolean empty() {
return q1.isEmpty();
}
public int top() {
return top;
}
}
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
class Solution {
public static boolean hasAllCodes(String s, int k) {
int need = 1 << k;
boolean[] got = new boolean[need];
int allOne = need - 1;
int hashVal = 0;
for (int i = 0; i < s.length(); i++) {
hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
if (i >= k - 1 && !got[hashVal]) {
got[hashVal] = true;
need--;
if (need == 0) {
return true;
}
}
}
return false;
}
}
Input: deck = [1,2,3,4,4,3,2,1]
Output: true
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map count = new HashMap<>();
for (int num : deck) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int g = count.values().stream().reduce(this::gcd).orElse(0);
return g > 1;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
var isBoomerang = function(points) {
let [x1, y1] = points[0];
let [x2, y2] = points[1];
let [x3, y3] = points[2];
return (x1 !== x2 || y1 !== y2) &&
(x1 !== x3 || y1 !== y3) &&
(x2 !== x3 || y2 !== y3) &&
(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) !== 0;
};
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map parent = new HashMap<>();
List candidates = new ArrayList<>();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[]{parent.get(edge[1]), edge[1]});
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}
int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set cycle = orbit(root, parent).seen;
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
return edge;
}
}
}
Map> children = new HashMap<>();
for (int v : parent.keySet()) {
int pv = parent.get(v);
children.computeIfAbsent(pv, k -> new ArrayList<>()).add(v);
}
boolean[] seen = new boolean[N + 1];
Stack stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
stack.addAll(children.get(node));
}
}
}
for (boolean b : seen) {
if (!b) {
return candidates.get(0);
}
}
return candidates.get(1);
}
public OrbitResult orbit(int node, Map parent) {
Set seen = new HashSet<>();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}
class OrbitResult {
int node;
Set seen;
OrbitResult(int n, Set s) {
node = n;
seen = s;
}
}