LC 150 (first part) Flashcards
(41 cards)
1
Q
- Merge Sorted Array
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
A
public void merge(int[] nums1, int m, int[] nums2, int n) {
int writer = nums1.length - 1;
int reader1 = m - 1;
int reader2 = n - 1;
while (writer >= 0 && reader1 >= 0 && reader2 >= 0) {
if (nums1[reader1] > nums2[reader2]) {
nums1[writer] = nums1[reader1];
reader1--;
} else {
nums1[writer] = nums2[reader2];
reader2--;
}
writer--;
}
// If there are remaining elements in nums2, copy them to nums1
while (reader2 >= 0) {
nums1[writer] = nums2[reader2];
writer--;
reader2--;
}
}
2
Q
- Remove Element
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
A
public int removeElement(int[] nums, int val) {
int j = 0;
for(int i = 0; i< nums.length; i++){
if(nums[i] != val){
nums[j] = nums[i];
j++;
}
}
return j;
}
3
Q
- Remove Duplicates from Sorted Array
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
A
class Solution {
public int removeDuplicates(int[] nums) {
int j = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[j] = nums[i];
j++;
}
}
return j;
}
}
4
Q
- Majority Element
Input: nums = [3,2,3]
Output: 3
A
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
5
Q
- Rotate Array
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
A
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
6
Q
- Best Time to Buy and Sell Stock
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
A
class Solution {
public int maxProfit(int[] prices) {
int lowestPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int i = 0; i < prices.length; i++){
}
}
}
7
Q
- Best Time to Buy and Sell Stock II
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
A
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
8
Q
- Jump Game
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
A
public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}
9
Q
- Jump Game II
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
A
class Solution {
public int jump(int[] nums) {
// The starting range of the first jump is [0, 0]
int answer = 0, n = nums.length;
int curEnd = 0, curFar = 0;
for (int i = 0; i < n - 1; ++i) {
// Update the farthest reachable index of this jump.
curFar = Math.max(curFar, i + nums[i]);
// If we finish the starting range of this jump,
// Move on to the starting range of the next jump.
if (i == curEnd) {
answer++;
curEnd = curFar;
}
}
return answer;
}
}
10
Q
- Product of Array Except Self
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
A
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] L = new int[length];
int[] R = new int[length];
int[] answer = new int[length];
L[0] = 1;
for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1];
}
R[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1];
}
for (int i = 0; i < length; i++) {
answer[i] = L[i] * R[i];
}
return answer;
}
}
11
Q
- Length of Last Word
Input: s = “Hello World”
Output: 5
Explanation: The last word is “World” with length 5.
A
class Solution {
public int lengthOfLastWord(String s) {
s = s.trim(); // trim the trailing spaces in the string
return s.length() - s.lastIndexOf(" ") - 1;
}
}
12
Q
- Longest Common Prefix
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”
A
class Solution {
public String longestCommonPrefix(String[] strs) {
StringBuilder result = new StringBuilder();
for(int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (int j = 1; j< strs.length; j++) {
if(i > strs[j].length()-1){
return result.toString();
}
char b = strs[j].charAt(i);
if(b!=c){
return result.toString();
}
}
result.append(c);
}
return result.toString();
}
}
13
Q
- Reverse Words in a String
Input: s = “the sky is blue”
Output: “blue is sky the”
A
class Solution {
public String reverseWords(String s) {
String[] split = s.trim().split(" ");
int left = 0;
int right = split.length - 1;
while( left < right ) {
String temp = split[left];
split[left] = split[right];
split[right] = temp;
left++;
right--;
}
StringBuffer result = new StringBuffer();
for(String s1: split) {
if(s1!=""){
result.append(s1);
result.append(" ");
}
}
return result.toString().trim();
}
}
14
Q
- Zigzag Conversion
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
A
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
StringBuilder answer = new StringBuilder();
int n = s.length();
int charsInSection = 2 * (numRows - 1);
for (int currRow = 0; currRow < numRows; ++currRow) {
int index = currRow;
while (index < n) {
answer.append(s.charAt(index));
// If currRow is not the first or last row
// then we have to add one more character of current section.
if (currRow != 0 && currRow != numRows - 1) {
int charsInBetween = charsInSection - 2 * currRow;
int secondIndex = index + charsInBetween;
if (secondIndex < n) {
answer.append(s.charAt(secondIndex));
}
}
// Jump to same row's first character of next section.
index += charsInSection;
}
}
return answer.toString();
}
}
15
Q
- Find the Index of the First Occurrence in a String
Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
A
class Solution {
public int strStr(String haystack, String needle) {
int m = needle.length();
int n = haystack.length();
for (int windowStart = 0; windowStart <= n - m; windowStart++) {
for (int i = 0; i < m; i++) {
if (needle.charAt(i) != haystack.charAt(windowStart + i)) {
break;
}
if (i == m - 1) {
return windowStart;
}
}
}
return -1;
}
}
16
Q
- Valid Palindrome
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
A
class Solution {
public boolean isPalindrome(String s) {
for( int i = 0, j = s.length() - 1;
i < j;
i++, j--
) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
// Skip non-alphanumeric characters from the end
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))){
return false;
}
}
return true;
}
}
17
Q
- Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Input: s = “abc”, t = “ahbgdc”
Output: true
Input: s = “axc”, t = “ahbgdc”
Output: false
A
class Solution {
public boolean isSubsequence(String s, String t) {
int sPointer = 0;
int tPointer = 0;
if(s.equals("")) return true;
while(sPointer < s.length() &&tPointer < t.length()) {
if(s.charAt(sPointer) == t.charAt(tPointer)){
sPointer++;
tPointer++;
if(sPointer >= s.length()) return true;
} else {
tPointer++;
}
}
return false;
}
}
18
Q
- Two Sum II - Input Array Is Sorted
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
A
class Solution {
public int[] twoSum(int[] numbers, int target) {
int lo = 0, hi = numbers.length - 1;
while (lo < hi) {
int curSum = numbers[lo] + numbers[hi];
if (curSum == target) {
return new int[]{lo + 1, hi + 1};
} else if (curSum > target) {
hi--;
} else {
lo++;
}
}
return new int[]{-1, -1};
}
}
19
Q
- Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
A
class Solution {
public int maxArea(int[] height) {
int max = 0;
int l = 0;
int r = height.length - 1;
while(l<r){
int h = Math.min(height[l], height[r]);
int w = r-l;
max = Math.max(max, h * w);
if(height[l] < height[r]){
l++;
} else {
r--;
}
}
return max;
}
}
20
Q
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Input: ransomNote = “a”, magazine = “b”
Output: false
Input: ransomNote = “aa”, magazine = “ab”
Output: false
A
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character,Integer> magazineMap = new HashMap<>();
for(Character c: magazine.toCharArray()){
magazineMap.put(c, magazineMap.getOrDefault(c,0) +1);
}
for(Character c: ransomNote.toCharArray()){
if(magazineMap.containsKey(c)){
int count = magazineMap.get(c);
if(count < 1){
return false;
} else {
magazineMap.put(c, count - 1);
}
} else {
return false;
}
}
return true;
}
}
21
Q
- Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Example 1:
Input: s = “egg”, t = “add”
Output: true
Example 2:
Input: s = “foo”, t = “bar”
Output: false
A
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length()) return false;
HashMap<Character,Character> map = new HashMap<Character,Character>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(map.containsKey(c) ){
if(map.containsKey(c)){
char mapped = map.get(c);
if(mapped != t.charAt(i)) {
return false;
}
}
}
else {
if(map.containsValue(t.charAt(i))) return false;
map.put(c, t.charAt(i));
}
}
return true;
}
}
22
Q
- Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
Example 1:
Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Example 2:
Input: pattern = “abba”, s = “dog cat cat fish”
Output: false
Example 3:
Input: pattern = “aaaa”, s = “dog cat cat dog”
Output: false
A
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] splitted = s.split(" ");
if(pattern.length() != splitted.length) return false;
HashMap<Character, String> map = new HashMap<>();
HashMap<String, Character> reverseMap = new HashMap<>();
for(int i = 0; i < pattern.length(); i++) {
Character c = pattern.charAt(i);
if(map.containsKey(c)){
String val = map.get(c);
if(!val.equals(splitted[i])) return false;
} else if (reverseMap.containsKey(splitted[i])) {
return false;
}
else {
map.put(c, splitted[i]);
reverseMap.put(splitted[i], c);
}
}
return true;
}
}
23
Q
- Valid Anagram
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
A
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
return sort(s).equals(sort(t));
}
public String sort(String s) {
char[] cArr = s.toCharArray();
java.util.Arrays.sort(cArr);
return new String(cArr);
}
}
24
Q
- Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
A
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List> map = new HashMap<String, List>();
for(String s: strs) {
String key = sort(s);
if(map.containsKey(key)) {
map.get(key).add(s);
} else {
LinkedList<String> list = new LinkedList<>();
list.add(s);
map.put(key, list);
}
}
List<List<String>> result = new LinkedList<List<String>>();
//for(Entry<String, List> e: map.entrySet()) {
// result.add(e.getValue());//returns list
//}
result.addAll(map.values());
return result;
}
public String sort(String s) {
char[] cArr = s.toCharArray();
java.util.Arrays.sort(cArr);
return new String(cArr);
}
}
25
1. Two Sum
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
```
class Solution {
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
// In case there is no solution, we'll just return null
return null;
}
}
```
26
202. Happy Number
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
```
class Solution {
public boolean isHappy(int n) {
HashSet set = new HashSet<>();
return helper(n, set);
}
public boolean helper(int n, HashSet previous) {
if(previous.contains(n)) return false;
previous.add(n);
String nStr = Integer.toString(n);
int sum = 0;
for(char c : nStr.toCharArray()) {
int cAsInt= Character.getNumericValue(c);
int squared = cAsInt * cAsInt;
sum += squared;
}
if(sum==1) return true;
return helper(sum, previous);
}
}
```
27
219. Contains Duplicate II
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
```
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
//number, last position in array
HashMap map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) {
int lastPos = map.get(nums[i]);
if(i - lastPos <= k) return true;
map.put(nums[i], i);
} else {
map.put(nums[i], i);
}
}
return false;
}
}
````
28
128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
```
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length <= 1) return nums.length;
Arrays.sort(nums);
int longestSequence = 1;
int currentSequence = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentSequence++;
} else if (nums[i] != nums[i - 1]) {
currentSequence = 1;
}
longestSequence = Math.max(longestSequence, currentSequence);
}
return longestSequence;
}
}
```
29
228. Summary Ranges
You are given a sorted unique integer array nums.
A range [a,b] is the set of all integers from a to b (inclusive).
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
"a->b" if a != b
"a" if a == b
Example 1:
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Example 2:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
```
class Solution {
public List summaryRanges(int[] nums) {
int start = 0;
List result = new LinkedList<>();
for(int i = 0; i < nums.length; i++) {
if((i+1 < nums.length) && nums[i] + 1 != nums[i+1]) {
if(start == i) {
result.add(Integer.toString(nums[i]));
} else {
String s = Integer.toString(nums[start]) + "->" + Integer.toString(nums[i]);
result.add(s);
}
start = i+1;
}
if((i+1 >= nums.length)){
if(start == i) {
result.add(Integer.toString(nums[i]));
} else {
String s = Integer.toString(nums[start]) + "->" + Integer.toString(nums[i]);
result.add(s);
}
}
}
return result;
}
}
```
30
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
```
class MinStack {
Stack minStack = new Stack<>();
Node top = null;
public MinStack(){
}
private class Node {
private int val;
private Node next;
private Node(int v) {
val = v;
}
}
public void push(int val) {
//super.push(val);
Node oldTop = top;
top = new Node(val);
top.next = oldTop;
if(minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
//Integer result = (Integer) super.pop();
if(top==null) {
throw new RuntimeException();
}
if(top.val == getMin()) {
minStack.pop();
}
Node newTop = top.next;
top = newTop;
}
public int top() {
if(top==null) {
throw new RuntimeException();
}
return top.val;
}
public int getMin() {
if(minStack.isEmpty()) {
return 0;
}
return minStack.peek();
}
}
```
31
141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
```
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
```
32
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
```
public ListNode addTwoNumbers(ListNode n1, ListNode n2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while(n1 != null || n2 != null || carry != 0) {
int int1 = (n1 == null) ? 0 : n1.val;
int int2 = (n2 == null) ? 0 : n2.val;
int sum = int1 + int2 + carry;
int listval = sum % 10;
ListNode newguy = new ListNode(listval);
tail.next = newguy;
carry = (sum >= 10) ? 1 : 0;
if(n1!=null)n1=n1.next;
if(n2!=null)n2=n2.next;
tail=tail.next;
}
ListNode head = dummy.next;
dummy.next = null;
return head;
}
```
33
21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
```
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
else if(l2 == null) return l1;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(l1 != null && l2!= null){
if(l1.val <= l2.val){
curr.next = l1;
l1 = l1.next;
}else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 == null? l2:l1;
return dummy.next;
}
```
34
138. Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
```
import java.util.HashMap;
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
HashMap visited = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) return null;
// Check if the node has already been visited
if (visited.containsKey(head)) {
return visited.get(head);
}
// Create a new node with the current value
Node newGuy = new Node(head.val);
// Mark the current node as visited
visited.put(head, newGuy);
// Recursively copy the next and random pointers
newGuy.next = copyRandomList(head.next);
newGuy.random = copyRandomList(head.random);
return newGuy;
}
}
```
35
25. Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
```
class Solution {
private class Segment{
ListNode head;
ListNode tail;
ListNode startOfNext;
int remainderK;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyhead = new ListNode(0);
ListNode tail = dummyhead;
ListNode current = head;
while(current!=null) {
Segment currentSegment = nextKNodes(current, k);
if(length(currentSegment.head) == k) {
ListNode startOfReversed = reverse(currentSegment.head);
tail.next = startOfReversed;
tail = currentSegment.head;
} else {
tail.next = currentSegment.head;
tail = currentSegment.tail;
current = null;
continue;
}
current = currentSegment.startOfNext;
System.out.println();
}
return dummyhead.next;
}
int length(ListNode current) {
int length = 0;
while(current!=null) {
length++;
current = current.next;
}
return length;
}
//takes long list 1->2->3->4->5->6->7
//returns first k elements
//k=3, returns 1->2->3
Segment nextKNodes(ListNode head, int k) {
ListNode current = head;
while(current!=null && k>1) {
current = current.next;
k--;
}
Segment result = new Segment();
result.head = head;
result.tail = current;
result.startOfNext = (current==null) ? null : current.next;
result.remainderK = k;
if(current!=null) current.next = null;
return result;
}
ListNode reverse(ListNode n) {
ListNode previous = null;
ListNode current = n;
ListNode next = null;
while(current!=null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
}
```
36
19. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
```
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i
37
82. Remove Duplicates from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
```
(non optimal solution)
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null|| head.next==null ){
return head;
}
HashMapmap=new HashMap<>();
ListNode dummy=new ListNode(0);
ListNode prev=dummy;
ListNode curr=head;
while(curr!=null){
if(map.containsKey(curr.val)){map.put(curr.val,map.get(curr.val)+1);}
else{map.put(curr.val,1);}
curr=curr.next;
}
curr=head;
while(curr!=null){
if(map.get(curr.val)==1){
prev.next=curr;
prev=curr;}
curr=curr.next;}
if(prev.next!=null){
prev.next=null;
}
return dummy.next;
}
}
```
38
61. Rotate List
Given the head of a linked list, rotate the list to the right by k places.
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Input: head = [0,1,2], k = 4
Output: [2,0,1]
```
public ListNode rotateRight(ListNode head, int k) {
if(head==null) return null;
//find length
ListNode fast = head;
ListNode slow = head;
int length = 1;
while(fast.next!=null) {
fast=fast.next;
length++;
}
int moveSlow = k % length;
for(int i=length-k%length;i>1;i--) {
slow = slow.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
//move to modk, cut the list
//attach list to begining
}
```
39
86. Partition List
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
```
public ListNode partition(ListNode head, int x) {
ListNode current = head; // Pointer to traverse the original list
ListNode lessDummy = new ListNode(0); // Dummy node for nodes < x
ListNode lessTail = lessDummy; // Tail pointer for less list
ListNode greaterDummy = new ListNode(0); // Dummy node for nodes >= x
ListNode greaterTail = greaterDummy; // Tail pointer for greater list
// Traverse the original list
while (current != null) {
if (current.val < x) {
// Append current node to the less list
lessTail.next = new ListNode(current.val);
lessTail = lessTail.next; // Move the tail pointer
} else {
// Append current node to the greater list
greaterTail.next = new ListNode(current.val);
greaterTail = greaterTail.next; // Move the tail pointer
}
current = current.next; // Move to the next node
}
// Attach the greater list to the end of the less list
lessTail.next = greaterDummy.next;
// Return the modified list starting from the first node after the less dummy node
return lessDummy.next;
}
```
40
146. LRU Cache
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
```
class ListNode {
int key;
int val;
ListNode next;
ListNode prev;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
int capacity;
Map dic;
ListNode head;
ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!dic.containsKey(key)) {
return -1;
}
ListNode node = dic.get(key);
remove(node);
add(node);
return node.val;
}
public void put(int key, int value) {
if (dic.containsKey(key)) {
ListNode oldNode = dic.get(key);
remove(oldNode);
}
ListNode node = new ListNode(key, value);
dic.put(key, node);
add(node);
if (dic.size() > capacity) {
ListNode nodeToDelete = head.next;
remove(nodeToDelete);
dic.remove(nodeToDelete.key);
}
}
public void add(ListNode node) {
ListNode previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
public void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
```
41
Binary Tree General
is the next set of cards i need to make
