1). Remove K Digits
Given a non-negative integer number represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero
Example 1: Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2: Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3: Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Steps:
Java Solution
2). Reverse Linked List
Reverse a linked list from position m to n. Do it in one-pass.
Note:
Input: 1- > 2- > 3- > 4- > 5- > NULL, m = 2, n = 4
Output: 1- > 4- > 3- > 2- > 5- > NULL
Algorithm:-
Step 1: Decrement m and n until m reaches 1. After completion of step 1:
a). m will become 1 and n will be equal to previous value of m.
b). current will point to the element at n position.
c). previous will be the previous of element at n position.
Step 2: Reverse the nodes until n becomes 0. After completion of step 2:
a). m will remain 1, and n will be 0.
b). current will point to the element at last position.
c). previous will be the previous of element at the last position.
d). previous will be the element at n position (n which was passed).
e). ncurrent will be the element at m position (m which was passed), nprevious will be its previous element.
Step 3: nprevious will point to previous and ncurrent will point to current.
GIT URL: Leet Code solution: Reverse a linked list from position m to n
Java Solution
3). Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed.
Example: Given 1- > 2- > 3- > 4, you should return the list as 2- > 1- > 4- > 3.
GIT URL: Leet Code solution: Swap Nodes in Pairs solution
Java Solution
4). Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Algorithm:
Iterate the 2D array, every-time you encounter the 1:
a). increase the island count
b). recursively replace all the horizontally/vertically land(1) with water(0).
GIT URL: Leet Code solution: Number of Islands solution
Java Solution
-K Himaanshu Shuklaa..
Given a non-negative integer number represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero
Example 1: Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2: Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3: Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Steps:
- We will iterate for k times.
- In each iteration we will check remove the current digit if it's equal or smaller then next number.
- After iteration, we need to remove all the leading zeros.
Java Solution
2). Reverse Linked List
Reverse a linked list from position m to n. Do it in one-pass.
Note:
- 1 is less than or equal to m.
- m is less than or equal to n.
- n is less than or equal to the length of list.
Input: 1- > 2- > 3- > 4- > 5- > NULL, m = 2, n = 4
Output: 1- > 4- > 3- > 2- > 5- > NULL
Algorithm:-
Step 1: Decrement m and n until m reaches 1. After completion of step 1:
a). m will become 1 and n will be equal to previous value of m.
b). current will point to the element at n position.
c). previous will be the previous of element at n position.
Step 2: Reverse the nodes until n becomes 0. After completion of step 2:
a). m will remain 1, and n will be 0.
b). current will point to the element at last position.
c). previous will be the previous of element at the last position.
d). previous will be the element at n position (n which was passed).
e). ncurrent will be the element at m position (m which was passed), nprevious will be its previous element.
Step 3: nprevious will point to previous and ncurrent will point to current.
GIT URL: Leet Code solution: Reverse a linked list from position m to n
Java Solution
3). Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed.
Example: Given 1- > 2- > 3- > 4, you should return the list as 2- > 1- > 4- > 3.
GIT URL: Leet Code solution: Swap Nodes in Pairs solution
Java Solution
4). Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Algorithm:
Iterate the 2D array, every-time you encounter the 1:
a). increase the island count
b). recursively replace all the horizontally/vertically land(1) with water(0).
GIT URL: Leet Code solution: Number of Islands solution
Java Solution
-K Himaanshu Shuklaa..
No comments:
Post a Comment