Point:
- how to create a LinkedList
- how to iterable a linkedlist
- if the sum value over then 10 should carry it
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 addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ret = new ListNode(0);
ListNode current = ret;
// to save the current value
int carry = 0;
// loop the linked list
while (l1 != null || l2 != null || carry > 0) {
int sum = 0;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
sum += carry;
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}
return ret.next;
}
}Point:
- The best solution is sliding window
- what is the sliding window sliding window is a algorithm to solve a sub sequence problem
- which problem is sliding window problem
- First thing is, we have given something like an “Array” | OR | “String”
- Second thing is, they are talking about either “subsequence” | OR | “substring”
- And third most thing is, either we have given a “window size i.e. k” | OR | we have to “manually find out window size”
If your score lies from 2/3 to 3/3 that’s a gauranteed sliding window problem
- the template code for sliding window
while(j < size()){ // Calculation’s happen’s here
if(condition < k){ j++; }
else if(condition == k){ // ans <– calculation j++; }
else if(condition > k){ while(condition > k){ // remove calculation for i i++; } j++; }
} return ans;
- the approach
- Use sliding window with hashset, use left and right pointers to move the window .
- If the set doesn’t contains character then first add into the set and calculate the maxLength hand-in-hand…
- if character already present in the set that means you have to move your sliding window by 1 , before that you have to remove all the characters that are infront of the character that is present already in window before.
- Now you have to remove that character also and move the left pointer and also add the new character into the set.
- chinese approach
- 首先呢，就是获取原字符串的长度。
- 接着维护一个窗口(数组、哈希、队列)
- 窗口一步一步向右扩展
- 窗口在向右扩展滑动过程，需要判断左边是否需要缩减
- 最后比较更新答案
int left =0，right = 0; while (right < s.size()){ //增大窗口 window.add(s[right]); right++;
while (window needs shrink){ //缩小窗口 window.remove (s[left]); left ++; } }
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet set = new HashSet<>();
int windowSize = 0;
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (!set.contains(s.charAt(i))) {
set.add(s.charAt(i));
result = Math.max(result, i - windowSize + 1);
} else {
while(s.charAt(windowSize)!=s.charAt(i)){
set.remove(s.charAt(windowSize));
windowSize++;
}
set.remove(s.charAt(windowSize));
windowSize++;
set.add(s.charAt(i));
}
}
return result;
}
}- the one of solution for this problem is merge the two arrays to a new sorted array. but the time complex is O(m + n) space complex is O(m + n)
- the another solution is save the space and time complex is O(log(n + m))
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int l1 = nums1.length;
int l2 = nums2.length;
int n = l1 + l2;
int[] newArray = new int[n];
int i = 0, j = 0, k = 0;
while (i <= l1 && j <= l2) {
if (i == l1) {
while(j < l2) newArray[k++] = nums2[j++];
break;
} else if (j == l2) {
while(i < l1) newArray[k++] = nums1[i++];
break;
}
if (nums1[i] < nums2[j]) {
newArray[k++] = nums1[i++];
} else {
newArray[k++] = nums2[j++];
}
}
return n%2 == 0 ? (newArray[n/2 - 1] + newArray[n / 2]) / 2.0 : newArray[n/2];
}
}- we have two cases, if the middle index is i:
- the char in i - 1 is equals to i + 1. the middle char is one
adbabdc
- the char in i is equals to i + 1. the middle char is two
baac
abba
- the char in i - 1 is equals to i + 1. the middle char is one
- this solution time complex is O(n^2) and space complex is O(n)
class Solution {
String result = "";
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}
for (int i = 0; i < s.length(); i++) {
expand(s, i, i);
expand(s, i, i + 1);
}
return result;
}
public void expand(String s, int left, int right) {
while (left >= 0 && right < s.length()) {
if (s.charAt(left) != s.charAt(right)) {
break;
}
left--;
right++;
}
if (result.length() < (right - left - 1)) {
result = s.substring(left + 1, right);
}
}
}- this problem is easy to to it loop the x and use x % 10 to get the last value and use x / 10 to reduse the value
- the point of this problem is how to deal with the overflow problem 1000000009 –> 9000000001
class Solution {
public int reverse(int x) {
int result = 0;
while (x != 0) {
// if result > Integer.MAX_VALUE then result / 10 > Integer.MAX_VALUE. result * 10 is overflow
if (Math.abs(result) > Integer.MAX_VALUE / 10) return 0;
result = result * 10 + x % 10;
x = x / 10;
}
return result;
}
}- Start traversing the provided string(str)
- Skip all the leading white spaces. eg: ” -123456” –> “-123456”
- Check for sign cases(+-). eg: “-123456”. If +, then set the variable(boolean) isNegative to true and if it’s -, set isNegative to false
- Iterate over the next remaining characters and keep adding them in result by converting the digits(in character form) to integer form. eg: “-123456” –> -123456, until the non-digit character is found.
class Solution {
public int myAtoi(String s) {
int result = 0;
int sign = 1;
int index = 0;
if (s == null || s.length() == 0) {
return 0;
}
while (index < s.length() && s.charAt(index) == ' ') {
index++;
}
if (index < s.length()) {
if (s.charAt(index) == '+') {
sign = 1;
index++;
} else if (s.charAt(index) == '-') {
sign = -1;
index++;
}
}
while (index < s.length() && (s.charAt(index) <= '9' && s.charAt(index) >= '0')){
int num = (s.charAt(index) - '0');
if (Math.abs(result) > Integer.MAX_VALUE / 10 || (Math.abs(result) >= Integer.MAX_VALUE / 10 && num > 7)) {
if (sign == -1) {
return Integer.MIN_VALUE;
} else {
return Integer.MAX_VALUE;
}
};
result = result * 10 + num;
index++;
}
return result * sign;
}
}- this is a DP problem (Dynamic Programming).
- which problem is dp problem 1.
- how to solve a DP problem: 1.
- how to solve this problem sove this problem with dp Here the approach is very simple we basically must create a DP to store the states. For any DP problem all follow the same rule that we should memoize the truth value of (n,m)(n,m)(n,m) then we need the values of (n−1,m)(n-1 , m)(n−1,m) or (n,m−1)(n ,m-1)(n,m−1) or (n−1,m−1)(n-1 , m-1)(n−1,m−1) this would be the whole point of DP.
class Solution {
public boolean isMatch(String s, String p) {
if (p == null || p.length() == 0) return (s == null || s.length() == 0);
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i=2; i<=p.length(); i++) {
dp[0][i] = p.charAt(i-1) == '*' && dp[0][i-2];
}
for (int i = 1; i <= p.length(); i++) {
for (int j = 1; j <= s.length(); j++) {
if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
dp[j][i] = dp[j-1][i-1];
} else if (p.charAt(i - 1) == '*') {
dp[j][i] = dp[j][i-2] || ((s.charAt(j-1) == p.charAt(i-2) || p.charAt(i-2) == '.') && dp[j-1][i]);
}
}
}
return dp[s.length()][p.length()];
}
}- the height is the num in the array and the width is the index between two nums area = min(left, right) * (right - left) so if we want to get a biggest area, we should to get a highest height and largest width
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int max = 0;
while (i <= j - 1) {
int area = (j - i) * Math.min(height[i], height[j]);
max = Math.max(area, max);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return max;
}
}//optimised -> should have thought from right to left.
class Solution {
public int romanToInt(String s) {
int res = 0, num = 0;
for (int i = s.length()-1; i>=0; i--) {
switch(s.charAt(i)) {
case 'I': num = 1; break;
case 'V': num = 5; break;
case 'X': num = 10; break;
case 'L': num = 50; break;
case 'C': num = 100; break;
case 'D': num = 500; break;
case 'M': num = 1000; break;
}
if (4 * num > res) res += num;
else res -= num;
}
return res;
}
}This code is used to find the longest common prefix of an array of strings, which is defined as the longest string that is a prefix of all the strings in the array. By sorting the array and then comparing the first and last elements, the code is able to find the common prefix that would be shared by all strings in the array.
class Solution {
public String longestCommonPrefix(String[] strs) {
Arrays.sort(strs);
String min = strs[0];
String max = strs[strs.length - 1];
int index = 0;
while (index < min.length() && index < max.length()) {
if (min.charAt(index) == max.charAt(index)) {
index++;
} else {
break;
}
}
return min.substring(0, index);
}
}15.3Sum
- X(time complex is too long) Solved using Array(Three Nested Loop) + Sorting + Hash Table(set). Brute Force Approach
class Solution { public List<List<Integer>> threeSum(int[] nums) { if (nums == null || nums.length < 3) return new ArrayList<>(); Arrays.sort(nums); Set<List<Integer>> result = new HashSet<>(); for(int i =0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { for (int z= j + 1; z < nums.length; z++) { if (nums[i] + nums[j] + nums[z] == 0 ) { result.add(Arrays.asList(nums[i], nums[j], nums[z])); } } } } return new ArrayList<>(result); } }
- Solved using Array(Two Nested Loop) + Sorting. Optimized Approach.
public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { // avoid duplicate A if (i >= 1 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right] + nums[i]; if (sum == 0) { List<Integer> temp = new ArrayList<>(); temp.add(nums[left]); temp.add(nums[i]); temp.add(nums[right]); result.add(temp); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum > 0) { right--; continue; } else if (sum < 0) { left++; continue; } } } return result; } }
- this is a backtracking problem. you can read this page backtracking
- To solve this problem, we can use a recursive approach. We define a recursive function that takes the input string, an output string to keep track of the current combination of letters, an index to keep track of the current digit in the input string, a vector to store all possible combinations, and a mapping array that maps each digit to the corresponding set of letters.
class Solution { private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); if (digits == null || digits.length() == 0) { return result; } helper(result, digits, new StringBuilder(), 0); return result; } private void helper(List<String> result, String digits, StringBuilder sb, int index) { if (index == digits.length()) { result.add(sb.toString()); return; } String letters = KEYS[digits.charAt(index) - '0']; for (char c : letters.toCharArray()) { sb.append(c); helper(result, digits, sb, index + 1); sb.deleteCharAt(sb.length() - 1); } } }
- with a single linked list, the only way to find the end of the list, and thus the n’th node from the end, is to actually iterate all the way to the end.
- we can simply stagger our two pointers by n nodes by giving the first pointer (fast) a head start before starting the second pointer (slow). Doing this will cause slow to reach the n’th node from the end at the same time that fast reaches the end.
/** * 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 fast = head, slow = head; for (int i = 0; i < n; i++) { fast = fast.next; } // n == ListNode.length if (fast == null) return head.next; // we neet to find the (n + 1)th node to delete the nth node, so we should test the fast.next == null not fast == null while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; } }
- this problem we can use stack to solve it
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.empty()) {
return false;
}
if (c == ')' && stack.peek() == '(') {
stack.pop();
} else if (c == '}' && stack.peek() == '{') {
stack.pop();
} else if (c == ']' && stack.peek() == '[') {
stack.pop();
} else {
return false;
}
}
}
return stack.empty();
}
}- we can slove it with recursion
The main logic is to find the smaller value, and then point its next pointer to the larger linked list
/** * 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; } }
- we can also do it with recursion, use left and right to see how many () in current string and ( ) must valid.
- we need two recursions.
- if left < n, we should add ( in string
- if right < left, it indicates that the brackets do not match, you need to add )
- if the string length equals n * 2 we need return and stop program
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
caluate(0, 0, "", n, result);
return result;
}
public void caluate(int left, int right, String str, int n, List<String> result) {
if (str.length() == n * 2) {
result.add(str);
return;
}
if (left < n ) caluate(left + 1, right, str + "(", n, result);
if (right < left) caluate(left, right + 1, str + ")", n, result);
}
}- A very simple solution is to loop through all of the nodes, add each node’s value to a list, and then convert the result back to a linked list.
time complex: O(nlogn) -> n is the total nodes in lists
space complex: O(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 mergeKLists(ListNode[] lists) { ArrayList<Integer> arrayList = new ArrayList<Integer>(); for (int i = 0; i < lists.length; i++) { while (lists[i] != null) { arrayList.add(lists[i].val); lists[i] = lists[i].next; } } Collections.sort(arrayList); ListNode head = new ListNode(); ListNode answer = head; for (int i = 0; i < arrayList.size(); i++) { head.next = new ListNode(arrayList.get(i)); head = head.next; } return answer.next; } }
- Another solution is to use recursion. In problem 21, we solved the task of merging two sorted lists. We can apply this method by splitting the list into pairs and merging them recursively.
time complex: O(nlog(k))
space complex: O(log(k))
/** * 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; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return mergeHepler(lists, 0, lists.length - 1); } private ListNode mergeHepler(ListNode[] lists, int start, int end) { if (start == end) { return lists[start]; } if (start + 1 == end) { return merge(lists[start], lists[end]); } int mid = (start + end) / 2; ListNode l1 = mergeHepler(lists, start, mid); ListNode l2 = mergeHepler(lists, mid + 1, end); return merge(l1, l2); } private ListNode merge(ListNode l1, ListNode l2) { if (l1 != null && l2 != null) { if (l1.val < l2.val) { l1.next = merge(l1.next, l2); return l1; } else { l2.next = merge(l1, l2.next); return l2; } } if (l1 == null) { return l2; } return l1; } }
- we can check if i is less than i + 1, we can find an index for all unique numbers in the array. We can then insert each of these numbers to the beginning of the array.
public class Solution {
public int removeDuplicates(int[] nums) {
int result = 1;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
nums[result] = nums[i + 1];
result++;
}
}
return result;
}
}- using the api in java
class Solution { public int strStr(String haystack, String needle) { return haystack.indexOf(needle); } }
- using sliding window
class Solution { public int strStr(String haystack, String needle) { int j = 0; for (int i = 0; i < haystack.length(); i++) { if (haystack.charAt(i) == needle.charAt(j)) { j++; } else { i = i - j; j = 0; } if (j == needle.length()) { return i - j + 1; } } return -1; } }
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; //Cornor case when -2^31 is divided by -1 will give 2^31 which doesnt exist so overflow
boolean negative = dividend < 0 ^ divisor < 0; //Logical XOR will help in deciding if the results is negative only if any one of them is negative
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
int quotient = 0, subQuot = 0;
while (dividend - divisor >= 0) {
for (subQuot = 0; dividend - (divisor << subQuot << 1) >= 0; subQuot++);
quotient += 1 << subQuot; //Add to the quotient
dividend -= divisor << subQuot; //Substract from dividend to start over with the remaining
}
return negative ? -quotient : quotient;
}
}- this approach is based on that this list can be divided into two sorted list
public class Solution {
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[end] >= target && nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}- we use binary search to search the target value and target + 1 value
public class Solution { public int[] searchRange(int[] nums, int target) { int start = binarySearch(nums, target); int end = binarySearch(nums, target + 1); return start == end ? new int[] {-1, -1} : new int[] {start, end - 1}; } public int binarySearch(int[] nums, int target) { int start = 0, end = nums.length; while (start < end) { int mid = (start + end) / 2; if (nums[mid] < target) { start = mid + 1; } else { end = mid; } } return start; } }
36.Valid Sudoku
- we can use hashset to save the checked value
use (7)1 to save the value 1 in line 7
use 1(7) to save the value 1 in row 7
use 1(7)1 to save the value in small 3x3 squares
class Solution { public boolean isValidSudoku(char[][] board) { Set<String> set = new HashSet<>(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') { String s = String.format("(%c)", board[i][j]); if (!set.add(s + i) || !set.add(j + s) || !set.add(i / 3 + s + j / 3)) { return false; } } } } return true; } }
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent