其他算法-剑指offer

字数统计: 6.4k字   |   阅读时长: 32分

其他算法

打印从1到最大的n位数

https://www.nowcoder.com/practice/4436c93e568c48f6b28ff436173b997f?tpId=13&tqId=2273153&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 判断每个数字的长度
    主要在于判断数字的长度，数字转成字符串的方式
  1. “” + a
  2. Double.toString(double)
  3. StringBuilder.toString()
  4. while循环
    1
    2
    3
    4
    5
    6
    7
    private int getLength(int n) {
        int i;
        for (i=0; n>0; i++) {
            n /= 10;
        }
        return i;
    }
  • 求出最大长度
    使用以上判断长度的方法都超时，应该直接使用Math.pow(10, n) - 1求出最大长度

不过要强制类型转换，精度只能自动升级，无法自动降级

然后创建该长度的数组，逐一赋值，不过要从1开始，比索引值大1

1
2
3
4
5
6
7
8
9
public int[] printNumbers (int n) {
    // write code here
    int length = (int)Math.pow(10, n)-1;
    int[] result = new int[length];
    for (int i=0; i<length; i++) {
        result[i] = i+1;
    }
    return result;
}

数字序列中某一位的数字

https://www.nowcoder.com/practice/29311ff7404d44e0b07077f4201418f5?tpId=13&tqId=2285751&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • StringBuilder计数
    利用StringBuilder从0开始添加，不停地判断stringbuilder的长度，是否达到或超过了n，超过了返回charAt(n)，使用(int)charAt(n) - (int)’0’转成数字

  • 累加计数
    每增加一个数字，计算它的长度，并累加进总长度，当加到i时，总长度index(注意有第0位，其实第多少位是索引)超过给定的长度n

index = index - getLength(i) 得到还没有加i时的长度，n - index 得到差几位

调整数组顺序奇数位于偶数前面(二)

https://www.nowcoder.com/practice/0c1b486d987b4269b398fee374584fc8?tpId=265&tqId=39274&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D13%26type%3D265&difficulty=2&judgeStatus=undefined&tags=&title=

  • 新建数组
    遍历原来的数组，根据奇偶判断加入到新数组的头部与尾部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] reOrderArrayTwo (int[] array) {
     // write code here
     if (array.length <= 1) {
         return array;
     }
     int[] result = new int[array.length];
     int left = 0, right = array.length-1;
     for (int i=0; i<array.length; i++) {
         if ((array[i] & 1) == 1) {
             result[left++] = array[i];
         } else {
             result[right--] = array[i];
         }
     }
     return result;
}
  • 原位操作
    左边循环找到偶数，右边循环找到奇数，然后交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] reOrderArrayTwo (int[] array) {
    // write code here
    if (array.length <= 1) {
        return array;
    }
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        // while 循环加上left < right ,防止都是奇数或者偶数，left或者right越界
        while (left<right && array[left]%2==1) {
            left++;
        }
        while (left<right && array[right]%2 == 0) {
            right--;
        }
        if (left < right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    return array;
}

构建乘积数组

https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=23445&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 使用除法
    计算数组A的总乘积multi，B[i] = multi / A[i]，但是不排除A[i] 为 0的情况，这时候就需要重新计算除该元素外的其他元素的乘积，代码反而多了起来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] multiply(int[] A) {
    int multi = 1;
    int length = A.length;
    for (int i=0; i<length; i++) {
        multi *= A[i];
    }
    int[] B = new int[length];
    for (int i=0; i<length; i++) {
        if (A[i] == 0) {
            B[i] = this.getMultiExcept(A, i);
        } else {
            B[i] = multi / A[i];
        }
    }
    return B;
}

public int getMultiExcept(int[] A, int index) {
    int multi = 1;
    for (int i=0; i<A.length; i++) {
        if (i == index) {
            continue;
        }
        multi *= A[i];
    }
    return multi;
}
  • 不用除法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int[] multiply(int[] A) {
        int multi = 1;
        int length = A.length;
        int[] B = new int[length];
        for (int i=0; i<length; i++) {
            B[i] = this.getMultiExcept(A, i);
        }
        return B;
    }

    public int getMultiExcept(int[] A, int index) {
        int multi = 1;
        for (int i=0; i<A.length; i++) {
            if (i == index) {
                continue;
            }
            multi *= A[i];
        }
        return multi;
    }
  • 更优算法
    图片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] multiply(int[] A) {
    int multi = 1;
    int length = A.length;
    int[] B = new int[length];
    B[0] = 1;
    // B[i] 为 不包括i的前面所有A元素的乘积
    for (int i=1; i<length; i++) {
        B[i] = B[i-1] * A[i-1];
    }
    int temp = 1;
    // temp 为不包括的后面所有A元素的乘积，再乘以B[i](不包括i的前面所有A元素的乘积) 
    // 就是i前面元素与后面元素的乘积
    for (int i=length-2; i>=0; i--) {
        temp *= A[i+1];
        B[i] = B[i] * temp;
    }
    return B;
}

第一个只出现一次的字符

https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=23258&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 利用map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public int FirstNotRepeatingChar(String str) {
        char[] chars = str.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (int i=0; i<chars.length; i++) {
            map.put(chars[i], map.getOrDefault(chars[i], 0)+1);
        }
        for (int i=0; i<chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }

调整数组顺序使奇数位于偶数前面（一）

https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=13&tqId=1374930&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 写错了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int[] reOrderArray (int[] array) {
        // write code here
        for (int i=0; i<array.length-1; i++) {
            if (array[i] % 2 == 1) {
                continue;
            }
            // 如果array[i]是偶数，和后面的第一个奇数交换
            for (int j=i+1; j<array.length; j++) {
                if (array[j] % 2 == 1) {
                    this.swap(array, i, j);
                    break;
                }
            }
        }
        return array;
    }
    private void swap(int[] array, int src, int des) {
        int temp = array[src];
        array[src] = array[des];
        array[des] = temp;
    }
    [2, 4, 6, 5, 7] 会输出 [5, 7, 6, 2, 4] 没有保证相对顺序
  • 使用奇数、偶数列表保存结果
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int[] reOrderArray (int[] array) {
        // write code here
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        int length = array.length;
        for (int i=0; i<length; i++) {
            if (array[i] % 2 == 1) {
                odd.add(array[i]);
            } else {
                even.add(array[i]);
            }
        }
        int[] result = new int[length];
        for (int i=0; i<odd.size(); i++) {
            result[i] = odd.get(i);
        }
        for (int i=0; i<even.size(); i++) {
            result[i + odd.size()] = even.get(i);
        }
        return result;
    }
  • 原位修改
    遍历数组，找到奇数，插入到已有的奇数后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] reOrderArray (int[] array) {
    // write code here
    int i = 0; // i之前的数组(不包括i)都是奇数
    for (int j=0; j<array.length; j++) {
        // 找到奇数，保存该奇数 [i, j-1]数组整体后移一位
        if (array[j] % 2 == 1) {
            int temp = array[j];
            this.move(array, i, j);
            array[i++] = temp;
        }
    }
    return array;
}
// [startIndex, endIndex-1]范围的数组整体后移一位
private void move(int[] array, int startIndex, int endIndex) {
    for (int i=endIndex; i>startIndex; i--) {
        array[i] = array[i-1];
    }
}

剪绳子

https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=587690&ru=%2Fpractice%2F106f666170554379ab1974e5a601e741&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 贪心
    图片

每段相等时乘积最大，求导发现每段等于e时，乘积最大，e取不到，取3时乘积最大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int cutRope (int n) {
    // write code here
    // 因为至少分成两段，2与3也要分
    if (n <= 3) {
        return n - 1;
    }
    return this.helper(n);
}

private int helper(int n) {
    // 刚好被3剪完，返回1
    if (n == 0) {
        return 1;
    }
    // 不能剪成1，在长度为4的时候剪成2*2
    if (n == 4) {
        return 2 * 2;
    }
    if (n == 2) {
        return 2;
    }
    
    return 3 * helper(n - 3);
}
  • 动态规划
    1
    2
    3
    4
    5
    6
    7
    1. dp[i] 长度为i的绳子最大乘积
    2. dp[i] = max(1 * dp[i-1], 2 * dp[i-2], ..., j*dp[i-j]) 把绳子分成两部分，没剪的部分(j)和剪的部分(dp[i-j])
    3. dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 4
    4. 前后遍历
    5. 6
    dp[i] 0 1 2 3 4 6 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int cutRope (int n) {
    // write code here
    if (n <= 3) {
        return n - 1;
    }
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for (int i=4; i<=n; i++) {
        for (int j=1; j<i; j++) {
            dp[i] = Math.max(dp[i], j * dp[i-j]);
        }
    }
    return dp[n];
}

剪绳子进阶版本

https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741?tpId=13&tqId=2254224&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 快速乘法与快速幂
    要求时间复杂度是O(logn)，之前使用递归的方式不断乘以3时间复杂度是O(n)。可以发现不断乘以3的运算是幂运算，而快速幂时间复杂度正好是O(logn)

可以通过 number % 3 的结果提前知道3的幂运算次数，从而使用快速幂运算

numer % 3 == 0 幂运算次数 number / 3

number % 3 == 1 需要减去一个3，和剩下的1凑成4 幂运算次数 number / 3 - 1

number % 3 == 2 幂运算次数 number / 3

由于number 数字特别大，在快速幂中，result * result 可能会超过long的最大值

在所以需要自己定义乘法操作，在防止溢出，这也是题目让最后结果取模一个数字的原因

可以在快速乘法中取模给定的数字，防止溢出

快速乘法(快速乘法并不快，而是用加法代替乘法，在求解的过程中取模，防止溢出)

a * b = a * (1 * 2^(n-1) + 0 * 2^(n-2) + … + 1 * 2^(2) + 0 * 2^(1) + 1 * 2^(0))

a * b = a * 2^(n-1) * 1 + a * 2 (n - 2) * 0 + …

可以发现每一项都是 a * 二进制中的某一位 * 2的幂 可以通过位运算得到2的幂与二进制中的某一位，a * 2的幂可以通过移位实现，左移n位，相当于乘以2的n次幂

进阶版绳子的最大长度从60扩大为了10^14，在快速幂result * result时可能溢出，需要使用快速乘法，在函数中取模运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private long mod = 998244353;
public long cutRope (long number) {
    // write code here
    if (number <= 3) {
        return number - 1;
    }
    long result;
    if (number % 3 == 0) {
        result = this.quickPower(3, number / 3);
    } else if (number % 3 == 1){
        result = this.quickMulti(this.quickPower(3, number / 3 - 1), 4);
    } else {
        result = this.quickMulti(this.quickPower(3, number / 3), 2);
    }
    return result;
}

private long quickPower(long x, long y) {
    if (y == 0) {
        return 1;
    }
    long result = quickPower(x, y/2);
    if (y % 2 == 0) {
        return this.quickMulti(result, result);
    } else {
        return this.quickMulti(this.quickMulti(result, result), x);
    }
}

private long quickMulti(long x, long y) {
    // (a + mod) * b = a * b + mod * b   mod * b % mod 为 0
    // 所以可以提前对(a + mod) % mod，并不影响结果
    // 即 x * y % mod = (x % mod) * (y % mod)
    // 提前对x y 取模，减少运算次数
    x %= this.mod;
    y %= this.mod;
    long sum = 0;
    while (y != 0) {
        // 不能写成 sum += x * (y & 1) % this.mod
        // 要分开写，上面只是对x * (y & 1)取模，并不是对相加后的sum取模
        sum += x * (y & 1); 
        sum %= this.mod; 
        y >>= 1;
        x <<= 1;
    }
    return sum; 
}

注意到给出的mod值998244353，即使这两个值相乘，是18为数，long最大值是19位，没有溢出所以自定义乘法可以简单点，先x y取模，最后的结果再取模，肯定不会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private long mod = 998244353;
public long cutRope (long number) {
    // write code here
    if (number <= 3) {
        return number - 1;
    }
    long result;
    if (number % 3 == 0) {
        result = this.quickPower(3, number / 3);
    } else if (number % 3 == 1){
        result = this.myMulti(this.quickPower(3, number / 3 - 1), 4);
    } else {
        result = this.myMulti(this.quickPower(3, number / 3), 2);
    }
    return result;
}

private long quickPower(long x, long y) {
    if (y == 0) {
        return 1;
    }
    long result = quickPower(x, y/2);
    if (y % 2 == 0) {
        return this.myMulti(result, result);
    } else {
        return this.myMulti(this.myMulti(result, result), x);
    }
}

private long myMulti(long x, long y) {
    x %= this.mod;
    y %= this.mod;
    return x * y % this.mod; 
}

数组中出现超过一半的数字

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=23271&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

1
2
3
4
5
6
7
8
9
10
11
public int MoreThanHalfNum_Solution(int [] array) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<array.length; i++) {
        int current = array[i];
        map.put(current, map.getOrDefault(current, 0)+1);
        if (map.get(current) > array.length/2) {
            return current;
        } 
    }
    return -1;
}

数组排列成最小的数

https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=23288&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 回溯 内存溢出
    相同长度的字符串数字，字典顺序越小，数字的值越小

可以找到数组的全排列，每一种排列都变成相同长度的字符串，然后根据字典顺序找到最小值，因为数字根大，超过了整型的范围，只能变成字符串，比较大小

由于number很长，当number为10时，会产生10！个排列方式，result存不下，内存溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private List<String> result = new ArrayList<>();
private StringBuilder path = new StringBuilder();
private int length;
public String PrintMinNumber(int [] numbers) {
    int length =numbers.length;
    if (length == 0) {
        return "";
    }
    for (int i=0; i<length; i++) {
        String temp = "" + numbers[i];
        this.length += temp.length();
    }
    boolean[] used = new boolean[length];
    this.backtrack(numbers, used);
    String minString = this.result.get(0);
    for (int i=1; i<this.result.size(); i++) {
        String current = this.result.get(i);
        if (current.compareTo(minString) < 0) {
            minString = current;
        }
    }
    return minString;
}

private void backtrack(int[] numbers, boolean[] used) {
    if (this.path.length() == this.length) {
        this.result.add(path.toString());
        return;
    }
    
    for (int i=0; i<numbers.length; i++) {
        if (used[i]) {
            continue;
        }
        this.path.append(numbers[i]);
        used[i] = true;
        backtrack(numbers, used);
        String temp = "" + numbers[i];
        int pathLength = this.path.length();
        int tempLength = temp.length();
        this.path.delete(pathLength - tempLength, pathLength);
        used[i] = false;
    }
}
  • 重新定义大小关系
    定义新的大小关系，比较字符串 num1num2 与 num2num1字典顺序(相同长度的字符串数字，字典顺序越小，数字的值越小)，如果num1num2字典顺序小，说明num1应该在前面；如果num2num1字典顺序小，说明num2应该在前面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private List<String> result = new ArrayList<>();
private StringBuilder path = new StringBuilder();
private int length;
private class MyComparator implements Comparator<Integer> {
    // 排序方法会根据返回值比较大小，如果小于0，说明num1应该在num2前面
    // 大于0，num1应该在num2后面
    @Override
    public int compare(Integer num1, Integer num2) {
        String str1 = "" + num1 + num2;
        String str2 = "" + num2 + num1;
        return str1.compareTo(str2);
    }
}
public String PrintMinNumber(int [] numbers) {
    int length = numbers.length;
    Integer[] nums = new Integer[length];
    for (int i=0; i<length; i++) {
        nums[i] = numbers[i];
    }
    Arrays.sort(nums, new MyComparator());
    StringBuilder builder = new StringBuilder();
    for (int i=0; i<length; i++) {
        builder.append(nums[i]);
    }
    return builder.toString();
}

丑数

https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=23296&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 直接方法 超时
    从2开始往后查找，如果是丑数，丑数的数量增加1，直到丑数的数量等于index

丑数的判断方法判断能否被2 3 5 整除，如果能整除，就循环除以2 3 5，如果最后只剩下1，说明被2 3 5 除尽了，是丑数，否则不是丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int GetUglyNumber_Solution(int index) {
    if (index <= 1) {
        return index;
    }
    int counter = 1;
    int i=2;
    while (counter != index) {
        if (this.isUglyNumber(i++)) {
            counter++;
        }
    }
    return --i;
}

private boolean isUglyNumber(int n) {
    while (n % 2 == 0) {
        n /= 2;
    }
    while (n % 3 == 0) {
        n /= 3;
    }
    while (n % 5 == 0) {
        n /= 5;
    }
    return n == 1;
}
  • 优化 超时
    直接取模 2 3 5下降太慢，丑数也是235的乘积组合，取模已有的丑数，可以下降快点，但还是超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34



public int GetUglyNumber_Solution(int index) {
    if (index <= 1) {
        return index;
    }
    List<Integer> list = new ArrayList<>();
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    if (index <= 5) {
        return list.get(index - 2);
    }
    int counter = 5;
    int i=6;
    while (counter != index) {
        if (this.isUglyNumber(i++, list)) {
            counter++;
        }
    }
    return --i;
}

private boolean isUglyNumber(int n, List<Integer> list) {
    for (int i=list.size()-1; i>=0; i--) {
        int current = list.get(i);
        while (n % current == 0) {
            n /= current;
        }
    }
    return n == 1;
}
  • 构造丑数
    用已经构造的丑数乘以 2 3 5，如果被选中了，对应指针就向后移动一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int GetUglyNumber_Solution(int index) {
    // 1 2 3 4 5 6
    if (index <= 6) {
        return index;
    }
    int p2 = 0;
    int p3 = 0;
    int p5 = 0;
    int[] result = new int[index];
    result[0] = 1;
    for (int i=1; i<index; i++) {
        result[i] = Math.min(result[p2] * 2, Math.min(result[p3] * 3, result[p5] * 5));
        // 三个if 而不是用else，当出现相同乘积时都要移动，不然会出现重复的
        if (result[i] == result[p2] * 2) {
            p2++;
        } 
        if (result[i] == result[p3] * 3) {
            p3++;
        }
        if (result[i] == result[p5] * 5){
            p5++;
        }
    }
    return result[index-1];
}

和为S的连续序列

https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=23251&ru=%2Fpractice%2F6aa9e04fc3794f68acf8778237ba065b&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 滑动窗口
    滑动窗口就是在遍历过程中，动态地排除不可能地情况

当滑动窗口内的和比sum大的时候，以当前left作为开始，以right以及right后面作为结束的序列都排除了，所以left左移

当滑动窗口内的和比sum小的时候，以right作为结束，left以及left后面作为开始的序列都排除了，所以right右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    // 序列最短是2，比2小的和都是不存在的
    if (sum <= 2) {
        return  result;
    }
    int left = 1;
    int right = 2;
    while (left < right && right <= sum/2+1) {
        // 根据等差数列性质求和
        int tempSum = (int)((right + left) / 2.0 * (right - left + 1));
        if (tempSum == sum) {
            this.saveResult(result, left, right);
            right++;
        } else if(tempSum < sum) {
            right++;
        } else {
            left++;
        }
    }
    return result;
}

private void saveResult(ArrayList<ArrayList<Integer>> result, int left, int right) {
    ArrayList<Integer> temp = new ArrayList<>();
    for (int i=left; i<=right; i++) {
        temp.add(i);
    }
    result.add(temp);
}

和为S的两个数

https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=23295&ru=%2Fpractice%2Fc451a3fd84b64cb19485dad758a55ebe&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

想使用集合，contains 某个数的时候快一些

  • set 错误****没考虑相同数字的数量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
        public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
            ArrayList<Integer> result = new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            for (int i=0; i<array.length; i++) {
                set.add(array[i]);
            }
            for (int i=0; i<array.length && array[i]<sum; i++) {
    // 
                if (set.contains(sum - array[i])) {
                    result.add(array[i]);
                    result.add(sum - array[i]);
                    break;
                }
            }
            return result;
        }

  • set 处理相同数字

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
        public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
            ArrayList<Integer> result = new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            for (int i=0; i<array.length; i++) {
                set.add(array[i]);
            }
            for (int i=0; i<array.length && array[i]<sum; i++) {
    // 当array[i] 与 sum-array[i]相同的时候，判断该数字是否出现了超过两次
                if (set.contains(sum - array[i]) && array[i] != sum - array[i] || array[i] == sum - array[i] && this.moreThanTwice(array, array[i])) {
                    result.add(array[i]);
                    result.add(sum - array[i]);
                    break;
                }
            }
            return result;
        }
        
        private boolean moreThanTwice(int[] array, int n) {
            int counter = 0;
            for (int i=0; i<array.length; i++) {
                if (array[i] == n) {
                    counter++;
                    if (counter == 2) {
                        return true;
                    }
                }
            }
            return false;
        }

  • set优化，无需处理相同数字，边判断边加入set中，sum-array[i] 如果在集合中，就返回，如果不在就把array[i]加入到set中，这样，如果sum-array[i]与array[i]相同，也是因为之前出现过array[i]，当前array[i]还没有加入到set中，这种方法不好想到

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Set<Integer> set = new HashSet<>();
        for (int i=0; i<array.length; i++) {
            // set记录之前出现过的数字，array[i]肯定在当前数组中，不用判断，只用
            // 判断之前的数字中是否有temp即可
            int temp = sum - array[i];
            if (set.contains(temp)) {
                result.add(temp);
                result.add(array[i]);
                break;
            } else {
                set.add(array[i]);
            }
        }
        return result;
    }

  • map
    使用map记录出现的次数，如果array[i] 与 sum-array[i]相同，直接查看出现的次数是否超过2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
    ArrayList<Integer> result = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<array.length; i++) {
        map.put(array[i], map.getOrDefault(array[i], 0)+1);
    }
    for (int i=0; i<array.length && array[i]<sum; i++) {
        if (array[i] != sum - array[i] && map.containsKey(sum - array[i]) || array[i] == sum - array[i] && map.get(array[i]) >= 2) {
            result.add(array[i]);
            result.add(sum - array[i]);
            break;
        }
    }
    return result;
}

  • 双指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int n1 = array[left];
            int n2 = array[right];
            if (sum == n1 + n2) {
                result.add(n1);
                result.add(n2);
                break;
            } else if (sum > n1 + n2) { 
                // 与最大的数n2相加都不够sum，说明n1太小，与n1的所有组合情况都被排除
                left++;
            } else {
                // sum < n1 + n2 与最小的n1相加都超过sum，说明n2太大，与n2的所有组合情况都被排除
                right--;
            }
        }
        return result;
    }

  • 圆圈中最后剩下的数
    https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=23265&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 直接方法
    从特殊到一般，假如最初的数字序列为0 1 2 3 4 m=5

报m-1=4的小孩应该删除，也就是 m - 1 % n，可以从m-1<n的情况中总结出规律，应该用

m - 1 % n，而不是 m % n

取模运算的意义x % y一种理解方式是，[0, x-1]数字顺序排列，每行y个数，排成方阵，最后一个数x所在的列数，就是取模的结果

0 123 … y-1

0 1 2 3 … y-1

y y+1 y+2 y+3 … 2y-1

2y …

x-2 x-1 x

这种理解方式恰好于报数的意义一致，[0, m-1]报数，m-1 % n 运算得到的结果就是报m-1这个数字小孩的编号，删除这个小孩，后面的小孩补充过来

由于从下一个小孩接着数，m-1 % n表示从头开始数，还应该加上startIndex(也就是刚删除的index)，表示多数startIndex个数，然后再从startIndex从0往后数一直到m-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int LastRemaining_Solution(int n, int m) {
    List<Integer> list = new ArrayList<>();
    for (int i=0; i<n; i++) {
        list.add(i);
    }
    this.removeNumber(list, m, 0);
    return list.get(0);
}

private void removeNumber(List<Integer> list, int m, int startIndex) {
    int size = list.size();
    if (size == 1) {
        return;
    }
    // 多数startIndex个数，然后再从0数到m-1
    int removeIndex = (m - 1 + startIndex) % size;
    // 删除这个小孩
    list.remove(removeIndex);
    // 继续递归
    removeNumber(list, m, removeIndex);
}
  • 数学推导+递归，太抽象了，没看懂
    图片
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        //没有小朋友的情况
        if(n == 0 || m == 0) 
            return -1;
        int x = 0;
        //从小到大，更新x
        for(int i = 2; i <= n; i++)
            x = (m + x) % i;
        return x;
    }
}

字符流中第一个不重复的字符

  • map list
    map记录出现次数

list记录插入顺序，找到第一个次数是1的字符返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//Insert one char from stringstream
private Map<Character, Integer> map = new HashMap<>();
private List<Character> list = new ArrayList<>();
public void Insert(char ch)
{
    list.add(ch);
    // 如果之前出现过，次数加1，没出现过次数为0
    map.put(ch, map.getOrDefault(ch, 0)+1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
    for (Character value : list) {
        if (map.get(value) == 1) {
            // 要求返回值是char 返回对象形式Character也是允许的
            return value;
        }
    }
    return '#';
}
  • map queue
    map记录出现次数

queue记录出现顺序，另外，字母出现次数超过1次就删除，后续就不用遍历判断它了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//Insert one char from stringstream
private Map<Character, Integer> map = new HashMap<>();
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch)
{
    queue.add(ch);
    map.put(ch, map.getOrDefault(ch, 0)+1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
    while (!queue.isEmpty()) {
        char current = queue.element();
        if (map.get(current) > 1) {
            // 如果次数超过1次，就出队，以后
            queue.remove();
        } else {
            return current;
        }
    }
    return '#';
}

左旋转字符串

  • 直接方法
    观察发现就是把左边的一部分拼接到右边的末尾，顺序不变

而且当左移超过字符串长度之后，取模之后，在左移，结果一样

1
2
3
4
5
6
7
8
9
10
11
12
public String LeftRotateString(String str,int n) {
    int length = str.length();
    if (length <= 1) {
        return str;
    }
    // 取模，减去多余的移位次数 不过当n == length时，n为0。moved应该为整个字符串，但是确为空
    // reaming应该为空，但是是整个字符串 不过不影响最终结果
    n %= length;
    String moved = str.substring(0, n);
    String remaining = str.substring(n, length);
    return remaining + moved;
}

1出现的次数

https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=23272&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 逐个数，累加
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public int NumberOf1Between1AndN_Solution(int n) {
        int result = 0;
        for (int i=1; i<=n; i++) {
            result += this.countNumber(i);
        }
        return result;
    }

    // 循环 模10 除以10的方式提取各个位的数字 
    private int countNumber(int n) {
        int counter = 0;
        while(n != 0) {
            if (n % 10 == 1) {
                counter++;
            }
            n /= 10;
        }
        return counter;
    }
    // 变成字符串逐位查看是否是1，用字符串比较慢
    private int countNumberByString(int n) {
        String temp = "" + n;
        int counter = 0;
        for (char value : temp.toCharArray()) {
            if (value == '1') {
                counter++;
            }
        }
        return counter;
    }
  • 找规律，直接计算1
    https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

按位分类讨论，计算每一位1出现的次数，然后相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int NumberOf1Between1AndN_Solution(int n) {
    int length = ("" + n).length();
    int result = 0;
    for (int i=0, weight=1; i<length; i++, weight*=10) {
        int low = n % weight;
        int high = n / (weight * 10);
        int current = n / weight % 10;
        if (current == 0) {
            // current == 0时，高位[0, high-1]都能取到，当前位不可能为1
            result += (high - 1 + 1) * weight;
        } else if (current == 1) {
            // current == 1时，高位[0, high-1]所有可能情况才能取到，高位为high时，情况只有low+1种
            result += (high - 1 + 1) * weight + low + 1;
        } else {
            // current >= 2时 高位为high时，当前位置1的所有可能情况都能取到
            // 高位取[0, high]每一个数时，都有weight种情况
            result += (high + 1) * weight;
        }
    }
    return result;
}
赏

谢谢你请我喝杯可乐

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾