二维数组中的查找
public boolean Find(int target, int [][] array) {
if(array==null || array.length==0){
return false;
}
int m = array.length;
int n = array[0].length;
//从该二维数组的右上角 (0,n-1) 位置开始查找
//类似二分查找
for(int i=0,j=n-1;i<m && j>=0;){
if(array[i][j]==target){
return true;
}else if(array[i][j]<target){ //(array[i][j] 值小了，向下移动值才会变大
i++;
}else{
assert array[i][j]>target;
j--;
}
}
return false;
}数组中重复的数字
public boolean duplicate(int numbers[],int length,int [] duplication) {
for(int i=0;i<length;i++){
if(numbers[i]!=numbers[numbers[i]]){
swap(numbers,i,numbers[i]);
i--;
}
}
for(int i=0;i<length;i++){
if(numbers[i]!=i){
duplication[0]=numbers[i];
return true;
}
}
return false;
}
private void swap(int[] nums,int i,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}构建乘积数组
/**
思路：
B0 | 1 A1 A2 A3 A4 ... A(n-2) A(n-1)
B1 | A0 1 A2 A3 A4 ... A(n-2) A(n-1)
B2 | A0 A1 1 A3 A4 ... A(n-2) A(n-1)
B3 | A0 A1 A2 1 A4 ... A(n-2) A(n-1)
B4 | A0 A1 A2 A3 1 ... A(n-2) A(n-1)
...
B(n-2) | A0 A1 A2 A3 A4 ... 1 A(n-1)
B(n-1) | A0 A1 A2 A3 A4 ... A(n-2) 1
*/
public int[] multiply(int[] A) {
if(A==null || A.length==0){
return null;
}
int n=A.length;
int[] B=new int[n];
//计算左下角乘积
B[0]=1;
for(int i=1;i<n;i++){
B[i]=B[i-1]*A[i-1];
}
//计算右上角乘积
int product=1;
for(int i=n-2;i>=0;i--){
product*=A[i+1];
B[i]=B[i]*product; //最后是获取 B[0]=A[1]*A[2]*A[3]*...*A[n-1]
}
return B;
}调整数组顺序使奇数位于偶数前面
//思路一:
//暴力解法
//时间复杂度:O(n)
//空间复杂度：O(n)
//调整数组顺序使奇数位于偶数前面
public void reOrderArray(int [] array) {
if(array==null || array.length==0){
return;
}
int[] newArray = new int[array.length];
int index=0;
for(int i=0;i<array.length;i++){
if(array[i]%2==1){
newArray[index++] = array[i];
}
}
for(int i=0;i<array.length;i++){
if(array[i]%2==0){
newArray[index++] = array[i];
}
}
index=0;
for(int num : newArray){
array[index++] =num;
}
}
@Test
public void test(){
int[] nums={1,2,3,4,5,6,7};
reOrderArray(nums);
}//思路二：
//利用冒泡排序算法的思想：
//每次将偶数冒到最右边（冒泡排序是稳定排序，不用担心顺序问题）
//注意：冒泡排序中是将数字大的冒出，这里是将偶数冒出
//时间复杂度：O(n^2)
//空间复杂度：O(1)
//调整数组顺序使奇数位于偶数前面
public void reOrderArray(int [] array) {
if(array==null || array.length==0){
return;
}
int n = array.length;
for(int i=n-1;i>=0;i--){
for(int j=1;j<=i;j++){ //相邻元素对比，冒出偶数
if(isEven(array[j-1]) && !isEven(array[j])){
//array[j-1] 是偶数，array[j] 是奇数就交换
swap(array,j-1,j);
}
}
}
}
private void swap(int[] nums,int i,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
//判断一个数是否是偶数
private boolean isEven(int num){
return (num%2==0);
}顺时针打印矩阵
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
int m = matrix.length;
int n = matrix[0].length;
int top=0,down=m-1;
int left=0,right=n-1;
while(top<=down && left<=right){
for(int j=left;j<=right;j++){
res.add(matrix[top][j]);
}
top++;
for(int i=top;i<=down;i++){
res.add(matrix[i][right]);
}
right--;
if(top<=down){ // 经过前面的 top++ 后，top 有可能大于 down，此时是没有意义的
for(int j=right;j>=left;j--){
res.add(matrix[down][j]);
}
down--;
}
if(left<=right){ // 经过前面的 right-- 后，right 有可能小于 left,此时是没有意义的
for(int i=down;i>=top;i--){
res.add(matrix[i][left]);
}
left++;
}
}
return res;
}连续子数组的最大和
//思路：
//动态规划思路
//dp[i] 表示以 array[i] 结尾的元素连续子数组的最大连续和
//dp[i-1]>0 时，dp[i] = dp[i-1] + array[i]
//否则，dp[i] = array[i]
//写法一：
//时间复杂度：O(n)
//空间复杂度：O(n)
//连续子数组的最大和
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
//dp[i] 表示以array[i]结尾的元素连续子数组的最大连续和
int[] dp = new int[n];
dp[0] = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
if(dp[i-1]>0){
dp[i] =dp[i-1]+array[i]; //array[i] 加上任意一个 > 0 的数都会大于原来的数
}else{
dp[i] = array[i];
}
res = Math.max(res,dp[i]);
}
return res;
}//写法二:
//时间复杂度：O(n)
//空间复杂度：O(1)
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
int pre1 = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
int pre2 = (pre1>0)?(pre1+array[i]):array[i];
pre1 = pre2;
res = Math.max(res,pre2);
}
return res;
}把数组排成最小的数
//思路：
//可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，
//应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，
//那么应该把 S1 排在前面，否则应该把 S2 排在前面。
import java.util.Arrays;
import java.util.Comparator;
//把数组排成最小的数
public String PrintMinNumber(int [] numbers) {
StringBuilder res = new StringBuilder();
if(numbers==null || numbers.length==0){
return res.toString();
}
int n = numbers.length;
String[] nums = new String[n];
for(int i=0;i<n;i++){
nums[i]=numbers[i]+"";
}
//TODO:定义排序规则
Arrays.sort(nums, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
//如果 s1+s2 < s2+s1，则 s1 排在前面（默认是按照升序排列的）
return (s1+s2).compareTo(s2+s1);
}
});
for(String num:nums){
res.append(num);
}
return res.toString();
}和为 S 的两个数字
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
ArrayList<Integer> res = new ArrayList<>();
int start=0;
int end =array.length-1;
while(start<end){
if(array[start]+array[end]==sum){ //TODO:最先找到的这两个数的乘积最小的。
res.addAll(Arrays.asList(array[start],array[end]));
return res;
}else if(array[start]+array[end]<sum){
start++;
}else {
end--;
}
}
return res;
}数组中出现次数超过一半的数字
//思路：
//Boyer-Moore Majority Vote Algorithm （摩尔投票算法）
// 在线性时间 O(n) 和空间复杂度的情况下，在一个元素序列中查找最多的元素。
// 算法在局部变量中定义一个序列元素(m)和一个计数器(cnt)，初始化的情况下计数器为0。
// 依次扫描序列中的元素，当处理元素 x 的时候：
// 如果计数器为 0，那么将 x 赋值给 m，然后将计数器(cnt) 设置为1；
// 如果计数器不为 0，那么将序列元素 m 和 x 比较，如果相等，那么计数器加 1，
// 如果不等，那么计数器减 1。
// 处理之后，最后存储的序列元素(m)，就是这个序列中最多的元素。
public int MoreThanHalfNum_Solution(int [] array) {
int cnt=0;
int majority = array[0];
for(int num : array){
if(cnt==0){
majority = num;
cnt=1;
}else if(majority==num){
cnt++;
}else{
cnt--;
}
}
cnt=0;
for(int num:array){
if(num==majority){
cnt++;
}
}
return (cnt>array.length/2)?majority:0;
}扑克牌顺子
//思路：使用大小王来补充中间差的牌
//为了方便统计大小王，先进行排序。
public boolean isContinuous(int [] numbers) {
if(numbers==null || numbers.length!=5){
//必须是5张牌，形成顺子
return false;
}
Arrays.sort(numbers);
int n =numbers.length;
int cnt=0; //统计大小王数量
for(int i=0;i<n;i++){
if(numbers[i]==0){
cnt++;
}else{
break;
}
}
for(int i=cnt;i<n-1;i++){
if(numbers[i]==numbers[i+1]){ //牌相等，不可能形成顺子
return false;
}
int diff = numbers[i+1]-numbers[i]-1;
cnt -= diff;
}
return cnt>=0;
}