接上一篇的，有字数限制就变两个了。
- Matrix Position
Given an NxN matrix with unique integers: Find and print positions of all numbers such that
it is the biggest in its row and also the smallest in its column . e.g. : In 3 x 3 with elements.
1 2 3
4 5 6
7 8 9
the number is 3 and position (1,3)
public static String matrixPosition (int[][] grid) {
if (grid == null || grid.length != grid[0].length) throw new IllegalArgumentException();
StringBuilder result = new StringBuilder();
int row = grid.length;
int col = grid[0].length;
//use hashmap to store the coordinate with the max value of the row. key stands for column and value stands for row.
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < row; i++) {
//find max value and its position of the row.
int max = Integer.MIN_VALUE;
Integer[] position = new Integer[2];
for (int j = 0; j < col; j++) {
if (max < grid[i][j]) {
max = grid[i][j];
position[0] = i;
position[1] = j;
}
}
int rowMax = grid[position[0]][position[1]];
//store the position with max value in map (col, row)
if (!map.containsKey(position[1])) {
map.put(position[1], position[0]);
} else {
int pre = map.get(position[1]);
if (pre > rowMax) {
map.put(position[1], position[0]);
}
}
}
// read positions with largest value of the rows from map, and check if they are the smallest of the col.
for (int currCol: map.keySet()) {
int currRow = map.get(currCol);
int rowMax = grid[currRow][currCol];
int i = 0;
for (; i < row; i++) {
if (grid[i][currCol] < rowMax) {
break;
}
}
if (i == row) {
result.append("Number " + rowMax + " position (" + currRow + ", " + currCol + ") ");
}
}
return result.toString();
}
- Replace String
From a given string, replace all instances of ‘a’ with ‘one’ and ‘A’ with ‘ONE’.
Example Input: " A boy is playing in a garden"
Example Output: " ONE boy is playing in one garden"
– Not that ‘A’ and ‘a’ are to be replaced only when they are single characters, not as part of
another word.
public static String replaceString (String input) {
if (input == null) return input;
String[] words = input.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < words.length; i++) {
String curr = words[i];
if (curr.equals("a")) {
sb.append("one ");
} else if (curr.equals("A")) {
sb.append("ONE ");
} else {
sb.append(words[i] + " ");
}
}
String result = sb.toString();
return result.substring(0, result.length() - 1);
}
- Replace AEIOU
Replace a,e,i,o,u with A,E,I,O,U.
At most four eligible letters from the rear of the string are replaced.
The first three eligible letters in the string are always exempted from replacement.
public static String replaceAEIOU (String input) {
if (input == null) {
return input;
}
int i = 0, j = input.length() - 1, count = 0;
Set<Character> set = new HashSet<>();
set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u');
while (i < input.length()) {
if (set.contains(input.charAt(i))) {
count++;
if (count == 3) {
break;
}
}
i++;
}
count = 0;
while (j > i) {
char curr = input.charAt(j);
if (set.contains(curr)) {
count++;
input = input.substring(0, j) + (char) (curr + 'A' - 'a') + input.substring(j+1, input.length());
if (count == 4) {
break;
}
}
j--;
}
return input;
}
- Security Keypad
There is a security keypad at the entrance of a building. It has 9 numbers 1 - 9 in a 3x3
matrix format.
1 2 3
4 5 6
7 8 9
The security has decided to allow one digit error for a person but that digit should be
horizontal or vertical. Example: for 5 the user is allowed to enter2, 4, 6, 8 or for 4 the user
is allowed to enter 1, 5, 7. IF the security code to enter is 1478 and if the user enters 1178
he should be allowed. Write a function to take security code from the user and print out if
he should be allowed or not.
public static boolean securityKeypad (int input, int expect) {
if (input == expect) {
return true;
}
String inputStr = Integer.toString(input);
String expectStr = Integer.toString(expect);
if (inputStr.length() != expectStr.length()) {
return false;
}
//check digit one by one
int count = 0;
for (int i = 0; i < inputStr.length(); i++) {
char currInput = inputStr.charAt(i);
char currExpect = expectStr.charAt(i);
if (currInput == currExpect) {
continue;
} else {
// current digit does not equal to expect digit, check if current digit is on the same row or same col of expected digit.
int expectNum = (int) (currExpect - '0' - 1);
int inputNum = (int) (currInput - '0' - 1);
int expectRow = expectNum / 3;
int expectCol = expectNum % 3;
int inputRow = inputNum / 3;
int inputCol = inputNum % 3;
Count++;
if (expectRow != inputRow && inputCol != expectCol || count == 2) {
return false;
}
if (expectRow != inputRow && Math.abs(expectNum - inputNum) > 3) {
return false;
}
if (expectCol != inputCol && Math.abs(expectCol - inputCol) > 1) {
return false;
}
}
}
return true;
}
- Seeds Number
Find the seed of a number.
Eg : 1716 = 14314*3 =1716 so 143 is the seed of 1716. Find all possible seed for a
given number.
public static List<Integer> seedNum (int num) {
List<Integer> result = new ArrayList<>();
//use double in case input number is Integer.MIN_VALUE
double number = (double) num;
number = num > 0? number: 0 - number;
for (int i = (int) Math.sqrt(number); i < number; i++) {
//System.out.println(i);
if (isSeed(i, number)) {
result.add(i);
}
}
return result;
}
private static boolean isSeed (int num, double target) {
double product = (int) num;
while (num != 0) {
int curr = num % 10;
product *= curr;
num /= 10;
}
return product == target;
}
- Tic Tac Toe
N*N matrix is given with input red or black. You can move horizontally, vertically or
diagonally. If 3 consecutive same colors found, that color will get 1 point. So if 4 red are
vertically then point is 2. Find the winner.
public static String ticTacToe (int grid[][]) {
if (grid == null || grid.length != grid[0].length) {
throw new IllegalArgumentException();
}
//in grid 1 stands for black and 1 stands for red.
int red = 0;
int black = 0;
int row = grid.length;
int col = grid[0].length;
//check vertically
for (int j = 0; j < col; j++) {
for (int i = 0; i < row -2; i++) {
if (grid[i][j] == grid[i+1][j] && grid[i][j] == grid[i+2][j]) {
if (grid[i][j] == 1) {
black++;
} else {
red++;
}
}
}
}
//check horizontally
for (int i = 0; i < row; i++) {
for (int j = 0; j < col - 2; j++) {
if (grid[i][j] == grid[i][j+1] && grid[i][j] == grid[i][j+2]) {
if (grid[i][j] == 1) {
black++;
} else {
red++;
}
}
}
}
//check 45
for (int i = 0; i < row - 2; i++) {
for (int j = 2; j < col; j++) {
if (grid[i][j] == grid[i+1][j-1] && grid[i][j] == grid[i+2][j-2]) {
if (grid[i][j] == 1) {
black++;
} else {
red++;
}
}
}
}
//check 135
for (int i = 0; i < row - 2; i++) {
for (int j = 0; j < col - 2; j++) {
if (grid[i][j] == grid[i+1][j+1] && grid[i][j] == grid[i+2][j+2]) {
if (grid[i][j] == 1) {
black++;
} else {
red++;
}
}
}
}
System.out.println(red + " " + black);
return red > black? "red": "black";
}
- Fill a “magic square” matrix.
A magic square of order n is an arrangement of the numbers from 1 to n^2 in an n by n
matrix with each number occurring exactly once so that each row, each column and each
main diagonal has the same sum. Then should be an odd number. In the middle cell of the
top row, fill number 1.Then go to above row and right column, and fill following number 2.
If it’s out of boundary, go to the opposite row or column. If the next cell is already
occupied, go to the cell below this cell and fill following number. An exampleof 5*5 grid is
like this for the first 9 numbers:
0 0 1 8 0
0 5 7 0 0
4 6 0 0 0
0 0 0 0 3
0 0 0 2 9
public static int[][] magicMatrix (int n) {
if (n < 0 || n % 2 == 0) {
throw new IllegalArgumentException();
}
int count = 1;
int i = 0;
int j = n / 2;
int[][] grid = new int[n][n];
while (count <= n * n) {
grid[i][j] = count++;
int nextI = i - 1;
int nextJ = j + 1;
if (nextI < 0) {
nextI = n - 1;
}
if (nextJ == n) {
nextJ = 0;
}
if (grid[nextI][nextJ] != 0) {
nextI = i + 1;
nextJ = j;
if (nextI == n) {
nextI = 0;
}
}
i = nextI;
j = nextJ;
}
return grid;
}
- Bull and Cows Game
There’s a word guessing game. One person think a word, and the other one guess a word,
both words have the same length. The person should return the number of bulls and cows
for the guessing. Bulls represent the number of same characters in the same spots,
whereas cows represent the number of characters guessed right but in the wrong spots.
Write a program with two input strings, return the number of bulls and cows.
public static String bullAndCow (String think, String guess) {
if (think == null || guess == null || think.length() != guess.length()) {
throw new IllegalArgumentException();
}
int bull = 0;
int cow = 0;
int[] letters = new int[26];
for (int i = 0; i < think.length(); i++) {
if (think.charAt(i) == guess.charAt(i)) {
bull++;
} else {
char t = think.charAt(i);
char g = guess.charAt(i);
t = Character.toLowerCase(t);
g = Character.toLowerCase(g);
letters[t-'a']++;
letters[g-'a']--;
}
}
int diff = 0;
for (int i = 0; i < 26; i++) {
diff += Math.abs(letters[i]);
}
cow = (think.length() * 2 - bull * 2 - diff) / 2;
return "bull " + bull + "; cow " + cow;
}
- Palindromes
Print all palindromes of size greater than or equal to 3 of a given string. (How to do it with
DP)?
public static List<String> palindrome (String input) {
if (input == null || input.length() < 3) {
return null;
}
List<String> result = new ArrayList<>();
int minSize = 3;
findPalindrome(minSize / 2.0, input, result, minSize);
return result;
}
private static void findPalindrome (double mid, String input, List<String> result, int minSize) {
if (mid + minSize / 2 > input.length()) {
return;
}
checkPalindrome((int) Math.floor(mid), (int) Math.ceil(mid), minSize, input, result);
mid += 0.5;
}
private static void checkPalindrome (int start, int end, int minSize, String input, List<String> result) {
if (start < 0 || end >= input.length()) return;
if (input.charAt(start) == input.charAt(end)) {
if (end - start + 1 >= minSize) {
result.add(input.substring(start, end + 1));
}
checkPalindrome(start - 1, end + 1, minSize, input, result);
} else {
return;
}
}
- Unique Number
Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3,
3, 3, 5, 5, 5, 9, 9, 9, 9)-> (1, 3, 5, 9).
public static Integer[] uniqueNum (int[] nums) {
if (nums == null) {
return null;
}
int i = 0;
List<Integer> list = new ArrayList<>();
while (i < nums.length) {
int curr = nums[i];
int len = 1;
while (i + len < nums.length && nums[i+len] == curr) {
len++;
}
list.add(curr);
i += len;
}
Integer[] array = new Integer[list.size()];
list.toArray(array);
return array;
}
- Subtraction of two Arrays
Suppose you want to do the subtraction of two numbers. Each digit of the numbers is
divided and put in an array. Like A=[1,2, 3, 4, 5], B=[4, 5, 3, 5]. You should output an
array C=[7, 8, 1, 0].Remember that your machine can’t hand numbers larger than 20.
public static List<Integer> subtraction (int[] a, int[] b) {
if (a == null || b == null || a.length < b.length) {
return null;
}
int i = a.length - 1;
int j = b.length - 1;
List<Integer> result = new ArrayList<>();
while (j >= 0) {
if (a[i] >= b[j]) {
result.add(0, a[i] - b[j]);
} else {
a[i-1]--;
result.add(0, a[i] + 10 - b[j]);
}
j--;
i--;
}
while (i > 0) {
if (a[i] >= 0) {
result.add(0, a[i]);
} else {
a[i-1]--;
result.add(0, 10 + a[i]);
}
i--;
}
if (i == 0 && a[i] != 0) {
result.add(0, a[i]);
}
return result;
}
- Basketball Hit Rate
The hit rate of the basketball game is given by the number of hits divided by the number of
chances. For example, you have 73 chances but hit 15 times, then your hit rate is
15/73=0.205 (keep the last3 digits). On average, you have 4.5 chances in each basketball
game. Assume the total number of games is 162. Write a function for a basketball player.
He will input the number of hits he has made, the number of chances he had, and the
number of remaining games. The function should return the number of future hits, so that
he can refresh his hit rate to 0.45
public static int basketballHit (int remaining, int hits, int chances) {
if (remaining < 0 || chances < 0 || hits < 0 || chances + remaining == 0) {
throw new IllegalArgumentException();
}
int result = (int) Math.ceil(0.45 * (chances + remaining * 4.5) - hits);
return result;
}
- Clock Angle
We are given a specific time(like 02:23), we need to get the angle between hour and
minute(less than 180)
public static int clockAngle (int hr, int min) {
if (hr < 0 || hr > 12 || min < 0 || min > 60) {
throw new IllegalArgumentException();
}
int hrAngle = hr * (360 / 12);
int minAngle = min * (360 / 60);
int diffAngle = Math.abs(hrAngle - minAngle);
if (diffAngle > 180) {
diffAngle = 360 - diffAngle;
}
return diffAngle;
}
- Jump Chess
There’s a N*N board, two players join the jump game. The chess could go vertically and
horizontally. If the adjacent chess is opponent player’s and the spot beside that is empty, then
the chess could jump to that spot. One chess could not been jumped twice. Given the position
of the spot on the board, write the program to count the longest length that chess could go.
public static int jumpChess (int[][] grid, int i, int j) {
if (grid == null || grid.length == 0 || grid[0].length == 0 || i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
throw new IllegalArgumentException();
}
int len = helper(i, j, grid, 0);
return len;
}
private static int helper (int i, int j, int[][] grid, int len) {
System.out.println(i + " , " + j + " len: " + len);
grid[i][j] |= 4;
int max = len;
if (i - 2 >= 0 && grid[i-1][j] == 2 && grid[i-2][j] == 0) {
grid[i-1][j] |= 4;
max = Math.max(max, helper(i - 2, j, grid, len + 1));
}
if (i + 2 < grid.length && grid[i+1][j] == 2 && grid[i+2][j] == 0) {
grid[i+1][j] |= 4;
max = Math.max(max, helper(i + 2, j, grid, len + 1));
}
if (j - 2 >= 0 && grid[i][j-1] == 2 && grid[i][j-2] == 0) {
grid[i][j-1] |= 4;
max = Math.max(max, helper(i, j - 2, grid, len + 1));
}
if (j + 2 < grid[0].length && grid[i][j+1] == 2 && grid[i][j+2] == 0) {
grid[i][j+2] |= 4;
max = Math.max(max, helper (i, j + 2, grid, len + 1));
}
return max;
}
- Substring Addition
Write a program to add the substring. eg :say you have a list {1 7 6 3 5 8 9 } and user is
entering a sum 16. Output should display(2-4) that is {7 6 3} cause 7+6+3=16.
public static String substringAddition (int[] nums, int target) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException();
}
int i = 0;
int j = 0;
int sum = nums[i];
while (j < nums.length) {
if (i > j) {
j++;
if (j == nums.length) {
return null;
}
i = j;
sum = nums[i];
}
if (sum > target) {
sum -= nums[i];
i++;
} else if (sum < target) {
j++;
if (j == nums.length) {
return null;
}
sum += nums[j];
} else {
return "(" + i + ", " + j + ")";
}
}
return null;
}
- Balanced String
Given a string that has{},[],() and characters. Check if the string is balanced. E.g. {a[(b)]}
is balanced. {a[(b])} is unbalanced.
public static boolean balanceStr (String s) {
if (s == null || s.length() == 0) {
throw new IllegalArgumentException();
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char temp = s.charAt(i);
if (temp == '(' || temp == '{' || temp == '[') {
stack.push(temp);
continue;
}
if (temp == ')') {
char curr = stack.pop();
if (curr != '(') {
return false;
} else {
continue;
}
}
if (temp == ']') {
char curr = stack.pop();
if (curr != '[') {
return false;
} else {
continue;
}
}
if (temp == '}') {
char curr = stack.pop();
if (curr != '{') {
return false;
} else {
continue;
}
}
}
return true;
}
- Edge Detection
Two-dimensional array representation of an image can also be represented by a
one-dimensional array of W*H size, where W represent row and H represent column size
and each cell represent pixel value of that image. You are also given a threshold X. For
edge detection, you have to compute difference of a pixel value with each of its adjacent
pixel and find maximum of all differences. And finally compare if that maximum difference
is greater than threshold X. if so, then that pixel is an edge pixel and have to display it.
public static void edgeDetection (int[]image, int col, int threshold) {
if (image == null || col < 1 || image.length % col != 0) {
throw new IllegalArgumentException();
}
List<Integer> result = new ArrayList<>();
int row = image.length / col;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int curr = image[i*col+j];
int minRow = Math.max(0, i - 1);
int maxRow = Math.min(row - 1, i + 1);
int minCol = Math.max(0, j - 1);
int maxCol = Math.min(col - 1, j + 1);
System.out.println(curr);
if (greaterThanThreshold(image, curr, threshold, minRow, minCol, maxRow, maxCol, col)) {
System.out.println("Element NO" + (i * col + j + 1) + " is edge pixel.");
}
}
}
}
private static boolean greaterThanThreshold (int[] image, int curr, int threshold, int minRow, int minCol, int maxRow, int maxCol, int col) {
int max = 0;
for (int i = minRow; i <= maxRow; i++) {
for (int j = minCol; j <= maxCol; j++) {
max = Math.max(max, Math.abs(curr - image[i*col+j]));
}
}
return max > threshold;
}
- Plus Equal Number
Given a number find whether the digits in the number can be used to form an equation
with + and ‘=’. That is if the number is123, we can have an equation of 1+2=3. But even
the number 17512 also forms the equation 12+5=17.
public static void equation (int num) {
if (num < 100) {
throw new IllegalArgumentException();
}
String numStr = Integer.toString(num);
for (int i = 1; i <= numStr.length() / 2; i++) {
for (int j = i + 1; j <= numStr.length() / 2 + i; j++) {
int num1 = Integer.parseInt(numStr.substring(0, i));
int num2 = Integer.parseInt(numStr.substring(i, j));
int num3 = Integer.parseInt(numStr.substring(j));
if (checkSum(num1, num2, num3)) {
return;
}
}
}
}
private static boolean checkSum (int num1, int num2, int num3) {
if (num1 + num2 == num3) {
System.out.println("" + num1 + num2 + num3 + ": " + num1 + "+" + num2 + "=" + num3 );
return true;
} else if (num1 + num3 == num2) {
System.out.println("" + num1 + num2 + num3 + ": " + num1 + "+" + num3 + "=" + num2);
return true;
} else if (num2 + num3 == num1) {
System.out.println("" + num1 + num2 + num3 + ": " + num2 + "+" + num3 + "=" + num1);
return true;
} else {
return false;
}
}
- Octal and Decimal Palindrome
The decimal and octal values of some numbers are both palindromes sometimes. Find such
numbers within a given range.
public static List<Integer> octalAndDecimalPalindrome (int start, int end) {
if (start > end || end < 0) {
throw new IllegalArgumentException();
}
List<Integer> result = new ArrayList<>();
for (int i = start; i <= end; i++) {
String decimal = Integer.toString(i);
if (isPalindrome(decimal)) {
String octal = makeOctal(i);
if (isPalindrome(octal)) {
result.add(i);
}
}
}
return result;
}
private static boolean isPalindrome (String numStr) {
int i = 0;
int j = numStr.length() - 1;
while (i < j) {
if (numStr.charAt(i) != numStr.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
private static String makeOctal (int num) {
StringBuilder sb = new StringBuilder();
int index = 1;
while (num != 0) {
int curr = num % 8;
sb = sb.insert(0, Integer.toString(curr));
num /= 8;
}
return sb.toString();
}
- **Anagram
Enumerate all possible anagrams of a random string where capital letters, numbers, and
symbols are not allowed to move within the string.
(Version1. anagrams 输入一个String， 1.大写字母不能变小写 2.大写字母或者其他字符位置不
变 3.不能有数字0-9. 4. 根据小写字符输出anagrams.)
(Version2. Anagrams 有四个原则：1、Character case 不能变（A 不能变a）。2、只有小写能
移动（大写和特殊符号不能动位置）。3、数字是非法输入。 4、忘了。。 总之最后输出所有满
足条件的anagrams。)
(Version3. 不能输入数字（这个要validate input），然后字母和其他符号位置不变，permutate
写字母)
(Version4. Anagram 的题，要求大写字母不用动，还有就是数字是invalid input。。。)
(Given a string. symbols, capital letter and numbers cannot move, print all anagrams.)
(Related) **Permutation
Get a string (word) from user, then make every possible permutation words. Ex. Input: tree
Output： tree, rett, rete, reet, etre, eetr, eert, eter, eret, teer, reet…
(Given a password in number: write an algorithm to print all possible combinations of that
password.
Hint: try from to go from all possible combinations of lower bound to the valid upper bounds.)
public static List<String> anagram (String input) {
if (input == null) {
throw new IllegalArgumentException();
}
List<String> result = new ArrayList<>();
List<Integer> positions = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char curr = input.charAt(i);
if (curr >= 'a' && curr <= 'z') {
positions.add(i);
}
}
List<List<Integer>> permutations = new ArrayList<List<Integer>>();
helper(permutations, new ArrayList<Integer>(), positions);
char[] inputArray = input.toCharArray();
char[] modifications = input.toCharArray(); //需要两个
for (List<Integer> list: permutations) {
for (int i = 0; i < positions.size(); i++) {
modifications[positions.get(i)] = inputArray[list.get(i)];
}
String temp = new String(modifications);
result.add(temp);
System.out.println(temp);
}
return result;
}
private static void helper (List<List<Integer>> result, List<Integer> curr, List<Integer> options) {
if (options.size() == 0) {
result.add(curr);
return;
}
for (Integer i: options) {
curr.add(i);
List<Integer> changes = new ArrayList<Integer>(options); //for 内部不能改变options
changes.remove(i);
helper(result, new ArrayList<Integer>(curr), changes);
curr.remove(i);
}
}
- ***Cards Play
54 张牌, 每张牌上 1-9, A-E 各一个数字 + 一个Letter, 比如 3D, 4F, 5A, 7C; 有一个string 输入,
写一个program 每次读4 张牌, 1 到4，如果发现 1 和 4 letter 一样， 丢弃 中间 2 张，在重新读
1 号 位置 到 4 号 4 张牌， 如果1 和4， number 一样， 4 张全部不要， 如果 又没有 number
一样，也没有 letter 一样， 读 2 到5 号 新的4 张牌，再比较 first card 和 last card ， 做同样的
事情， 最后如果全部扔掉, print You Win, 如果手里还剩牌，print You lose 和牌的个数；如果
数字相同 就全部丢掉， 如果数字不同，比较字母 ；如果字母相同， 丢中间的2 张； 如果 字母
数字 全部不同， index 到 2 3 4 5 张 card； 做一样的事情； 但是只要丢牌 index 就 重新 开始
1,2,3,4;
public static boolean youWin (String input) {
if (input == null || input.length() % 2 != 0) {
throw new IllegalArgumentException();
}
List<String> list = new ArrayList<>();
for (int i = 0; i < input.length() - 1; i += 2) {
list.add(input.substring(i, i + 2));
}
int start = 0;
while (start < list.size() - 3) {
String first = list.get(start);
String forth = list.get(start + 3);
if (first.charAt(1) == forth.charAt(1)) {
list.remove(start);
list.remove(start);
start = 0;
} else if (first.charAt(0) == forth.charAt(0)) {
for (int i = 0; i < 4; i++) {
list.remove(start);
}
start = 0;
} else {
start++;
}
}
return list.size() == 0;
}
void printNthFromLast(int n)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0;
if (head != null)
{
while (count < n)
{
if (ref_ptr == null)
{
System.out.println(n+" is greater than the no "+
" of nodes in the list");
return;
}
ref_ptr = ref_ptr.next;
count++;
}
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
System.out.println("Node no. "+n+" from last is "+
main_ptr.data);
}
}
你有三种篮子能装， 6，9，20。 给你一个数N, 找出所有正好装完N 的组合
static int[] basket = {6, 9, 20};
public static void fillBasket (int n) {
if (n <= 0) {
return;
}
List<List<Integer>> result = new ArrayList<>();
int[] maxLen = new int[basket.length];
for (int i = 0; i < basket.length; i++) {
maxLen[i] = n / basket[i];
}
helper(result, new ArrayList<Integer>(),0, 0, maxLen, n);
for (List<Integer> list: result) {
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " of " + basket[i] + " ");
}
System.out.println();
}
}
private static void helper (List<List<Integer>> result, List<Integer> curr,int sum, int pos, int[] maxLen, int target) {
if (pos == basket.length) {
if (sum == target) {
result.add(new ArrayList<>(curr));
}
return;
}
if (sum > target) {
return;
}
int max = maxLen[pos];
int num = basket[pos];
for (int i = 0; i <= max; i++) {
List<Integer> next = new ArrayList<>(curr);
next.add(i);
helper(result, next, sum + i * num, pos + 1, maxLen, target);
}
}
OA：
今天完成了OA，除了编程，其他三个部分地里都有，确实不是很难，MIIS新语言稍微花点时间，仔细就好了
编程题有两道没见过。
- Multiplicative Encryption. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
之前没见过这题。 说是要将一段text（就是一个String）加密。每一个alphabetic字符对应一个数 A-1， B-2，Z-26. 给一个key是一个整数N。
假设N=2， 那么A变成 1*N%26=2， A变成2对应的B。 非alphabetic的字符不用进行encryption。 要求输出加密后的文本。
2.Hunkey Hybrid
又是没见过的。说是有一家企业做了一个车载应用，这个应用记录行车的数据，有当前fuel的量，miles，minutes，还有speed。
这四种数据都是以数组的形式记录。 这个应用在每个时间点会记录数据并把数据加入每个字符串。fuel数组的数字代表记录时车的油量，miles数字代表自上次记录行了多少miles，minutes代表上次记录到这次之间间隔的时间，speed代表记录时的车速。
举个例子，下面是一段行车的数据。.
fuel 5, 4, 3, 8, 7, 5, 3, 6, 4, 3.
miles 0, 25, 30, 0, 20, 25, 30, 0, 20, 15.
minutes 0, 20, 25, 0, 15, 20, 26, 0, 24, 13
speed 0, 65, 0, 0, 45, 55, 0, 0, 55, 24
on off on off on
车会停下来加油，之后再启动。车启动和停止的时候一定会做一次记录。
题的问题是要求写一个函数，输入时行车数据，输出是根据输入的行车数据计算的这段时间的MPG，MPH。
并且要对行车数据进行validate，看是否是合法的数据。
- Telephone number
题库里有，让产生电话号码，以三个数不能有，包含4的必须以4打头的那道。
4.Transpose String
题库里有，让把一个字符串经过transpose变换成另一个字符串，只能交换字符串里相邻的字符。