Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. Analysis To find the trapped water at position i, we need to find the maximum value of the left elements of i and right elements of … Read more [LeetCode] Trapping Rain Water (Java)
Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. Analysis We are required to use constant space. So we need to use the array. We can put the element, which value is i, in position i – 1. After … Read more [LeetCode] First Missing Positive (Java)
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. Analysis In fact, in … Read more [LeetCode] Search for a Range (Java)
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. … Read more [LeetCode] Search in Rotated Sorted Array (Java)
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and … Read more [LeetCode] Next Permutation (Java)
Divide two integers without using multiplication, division and mod operator. Analysis We can keep subtract divisor from dividend until dividend is smaller than 0, than count the subtract numbers. But it will costs a very long time if the divisor is very small comparing to dividend. Shift can be used to solve this problem. We … Read more [LeetCode] Divide Two Integers (Java)
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Analysis At first I thought this problem was quite easy. We can just pick the smallest one from all heads of lists and then connect it to the final list. But the complexity of this algorithm will be O(n2k), in which … Read more [LeetCode] Merge k Sorted Lists (Java)
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note: Although the above answer is in lexicographical order, your answer could be in any order you want. Analysis It’s a easy question. But we … Read more [LeetCode] Letter Combinations of a Phone Number (Java)
In LeetCode, there are a set of problems to find the sum of several integers from an array to be a target value. Two Sum Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that … Read more [LeetCode] Two Sum, 3 Sum, 3 Sum closest and 4 Sum (Java)
We may install some software manually. For example, we can run the Idea Intellij by running idea.sh. But it’s not so convenient. So we can create a shortcut for the problem. Create a Idea.desktop file on the desktop. The content is as follow.
Comment=Idea IntelliJ 13.0
You may need to change the paths in the file and … Read more Create shortcut in Ubuntu