Arrays An array is a group of like-typed variables that are referred to by a common name.Arrays in Java work differently than they do in C/C++. Following are some important point about Java arrays. In Java all arrays are dynamically allocated.(discussed below) Since arrays are objects in Java, we can find their length using member …
Longest Increasing Subsequence
This No.300 in LeetCode. Here are two approaches for this problem, I will introduce both of them here. Dynamic Programming – O(n^2) The first solution using Dynamic Programming. We will create a one-dimension dp array. We will go over the whole array, and store the numbers of greater number in dp array. class Solution { …
A simple Binary Search Template
def lower_bound(array, first, last, value) # return first !< val in [first, last) while first < last: # not empty mid = first + (last – first)/2. # no overflow if array[mid] < val : first = mid + 1 else: last = mid return first. # or last No need to worry about onverflow: …
Tree Traversals
Inorder Traversal Algorithm Inorder(tree) Traverse the left subtree, i.e., call Inorder(left-subtree) Visit the root. Traverse the right subtree, i.e., call Inorder(right-subtree) Preorder Traversal Algorithm Preorder(tree) Visit the root. Traverse the left subtree, i.e., call Preorder(left-subtree) Traverse the right subtree, i.e., call Preorder(right-subtree) Postorder Traversal Algorithm Postorder(tree) Traverse the left subtree, i.e., call Postorder(left-subtree) Traverse the …
This is No.63 in Leetcode. My original solution is: class Solution { private int path = 0; public int uniquePathsWithObstacles(int[][] obstacleGrid) { // get i and j int i = obstacleGrid[0].length; int j = obstacleGrid.length; i–; j–; findPath(i, i, path, obstacleGrid); return path; } private void findPath(int i, int j, int path, int[][] obstacleGrid){ // …
Kth Largest Element in an Array
This is No.215 in Leetcode. The description: Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. My own solution is: class Solution { public int findKthLargest(int[] nums, int k) { // sort array first Arrays.sort(nums); // get the …
Convert Sorted List to Binary Search Tree
This is No.109 in leetcode. Below is the solution: /** * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int * x) { val = x; } } */ /** * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode * right; TreeNode(int x) { …
Continue reading “Convert Sorted List to Binary Search Tree”
Reverse Linked List II
This is No.92 in leetcode. The problem description: Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. I have a wrong idea on this problem, so I post the reference solution below: class Solution { // Object level variables since we …
Remove Duplicates from Sorted List II
This is No.82. in leetcode. My code is given below: /** * 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 …
Rotate List
This is No.61 in leetcode. The description: Given a linked list, rotate the list to the right by k places, where k is non-negative. This is my original solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = …