Leetcode Easy Questions Review
Published:
Algorithms – Leetcode Easy Questions Review
Leetcode Easy Questions Review
1. Two Sum
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums==null||nums.length==0){
return null;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[]{i,map.get(target-nums[i])};
} else{
map.put(nums[i],i);
}
}
return null;
}
}
9. Palindrome Number
class Solution {
public boolean isPalindrome(int x) {
int newX = 0;
int target = x;
if(x<0){
return false;
}
while(x>0){
int temp = x%10;
newX=newX*10+temp;
x=x/10;
}
return newX==target;
}
}
13. Roman to Integer
class Solution {
public int romanToInt(String s) {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int res = 0;
int n = s.length();
int i = 0;
while(i<n){
if(s.substring(i,i+1).equals(symbols[0])){
res+=values[0];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[1])){
res+=values[1];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[2])){
res+=values[2];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[3])){
res+=values[3];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[4])){
res+=values[4];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[5])){
res+=values[5];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[6])){
res+=values[6];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[7])){
res+=values[7];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[8])){
res+=values[8];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[9])){
res+=values[9];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[10])){
res+=values[10];
i++;
} else if(i<n-1&&s.substring(i,i+2).equals(symbols[11])){
res+=values[11];
i+=2;
} else if(s.substring(i,i+1).equals(symbols[12])){
res+=values[12];
i++;
}
}
return res;
}
}
14. Longest Common Prefix
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs==null||strs.length==0){
return "";
}
String temp = strs[0];
int i = temp.length();
while(i>0){
boolean flag = true;
temp=temp.substring(0,i);
for(String str:strs){
if(!str.startsWith(temp)){
flag = false;
break;
}
}
if(flag){
return temp;
}
i--;
}
return "";
}
}
20. Valid Parentheses
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.isEmpty()){
return false;
} else{
char top = stack.peek();
if((c==')'&&top=='(')||(c==']'&&top=='[')||(c=='}'&&top=='{')){
stack.pop();
} else{
return false;
}
}
}
return stack.isEmpty();
}
}
21. Merge Two Sorted Lists
/**
* 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){
return list2;
}
if(list2==null){
return list1;
}
if(list1.val<list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
} else {
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
}
}
26. Remove Duplicates from Sorted Array
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] without duplicates
nums[slow] = nums[fast];
}
fast++;
}
// Array length is index + 1
return slow + 1;
}
}
27. Remove Element
class Solution {
public int removeElement(int[] nums, int val) {
if(nums==null){
return 0;
}
int n = nums.length;
int slow = 0;
int fast = 0;
while(fast<n){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
28. Implement strStr()
class Solution {
public int strStr(String haystack, String needle) {
if(haystack==null||needle==null){
return -1;
}
int n = haystack.length();
for(int i=0;i<n;i++){
String temp=haystack.substring(i,n);
if(temp.startsWith(needle)){
return i;
}
}
return -1;
}
}
35. Search Insert Position
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums==null){
return 0;
}
int n = nums.length;
int begin = 0;
int end = n;
while(begin<end){
int mid=(begin+end)/2;
if(nums[mid]==target){
return mid;
} else if(nums[mid]<target){
begin=mid+1;
} else {
end=mid;
}
}
return begin;
}
}
53. Maximum Subarray
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp=new int[n];
dp[0]=nums[0];
int maxNum = dp[0];
for(int i=1;i<n;i++){
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>maxNum){
maxNum=dp[i];
}
}
return maxNum;
}
}
58. Length of Last Word
class Solution {
public int lengthOfLastWord(String s) {
String temp=s.trim();
String[] res = temp.split("\\s+");
return res[res.length-1].length();
}
}
66. Plus One
class Solution {
public int[] plusOne(int[] digits) {
if(digits==null||digits.length==0){
return new int[]{1};
}
int n = digits.length;
digits[n-1]+=1;
boolean flag=false;
for(int i=n-1;i>=0;i--){
if(flag){
digits[i]+=1;
flag=false;
}
if(digits[i]>=10){
digits[i]-=10;
flag=true;
}
}
if(!flag){
return digits;
}
int[] res = new int[n+1];
res[0]=1;
for(int i=0;i<n;i++){
res[i+1]=digits[i];
}
return res;
}
}
67. Add Binary
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
69. Sqrt(x)
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}
}
70. Climbing Stairs
class Solution {
public int climbStairs(int n) {
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}
83. Remove Duplicates from Sorted 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 deleteDuplicates(ListNode head) {
ListNode p = head;
if(head==null||head.next==null){
return head;
}
while(p!=null){
ListNode q = p.next;
while(q!=null&&q.val==p.val){
p.next=q.next;
q=q.next;
}
p=p.next;
}
return head;
}
}
88. Merge Sorted Array
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
}
94. Binary Tree Inorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null){
return res;
}
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}
}
100. Same Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
} else if(p==null&&q!=null){
return false;
} else if(p!=null&&q==null){
return false;
} else {
return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
}
104. Maximum Depth of Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
} else {
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
}
108. Convert Sorted Array to Binary Search Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return convert(nums,0,nums.length-1);
}
public TreeNode convert(int[] nums, int begin, int end){
if(begin>end||end>=nums.length){
return null;
}
int mid = (begin+end)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left=convert(nums,begin,mid-1);
root.right=convert(nums,mid+1,end);
return root;
}
}
110. Balanced Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
} else {
return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
} else {
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
}
111. Minimum Depth of Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
}
112. Path Sum
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
} else if(root.left==null&&root.right==null){
return targetSum==root.val;
} else {
return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
}
}
}
118. Pascal’s Triangle
class Solution {
public List<List<Integer>> generate(int numRows) {
if(numRows<=0){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
temp.add(1);
res.add(new ArrayList<>(temp));
for(int i=1;i<numRows;i++){
temp.clear();
for(int j=0;j<=i;j++){
int t = 0;
if(j<i){
t+=res.get(i-1).get(j);
}
if(j>0){
t+=res.get(i-1).get(j-1);
}
temp.add(t);
}
res.add(new ArrayList<>(temp));
}
return res;
}
}
119. Pascal’s Triangle II
class Solution {
public List<Integer> getRow(int rowIndex) {
if(rowIndex<0){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
temp.add(1);
res.add(new ArrayList<>(temp));
for(int i=1;i<=rowIndex;i++){
temp.clear();
for(int j=0;j<=i;j++){
int t = 0;
if(j<i){
t+=res.get(i-1).get(j);
}
if(j>0){
t+=res.get(i-1).get(j-1);
}
temp.add(t);
}
res.add(new ArrayList<>(temp));
}
return res.get(rowIndex);
}
}
121. Best Time to Buy and Sell Stock
class Solution {
public int maxProfit(int[] prices) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
125. Valid Palindrome
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sb = new StringBuffer();
for(char c:s.toCharArray()){
if(Character.isDigit(c)||Character.isLetter(c)){
sb.append(c);
}
}
String str1 = sb.toString();
String str2 = sb.reverse().toString();
return str1.equalsIgnoreCase(str2);
}
}
136. Single Number
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int num:nums){
res = res ^ num;
}
return res;
}
}
141. Linked List Cycle
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null&&slow!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
144. Binary Tree Preorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null){
return res;
}
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}
}
145. Binary Tree Postorder Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null){
return res;
}
res.addAll(postorderTraversal(root.left));
res.addAll(postorderTraversal(root.right));
res.add(root.val);
return res;
}
}
155. Min Stack
class MinStack {
private Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if(stack.isEmpty()){
stack.push(new int[]{val,val});
} else {
int[] peek = stack.peek();
int minValue = peek[1];
if(val<minValue){
minValue=val;
}
stack.push(new int[]{val,minValue});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
160. Intersection of Two Linked Lists
/**
* 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) {
ListNode p1 = headA;
ListNode p2 = headB;
while(p1!=p2){
if(p1==null){
p1=headB;
} else{
p1=p1.next;
}
if(p2==null){
p2=headA;
} else {
p2=p2.next;
}
}
return p1;
}
}
168. Excel Sheet Column Title
class Solution {
public String convertToTitle(int columnNumber) {
if(columnNumber<0){
return null;
}
StringBuffer sb = new StringBuffer();
while(columnNumber!=0){
columnNumber--;
sb.insert(0,converWithin26(columnNumber%26));
columnNumber=columnNumber/26;
}
return sb.toString();
}
public char converWithin26(int num){
return (char)('A'+num);
}
}
169. Majority Element
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
171. Excel Sheet Column Number
class Solution {
public int titleToNumber(String columnTitle) {
int sum = 0;
for(char c:columnTitle.toCharArray()){
sum=sum*26+(c-'A')+1;
}
return sum;
}
}
190. Reverse Bits
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
return Integer.reverse(n);
}
}
191. Number of 1 Bits
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}
202. Happy Number
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
set.add(n);
while(n!=1){
n=calc(n);
if(set.contains(n)){
return false;
} else {
set.add(n);
}
}
return true;
}
public int calc(int n){
int sum = 0;
while(n!=0){
int temp = n%10;
sum=sum+temp*temp;
n=n/10;
}
return sum;
}
}
203. Remove Linked List Elements
/**
* 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 removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur!=null){
if(cur.val==val){
pre.next=cur.next;
cur=cur.next;
continue;
}
cur=cur.next;
pre=pre.next;
}
return dummy.next;
}
}
205. Isomorphic Strings
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length()){
return false;
}
HashMap<Character, Character> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
if(!map.containsKey(s.charAt(i))){
if(map.containsValue(t.charAt(i))){
return false;
}
map.put(s.charAt(i), t.charAt(i));
} else{
if(map.get(s.charAt(i))!=t.charAt(i)){
return false;
}
}
}
return true;
}
}
206. Reverse 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 reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
217. Contains Duplicate
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) {
if (set.contains(x)) {
return true;
} else {
set.add(x);
}
}
return false;
}
}
219. Contains Duplicate II
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
for(int i=0;i<n;i++){
if(i>k){
set.remove(nums[i-k-1]);
}
if(set.contains(nums[i])){
return true;
}
set.add(nums[i]);
}
return false;
}
}
225. Implement Stack using Queues
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
226. Invert Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return root;
}
TreeNode right = invertTree(root.left);
TreeNode left = invertTree(root.right);
root.right = right;
root.left = left;
return root;
}
}
228. Summary Ranges
class Solution {
public List<String> summaryRanges(int[] nums) {
int n = nums.length;
int i = 0;
List<String> res = new ArrayList<>();
while(i<n){
int j=i;
while(j<n&&nums[j]==nums[i]+j-i){
j++;
}
j--;
if(i!=j){
res.add(nums[i]+"->"+nums[j]);
} else {
res.add(String.valueOf(nums[i]));
}
i=j+1;
}
return res;
}
}
231. Power of Two
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
}
232. Implement Queue using Stacks
class MyQueue {
private Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/**
* add element to the end of the queue
*/
public void push(int x) {
s1.push(x);
}
/**
* Remove the element at the head of the queue and return
*/
public int pop() {
// Call peek first to ensure that s2 is not empty
peek();
return s2.pop();
}
/**
* Returns the head element of the queue
*/
public int peek() {
if (s2.isEmpty())
// push the elements of s1 into s2
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.peek();
}
/**
* Check if the queue is empty
*/
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
234. Palindrome 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 boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// Find the tail node of the first half of the linked list and reverse the second half of the linked list
ListNode left = findMid(head);
ListNode right = reverse(left);
// Judging whether a palindrome
ListNode p1 = head;
ListNode p2 = right;
while (p2 != null) {
if (p1.val Judging whether a palindrome{
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
public ListNode reverse(ListNode head){
if(head==null){
return head;
}
ListNode prev = null;
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
public ListNode findMid(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(slow!=null&&fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
if(fast!=null){
slow=slow.next;
}
return slow;
}
}
235. Lowest Common Ancestor of a Binary Search Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(root==p||root==q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left==null){
return right;
}
if(right==null){
return left;
}
return root;
}
}
237. Delete Node in a Linked List
/**
* 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;
}
}
242. Valid Anagram
class Solution {
public boolean isAnagram(String s, String t) {
Map<Character,Integer> sMap = new HashMap<>();
Map<Character,Integer> tMap = new HashMap<>();
if(s.length()!=t.length()){
return false;
}
int n = s.length();
for(int i=0;i<n;i++){
sMap.put(s.charAt(i),sMap.getOrDefault(s.charAt(i),0)+1);
tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)+1);
}
for(char c='a';c<='z';c++){
if(!sMap.getOrDefault(c,0).equals(tMap.getOrDefault(c,0))){
return false;
}
}
return true;
}
}
257. Binary Tree Paths
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root,res,new ArrayList<>());
return res;
}
public void dfs(TreeNode root, List<String> res, List<Integer> temp){
if(root==null){
return;
}
if(root.left==null&&root.right==null){
temp.add(root.val);
StringBuffer sb = new StringBuffer();
for(int i=0;i<temp.size();i++){
sb.append(temp.get(i));
if(i<temp.size()-1){
sb.append("->");
}
}
res.add(sb.toString());
temp.remove(temp.size()-1);
}
temp.add(root.val);
StringBuffer sb = new StringBuffer();
for(int i=0;i<temp.size();i++){
sb.append(temp.get(i));
if(i<temp.size()-1){
sb.append("->");
}
}
dfs(root.left,res,temp);
dfs(root.right,res,temp);
temp.remove(temp.size()-1);
}
}
258. Add Digits
class Solution {
public int addDigits(int num) {
do{
num=sumUp(num);
} while(num/10!=0);
return num;
}
public int sumUp(int num){
int sum = 0;
while(num!=0){
sum+=num%10;
num=num/10;
}
return sum;
}
}
263. Ugly Number
class Solution {
public boolean isUgly(int n) {
if(n<=0){
return false;
}
while(n%5==0){
n=n/5;
}
while(n%3==0){
n=n/3;
}
while(n%2==0){
n=n/2;
}
return n==1;
}
}
268. Missing Number
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// XOR with the newly added index first
res ^= n;
// XOR with other elements and indices
for (int i = 0; i < n; i++)
res ^= i ^ nums[i];
return res;
}
}
278. First Bad Version
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
if(n<=0){
return 0;
}
int left=1;
int right=n;
while(left<right){
int mid = left+(right-left)/2;
if(isBadVersion(mid)){
right=mid;
} else {
left=mid+1;
}
}
return left;
}
}
283. Move Zeroes
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
left++;
}
right++;
}
}
}
290. Word Pattern
class Solution {
private List<Character> getKey(Map<Character,String> map,String value){
List<Character> keys=new ArrayList<>();
for (Map.Entry<Character, String> entry : map.entrySet()) {
if(value.equals(entry.getValue())){
keys.add(entry.getKey());
}
}
return keys;
}
public boolean wordPattern(String pattern, String s) {
String[] split = s.split("\\s+");
if(pattern.length()!=split.length){
return false;
}
Map<Character,String> map = new HashMap<>();
int n=split.length;
for(int i=0;i<n;i++){
if(!map.containsKey(pattern.charAt(i))&&!map.containsValue(split[i])){
map.put(pattern.charAt(i),split[i]);
} else if(map.containsKey(pattern.charAt(i))&&map.containsValue(split[i])){
String ss=map.get(pattern.charAt(i));
List<Character> ps=getKey(map,split[i]);
if(!ss.equals(split[i])||ps.size()!=1||!ps.get(0).equals(pattern.charAt(i))){
return false;
}
} else {
return false;
}
}
return true;
}
}
292. Nim Game
class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}