can please someone help with me this question Part 1 Recursion 1 Describe Hanoi
ID: 3838004 • Letter: C
Question
can please someone help with me this question
Part 1 Recursion 1 Describe Hanoi Tower Problem and give a recursive solution.
2 Given a positive integer num. Return its binary representation. Example1: x = 32, return 100000 Example1: x = 1024, return 10000000000 Note: Do not use any built-in library function such as bin.
3 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. Part 2 Searching and Sorting 6 Given an array of size n, find the majority element. The majority element is the element that appears more than n/3 times. You may assume that the array is non-empty and the majority element always exist in the array. 7 Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. 8 Design an O(n log n) worst-case time algorithm that counts the number of inversions in an array of n numbers. Inversion definition: If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3). Hint: Modify Mergesort. 9 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13. Note: You may assume k is always valid, 1 k n^2. Part 3 Array and List 10 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2. Note: Your algorithm should run in linear runtime complexity. 11 Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1. Example: Input: [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4] 12 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. Part 4 Collector 13 Given a text named “Hamlet.txt”. Find the ten most common words in Hamlet Hint: Use collections and re module. Part 5 String Manipulation 14 Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh". 15 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 = "python" return 0. s = "lovelife", return 1. Note: You may assume the string contain only lowercase letters. 16 Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". 17 Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000. Example 1: Input: "abab" Output: True Explanation: It's the substring "ab" twice. Example 2: Input: "aba" Output: False Example 3: Input: "abcabcabcabc" Output: True Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.) 18 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. Part 6 Comprehension 19 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",4 "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz" ] 20 You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap. For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend. 21 There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So the person at position 3 survives. If n = 7 and k = 3, then the safe position is 4. The persons at positions 3, 6, 2, 7, 5, 1 are killed in order, and person at position 4 survives. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. Give your analysis and compose a program to find the safe place. Hint: Using recursion and try to find the pattern.
Explanation / Answer
public class Solution
{
public ArrayList<Integer> spiralOrder(int[][] matrix)
{
ArrayList<Integer> result = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0) return result;
int m = matrix.length;
int n = matrix[0].length;
int x=0;
int y=0;
while(m>0 && n>0)
{
if(m==1)
{
for(int i=0; i<n; i++){
result.add(matrix[x][y++]);
}
break;
}
else if(n==1)
{
for(int i=0; i<m; i++)
{
result.add(matrix[x++][y]);
}
break;
}
for(int i=0;i<n-1;i++)
{
result.add(matrix[x][y++]);
}
for(int i=0;i<m-1;i++)
{
result.add(matrix[x++][y]);
}
for(int i=0;i<n-1;i++)
{
result.add(matrix[x][y--]);
}
for(int i=0;i<m-1;i++)
{
result.add(matrix[x--][y]);
}
x++;
y++;
m=m-2;
n=n-2;
}
return result;
}
}
Similarly, we can write the solution this way:
public List<Integer> spiralOrder(int[][] matrix)
{
List<Integer> result = new ArrayList<Integer>();
if(matrix==null||matrix.length==0||matrix[0].length==0)
return result;
int m = matrix.length;
int n = matrix[0].length;
int left=0;
int right=n-1;
int top = 0;
int bottom = m-1;
while(result.size()<m*n){
for(int j=left; j<=right; j++)
{
result.add(matrix[top][j]);
}
top++;
for(int i=top; i<=bottom; i++){
result.add(matrix[i][right]);
}
right--;
if(bottom<top)
for(int j=right; j>=left; j--)
{
result.add(matrix[bottom][j]);
}
bottom--;
if(right<left)
break;
for(int i=bottom; i>=top; i--)
{
result.add(matrix[i][left]);
}
left++;
}
return result;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.