最小差 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

示例：

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出： 3，即数值对(11, 8)
提示：

1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间[-2147483648, 2147483647]内
通过次数7,396提交次数17,910

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-difference-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

先对两个数组排序，然后以做两个有序链表合并成一个有序链表的思路，计算相邻的两个来自不同数组的元素的差值，并记录最小值

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
class Solution {
    public int smallestDifference(int[] a, int[] b) {
        if (a == null && b == null) return 0;
        if (a.length == 0 || b.length == 0) return 0;
        Arrays.sort(a);
        Arrays.sort(b);
        int indexA = 0, indexB = 0;
        int lastAValue = 0;
        int lastBValue = 0;
        long min = (long)Integer.MAX_VALUE;
        char last = '0';

        while (indexA < a.length || indexB < b.length) {
            if (indexA < a.length && indexB < b.length) {
                if (a[indexA] < b[indexB]) {
                    lastAValue = a[indexA];
                    if (last == 'b') {
                        min = Math.min(Math.abs((long)a[indexA] - (long)lastBValue), min);
                    }
                    last = 'a';
                    indexA++;
                } else if (a[indexA] > b[indexB]) {
                    lastBValue = b[indexB];
                    if (last == 'a') {
                        min = Math.min(Math.abs((long)b[indexB] - (long)lastAValue), min);
                    }
                    last = 'b';
                    indexB++;
                } else {
                    return 0;
                }
            } else if (indexA < a.length && Math.abs((long)a[indexA] - (long)lastBValue) <= min) {
                return (int) Math.abs((long)a[indexA] - (long)lastBValue);
            } else if (indexB < b.length && Math.abs((long)b[indexB] - (long)lastAValue) <= min) {
                return (int) Math.abs((long)b[indexB] - (long)lastAValue);
            } else {
                break;
            }
        }
        return (int)min;
    }
}

更优雅的写法

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
class Solution {
    public int smallestDifference(int[] a, int[] b) {
        if (a == null || b == null || a.length == 0 || b.length == 0) return -1;
        int minDiff = Integer.MIN_VALUE , aIdx = 0 , bIdx = 0;
        Arrays.sort(a);
        Arrays.sort(b);
        while (aIdx < a.length && bIdx < b.length) {
            //关键，解决溢出 ， 负数域 大于 正数域。
            minDiff = Math.max(minDiff,-Math.abs(a[aIdx] - b[bIdx]));

            if (a[aIdx] < b[bIdx]) {
                aIdx++;
            }
            else {
                bIdx++;
            }
        }
        //反置
        return Math.abs(minDiff);
    }
}

作者：tago-tech
链接：https://leetcode-cn.com/problems/smallest-difference-lcci/solution/shuang-zhi-zhen-jie-jue-absyi-chu-fang-fa-by-lcbir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：tago-tech来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

井字游戏 

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
设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。

以下是井字游戏的规则：

玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。

示例 1：

输入： board = ["O X"," XO","X O"]
输出： "X"
示例 2：

输入： board = ["OOX","XXO","OXO"]
输出： "Draw"
解释： 没有玩家获胜且不存在空位
示例 3：

输入： board = ["OOX","XXO","OX "]
输出： "Pending"
解释： 没有玩家获胜且仍存在空位
提示：

1 <= board.length == board[i].length <= 100
输入一定遵循井字棋规则

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/tic-tac-toe-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

行、列、正斜线和反斜线

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
48
49
50
51
52
53
54
class Solution {
    public String tictactoe(String[] board) {
        if (board == null || board.length == 0) return "Pending";

        boolean isPending = false;
        int len = board.length;
        int countXTilt1 = 0, countXTilt2 = 0;
        int countOTilt1 = 0, countOTilt2 = 0;

        int[] xColCount = new int[len];
        int[] oColCount = new int[len];

        for (int i = 0; i < board.length; i++) {
            char[] arr = board[i].toCharArray();
            int countX = 0, countO = 0;
            for (int j = 0; j < arr.length; j++) {

                if (arr[j] == 'X') xColCount[j]++;
                else if (arr[j] == 'O') oColCount[j]++;

                if (i == j) {
                    if (arr[j] == 'X') countXTilt1++;
                    else if (arr[j] == 'O') countOTilt1++;

                } else if (j == len - i - 1) {
                    if (arr[j] == 'X') countXTilt2++;
                    else if (arr[j] == 'O') countOTilt2++;
                }
                if (i == j && j == len / 2) {
                    if (arr[j] == 'X') countXTilt2++;
                    else if (arr[j] == 'O') countOTilt2++;
                }

                if (countOTilt1 == len || countOTilt2 == len) return "O";
                else if (countXTilt1 == len || countXTilt2 == len) return "X";

                if (arr[j] == 'X') countX++;
                else if (arr[j] == 'O') countO++;
                else isPending = true;
            }
            if (countO == 0 && countX == len) return "X";
            else if (countX == 0 && countO == len) return "O";
        }

        for (int i = 0; i < len; i++) {
            if (xColCount[i] == len) return "X";
            if (oColCount[i] == len) return "O";
        }

        if (isPending) return "Pending";
        return "Draw";
    }
}

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
48
49
class Solution {
    public String tictactoe(String[] board) {

        int length = board.length;
        int horizontal = 0; //横的和
        int vertical = 0; //纵的和
        int left = 0; //左斜线
        int right = 0; //右斜线
        boolean flag = false; //记录有没有空格

        for (int i = 0; i < length; i++) {

            horizontal = 0; vertical = 0;

            for (int j = 0; j < length; j++) {

                horizontal = horizontal +  (int) board[i].charAt(j);
                vertical = vertical + (int) board[j].charAt(i);

                if(board[i].charAt(j) == ' ') flag = true;

            }

            //横纵检查
            if (horizontal == (int)'X' * length || vertical == (int)'X' * length) return "X";
            if (horizontal == (int)'O' * length || vertical == (int)'O' * length) return "O";

            //两条斜线上的相加
            left = left + (int)board[i].charAt(i);
            right = right + (int)board[i].charAt(length - i - 1);

        }

        //两条斜线检查
        if (left == (int)'X' * length || right == (int)'X' * length) return "X";
        if (left == (int)'O' * length || right == (int)'O' * length) return "O";

        if (flag) return "Pending";
        return "Draw";

    }
}


作者：noscallion
链接：https://leetcode-cn.com/problems/tic-tac-toe-lcci/solution/qiu-he-de-si-xiang-java-ban-jia-zhu-shi-by-noscall/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

将数组分成三个子数组的方案数 

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
我们称一个分割整数数组的方案是 好的 ，当它满足：

数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。

 

示例 1：

输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2：

输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
示例 3：

输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。
 

提示：

3 <= nums.length <= 105
0 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

class Solution {
    public int waysToSplit(int[] nums) {
        int len = nums.length;
        int[] sum = new int[len + 1];
        //计算前缀和
        for (int i = 1; i < len + 1; i++) {
            sum[i] += nums[i - 1] + sum[i - 1];
        }
        int pre = 0;
        int cur = 0;
        long res = 0;
        
        for (int i = 0; i < len - 2; i++) {
            pre = Math.max(pre, i + 1);
            while (pre < len - 1 && sum[pre + 1] - sum[i + 1] < sum[i + 1]) {
                pre++;
            }
            if (pre == len - 1) {
                break;
            }
            cur = Math.max(pre, cur);
            while (cur < len - 1 && sum[len] - sum[cur + 1] >= sum[cur + 1] - sum[i + 1]) {
                cur++;
            }
            res += cur - pre;
        }
        return (int) (res % ((int) 1e9 + 7));
    }
}

作者：ling-ling-zhu-qi
链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays/solution/qian-zhui-he-by-ling-ling-zhu-qi-9clu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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
class Solution {
    public int waysToSplit(int[] nums) {
        int n=nums.length;
        int psum[]=new int[n+1];
        for (int i=0; i<n; ++i) {                                       //计算前缀和
            psum[i+1]=psum[i]+nums[i];
        }
        int res=0;
        int a=1, b=1;
        for (int i=0; i<n-2; ++i) {
            a=Math.max(i+1,a);
            while (a<n-1&&psum[a+1]-psum[i+1]<psum[i+1]) {
                a++;
            }
            if (a==n-1) {
                break;
            }
            b=Math.max(b,a);
            while (b<n-1&&psum[n]-psum[b+1]>=psum[b+1]-psum[i+1]) {
                b++;
            }
            res=(res+(b-a))%1000000007;
        }
        return res;
    }
}

作者：maple_lin21
链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays/solution/javashuang-bai-chao-jian-ji-de-xie-fa-by-weqt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

大餐计数

1711. 大餐计数

难度：中等（竞赛题）

大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。

你可以搭配 任意 两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

1
2
3
4
输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：

1
2
3
输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

  • 1 <= deliciousness.length <= 10^5
  • 0 <= deliciousness[i] <= 2^20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private static final int MOD = 1000000007;

    public int countPairs(int[] arr) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int len = arr.length;
        countMap.put(arr[0], 1);
        int ansCount = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= 21; j++) {
                // 计算美味程度之和
                // 如果能组成2的幂则存在，否则是0
                ansCount = (ansCount + countMap.getOrDefault((1 << j) - arr[i], 0)) % MOD;
            }
            countMap.put(arr[i], countMap.getOrDefault(arr[i], 0) + 1);
        }

        return ansCount;
    }
}

参考文献

余先声的竞赛记录

展开全文 >>

单词频率 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
设计一个方法，找出任意指定单词在一本书中的出现频率。

你的实现应该支持如下操作：

WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
get(word)查询指定单词在书中出现的频率
示例：

WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
wordsFrequency.get("you"); //返回0，"you"没有出现过
wordsFrequency.get("have"); //返回2，"have"出现2次
wordsFrequency.get("an"); //返回1
wordsFrequency.get("apple"); //返回1
wordsFrequency.get("pen"); //返回1
提示：

book[i]中只包含小写字母
1 <= book.length <= 100000
1 <= book[i].length <= 10
get函数的调用次数不会超过100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/words-frequency-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class WordsFrequency {

    Map<String, Integer> map = null;

    public WordsFrequency(String[] book) {
        map = new HashMap<>();
        for (String bk : book) {
            map.put(bk, map.getOrDefault(bk, 0) + 1);
        }
    }

    public int get(String word) {
        return map.getOrDefault(word, 0);
    }
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency obj = new WordsFrequency(book);
 * int param_1 = obj.get(word);
 */

c++实现哈希表

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/* 单词最大长度 */
#define MAX_WORD_LEN 11

/* 每个元素所带的数据 */
typedef struct {
    char word[MAX_WORD_LEN];
    int cnt;
} hash_set_elem_t;

/* 哈希表容量，一定要大于元素最大个数 */
#define HASH_SET_CAPACITY 100001
/* 哈希表取模的质数，也即哈希桶的个数，小于HASH_SET_CAPACITY */
#define PRIME 99997

/* 元素的哈希函数 */
int elem_hash(const hash_set_elem_t *elem)
{
    const char *str = elem->word;
    unsigned int r = 0;
    int len = strlen(str);

    int i;
    for (i = 0; i < len; i++) {
        r = (r * 31 + str[i]) % PRIME;
    }

    return r % PRIME;
}

/* 元素的比较函数 */
bool cmp(const char *elem1, const char *elem2)
{
    return strcmp(elem1, elem2) == 0;
}

/* 哈希集合 */
typedef struct {
    int head[PRIME]; /* 首节点下标 */

    struct {
        hash_set_elem_t elem;
        int next;
    } node[HASH_SET_CAPACITY]; /* 静态链表 */

    int size; /* 实际元素个数 */
    int (*hash)(const hash_set_elem_t *elem); /* 元素的哈希函数 */
    bool (*cmp)(const char *elem1, const char *elem2); /* 元素的比较函数 */
} WordsFrequency;

/* 创建一个哈希集合 */
WordsFrequency *hash_set_create(int (*hash)(const hash_set_elem_t *elem),
                            bool (*cmp)(const char *elem1, const char *elem2))
{
    WordsFrequency *result = (WordsFrequency *)malloc(sizeof(WordsFrequency));
    memset(result->head, -1, sizeof(result->head));
    memset(result->node, -1, sizeof(result->node));
    for (int i = 0; i < HASH_SET_CAPACITY; i++) {
        (result->node)[i].elem.cnt = 0;
    }
    result->size = 0;
    result->hash = hash;
    result->cmp = cmp;
    return result;
}

/* 添加一个元素，如果已存在则添加失败 */
bool hash_set_add(WordsFrequency *set, const hash_set_elem_t *elem)
{
    int i;
    int hash = set->hash(elem);

    /* 已经存在,出现次数+1 */
    for (i = set->head[hash]; i != -1; i = set->node[i].next) {
        if (set->cmp(elem->word, set->node[i].elem.word)) {
            (set->node[i].elem.cnt)++;
            return false;
        }
    }

    /* 不存在，则插入在首节点之前*/
    set->node[set->size].next = set->head[hash];
    strcpy(set->node[set->size].elem.word, elem->word);
    (set->node[set->size].elem.cnt)++;
    set->head[hash] = set->size++;

    return true;
}

WordsFrequency *wordsFrequencyCreate(char **book, int bookSize)
{
    WordsFrequency *set = hash_set_create(elem_hash, cmp);
    hash_set_elem_t e;

    for (int i = 0; i < bookSize; i++) {
        strcpy(e.word, book[i]);
        e.cnt = 0;
        hash_set_add(set, &e);
    }

    return set;
}

int wordsFrequencyGet(WordsFrequency *set, char *word)
{
    int i;

    if (word == NULL || strlen(word) == 0) {
        return 0;
    }

    int hash = set->hash(word);
    for (i = set->head[hash]; i != -1; i = set->node[i].next) {
        if (set->cmp(word, set->node[i].elem.word)) {
            return set->node[i].elem.cnt;
        }
    }
    return 0;
}

/* 销毁哈希集合 */
void wordsFrequencyFree(WordsFrequency *obj)
{
    free(obj);
    obj = NULL;
}

/**
 * Your WordsFrequency struct will be instantiated and called as such:
 * WordsFrequency* obj = wordsFrequencyCreate(book, bookSize);
 * int param_1 = wordsFrequencyGet(obj, word);
 * wordsFrequencyFree(obj);
*/

作者：yuxiaochen99
链接：https://leetcode-cn.com/problems/words-frequency-lcci/solution/chun-czi-ji-shi-xian-ha-xi-huo-zhe-shi-yong-uthash/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：yuxiaochen99来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

分隔链表 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

 

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5
通过次数64,632提交次数106,650

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode dummyNode1 = new ListNode(0);
        ListNode dummyNode2 = new ListNode(0);
        ListNode cur = head;
        ListNode minListNode = dummyNode1;
        ListNode maxListNode = dummyNode2;

        while (cur != null) {

            if (cur.val < x) {
                minListNode.next = cur;
                minListNode = minListNode.next;
                cur = cur.next;
                minListNode.next = null;
            } else {
                maxListNode.next = cur;
                maxListNode = maxListNode.next;
                cur = cur.next;
                maxListNode.next = null;
            }
        }
        minListNode.next = dummyNode2.next;
        return dummyNode1.next;
    }
}

时间复杂度O(n)，空间复杂度O(1)

展开全文 >>

峰与谷 

1
2


排序做法

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
class Solution {

    public void wiggleSort(int[] nums) {
        if (nums != null && nums.length == 0) return;
        Arrays.sort(nums);

        int[] arr = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i];
        }

        int index1 = nums.length - 1, index2 = 0;

        int resIndex = 0;
        while (resIndex < nums.length) {

            if (resIndex % 2 == 0) {
                nums[resIndex] = arr[index1--];
                resIndex++;
            } else {
                nums[resIndex] = arr[index2++];
                resIndex++;
            }
        }
    }
}

交换位置时间复杂度O（N）

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {    

    public void wiggleSort(int[] nums) {
        int n = nums.length;
        for(int i = 1;i < n; i++){
            //如果是奇数，且小于前面的，或者如果是偶数，且大于前面的，那就要交换
            if(((i & 1) == 1 && nums[i] < nums[i-1])||((i &1) == 0 && nums[i] > nums[i-1])){
                int temp = nums[i];
                nums[i] = nums[i-1];
                nums[i-1] = temp;
            }
        }
    }
}


参考文献
作者：jerry_nju来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

数字流的秩 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]
提示：

x <= 50000
track 和 getRankOfNumber 方法的调用次数均不超过 2000 次
通过次数2,493提交次数4,017

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rank-from-stream-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
48
49
50
51
52
53
54
55
class FenwickTree {
    int n;
    int[] C;

    //初始化
    public FenwickTree(int n) {
        this.n = n;
        this.C = new int[n];
    }

    // 单点更新：将 i 位置与其直接关联的 C 都更新一遍
    public void update(int i) {
        while (i < n) {
            C[i]++;
            i += lowbit(i);
        }
    }

    //传进来的值-1过，查询之前有多少个数
    //区间查询：查询小于等于 i 的元素个数
    public int query(int i) {
        int sum = 0;
        while (i >= 1) {
            sum += C[i];
            i -= lowbit(i);
        }
        return sum;
    }

    //算lowbit
    public int lowbit(int x) {
        return x & (-x);
    }
}

class StreamRank {
    FenwickTree fenwickTree;

    public StreamRank() {
        fenwickTree = new FenwickTree(50_005);
    }

    public void track(int x) {
        fenwickTree.update(x + 1);
    }

    public int getRankOfNumber(int x) {
      return fenwickTree.query(x + 1);
    }
}

作者：a-fei-8
链接：https://leetcode-cn.com/problems/rank-from-stream-lcci/solution/tao-yuan-san-xiong-zhi-zhi-shu-zi-liu-de-zhi-by-a-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

树状数组

树状数组学习笔记树状数组能解决的问题

展开全文 >>

搜索旋转数组

面试题 10.03. 搜索旋转数组

难度中等46

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

1
2
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:

1
2
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）

提示:

  1. arr 长度范围在[1, 1000000]之间

通过nums[l]与nums[mid]的比较来判断

  • 如果左值小于中值，那么说明左边是递增的
    • 如果左值小于等于target并且target小于等于中值：r = mid
    • 否则 l = mid+1
  • 如果左值大于中值，那么说明右边是递增的
    • 如果左值小于等于target或者target小于等于中值: r = mid
    • 否则l = mid +1
  • 如果左值等于中值，那么说明有可能找到了目标
    • 如果左值不等于target，那么l++
    • 如果左值等于target，那么r=l
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
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (right == -1)
            return -1;
        while (left < right) {                                         // 循环结束条件left==right
            int mid = left + (right - left) / 2;                       // 防止溢出
            if (nums[left] < nums[mid]) {                              // 如果左值小于中值，说明左边区间升序               
                if (nums[left] <= target && target <= nums[mid]) {     // 如果目标在左边的升序区间中，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] > nums[mid]) {                       // 如果左值大于中值，说明左边不是升序，右半边升序
                if (nums[left] <= target || target <= nums[mid]) {     // 如果目标在左边，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] == nums[mid]) {                      // 如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
                if (nums[left] != target) {                            // 如果左值不等于目标，说明还没找到，需要逐一清理重复值。
                    left++;
                } else {                                               // 如果左值等于目标，说明已经找到最左边的目标值 
                    right = left;                                      // 将右边界移动到left，循环结束
                }
            }
        }
        return (nums[left] == target) ? left : -1;                     // 返回left，或者-1
    }
}

数组的旋转就是循环移动，不管旋转多少次，一定是左边递增，中间断开，右边递增的

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
48
49
50
51
52
53
class Solution {
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if (arr[left] > arr[right] && arr[left] < arr[mid] && arr[mid] != target) {      // 左半边递增
                if (target < arr[mid] && target >= arr[left]) {                              // target在范围内
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[left] < arr[right]) {                                            // 右半边递增

                if (target < arr[left] || target > arr[right]) return -1;
                if (target < arr[mid]) {
                    right = mid - 1;
                } else if (target > arr[mid]) {
                    left = mid + 1;
                } else {
                    int index = mid;
                    for (int i = mid; i >= 0; i--) {
                        if (arr[i] == arr[mid]) index = i;
                        else return index;
                    }
                }
            } else if (arr[left] == arr[mid] && arr[mid] != target) {
                for (int i = left; i < mid; i++) {
                    if (arr[i] == target) {
                        return i;
                    }
                }
                left = mid + 1;
            } else {                                                                        // 断点在中间
                if (target != arr[right]) {
                    right--;
                } else {
                    if (target == arr[0]) return 0;
                    if (target == arr[right]) {
                        int index = right;
                        for (int i = right; i >= 0; i--) {
                            if (arr[i] == arr[right]) index = i;
                            else return index;
                        }
                    }
                }
            }
        }

        return -1;
    }
}

高效优雅的题解

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
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (right == -1)
            return -1;
        while (left < right) {                                         // 循环结束条件left==right
            int mid = left + (right - left) / 2;                       // 防止溢出
            if (nums[left] < nums[mid]) {                              // 如果左值小于中值，说明左边区间升序               
                if (nums[left] <= target && target <= nums[mid]) {     // 如果目标在左边的升序区间中，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] > nums[mid]) {                       // 如果左值大于中值，说明左边不是升序，右半边升序
                if (nums[left] <= target || target <= nums[mid]) {     // 如果目标在左边，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] == nums[mid]) {                      // 如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
                if (nums[left] != target) {                            // 如果左值不等于目标，说明还没找到，需要逐一清理重复值。
                    left++;
                } else {                                               // 如果左值等于目标，说明已经找到最左边的目标值 
                    right = left;                                      // 将右边界移动到left，循环结束
                }
            }
        }
        return (nums[left] == target) ? left : -1;                     // 返回left，或者-1
    }
}

作者：armeria-program
链接：https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/er-fen-fa-by-armeria-program/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：armeria-program来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

变位词组

面试题 10.02. 变位词组

难度：中等

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

注意: 本题相对原题稍作修改

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String temp = String.valueOf(arr);
            List<String> list = map.getOrDefault(temp, new ArrayList<String>());
            list.add(strs[i]);
            map.put(temp, list);
        }

        List<List<String>> res = new ArrayList<>();
        for (Map.Entry entry : map.entrySet()) {
            res.add((List<String>) entry.getValue());
        }
        return res;
    }
}

计数+哈希表

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
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

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>希望有一天被领走