一.计算日期到天数转换
注意点：
1.年份为四位数，日期要合法。
2.要考虑闰年2月多少天。
我们可以用一个数组来存放12个月中的日期，Month[12],
1、3、5、7、8、10、12 每月31天，4、6、9、11为30天。 二、2月正常为28天，如果为闰年，则多一天为29天。则把12个月的天数一一填进去。
Month[12]={31,28,31,30,31,30,31,31,30,31,30,31};
然后再讨论闰年的情况。
if(year%4==0&&year%100!=0||year%400==0) { Month[1]++//如果是闰年那么二月就变成29天了。 }
那么该月到现在有多少天呢？
int i; for(i=0;i<month;i++) { daycount=daycount+Month[month-1]; } 然后再加上本月已经过的那几天 daycount+=day;
代码如下
int main() { int year, m; int month[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 }; int day; scanf("%d%d%d", &year, &m, &day); if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) { month[1]++; } int daycount = 0; int i; for (i = 0;i < m - 1;i++) { daycount += month[i]; } daycount += day; printf("%d", daycount); return 0; }
二. 旋转数组的最小数字
旋转数组：打比方把A段搬到B段后面就变成了下面这样：
要求在这里找到最小值该如何找呢？
一.暴力求解：主要对数组遍历取最小数
1.特殊情况，如果数组为空，则直接返回0
2.创建最小值mins，可以是数组第一个也可以是int最大数
3.遍历数组每个元素arr[i]，并更新最小值mins=min(mins,arr[i])
4.遍历结束，直接返回mins.
** * * @param rotateArray int整型一维数组 * @param rotateArrayLen int rotateArray数组长度 * @return int整型 */ int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) { int mins=rotateArray[0]; int i; for(i=0;i<rotateArrayLen;i++) { if(rotateArray[i]<mins) { mins=rotateArray[i]; } } // write code here return mins; }
二.二分法：排序数组的查找问题首先考虑使用 二分法 解决。
最小值一定在序列A这里面如果A序列为升序则A序列的第一个就是最小值，所以每次二分取得中间值与最右边的值进行比较然后就能找到最小值了。
/** * * @param rotateArray int整型一维数组 * @param rotateArrayLen int rotateArray数组长度 * @return int整型 */ int minNumberInRotateArray(int arr[], int rotateArrayLen ) { int left=0; int right=rotateArrayLen-1; while(left < right) { int mid=(left+right)/2; if(arr[mid]>arr[right]) { left=mid+1; } else if(arr[mid]==arr[right]) { right--; } else { right=mid; } } return arr[left]; // write code here }
三.二分查找-I
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param numsLen int nums数组长度 * @param target int整型 * @return int整型 */ int search(int* nums, int numsLen, int target ) { int left=0; int right=numsLen-1; while(left<=right) { int mid=(left+right)/2; if(nums[mid]==target) { return mid; } else if (nums[mid]<target) { left=mid+1; } else { right=mid-1; } } return -1; // write code here }
最基本的二分查找。
四. 二维数组中的查找
是一维数组二分查找的进一步扩展到二维上
这个就每行都进行二分查找。4行就四次二分查找。
两种思路 一种是： 把每一行看成有序递增的数组， 利用二分查找， 通过遍历每一行得到答案， 时间复杂度是nlogn public class Solution { public boolean Find(int [][] array,int target) { for(int i=0;i<array.length;i++){ int low=0; int high=array[i].length-1; while(low<=high){ int mid=(low+high)/2; if(target>array[i][mid]) low=mid+1; else if(target<array[i][mid]) high=mid-1; else return true; } } return false; } } 另外一种思路是： 利用二维数组由上到下，由左到右递增的规律， 那么选取右上角或者左下角的元素a[row][col]与target进行比较， 当target小于元素a[row][col]时，那么target必定在元素a所在行的左边, 即col--； 当target大于元素a[row][col]时，那么target必定在元素a所在列的下边, 即row++； public class Solution { public boolean Find(int [][] array,int target) { int row=0; int col=array[0].length-1; while(row<=array.length-1&&col>=0){ if(target==array[row][col]) return true; else if(target>array[row][col]) row++; else col--; } return false; } }
