Remove Element
public class Lc27 {
public static int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < nums.length;) {
if (nums[i] == val) {
count++;
move(nums, i);
} else {
i++;
}
}
return nums.length - count;
}
public static void move(int[] nums, int position) {
for (int i = position; i < nums.length - 1; i++) {
nums[i] = nums[i + 1];
}
nums[nums.length - 1] = Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[] nums = { 0, 1, 2, 2, 3, 0, 4, 2 };
int val = 2;
System.out.println(removeElement(nums, val));
}
}Remove Duplicates from Sorted Array，这里用了六种排序，由于题目中有负数导致基数排序可能会出现数组下标错误
import java.util.ArrayList;
import java.util.List; /**
* 俩个排序算法
*
*/
public class Lc26 { public static int removeDuplicates(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
nums[i] = Integer.MAX_VALUE;
count++;
}
}
// nums = insertSort(nums);
// nums = shellSort(nums);
// nums = selectSort(nums);
// nums = bubbleSort(nums);
// quickSort(nums, 0, nums.length - 1);
nums = radixSort(nums); return nums.length - count;
} /**
* 插入排序，遍历所有的元素和以前排好的元素，如果选择的元素比以前的元素小就替换。
*/
public static int[] insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
}
}
return nums;
} /**
* 插入排序，遍历所有的元素和以前排好的元素，如果选择的元素比以前的元素小就替换。 希尔排序：在插入排序的基础上增加控制增量，逻辑分组数据，每次比较俩端数据
*/
public static int[] shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.length; i++) {
for (int j = i; j >= gap; j -= gap) {
if (nums[j] < nums[j - gap]) {
int temp = nums[j];
nums[j] = nums[j - gap];
nums[j - gap] = temp;
}
}
}
}
return nums;
} /**
* 选择排序：再要排序中的数组中，选出最小的数字和第一个数字替换，一次选出第二小的数组和第二个数字替换，一次类推
*/
public static int[] selectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
return nums;
} /*
* 冒泡排序:对当前还未排好顺序的元素进行自顶向下排序，交换相邻的俩个数字，小数上浮，大数下沉
*/
public static int[] bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
return nums;
} /**
* 快速排序：选取一个基准值，利用二分法对其排序
*/
public static void quickSort(int[] nums, int low, int hign) {
if (low < hign) {
int index = getIndex(nums, low, hign);
quickSort(nums, 0, index - 1);
quickSort(nums, index + 1, hign);
}
} private static int getIndex(int[] nums, int low, int hign) {
int temp = nums[low];
while (low < hign) {
while (low < hign && nums[hign] >= temp) {
hign--;
}
nums[low] = nums[hign]; while (low < hign && nums[low] <= temp) {
low++;
}
nums[hign] = nums[low];
}
nums[low] = temp;
return low;
} /**
* 基数排序：低位优先，比较每个数字的低位，依次到高位,注意是正整数
*/
public static int[] radixSort(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
if (max < nums[i]) {
max = nums[i];
}
} int digit = 0;
while (max != 0) {
max /= 10;
digit++;
} // init list
List<List<Integer>> buckets = new ArrayList<List<Integer>>();
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
} for (int i = 0; i < digit; i++) {
for (int j = 0; j < nums.length; j++) {
int key = (int) (nums[j] % Math.pow(10, i + 1) / Math.pow(10, i));
buckets.get(key).add(nums[j]);
}
int count = 0;
for (int j = 0; j < nums.length; j++) { while (buckets.get(j).size() > 0) {
nums[count++] = buckets.get(j).remove(0);
}
}
// 分配完之后，将桶中的元素依次复制回数组
}
return nums;
} public static void main(String[] args) {
int[] nums = { -1, 0, 0, 0, 0, 3, 3 };
System.out.println(removeDuplicates(nums));
} }
Remove Duplicates from Sorted Array II
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map; public class Lc80 {
public static int removeDuplicates(int[] nums) { // map(数字/次数)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
int temp = map.get(nums[i]);
if (temp >= 2) {
count++;
nums[i] = Integer.MAX_VALUE;
} else {
map.put(nums[i], ++temp);
}
} else {
map.put(nums[i], 1);
}
} Arrays.sort(nums);
return nums.length - count;
} public static void main(String[] args) {
int[] nums = { 1, 1, 1 };
System.out.println(removeDuplicates(nums));
}
}
Find the Celebrity
Rotate Array
public class Lc189 {
public static void rotate(int[] nums, int k) {
int previous = 0;
for (int i = 0; i < k; i++) {
previous = nums[nums.length - 1];
for (int j = 0; j < nums.length; j++) {
int temp = previous;
previous = nums[j];
nums[j] = temp;
}
}
}
public static void main(String[] args) {
int[] nums = { 1, 2, 3, 4, 5, 6, 7 };
int k = 3;
rotate(nums, k);
}
} First Missing Positive
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map; public class Lc41 {
public static int firstMissingPositive(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
nums[i] = Integer.MAX_VALUE;
} else {
map.put(nums[i], i);
}
} Arrays.sort(nums);
int min = 0;
int minPosition = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
minPosition = i;
min = nums[i];
break;
}
}
if (min != 1) {
return 1;
} int j = 1;
for (int i = minPosition; i < nums.length; i++, j++) {
if (nums[i] != j) {
return j;
}
}
return j; } public static void move(int[] nums, int position) {
for (int i = 0; i < nums.length - 1; i++) {
nums[i] = nums[i + 1];
}
nums[nums.length - 1] = Integer.MAX_VALUE;
} public static void main(String[] args) {
int[] nums = { 0, 2, 2, 1, 1 };
System.out.println(firstMissingPositive(nums));
}
}
Bulls and Cows
import java.util.ArrayList;
import java.util.List; public class Lc229 {
public static String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;
List<String> secretDigits = convertToAscall(secret);
List<String> guessDigits = convertToAscall(guess);
for (int i = 0; i < secretDigits.size(); i++) {
if (secretDigits.get(i).equals(guessDigits.get(i))) {
bulls++;
} else {
cows++;
}
}
return bulls + "A" + cows + "B"; } private static List<String> convertToAscall(String s) {
StringBuffer sb = new StringBuffer();
char[] chars = s.toCharArray();
for (char c : chars) {
sb.append((int) c).append(",");
}
String[] str = sb.toString().split(",");
List<String> lists = new ArrayList<>();
for (String string : str) {
lists.add(string);
} return lists;
} public static void main(String[] args) {
String secret = "1123";
String guess = "0111";
System.out.println(getHint(secret, guess));
}
}
参考文档：https://cspiration.com/leetcodeClassification#10309