基础算法设计

发表于 更新于 分类于 阅读次数： 本文字数： 943 阅读时长 ≈ 3 分钟

1.整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [$−2^{31}$, $2^{31}$ − $1$] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

思路

尝试使用构造字符串或者栈处理，但是题设环境不允许存储64位整数，最终无法判断是否在32位整数范围内。

数学方法解决，证明参考LeetCode官方题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int reverse(int x) {
        int ans=0;//反转后的数
        while(x!=0){
            //判断ans是否超出范围
            if(ans<Integer.MIN_VALUE/10||ans>Integer.MAX_VALUE/10){
                return 0;
            }
            int tmp=x%10;//取模，即取个位数
            x/=10;
            ans=ans*10+tmp;
        }
        return ans;
    }
}

2.加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

思路

数组末尾加一，判断是否有进位，若有则进位，若无则直接返回，以此类推。

注意：加一后有可能位数不变，也有可能位数加一，需要特殊处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] plusOne(int[] digits) {
        int n=digits.length;
        digits[n-1]+=1;//末位加一
        int carry=0;//进位
        for(int i=n-1;i>=0;i--){
            int tmp=digits[i]+carry;//本位+进位
            carry=tmp/10;//向前进位
            digits[i]=tmp%10;//本位
            //判断是否还有进位，若无，则退出循环
            if(carry==0){
                break;
            }
        }
        if(carry==0) return digits;//carry=0，说明位数没有改变
        int[] ans=new int[n+1];
        System.arraycopy(digits,0,ans,1,n);//位数改变处理
        ans[0]=1;
        return ans;
    }
}

3.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

使用哈希表，键为nums[i]，值为对应索引i，遍历数组，若哈希表中已经存在target-nums[i]，说明已经找到有效答案，若无，则将该键值对插入表中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();//哈希表
        for(int i=0;i<nums.length;i++){
            //判读表中是否包含target-nums[i]
            if(map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);//加入哈希表中
        }
        return new int[0];//无有效答案，返回空数组
    }
}

4.所有奇数长度子数组的和

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

思路

方法一.前缀和

计算前缀和，以len=1为起始间隔，每次len+2，依次累加求和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n=arr.length;
        int[] pre=new int[n+1];
        pre[0]=arr[0];
        int sum=0;
        for(int i=0;i<n;i++){
            pre[i+1]=pre[i]+arr[i];//前缀和
        }
        for(int i=0;i<n;i++){
            for(int len=1;i+len<=n;len+=2){
                sum+=pre[i+len]-pre[i];//累加
            }
        }
        return sum;
    }
}

方法二.数学

摘自LeetCode

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int sum=0;
        int n=arr.length;
        for(int i=0;i<n;i++){
            int left=i,right=n-i-1;//左、右个数
            int l_o=(left+1)/2,r_o=(right+1)/2;//两侧奇数
            int l_e=left/2+1,r_e=right/2+1;//两侧偶数
            sum+=arr[i]*(l_o*r_o+l_e*r_e);
        }
        return sum;
    }
}