剑指Offer算法题（java）

秒速五厘米 2022-03-11 15:50 204阅读 0赞

### 剑指Offer算法题java版 ###

*   *  1.构建数组的成绩
     *  2.字符流中第一个不重复的字符

## 1.构建数组的成绩 ##

![在这里插入图片描述][2019030811084798.png]  
1.思路：根据题意可规律可以得出B\[i\]的的值可以有以下矩阵中第i行的乘积  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDYxNDIx_size_16_color_FFFFFF_t_70]

public int[] multiply(int[] A) {
            
            int[] B = new int[A.length];
            // 1.先判断数组A是否为空
            if (A == null || A.length == 0) { return A; }
            // 2.假设B[i] = 1,因为1乘以任何数等于任何数
            B[0] = 1;
            // 3.将B拆分为A[0] *...* A[i-1]和A[n-1]*...*A[i+1] 两部分
            // 4.先计算左下三角形，此时B[0]只有一个元素，舍为1，
            // B[0]不包括A[0]
            for (int i = 1; i < A.length; i++) {
                B[i] = B[i-1] * A[i-1];
            }
            
            int tem = 1;
            // 5.计算右上三角形
            for (int i = A.length-2; i >= 0; i--) {
                tem *=A[i+1];
                B[i] *= tem;
            }
            return B;
    
        }

## 2.字符流中第一个不重复的字符 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDYxNDIx_size_16_color_FFFFFF_t_70 1]  
思路：  
这题可应用字符对应的ASCII的值作为数组的下标，该下标对应的数组元素默认为0，每次传入一个字符，在数组元素原来的基础上加1，遍历数组，把首个元素值为1的下标对应的字符返回

public class Solution {
        int[] hashTable = new int[256];
        StringBuffer buffer =  new StringBuffer();
        
        // Insert one char from stringstream
        public void Insert(char ch) {
            
            buffer.append(ch);
            
            if (hashTable[ch] == 0) {
                // 将ch字符对应的ascii码作为数组的下标
                hashTable[ch] = 1; 
            }else {
            hashTable[ch] = hashTable[ch] + 1;
            }
        }
    
        // return the first appearence once char in current stringstream
        public char FirstAppearingOnce() {
            
            // 转换成char类型的数组
            char[] ch = buffer.toString().toCharArray();
            
            for (char bu : ch) {
                // 利用数组的下标判断该元素是否为1，若是即该ch只出现一次
                if (hashTable[bu] == 1) {
                    return bu;
                }
            }
            return '#';
        }
    }

[2019030811084798.png]: /images/20220311/abaf94c4b95b40f9909476c849253b82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDYxNDIx_size_16_color_FFFFFF_t_70]: /images/20220311/ac1d7abfeabe4c699bee3bf492b46615.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDYxNDIx_size_16_color_FFFFFF_t_70 1]: /images/20220311/f8fc555c11c84dacbb2c2d49487eb6be.png