Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 504
Subscribers
-124 hours
-127 days
-4830 days
Posts Archive
6 504
Задача: 22. Generate Parentheses #medium
Условие:
Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.Решение:
public List<String> generateParenthesis(int n) {
Set<String> ans = new HashSet<>();
ans = createParenthesis(n, ans);
System.out.println("Ans: " + ans);
return new ArrayList<>(ans);
}
private static Set<String> createParenthesis(int n, Set<String> currentList) {
java.util.Set<String> temp = new HashSet<>();
if (n <= 0) return new HashSet<>();
if (n == 1) {
temp.add("()");
return temp;
}
currentList = createParenthesis(n - 1, currentList);
System.out.println("At n-1 " + String.valueOf(n-1) + ": " + currentList);
for (String parenthesis : currentList) {
for (int i = 0; i <= parenthesis.length(); i++) {
String newStr;
if (i == 0) {
System.out.println("At 0 for " + parenthesis);
newStr = "()" + parenthesis;
System.out.println(newStr);
} else if (i == parenthesis.length()) {
System.out.println("At last for " + parenthesis);
newStr = parenthesis + "()";
System.out.println(newStr);
} else {
System.out.println("At " + i + " for " + parenthesis);
newStr = parenthesis.substring(0, i) + "()" + parenthesis.substring(i);
System.out.println(newStr);
}
temp.add(newStr);
}
}
currentList = temp;
return currentList;
}6 504
Задача: №21. Merge Two Sorted Lists #easy
Условие:
Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.Решение:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1!=null && list2!=null){
if(list1.val<list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}
else{
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
}
if(list1==null)
return list2;
return list1;
}
}6 504
Задача: 43. Multiply Strings #medium
Условие:
Учитывая два неотрицательных целых числа num1 и num2, представленных в виде строк, верните произведение num1 и num2, также представленное в виде строки. Примечание. Вы не должны использовать встроенную библиотеку BigInteger или напрямую преобразовывать входные данные в целое число.Решение:
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] pos = new int[m + n];
for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j, p2 = i + j + 1;
int sum = mul + pos[p2];
pos[p1] += sum / 10;
pos[p2] = (sum) % 10;
}
}
StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}6 504
Задача: 44. Wildcard Matching #hard
Условие:
Учитывая входную строку (s) и шаблон (p), реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и где: '?' Соответствует любому отдельному символу. '*' Соответствует любой последовательности символов (включая пусту
ю последовательность). Сопоставление должно охватывать всю входную строку (не частично).Решение:
class Solution {
public boolean isMatch(String s, String p) {
int n=s.length();
int m=p.length();
boolean dp[][]=new boolean[n+1][m+1];
dp[0][0]=true;
for(int i=1;i<n+1;i++){
dp[i][0]=false;
}
for(int i=1;i<m+1;i++){
if(p.charAt(i-1)=='*')
dp[0][i]=dp[0][i-1];
} for(int i=1;i<n+1;i++){
for(int j=1;j<m+1;j++){
if(s.charAt(i-1)==p.charAt(j-1)|| p.charAt(j-1)=='?'){
dp[i][j]=dp[i-1][j-1];
}else if(p.charAt(j-1)=='*'){
dp[i][j]=dp[i-1][j]||dp[i][j-1];
}else{
dp[i][j]=false;
}
}
}
return dp[n][m];
}
}6 504
Задача: 45. Jump Game II #medium
Условие:
Вам дан массив целых чисел с нулевым индексом длины n. Изначально вы находитесь на позиции nums[0]. Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь на nums[i], вы можете перейти к любому nums[i + j], где: 0 <= j <= nums[i] и я + j < п Возвращает минимальное количество переходов для достижения nums[n - 1]. Тестовые примеры генерируются таким образом, что вы можете достичь nums[n - 1].Решение:
class Solution {
public int jump(int[] nums) {
int near = 0, far = 0, jumps = 0;
while (far < nums.length - 1) {
int farthest = 0;
for (int i = near; i <= far; i++) {
farthest = Math.max(farthest, i + nums[i]);
}
near = far + 1;
far = farthest;
jumps++;
}
return jumps;
}
}
6 504
Задача: №20. Valid Parentheses #easy
Условие:
Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа. Открытые скобки должны закрываться в правильном порядке. Каждой закрывающей скобке соответствует открытая скобка того же тип а.Решение:
```class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>(); // create an empty stack
for (char c : s.toCharArray()) { // loop through each character in the string
if (c == '(') // if the character is an opening parenthesis
stack.push(')'); // push the corresponding closing parenthesis onto the stack
else if (c == '{') // if the character is an opening brace
stack.push('}'); // push the corresponding closing brace onto the stack
else if (c == '[') // if the character is an opening bracket
stack.push(']'); // push the corresponding closing bracket onto the stack
else if (stack.isEmpty() || stack.pop() != c) // if the character is a closing bracket
// if the stack is empty (i.e., there is no matching opening bracket) or the top of the stack
// does not match the closing bracket, the string is not valid, so return false
return false;
}
// if the stack is empty, all opening brackets have been matched with their corresponding closing brackets,
// so the string is valid, otherwise, there are unmatched opening brackets, so return false
return stack.isEmpty();
}
}
```
6 504
Задача: №19. Remove Nth Node From End of List #medium
Условие:
Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок.Решение:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy;
ListNode slow = dummy;
// Move fast pointer n steps ahead
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// Move both pointers until fast reaches the end
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// Remove the nth node from the end
slow.next = slow.next.next;
return dummy.next;
}
}6 504
Задача: №18. 4Sum #medium
Условие:
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что: 0 <= a, b, c, d < n a, b, c и d различны. nums[a] + nums[b] + nums[c] + nums[d] == target Вы можете вернуть ответ в любом порядке.Решение:
public class Solution {
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<>();
if (index >= len) {
return res;
}
if (k == 2) {
int i = index, j = len - 1;
while (i < j) {
// Find a pair
if (target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target - nums[i]);
res.add(temp);
// Skip duplicates
while (i < j && nums[i] == nums[i + 1]) i++;
while (i < j && nums[j - 1] == nums[j]) j--;
i++;
j--;
} else if (target - nums[i] > nums[j]) {
i++;
} else {
j--;
}
}
} else {
for (int i = index; i < len - k + 1; i++) {
// Use current number to reduce kSum into k-1Sum
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
if (temp != null) {
// Add previous results
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
// Skip duplicates
while (i < len - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return res;
}
}6 504
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.Решение:
```java
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return Collections.emptyList();
String[] phone_map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> output = new ArrayList<>();
backtrack("", digits, phone_map, output);
return output;
}
private void backtrack(String combination, String next_digits, String[] phone_map, List<String> output) {
if (next_digits.isEmpty()) {
output.add(combination);
} else {
String letters = phone_map[next_digits.charAt(0) - '2'];
for (char letter : letters.toCharArray()) {
backtrack(combination + letter, next_digits.substring(1), phone_map, output);
}
}
}
}
```
6 504
Задача: №16. 3Sum Closest #medium
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.Решение:
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
int closest = 0;
// int min = Integer.MAX_VALUE;
int max = Integer.MAX_VALUE;
Arrays.sort(nums);
//target += 1;
for(int i=0; i<n-2; i++){
int j=i+1;
int k = n-1;
// min = Math.min(min,max);
while(j<k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == target)
return sum;
else if(sum < target)
j++;
else
k--;
int diff = Math.abs(sum - target);
if(diff < max){
max = diff;
closest = sum;
}
}
}
return closest;
}
}