package y2019.Algorithm.array;
import java.util.Arrays;
import java.util.Stack;
/**
* @ClassName Rotate
* @Description TODO 189. Rotate Array
*
* Given an array, rotate the array to the right by k steps, where k is non-negative.
*
* Input: [1,2,3,4,5,6,7] and k = 3
* Output: [5,6,7,1,2,3,4]
* Explanation:
* rotate 1 steps to the right: [7,1,2,3,4,5,6]
* rotate 2 steps to the right: [6,7,1,2,3,4,5]
* rotate 3 steps to the right: [5,6,7,1,2,3,4]
*
* @Author xiaof
* @Date 2019/7/6 18:44
* @Version 1.0
**/
public class Rotate {
public void solution(int[] nums, int k) {
//这里移动的意思就是把末尾循环遍历到前面,那么只要倒着遍历，然后跳转到开始就可以了
int index = nums.length - k % nums.length; //开始读取的位置
int[] nums2 = new int[nums.length];
int i = 0;
while(i < nums.length) {
if(index >= nums.length) {
index = 0;
}
nums2[i++] = nums[index++];
}
//复制到nums中
System.arraycopy(nums2, 0, nums, 0, nums.length);
}
public static void main(String args[]) {
int A1[] = {-1};
int k = 2;
Rotate fuc = new Rotate();
fuc.solution(A1, k);
System.out.println();
}
}
package y2019.Algorithm.array;
import java.util.HashSet;
import java.util.Set;
/**
* @ClassName ContainsDuplicate
* @Description TODO 217. Contains Duplicate
*
* Given an array of integers, find if the array contains any duplicates.
* Your function should return true if any value appears at least twice in the array,
* and it should return false if every element is distinct.
*
* Input: [1,2,3,1]
* Output: true
* Example 2:
*
* @Author xiaof
* @Date 2019/7/6 20:31
* @Version 1.0
**/
public class ContainsDuplicate {
public boolean solution(int[] nums) {
//判断是否有重复，很简单用set
Set set = new HashSet();
for(int a : nums) {
if(set.contains(a)) {
return true;
} else {
set.add(a);
}
}
return false;
}
}
package y2019.Algorithm.array;
import java.util.HashSet;
import java.util.Set;
/**
* @ClassName ContainsNearbyDuplicate
* @Description TODO 219. Contains Duplicate II
* Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such
* that nums[i] = nums[j] and the absolute difference between i and j is at most k.
*
* Input: nums = [1,2,3,1], k = 3
* Output: true
*
* Input: nums = [1,0,1,1], k = 1
* Output: true
*
* Input: nums = [1,2,3,1,2,3], k = 2
* Output: false
*
* @Author xiaof
* @Date 2019/7/6 20:36
* @Version 1.0
**/
public class ContainsNearbyDuplicate {
public boolean solution(int[] nums, int k) {
//1.因为范围内是k
//那么可以设置一个set，每次存放一个k范围内的值，超出部分丢掉即可
Set set = new HashSet();
for(int i = 0; i < nums.length; ++i) {
if(i > k) {
//如果超出范围，那么把范围外去掉
set.remove(nums[i - k - 1]);
}
//判断是否有重复
if(set.contains(nums[i])) {
return true;
} else {
set.add(nums[i]);
}
}
return false;
}
public static void main(String args[]) {
int A1[] = {1,2,3,1,2,3};
int k = 2;
ContainsNearbyDuplicate fuc = new ContainsNearbyDuplicate();
fuc.solution(A1, k);
System.out.println();
}
}
package y2019.Algorithm.array;
/**
* @ClassName MissingNumber
* @Description TODO 268. Missing Number
* Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
* Input: [3,0,1]
* Output: 2
*
* Input: [9,6,4,2,3,5,7,0,1]
* Output: 8
* @Author xiaof
* @Date 2019/7/6 21:09
* @Version 1.0
**/
public class MissingNumber {
//仔细看题，都是从0开始的，那么要计算从0开始到nums.length之间少的那个，我们只要算出总值减去所有哦值即可
public int solution(int[] nums) {
int sum = (nums.length + 1) * nums.length / 2;
for(int i = 0; i < nums.length; ++i) {
sum -= nums[i];
}
return sum;
}
public static void main(String args[]) {
int A1[] = {3,0,1};
int k = 2;
MissingNumber fuc = new MissingNumber();
fuc.solution(A1);
System.out.println();
}
}
package y2019.Algorithm.array;
/**
* @ClassName MoveZeroes
* @Description TODO 283. Move Zeroes283. Move Zeroes
* Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
* Input: [0,1,0,3,12]
* Output: [1,3,12,0,0]
* @Author xiaof
* @Date 2019/7/6 21:42
* @Version 1.0
**/
public class MoveZeroes {
public void solution(int[] nums) {
//哎，有的时候不能想太多，这个时候就得用2个数组
int[] newNums = new int[nums.length];
int indexNewNums = 0;
for(int n : nums) {
if(n != 0) {
newNums[indexNewNums++] = n;
}
}
//最后补上0
for(; indexNewNums < nums.length; ++indexNewNums) {
newNums[indexNewNums] = 0;
}
//拷贝回去
System.arraycopy(newNums, 0, nums, 0, nums.length);
}
public static void main(String args[]) {
int A1[] = {1,0};
int k = 2;
MoveZeroes fuc = new MoveZeroes();
fuc.solution(A1);
System.out.println();
}
}
package y2019.Algorithm.array;
/**
* @ClassName ThirdMax
* @Description TODO 414. Third Maximum Number
* Given a non-empty array of integers, return the third maximum number in this array.
* If it does not exist, return the maximum number. The time complexity must be in O(n).
*
* Input: [3, 2, 1]
* Output: 1
* Explanation: The third maximum is 1.
*
* @Author xiaof
* @Date 2019/7/6 22:40
* @Version 1.0
**/
public class ThirdMax {
//寻找第三大的数据
public int solution(int[] nums) {
//我们定义长度为3的数组，用来存放前三大的数据，最后0位就是第三大的数据
Integer[] maxNum = new Integer[3];
//初始化数据
for(int i = 0; i < maxNum.length; ++i) {
maxNum[i] = null;
}
for(int i = 0; i < nums.length; ++i) {
//依次和前三比较
int index = 0;
for(int j = 0; j < maxNum.length; ++j) {
if(maxNum[j] == null || maxNum[j] < nums[i]) {
++index;
} else if (nums[i] == maxNum[j]) {
//去除重复数据入列
index = -1;
break;
} else {
break;//如果比max里面的位置小那么直接跳出
}
}
if(index > 0) {
//修改位置
for(int k = 0; k < index - 1; ++k) {
//前面几位从新排序
maxNum[k] = maxNum[k+1];
}
maxNum[index - 1] = nums[i];
}
}
//如果不存在第三大的，那么就获取最大的
int max = maxNum[0] == null ? maxNum[2] : maxNum[0];
return max;
}
public static void main(String args[]) {
int A1[] = {1,2,-2147483648};
int k = 2;
ThirdMax fuc = new ThirdMax();
fuc.solution(A1);
System.out.println();
}
}