Day 1
字符串转为整数 (atoi)
2021.11.18
问题描述
问题是面试官描述的，如下：
接受输入一串数字（可带正负号），将其转换为int类型并输出，不能使用atoi函数等。面试官说不用考虑用户输入非法。
我的思路
面试的时候，想到的是把字符串转换成char数组，数的位置序号正好和数组位置是对应的，可以按照权值展开来计算。并不是优解，因为转换为了char数组，使用了辅助空间，空间复杂度变大。
要点归纳
- 算数；
- 有无符号；
- 考虑int溢出；
渣代码
public class autoInt {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String input = in.next();
System.out.println(autoInt(input));
}
public static int autoInt(String str){
int isSign =0;
int isNag = 0;
if(str == null) return 0;
if(str=="-2147483648") return -2147483648;
if(str.charAt(0)=='+'||str.charAt(0)=='-'){
isSign=1;
if(str.charAt(0)=='-') isNag=1;
}
//char[] st = str.toCharArray();
int result = 0;
for (int i = 0+isSign;i<str.length();i++){
result =result*10+(str.charAt(i)-'0');
if(result<0){
System.out.println("overflow");
return 0;
}
}
if(isNag==1){
return -result;
}
return result;
}
}
Day 2
第一个错误版本
问题描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
我的思路+解法
递归解决：用二分每次把全对或者全错的部分截断，直到只剩下一对一错，返回后一个结果；
效果：用时击败38.95%;内存消耗击败11.49%；菜啊
结论：应该是想麻烦了，而且使用递归会导致更多的资源消耗；
//每次把全对或者全错都截断；
public class Solution extends VersionControl {
public int firstBadVersion(int n){
if(isBadVersion(1))
return 1;
return Cut(1,n);
}
public int Cut(int start,int end){
if(end-start==1)
return end;
long secure = ((long)start+end)/2;
int mid =(int)secure;
//中间为坏，截去后半截
if(isBadVersion(mid)){
return Cut(start,mid);
}
//中间为好，截去前半截
else{
return Cut(mid,end);
}
}
}
更好的解：
优化的地方：
别转换成long类型，换种方法来解决溢出问题:
mid = low+(high-low)/2;不用递归，而是直接用while
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int low = 1;
int high=n;
int mid =1;
while(low<high){
mid = low+(high-low)/2;
if(isBadVersion(mid)){
high = mid;
}else{
low = mid+1;
}
}
return high;
}
}
Day 3
有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
我的思路
找到正负数的分界线，然后用两个游标，负数往左滑，正数往右滑，比较大小。当正数或者负数一方耗尽时，直接全部把剩余的数接上；
要注意的点：全正或者全负的时候；0算正数还是负数；
渣代码
//总感觉全正数的时候更优化，但是没找到更优雅的解法
class Solution {
public int[] sortedSquares(int[] nums) {
//找分界线；
int divide = 0;
//全正
if(nums[0]>=0) divide=0;
//全负；
else if(nums[nums.length-1]<=0) divide=nums.length-1;
else{
for(int i = 0;i<nums.length-1;i++){
if((nums[i]*nums[i+1]<=0)) {
divide=i;
break;
}
}
}
//正数指针
int i = divide+1;
//负数指针
int j = divide;
//写头
int index = 0;
int[] result = new int[nums.length];
//while这里有问题，比如全正全负
while((i<=nums.length-1) && (j)>=0){
if(nums[i]*nums[i]<=nums[j]*nums[j]){
result[index]=nums[i]*nums[i];
i++;
}else{
result[index]=nums[j]*nums[j];
j--;
}
index++;
}
//剩下的
while(i<=nums.length-1){
result[index]=nums[i]*nums[i];
i++;
index++;
}
while(j>=0){
result[index]=nums[j]*nums[j];
j--;
index++;
}
return result;
}
}
另一种解法（leetcode上的）
思路：不用考虑正负，直接从数组两端向中间读数比较；
我的思考：这样会不会多余了比较次数，比如全正全负时，就需要比较length次；而找到正负分界点做的指针的比较次数在大多情况下都更少；
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
} else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
}
轮转数组
解法一
直接每个元素右移动k次--BiBi超出时间限制了
class Solution {
public void rotate(int[] nums, int k) {
for(int i=1;i<=k;i++){
int temp = nums[nums.length-1];
for(int j = nums.length-1 ;j>0;j--){
nums[j]=nums[j-1];
}
nums[0]=temp;
}
}
}
解法二
也是简单粗暴，建立一个等长的辅助数组，把元素组0开始，length-k个元素拷贝到新数组的从k到末尾；再拷贝元素组的最后k个到新数组前面，最后把辅助数组的内容贴过去。
注意的点：数组拷贝时要拷贝的东西；考虑当移动次数大于数组元素个数时，取k=k%len；
效果：用时：击败了63.31%，内存消耗：击败了88.03%
public void rotate(int[] nums, int k) {
if(k>nums.length){
k=k%nums.length;
}
int[] helper =new int[nums.length];
System.arraycopy(nums,0,helper,k,nums.length-k);
for(int i =0;i<k;i++){
helper[i]=nums[nums.length-k+i];
}
for(int i =0;i<nums.length;i++)
nums[i]=helper[i];
}
}
折腾很久的解法三
思路：为了防止覆盖，把数组拆成(len/k)个长度为k的组+剩余部分(len%k)；形如，移动后为;将为一组来移动；
疑惑：用的数组长度为k，且k=k%len,辅助数组的长度小于解法二的len长数组，为什么内存消耗反而变大了。
效果：64%；65%
class Solution {
//更直接的方法，新建一个等长的辅助数组
public void rotate(int[] nums, int k) {
// //辅助数组，存放i,i+k,i+2k....
if(k>nums.length) k=k%nums.length;
if(k==0) return;
int times = nums.length / k;
int[] overflow =(int[])Arrays.copyOfRange(nums,nums.length-k,nums.length);
//开始分组复制、
for(int i =0;i<k;i++){
for(int n = times;n>0;n--){
if(i+n*k<nums.length)
nums[i+n*k]=nums[i+(n-1)*k];
}
}
for(int i=0;i<overflow.length;i++){
nums[i]=overflow[i];
}
}
//???为什么啊，解法二用了一个等长数组，解法算只用了长度为一定小于len的数组，，，为什么内存消耗变大了
}
完全没想到的解法：翻转数组
但是还是不知道原理，禁止在麻瓜面前使用魔法；
从leetcode找的解：
- 先整个把数组反转一下
- 把前半段反转
- 把后半段反转
举例来说:
nums = [1,2,3,4,5,6,7], k = 3
第一步，整个数组反转：7,6,5,4,3,2,1
第二步，把前半段反转：5,6,7,4,3,2,1
第三步，把后半段反转：5,6,7,1,2,3,4
作者：angela-x
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
Day 4
移动0
解法一
思路
一边统计0一边移动，每个元素移动前面的0个数次。
渣代码
class Solution {
public void moveZeroes(int[] nums) {
int movetimes = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]==0) movetimes++;
else if(movetimes!=0) move(nums,i,movetimes);
}
for(int i = 1;i<=movetimes;i++) nums[nums.length-i]=0;
}
public void move(int[] nums,int index,int times){
nums[index-times]=nums[index];
}
}
效果
时间：41.82% 内存：51.84%
更好的解法：双指针
思路
其实和我的解法差不多？但是用指针解放了计数要求。我的解法是指明向前移动多少格，双指针用一个指针来直接说明移动到哪。
效果
时间：65% 内存：35%
代码
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for(int n : nums){
if(n!=0){
nums[index]=n;
index++;
}
}
for(int i = index;i<nums.length;i++){
nums[i]=0;
}
}
}
一次遍历的双指针
思路
要一次遍历完成，就是优化掉放0的过程，把最后的置0变成交换； 上一版的双指针，把0值覆盖，这一步的双指针把0交换；
效果
时间：42% 内存：8%
代码
class Solution {
public void moveZeroes(int[] nums) {
if(nums==null) {
return;
}
//两个指针i和j
int j = 0;
for(int i=0;i<nums.length;i++) {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if(nums[i]!=0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j++] = tmp;
}
}
}
}
今天就到这，上午电脑坏了拿去修了，痛失260。5555
Day 5
题目一
题目描述
解法一
思路
一开始想的类似于二叉树剪枝，但是没有现成的树结构可以用。因为不用判断剪枝条件，所以直接改思路得到二叉树的输出结果:nums元素长度的01序列，序列的位数与nums元素对应，1代表有该元素，0代表没有。由于没有剪枝条件，直接for循环i++生成即可。
注意:
- 又忘记了次方的函数
Math.pow(a,b);返回double。 - 得到二进制的某一位：
方法一：
(num>>位数)&1;
方法二：(num >> (bit -1)) & 1;
效果
时间：100% 空间：94%
渣代码
class Solution {
//从0开始，按照位+1；
public List<List<Integer>> subsets(int[] nums) {
int set =(int)Math.pow(2,nums.length);
ArrayList<List<Integer>> result= new ArrayList<>();
for(int i=0;i<set;i++){
ArrayList<Integer> temp = new ArrayList<>();
for(int j = 0;j<nums.length;j++){
if(((i>>j)&1)==1){
temp.add(nums[j]);
}
}
result.add(temp);
}
return result;
}
}
没想到的解法二：递归
思路
从空集开始，递归加入每个元素到已有的每一个集合；
代码
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result= new ArrayList<>();
//加入空集；
result.add(new ArrayList<Integer>());
for(int num:nums){
List<List<Integer>> newSubsets = new ArrayList<>();
for(List<Integer> subset :result){
ArrayList<Integer> newSubset = new ArrayList<>(subset);
newSubset.add(num);
newSubsets.add(newSubset);
}
result.addAll(newSubsets);
}
return result;
}
}
题目二：
描述
类似压缩机制，输入 a2b3c4d 输出 abbcccdddd；输入数字个字母。破防题
渣代码
public class Solution {
public static void main(String[] args) {
String input ="a2b3c11d";
System.out.println(getSolution(input));
}
public static String getSolution(String str){
String result ="";
for(int i =0;i<str.length();i++){
char letter = str.charAt(i);
//字母
if(str.charAt(i)-'0'>9){
result += letter;
}
//是数字
else{
int j = i;
while (str.charAt(++j)-'0'<10);
letter=str.charAt(j);
int times = Integer.valueOf(str.substring(i,j));
while(times-->0){
result +=letter;
}
i=j;
}
}
return result;
}
}
题目三 两数之和
题目描述
我的解法
思路
逐个取数，算target-num，向后二分查找是否有答案；
渣代码
class Solution {
//逐个向右，二分查找
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
//题目暗示一定有答案，不用判断是否有可能没答案；
for(int i =0;i<numbers.length;i++){
int tar = target-numbers[i];
//本来想提早过滤，但是没有考虑负数+0;
// if(tar>(numbers[i]+numbers[numbers.length-1]))
// continue;
int index = BiSearch(numbers,i+1,tar);
if(index!=-1){
result[0] = i+1;
result[1] = index+1;
break;
}
}
return result;
}
//test过了，能用
public static int BiSearch(int[] nums,int start,int tar){
int left = start;
int right = nums.length;
while(left<=right){
int mid = left+(right-left)/2;
if(mid>nums.length-1) break;
if(nums[mid]==tar) return mid;
else if(nums[mid]>tar) right=mid-1;
else if(nums[mid]<tar) left=mid+1;
}
//失败
return -1;
}
}
京公网安备 11010502036488号