description:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
solution
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
if(nums[i] == target - nums[j]){
return new int[] {i,j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}description:
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 contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
solution:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}description:
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
solution:
class Solution {
public int reverse(int x) {
int result = 0;
while (x != 0){
int tail = x % 10;
int newResult = result * 10 + tail;
if ((newResult - tail) / 10 != result){
return 0;
}
result = newResult;
x = x / 10;
}
return result;
}
}description:
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
solution:
class Solution {
public boolean isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
}description:
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
example:
罗马数字有如下符号：
| 基本字符 | I | V | X | L | C | D | M |
|---|---|---|---|---|---|---|---|
| 对应阿拉伯数字 | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
计数规则：
- 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
- 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
- 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4
- 正常使用时，连续的数字重复不得超过三次
- 在一个数的上面画横线，表示这个数扩大1000倍（本题只考虑3999以内的数，所以用不到这条规则）
其次，罗马数字转阿拉伯数字规则（仅限于3999以内）：
从前向后遍历罗马数字，如果某个数比前一个数小，则加上该数。反之，减去前一个数的两倍然后加上该数
solution:
class Solution {
public int romanToInt(String s) {
int nums[]=new int[s.length()];
for(int i=0;i<s.length();i++){
switch (s.charAt(i)){
case 'M':
nums[i] = 1000;
break;
case 'D':
nums[i] = 500;
break;
case 'C':
nums[i] = 100;
break;
case 'L':
nums[i] = 50;
break;
case 'X' :
nums[i] = 10;
break;
case 'V':
nums[i] = 5;
break;
case 'I':
nums[i] = 1;
break;
}
}
int sum = 0;
for(int i = 0; i < nums.length - 1; i++){
if(nums[i] < nums[i + 1])
sum -= nums[i];
else
sum += nums[i];
}
return sum + nums[nums.length - 1];
}
}description:
Write a function to find the longest common prefix string amongst an array of strings.
solution:
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
// while (strs[i].indexOf(prefix) != 0) {
// prefix = prefix.substring(0, prefix.length() - 1);
// if (prefix.isEmpty()) return "";
for (; strs[i].indexOf(prefix) != 0;) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
// }
return prefix;
}
}description:
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
solution:
class Solution {
public boolean isValid(String s) {
if(s == null || "".equals(s.trim())){
return false;
}
char array[] = s.toCharArray();
int len = s.length();
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i < len; i++){
if(array[i] == '(' || array[i] == '{' || array[i] == '['){
stack.push(array[i]);
}else if(array[i] == ')' || array[i] == '}' || array[i] == ']'){
if(stack.isEmpty()){
return false;
}
char c = stack.peek();
stack.pop();
if(array[i] == ')'){
if(c != '('){
return false;
}
}
if(array[i] == '}'){
if(c != '{'){
return false;
}
}
if(array[i] == ']'){
if(c != '['){
return false;
}
}
}
}
if(!stack.isEmpty()){
return false;
}
return true;
}
}description:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode temp;
if (l1.val < l2.val) {
temp = l1;
temp.next = mergeTwoLists(l1.next, l2);
}
else {
temp = l2;
temp.next = mergeTwoLists(l1, l2.next);
}
return temp;
}
}description:
Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.
solution:
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}description:
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}description:
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be trun
solution:
class Solution {
public int mySqrt(int x) {
long i = 0;
long j = x / 2 + 1;
while (i <= j) {
long mid = (i + j) / 2;
if (mid * mid == x)
return (int)mid;
if (mid * mid < x)
i = mid + 1;
else
j = mid - 1;
}
return (int)j;
}
}description:
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
solution:
class Solution {
public int strStr(String haystack, String needle) {
int l1 = haystack.length(), l2 = needle.length();
if (l1 < l2) {
return -1;
} else if (l2 == 0) {
return 0;
}
int threshold = l1 - l2;
for (int i = 0; i <= threshold; i++) {
if (haystack.substring(i, i + l2).equals(needle)) {
return i;
}
}
return -1;
}
}description:
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
solution:
class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
String str = countAndSay(n - 1) + "*";
char[] c = str.toCharArray();
int count = 1;
String s = "";
for (int i = 0; i < c.length - 1; i++) {
if(c[i] == c[i+1]) {
count++;
} else {
s = s + count + c[i];
count = 1;
}
}
return s;
}
}description:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note: Bonus points if you could solve it both recursively and iteratively.
solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
}description:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
solution:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
while (n > 0) nums1[m+n-1] = (m == 0) || nums2[n - 1] > nums1[m - 1] ? nums2[--n] : nums1[--m];
}
}description:
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
solution:
class Solution {
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0], maxEndingHere = nums[0];
for (int i = 1; i < nums.length; ++i) {
maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}description:
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
solution:
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] newNumber = new int[n + 1];
newNumber[0] = 1;
return newNumber;
}
}description:
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
solution:
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}description:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
solution:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return rootdescription:
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5, Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
solution:
class Solution:
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
triangle = []
for row_num in range(numRows):
row = [None for _ in range(row_num + 1)]
# row = []
# for _ in range(row_num + 1):
# row += [None]
row[0] = 1
row[-1] = 1
for j in range(1, len(row) - 1):
row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]
triangle.append(row)
return triangledescription:
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note: Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
solution:
class Solution:
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return Truedescription:
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
solutions:
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return 2 * sum(set(nums)) - sum(nums)
# int result = 0;
# for (int i = 0; i<n; i++)
# {
# result ^=A[i];
# }
# return result;description:
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
solution:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return Falsedescription:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.solution:
public class MinStack {
Stack<Integer> stackNum = new Stack<Integer>();
Stack<Integer> stackMin = new Stack<Integer>();
public void push(int x) {
stackNum.push(x);
if(stackMin.isEmpty() || stackMin.peek() >= x) {
stackMin.push(x);
}
}
public void pop() {
int top = stackNum.pop();
if(top <= stackMin.peek()) {
stackMin.pop();
}
}
public int top() {
return stackNum.peek();
}
public int getMin() {
return stackMin.peek();
}
}description:
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
}description:
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
solution:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
min = float('inf')
profit = 0
for price in prices:
if min > price:
min = price
else:
if profit < price - min:
profit = price - min
return profit
# def maxProfit(prices):
# max_profit, min_price = 0, float('inf')
# for price in prices:
# min_price = min(min_price, price)
# profit = price - min_price
# max_profit = max(max_profit, profit)
# return max_profitdescription:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
solution:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))description:
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits: Special thanks to @ts for adding this problem and creating all test cases.
solution:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums)//2] description:
Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
Credits: Special thanks to @ts for adding this problem and creating all test cases.
solution:
class Solution:
def titleToNumber(self, s):
"""
:type s: str
:rtype: int
"""
s = s[::-1]
sum = 0
for exp, char in enumerate(s):
sum += (ord(char) - 65 + 1) * (26 ** exp)
return sumdescription:
Given an integer n, return the number of trailing zeroes in n!.
**Note: **Your solution should be in logarithmic time complexity.
solution:
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
r = 0
while n > 0:
n /= 5
r += n
return rdescription:
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
return bin(n).count('1')
# c = 0
# while n:
# n &= n - 1
# c += 1
# return cdescription:
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
solution:
class Solution {
public void rotate(int[] nums, int k) {
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--;
}
}
}description:
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
solution:
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
if(n == 0)
return 0;
int result = 0;
for(int i = 0; i < 32; i++) {
result <<= 1;
if ((n & 1) == 1) result++;
n >>= 1;
}
return result;
}
}description:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
solution:
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] mark = new int[nums.length];
mark[0] = nums[0];
mark[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
mark[i] = Math.max(nums[i] + mark[i-2], mark[i - 1]);
}
return mark[nums.length - 1];
}
}description:
Write an algorithm to determine if a number 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, and 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 numbers.
**Example: **19 is a happy number
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
solution:
class Solution {
public boolean isHappy(int n) {
Set<Integer> s = new HashSet<Integer>();
while (n != 1) {
int t = 0;
while (n != 0) {
t += (n % 10) * (n % 10);
n /= 10;
}
n = t;
if (s.contains(n)) break;
else s.add(n);
}
return n == 1;
}
}description:
Description:
Count the number of prime numbers less than a non-negative number, n.
solution:
class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
}
for (int j = 2; i * j < n; j++) {
notPrime[i*j] = true;
}
}
return count;
}
}description:
Reverse a singly linked list.
solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// is there something to reverse?
if (head != null && head.next != null)
{
ListNode pivot = head;
ListNode frontier = null;
while (pivot != null && pivot.next != null)
{
frontier = pivot.next;
pivot.next = pivot.next.next;
frontier.next = head;
head = frontier;
}
}
return head;
}
}description:
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
solution:
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) return true;
set.add(nums[i]);
}
return false;
}
}description:
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}description:
Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.
Note: You may assume the string contains only lowercase alphabets.
Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?
solution:
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}description:
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1
Input: [3,0,1]
Output: 2
Example 2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
solution:
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) numSet.add(num);
int expectedNumCount = nums.length + 1;
for (int number = 0; number < expectedNumCount; number++) {
if (!numSet.contains(number)) {
return number;
}
}
return -1;
}
}description:
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
solution:
class Solution {
public void moveZeroes(int[] nums) {
if (nums == null || nums.length ==0) return;
int insertPos = 0;
for (int num: nums) {
if(num != 0) nums[insertPos++] = num;
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
}description:
Given an integer, write a function to determine if it is a power of three.
Follow up: Could you do it without using any loop / recursion?
solution:
class Solution {
public boolean isPowerOfThree(int n) {
if (n < 1) return false;
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}description:
Write a function that takes a string as input and returns the string reversed.
Example: Given s = "hello", return "olleh".
solution:
public class Solution {
public String reverseString(String s) {
byte[] bytes = s.getBytes();
int i = 0;
int j = s.length() - 1;
while (i < j) {
byte temp = bytes[i];
bytes[i] = bytes[j];
bytes[j] = temp;
i++;
j--;
}
return new String(bytes);
}
}description:
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
solution:
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int pnt1 = 0;
int pnt2 = 0;
ArrayList<Integer> myList = new ArrayList<Integer>();
while ((pnt1 < nums1.length) && (pnt2 < nums2.length)) {
if (nums1[pnt1] < nums2[pnt2]) {
pnt1++;
}
else {
if (nums1[pnt1] > nums2[pnt2]) {
pnt2++;
}
else {
myList.add(nums1[pnt1]);
pnt1++;
pnt2++;
}
}
}
int[] res = new int[myList.size()];
for (int i = 0; i < res.length; i++) {
res[i] = (Integer)myList.get(i);
}
return res;
}
}description:
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example: Given a = 1 and b = 2, return 3.
solution:
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
}description:
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
solution:
class Solution {
public int firstUniqChar(String s) {
int freq[] = new int[26];
for (int i = 0; i < s.length(); i++)
freq[s.charAt(i) - 'a']++;
for (int j = 0; j < s.length(); j++) {
if (freq[s.charAt(j) - 'a'] == 1)
return j;
}
return -1;
}
}description:
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15,
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
solution:
class Solution {
public List<String> fizzBuzz(int n) {
List<String> ret = new ArrayList<String>(n);
for (int i = 1, fizz = 0, buzz = 0; i <= n; i++ ) {
fizz++;
buzz++;
if (fizz == 3 && buzz == 5) {
ret.add("FizzBuzz");
fizz = 0;
buzz = 0;
}else if (fizz == 3) {
ret.add("Fizz");
fizz = 0;
}else if (buzz == 5) {
ret.add("Buzz");
buzz = 0;
}else {
ret.add(String.valueOf(i));
}
}
return ret;
}
}description:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
solution:
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max)
backtrack(ans, cur+"(", open + 1, close, max);
if (close < open)
backtrack(ans, cur+")", open, close + 1, max);
}
}description:
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
solution:
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
perms = [[]]
for n in nums:
new_perms = []
for perm in perms:
for i in xrange(len(perm) + 1):
new_perms.append(perm[:i] + [n] + perm[i:])
perms = new_perms
return permsdescription:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke"is a subsequence and not a substring.
solution:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}description:
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOTallocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
solution:
public class Solution {
public void rotate(int[][] matrix) {
for(int i = 0; i<matrix.length; i++){
for(int j = i; j<matrix[0].length; j++){
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for(int i =0 ; i<matrix.length; i++){
for(int j = 0; j<matrix.length/2; j++){
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length-1-j];
matrix[i][matrix.length-1-j] = temp;
}
}
}
}description:
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
solution:
public class Solution {
public int uniquePaths(int m, int n) {
int[][] grid = new int[m][n];
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(i==0||j==0)
grid[i][j] = 1;
else
grid[i][j] = grid[i][j-1] + grid[i-1][j];
}
}
return grid[m-1][n-1];
}
}description:
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
solution:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());
Arrays.sort(nums);
for (int num : nums)
{
int size = ans.size();
for (int i = 0; i < size; i++)
{
List<Integer> tmp = new ArrayList<>(ans.get(i));
tmp.add(num);
ans.add(tmp);
}
}
return ans;
}
}description:
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
helper(root, res);
return res;
}
public void helper(TreeNode root, List < Integer > res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
}description:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
levelHelper(res, root, 0);
return res;
}
public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
if (root == null) return;
if (height >= res.size()) {
res.add(new LinkedList<Integer>());
}
res.get(height).add(root.val);
levelHelper(res, root.left, height + 1);
levelHelper(res, root.right, height + 1);
}
}