Q1: leetcode 771
Q2: In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.
Q3: partition
Q4: find kth
Q5: rainbow sort
Q6 : move 1 to the end
Q7: selection sort
Q8: a to the pow of b
Q9: first occurence using binary search
Q10: search in shifted array
'''
//Q
public class Solution {
public int search(int[] array, int target) {
// Write your solution here
if (array == null || array.length == 0) {
return -1;
}
int i = 0;
int j = array.length - 1;
while (i <= j) {
int m = i + (j - i) / 2;
if (array[m] == target) {
return m;
}
if (array[m] < array[j]) {
if (array[m] <= target && array[j] >= target) i = m + 1;
else j = m - 1;
} else {
if (array[m] >= target && array[i] <= target) j = m - 1;
else i = m + 1;
}
}
return -1;
}
}
//
public class Solution {
public int firstOccur(int[] array, int target) {
// Write your solution here
if (array == null || array.length == 0) {//== =
return -1;
}
int i = 0;
int j = array.length - 1;
while (i < j){
int m = (j - i) / 2 + i;
if (array[m] == target) {
j = m;
} else if (array[m] > target) {
j = m - 1;
} else {
i = m + 1;
}
}
if (j >= 0 && array[j] == target) {
return j;
}
return -1;
}
}
//
Q:
public class Solution {
public long power(int a, int b) {
// Write your solution here
return helper(a, b);
}
private long helper(int a, int b) {
//TODO: basecase
if (a == 1 || b == 0) { //
return 1;
}
if (a == -1) {
return (b & 1) == 1 ? -1 : 1;
}
if (b == 1) {
return a;
}
int m = b / 2;
return helper(a, m) * helper(a, b - m);
}
}
//
Q:leetcode 771
class Solution {
public int numJewelsInStones(String J, String S) {
Set<Character> set = new HashSet<>();
for (int i = 0; i < J.length(); i++) {
set.add(J.charAt(i));
}
int result = 0;
for (int i = 0; i < S.length(); i++) {
if (set.contains(S.charAt(i))){
result++;
}
}
return result;
}
}
// public boolean firstCanWin(int n){
return curCanWin(n);
}
private boolean curCanWin(int remaining) {
if (remaining <= 0) {
return true;//pre player can win
}
for (int i = 1; i < 10; i++) {
if (!curCanWin((remaining - i))) {
return true;
}
}
return false;
}
//Q
public boolean firstCanWin(int n){
return curCanWin(n);
}
private boolean curCanWin(int remaining) {
if (remaining <= 0) {
return true;//pre player can win
}
for (int i = 1; i < 10; i++) {
if (!curCanWin((remaining - i))) {
return true;
}
}
return false;
}
// private int partition(int[] a, int left, int right) {
// int pivotIdx = left + (int)(Math.random() * (right - left + 1));
int pivotIdx = right;
int pivot = a[pivotIdx];
swap(a, pivotIdx, right);
int i = left;
int j = right - 1;
while (i <= j) {
if (a[i] < pivot) {
i++;
} else if (a[i] >= pivot) {
j--;
} else {
swap(a, i++, j--);
}
}
swap(a, i, j);
return i;
}
private int findKth(int[] nums, int left, int right, int k) {
int m = k + left;
int privateIdx = partition(nums, left, right);
if (privateIdx == m) {
return privateIdx;
} else if (privateIdx > m) {
return findKth(nums, left,privateIdx - 1,k);
} else {
return findKth(nums, privateIdx + 1, right,k - (privateIdx - left + 1));
}
}
//
public void sort3Ways(int[] a, int target) {
int n = a.length;
int i = 0;
int j = 0;
int k = n - 1;
while (j < k) {
if (a[j] < target) {
swap(a, i++, j++);
} else if (a[j] == target) {
j++;
} else {
swap(a, j, k--);
}
}
return;
}
//Q
//slow 是-1 or 0 的init與slow pointer的物理意義是否是included 十分相關(guān)
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int n = nums.length;
int slow = 0;
int fast = 0;
while (fast < n) {
if (nums[fast] != 0) {
swap(nums, fast++, slow++);
} else {
fast++;
}
}
return;
}
//Q
public class Solution {
public int[] solve(int[] array) {
// Write your solution here
if (array == null || array.length == 0) {
return array;
}
int n = array.length;
for (int i = 0; i < n; i++) {
int tmp = -1;
int tmpVal = array[i];
for (int j = i + 1; j < n; j++) {
if (array[j] < tmpVal) {
tmpVal = array[j];
tmp = j;
}
}
if (i != -1) {
swap(array, tmp, i);
}
}
return array;
}
'''
