-
Notifications
You must be signed in to change notification settings - Fork 0
Array
qpzm7903 edited this page Aug 15, 2018
·
3 revisions
import org.junit.Test;
/**
* Created by on 2018/8/7.
* 对于有数数组，给定target，找出存在的index，或者插入的适合index
*/
public class P35 {
public static int searchInsert(int[] nums, int target) {
int low=0, high = nums.length-1;
int middle= 0;
while(low<=high){
middle = low + (high - low) /2;
if(nums[middle] > target){
high = middle - 1;
}else if (nums[middle] < target){
low = middle + 1;
}else if (nums[middle] == target){
return middle;
}
}
if(nums[middle] < target) return middle+1;
return middle;
}
@Test
public void test() {
assert searchInsert(new int[]{1,3,5,6}, 5) == 2;
assert searchInsert(new int[]{1,3,5,6}, 2) == 1;
assert searchInsert(new int[]{1,3,5,6}, 7) == 4;
assert searchInsert(new int[]{1,3,5,6}, 0) == 0;
}
}import org.junit.Test;
/**
* Created by on 2018/8/8.
* 也就是数组加1运算，数组元素非负，且第一位不是0.
*/
public class P66 {
public int[] plusOne(int[] digits) {
int n = digits.length;
int plus = 1;
for (int i = n - 1; i >= 0; i--) {
plus = (digits[i] + 1)/ 10;
digits[i]= (digits[i]+1)%10;
if(plus<=0) break;
}
if (digits[0] == 0) {
int[] result = new int[n + 1];
result[0] = 1;
for(int i=0;i<n;i++) {
result[i+1] = digits[i];
}
return result;
}
return digits;
}
@Test
public void tset() {
// System.out.println(plusOne(new int[]{1,2,3}));
System.out.println(10%10);
int[] result = plusOne(new int[]{9, 9, 9, 9});
for (int a : result) {
System.out.print(a +" ");
}
}
}import org.junit.Test;
/**
* Created by on 2018/8/8.
* 也就是数组加1运算，数组元素非负，且第一位不是0.
*/
public class P66 {
public int[] plusOne(int[] digits) {
int n = digits.length;
int plus = 1;
for (int i = n - 1; i >= 0; i--) {
plus = (digits[i] + 1)/ 10;
digits[i]= (digits[i]+1)%10;
if(plus<=0) break;
}
if (digits[0] == 0) {
int[] result = new int[n + 1];
result[0] = 1;
for(int i=0;i<n;i++) {
result[i+1] = digits[i];
}
return result;
}
return digits;
}
@Test
public void tset() {
// System.out.println(plusOne(new int[]{1,2,3}));
System.out.println(10%10);
int[] result = plusOne(new int[]{9, 9, 9, 9});
for (int a : result) {
System.out.print(a +" ");
}
}
}import org.junit.Test;
/**
* Created by on 2018/8/8.
*/
public class P167 {
public int[] twoSum(int[] numbers, int target) {
int j=0,i=0;
for(;i<numbers.length;i++) {
if ((j = binarySearch(numbers, target - numbers[i], i+1, numbers.length - 1)) != -1) {
return new int[]{i, j};
}
}
return new int[]{0, 0};
}
public int binarySearch(int[] numbers, int target, int start, int end) {
while (start <= end) {
int middle = start + (end - start) /2;
if (numbers[middle] > target) {
end = middle - 1;
} else if (numbers[middle] < target) {
start = middle + 1;
} else {
return middle;
}
}
return -1;
}
@Test
public void test() {
int[] data = new int[]{2, 7, 11, 15};
int[] result = twoSum(data, 22);
for (int a : result) {
System.out.print(a + " ");
}
}
}import org.junit.Test;
/**
* Created by on 2018/8/8.
*/
public class P167 {
public int[] twoSum(int[] numbers, int target) {
int j=0,i=0;
for(;i<numbers.length;i++) {
if ((j = binarySearch(numbers, target - numbers[i], i+1, numbers.length - 1)) != -1) {
return new int[]{i, j};
}
}
return new int[]{0, 0};
}
public int binarySearch(int[] numbers, int target, int start, int end) {
while (start <= end) {
int middle = start + (end - start) /2;
if (numbers[middle] > target) {
end = middle - 1;
} else if (numbers[middle] < target) {
start = middle + 1;
} else {
return middle;
}
}
return -1;
}
@Test
public void test() {
int[] data = new int[]{2, 7, 11, 15};
int[] result = twoSum(data, 22);
for (int a : result) {
System.out.print(a + " ");
}
}
}import org.junit.Test;
/**
* Created by on 2018/8/9.
* 将数组中0的元素放到后面，非零元素相对位置不变
* 进阶的要求是不适用额外的数组，最小化操作数量
*/
public class P283 {
public void moveZeroes(int[] nums) {
int end = checkZero(nums, nums.length - 1);
for (int i = 0; i < end; i++) {
if (nums[i] == 0) {
nums[i] = nums[end];
nums[end] = 0;
end = checkZero(nums, end - 1);
}
}
}
public int checkZero(int[] nums, int pos) {
for (int i = pos; i >= 0; i--) {
if (nums[i] != 0) return i;
}
return nums.length;
}
/**
* 错误的方法，相对位置变了
*/
@Test
public void test() {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
for (int a : nums)
System.out.print(a + " ");
}
public void moveZeroes1(int[] nums) {
int j = 0, i = 0;
for (; i < nums.length; i++) {
if (i == nums.length - 1) break;
if (nums[i] == 0) {
move(nums, j, i + 1);
j++;
}
}
}
public void move(int[] nums, int start, int end) {
for (int i = start; i < end; i++) {
int temp = nums[start];
nums[start] = nums[start + 1];
nums[start + 1] = temp;
}
}
/**
* 方法2测试
* 依旧错误
*/
@Test
public void test2() {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes1(nums);
for (int a : nums)
System.out.print(a + " ");
}
public void moveZeroes2(int[] nums) {
int j = 0, i = 0;
for (int k = 0; k < nums.length; k++)
if (nums[k] == 0) {
j = k;
break;
}
for (; i < nums.length; i++) {
if (nums[i] != 0 && nums[j] == 0) {
swap(nums, i, j);
j = findZero(nums, j + 1);
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int findZero(int[] nums, int start) {
for (int k = start; k < nums.length; k++) {
if (nums[k] == 0) return k;
}
return 0;
}
/**
* 方法3测试
* OK
* 还需要测试没有0的数据
*
*/
@Test
public void test3() {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes2(nums);
for (int a : nums)
System.out.print(a + " ");
System.out.println();
int[] nums2 = {1,2,0,3,0};
moveZeroes2(nums2);
for(int a:nums2)
System.out.print(a + " ");
System.out.println();
int[] nums3 = {0,1,0,0,0,2,0};
moveZeroes2(nums3);
for(int a:nums3)
System.out.print(a +" ");
System.out.println();
int[] nums4 = {1,2};
moveZeroes2(nums4);
for(int a:nums4)
System.out.print(a +" ");
}
/**
* 使用额外的数组自然最简单了
* @param nums
*/
public void moveZeroes4(int[] nums) {
int k = 0;
int [] temp = new int[nums.length];
for(int i=0;i<nums.length;i++)temp[i] = nums[i];
for(int i=0;i<temp.length;i++){
if(temp[i] != 0)
nums[k++] = temp[i];
}
for(;k<nums.length;k++){
nums[k] = 0;
}
}
/**
* 修正前三个方法
*/
public void moveZeroes5(int[] nums) {
int j=0;
for(int i=0;i<nums.length;i++) {
if(nums[i]!=0)
nums[j++] = nums[i];
}
for(;j<nums.length;j++)
nums[j] = 0;
}
@Test
public void test5() {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes5(nums);
for (int a : nums)
System.out.print(a + " ");
System.out.println();
int[] nums2 = {1,2,0,3,0};
moveZeroes5(nums2);
for(int a:nums2)
System.out.print(a + " ");
System.out.println();
int[] nums3 = {0,1,0,0,0,2,0};
moveZeroes5(nums3);
for(int a:nums3)
System.out.print(a +" ");
System.out.println();
int[] nums4 = {1,2};
moveZeroes5(nums4);
for(int a:nums4)
System.out.print(a +" ");
}
}import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* Created by on 2018/8/14.
* 找出所有出现两次的元素
* 进阶：
* 不使用额外的空间以及使用O(n)的时间，一下思路厉害！
* // when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
res.add(Math.abs(index+1));
nums[index] = -nums[index];
}
return res;
}
因为 1<= a[i] <= n n为数组的size
所以恰好可以用counting 方法
*/
public class P442 {
public List<Integer> findDuplicates(int [] nums) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new LinkedList<>();
for(int i=0;i<nums.length;i++) {
if (map.get(nums[i]) != null) {
map.put(nums[i], 2);
list.add(nums[i]);
} else {
map.put(nums[i], 1);
}
}
return list;
}
}import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by on 2018/8/15.
* 1 ≤ a[i] ≤ n n为数组大小，
* 输出没有在范围里的数字
* 进阶是不使用额外的空间，返回的list不算额外的空间。并且使用O(n)的时间。
* 如果不使用counting数组来辅助的话，直接使用ArrayList?好像也是可以的
* 看一段优秀的代码，使用nums[nums[i] -1] = -nums[nums[i]-1]标记见过的
*
* public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]) - 1;
if(nums[val] > 0) {
nums[val] = -nums[val];
}
}
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
ret.add(i+1);
}
}
return ret;}
*/
public class P448 {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums.length==0 || nums== null)return res;
int[] counting = new int[nums.length + 1];
for(int i=0;i<nums.length;i++) {
counting[nums[i]]++;
}
for(int i=1;i<counting.length;i++) {
if(counting[i] == 0 )
res.add(i);
}
return res;
}
@Test
public void test() {
int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
List<Integer> list = findDisappearedNumbers(nums);
for (Integer a : list) {
System.out.print(a + " ");
}
}
}/**
* Created by on 2018/8/14.
* 给定二进制数组，找到此数组中连续1的最大数量
*/
public class P485 {
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0;
int max = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] == 1){
count ++;
if(max < count) max = count;
}else{
count =0;
}
}
return max;
}
}import org.junit.Test;
/**
* Created by on 2018/8/15.
* 提莫队长的攻击，计算中毒时间
*/
public class P495 {
public int findPoisonedDuration(int[] timeSeries, int duration) {
if(timeSeries.length == 0 || timeSeries == null || duration <= 0 ) return 0;
int count = 0;
int pre = timeSeries[0];
for(int i=1;i<timeSeries.length;i++) {
if (pre + duration > timeSeries[i]) {
count += timeSeries[i] - pre;
} else {
count += duration;
}
pre = timeSeries[i];
}
count += duration;
return count;
}
@Test
public void test() {
int[] time = {1, 4};
int duration = 2;
assert findPoisonedDuration(time,duration) == 4;
int[] time1 = {1, 2};
int duration1 = 2;
assert findPoisonedDuration(time1, duration1) ==3;
}
@Test
public void test1() {
int [] time = {};
int duration = 100000;
System.out.println(findPoisonedDuration(time,duration));
}
}import java.util.Arrays;
/**
* Created by on 2018/8/9.
* 输入的数组数量为2N，则将2N个int分为N组，for i=0 to n sum+= min(ai,bi) 。理解起来就是，首先排序，然后把前面一半小的加起来？
* 错误的理解
* [1,4,3,2] - > 4 = min(1,2 ) + min(3,4)
* 目的是让和最大。
* 看的讨论里的证明，大致如下：
* 首先设定每一对(ai,bi) 中 ai <= bi
* 则sm = a1 + a2 + a3 ... + an
* di = bi - ai
* sa = a1 + b1 + ...an + bn
* sd = b1 - a1 + ... bn - an = d1 + d2 + ... dn
* sa = a1 + a1 + d1 + ... = 2sm + sd
* sm = (sa - sd)/2 sa是常量，只要sd小，所以让每一对尽可能靠近。所以代码？
*/
public class P561 {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum=0;
for(int i=0;i<nums.length;i+=2) {
sum+=nums[i];
}
return sum;
}
}/**
* Created by on 2018/8/14.
* 将数组reshpae，行主序，按行填充。
* public int[][] matrixReshape(int[][] nums, int r, int c) {
if(nums.length == 0 || r * c > nums.length * nums[0].length)
return nums;
int[][] res = new int[r][c];
int row = 0;
int col = 0;
for(int i = 0; i < nums.length; i++){
for(int j = 0; j < nums[i].length; j++){
res[row][col++] = nums[i][j];
if(col == c){
row++;
col = 0;
}
}
}
return res;
}
*/
public class P566 {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int sum = nums.length*nums[0].length;
if(sum < r *c )
return nums;
int [][] result = new int[r][c];
int [] temp = new int[sum];
int k=0;
for(int i=0;i<nums.length;i++) {
for(int j=0;j<nums[0].length;j++) {
temp[k++] = nums[i][j];
}
}
k = 0;
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
result[i][j] = temp[k++];
}
}
return result;
}
}import org.junit.Test;
/**
* Created by on 2018/8/10.
*
*/
public class P766 {
/**
* 不够好的方法，这样进行了很多++操作，应该是对于每一个元素，都检查它与右下角的元素是否相同即可。检查的矩阵为 n-1 * m-1 。
*/
public boolean isToeplitzMatrix(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int temp=0;
for(int k=n-2;k>=0;k--) {
for(int i=k, j=0,flag=0;i<n && j<m;i++,j++,flag++) {
if (flag == 0) {
temp = matrix[i][j];
} else if (temp == matrix[i][j]) {
} else {
return false;
}
}
}
for(int k=m-2;k>=0;k--) {
for(int i=0, j=k,flag=0;i<n && j<m;i++,j++,flag++) {
if (flag == 0) {
temp = matrix[i][j];
} else if (temp == matrix[i][j]) {
} else {
return false;
}
}
}
return true;
}
@Test
public void test() {
int[][] matrix = {{1, 2, 3, 4}, {5, 1, 2, 3}, {9, 5, 1, 2}};
assert true == isToeplitzMatrix(matrix);
int [][] martix1 = {{0},{1},{1}};
assert true == isToeplitzMatrix(martix1);
int[][] matrix2 = {{1, 2}, {2, 2}};
assert false == isToeplitzMatrix(matrix2);
}
/**
* 更好的解决方法
*
*/
public boolean isToeplitzMatrix1(int[][] matrix) {
for (int i = 0; i < matrix.length - 1; i++) {
for (int j = 0; j < matrix[i].length - 1; j++) {
if (matrix[i][j] != matrix[i + 1][j + 1]) return false;
}
}
return true;
}
}import org.junit.Test;
/**
* Created by on 2018/8/9.
* 给定二维数组表示图像，将图像水平翻转，然后反转，接着返回
* 水平就是每一行都会反转，[1,0,1,0] -> [0,1,0,1]
* 反转就是 [ [A] , [B] ] -> [ [B], [A] ]。
*/
public class P832 {
public int[][] flipAndInvertImage(int[][] A) {
for(int i=0;i<A.length;i++) {
horizontallyFlip(A[i]);
invert(A[i]);
}
return A;
}
public void horizontallyFlip(int[] nums) {
int start=0,end=nums.length-1;
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;end--;
}
}
public void invert(int[] nums) {
for(int i=0;i<nums.length;i++) {
nums[i] ^= 1;
}
}
@Test
public void test() {
int[] nums = {1,0,0,1,1,1};
horizontallyFlip(nums);
int[] result = {1,1,1,0,0,1};
for (int a : nums) {
System.out.print(a +" ");
}
// System.out.println();
// invert(nums);
// for (int a : nums) {
// System.out.print(a +" ");
// }
}
}/**
* Created by on 2018/8/10.
* 矩阵转置
*/
public class P867 {
public int[][] transpose(int[][] A) {
int n = A.length;
int m = A[0].length;
int [][] result = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[j][i] = A[i][j];
}
}
return result;
}
}