首页 > 代码库 > 今天的题目比较难理解。

今天的题目比较难理解。

2024-08-28 16:05:06   220人阅读

 

(1)String to Integer (atoi)

技术分享

技术分享

解题思路：

实现atoi函数，将字符串转换成整型数。题目要求：

1. 首先需要丢弃字符串前面的空格；(trim函数）

2. 然后可能有正负号（注意只取一个，如果有多个正负号，那么说这个字符串是无法转换的，返回0。比如测试用例里就有个“+-2”）；

3. 字符串可以包含0~9以外的字符，如果遇到非数字字符，那么只取该字符之前的部分，如“-00123a66”返回为“-123”；

4. 如果超出int的范围，返回边界值（2147483647或-2147483648）。

代码如下：

技术分享 
 1 public class Solution {
 2     public int myAtoi(String str) {  
 3         // 1. null or empty string  
 4         if (str == null) {
 5             return 0;  
 6         }  
 7         
 8         // 2. whitespaces  
 9         str = str.trim();  
10         if (str.length() == 0) {
11             return 0;
12         } 
13         
14         // 3. +/- sign  
15         int sign = 1;  
16         int i = 0;  
17         if (str.charAt(0) == ‘+‘) {  
18             i++;  
19         } else if (str.charAt(0) == ‘-‘) {  
20             sign = -1;  
21             i++;  
22         }  
23           
24         // 4. calculate real value  
25         double tmp = 0;  
26         for ( ; i < str.length(); i++) {  
27             int digit = str.charAt(i) - ‘0‘;  
28             if (digit < 0 || digit > 9) {
29                 break;  
30             } 
31             // 5. handle min & max  
32             if (sign == 1) {  
33                 tmp = 10*tmp + digit;  
34                 if (tmp > Integer.MAX_VALUE) return Integer.MAX_VALUE;  
35             } else {  
36                 tmp = 10*tmp - digit;  
37                 if (tmp < Integer.MIN_VALUE) return Integer.MIN_VALUE;  
38             }  
39         }  
40           
41         int ret = (int)tmp;  
42         return ret;  
43     }  
44 }
View Code

(2)Rotate Function

技术分享

解题思路：

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
       = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]

Then,

F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
              = (Bk[0] + ... + Bk[n-1]) - nBk[0]
              = sum - nBk[0]

Thus,

F(k) = F(k-1) + sum - nBk[0]

What is Bk[0]?

k = 0; B[0] = A[0];
k = 1; B[0] = A[len-1];
k = 2; B[0] = A[len-2];
故可以先求出f[0]和sum,然后利用公式逐步求F[1],F[2]...并比较大小选取最大值。
代码如下：
技术分享 
 1 public class Solution {
 2     public int maxRotateFunction(int[] A) {
 3         int allSum = 0;//所有数字之和
 4         int len = A.length;//数组长度
 5         int F = 0;
 6         for (int i = 0; i < len; i++) {
 7             F += i * A[i];//F[0]
 8             allSum += A[i];
 9         }
10         int max = F;
11         for (int i = len - 1; i >= 1; i--) {
12             F = F + allSum - len * A[i];//F[1],F[2],...
13             max = Math.max(F, max);//找出最大值
14         }
15         return max; 
16     }
17 }
View Code

（3）Add Binary

技术分享

解题思路：

从末尾依次对应相加来求，转成int中的相加会使代码比较简洁，因为可以用/和%来分别求出进位和当前往结果中添加的位。然后，把较长的字符串剩下的部分和进位相加放入结果。最后，还要判断进位此时是否为1，如果为1，则需要再往结果中添加1，否则返回结果。

代码一如下：较为简洁

技术分享 
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;//carry进位标志位
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - ‘0‘;
            if (i >= 0) sum += a.charAt(i--) - ‘0‘;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}
View Code

代码二：

技术分享 
 1 public class Solution {
 2     public String addBinary(String a, String b) {
 3         if(a.length() < b.length()){
 4             String tmp = a;
 5             a = b;
 6             b = tmp;
 7         }
 8         
 9         int pa = a.length()-1;
10         int pb = b.length()-1;
11         int carries = 0;
12         String rst = "";
13         
14         while(pb >= 0){
15             int sum = (int)(a.charAt(pa) - ‘0‘) + (int)(b.charAt(pb) - ‘0‘) + carries;
16             rst = String.valueOf(sum % 2) + rst;
17             carries = sum / 2;
18             pa --;
19             pb --;
20         }
21         
22         while(pa >= 0){
23             int sum = (int)(a.charAt(pa) - ‘0‘) + carries;
24             rst = String.valueOf(sum % 2) + rst;
25             carries = sum / 2;
26             pa --;
27         }       
28         
29         if (carries == 1)
30             rst = "1" + rst;
31         return rst;
32     }
33 }
View Code

（4）Nth Digit

技术分享

解题思路：

 * 这里首先分析一下位数和规律
 * 个位数：1-9，一共9个,共计9个数字
 * 2位数：10-99,一共90个，共计180个数字
 * 3位数：100-999，一共900个，共计270个数字
 * 4位数，1000-9999，一共9000个，共计36000个数字
 * 以此类推，
 * 这样我们就可以首先定位到是哪个数，再找到其对应的数字

代码如下：

技术分享 
 1 public class Solution {
 2     public int findNthDigit(int n) {
 3         //小心溢出
 4         int digitType = 1;
 5         long digitNum = 9;
 6         //定位到是几位数
 7         while(n > digitNum * digitType){
 8             n -= (int) digitNum * digitType ;
 9             digitType++;//几位数
10             digitNum *= 10;
11         }
12         //定位到是这些几位数里面的第几个的第几位
13         int indexInSubRange = (n -1) / digitType;//第几个
14         int indexInNum = (n -1) % digitType;//第几位
15         //还原数字
16         int num = (int)Math.pow(10,digitType - 1) + indexInSubRange ;
17         int result = Integer.parseInt((""+num).charAt(indexInNum)+"");
18         return result;
19     }
20 }
View Code

注意：用(n-1)/digitType的原因，因为后面还原数字的时候使用10的幂（10,100，...），但前面其实只有（9,99,...）个数，所有要先减一。

 

今天的题目比较难理解。


联系
我们