作者： admin

目标

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：

• 如果单词的长度为 1 或者 2 ，所有字母变成小写。
• 否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。

示例 1：

输入：title = "capiTalIze tHe titLe"
输出："Capitalize The Title"
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。

示例 2：

输入：title = "First leTTeR of EACH Word"
输出："First Letter of Each Word"
解释：
单词 "of" 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

示例 3：

输入：title = "i lOve leetcode"
输出："i Love Leetcode"
解释：
单词 "i" 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

说明：

• 1 <= title.length <= 100
• title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
• 每个单词由大写和小写英文字母组成，且都是 非空 的。

思路

这个要看清题目，单词的长度为 1 或者 2 ，所有字母变成小写。并不是指传入的title长度，而是title中的单词。此外要熟悉字符对应的ASCII码：

Character	ASCII
A-Z	65-90
a-z	97-122
空格	32

读取字符数组中的字符，记录第一个字符的index，跳过，将后续的字符均转为小写，直到遇到空格，记录单词字符个数。如果字符个数大于2，将first对应的字符转为大写，否则转为小写。

代码

/**
 * @date 2024-03-11 0:16
 */
public class CapitalizeTitle {

    public String capitalizeTitle(String title) {
        // 使用System.arraycopy复制的数组，可以直接操作
        char[] chars = title.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char first = (char) i++;
            int counter = 1;
            while (i < chars.length && chars[i] != 32) {
                if (chars[i] < 97) {
                    chars[i] = (char) (chars[i] + 32);
                }
                i++;
                counter++;
            }
            if (counter > 2) {
                if (chars[first] >= 97) {
                    chars[first] = (char) (chars[first] - 32);
                }
            } else {
                if (chars[first] < 97) {
                    chars[first] = (char) (chars[first] + 32);
                }
            }
        }
        return new String(chars);
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

nums 中的 K-or 是一个满足以下条件的非负整数：

只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。

返回 nums 的 K-or 值。

注意 ：对于整数 x ，如果 (2^i AND x) == 2^i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。
nums[0] 和 nums[5] 的第 1 位的值为 1 。
nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。
nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。
只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：因为 k == 6 == nums.length ，所以数组的 6-or 等于其中所有元素按位与运算的结果。因此，答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0 。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。

说明：

• 1 <= nums.length <= 50
• 0 <= nums[i] < 2^31
• 1 <= k <= nums.length

思路

这个目标看起来有些难以理解，其实简单来说就是要我们返回一个int类型的数字，这个数字的每一bit是由数组元素相应bit的值共同决定的。如果数组中在该bit位上为1的元素个数超过k，那么就将结果值的相应bit位置1，否则置0。

现在问题转化为累加数组元素在某一bit位的值，然后与k比较来确定输出结果相应bit的值。可以使用移位运算来判断数字在某一特定bit的值是否为1，例如：数字7的低四位为 0111，想要判断第4个bit（从右边开始数）是否为1，可以将其右移3位，然后与1按位与即可。因为我们要判断的bit位经过右移变成了第一位，并且数字1只有第一位为1，其余位为0。

代码

/**
 * @date 2024-03-06 0:26
 */
public class FindKOr {

    public int findKOr_v1(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < 31; i++) {
            int counter = 0;
            for (int num : nums) {
               // 判断可以省去，提高效率
//                if ((num >> i & 1) == 1) {
//                    counter++;
//                }
                counter += num >> i & 1;
            }
            if (counter >= k) {
                res |= 1 << i;
            }
        }
        return res;
    }
}

性能

目标

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

说明：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

思路

这道题是让我们仅使用push压入栈顶、peek获取栈顶元素、pop弹栈等API实现先进先出队列。

关键是要想明白一点，入栈与出栈操作的是不同的栈，出栈s2中的元素是从入栈s1中获取的，并且，只能在s2为空的时候，将s1中的元素一个个弹栈再入s2，这样才能保证顺序反转。

代码

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @date 2024-03-04 0:42
 */
public class MyQueue {
    private final Deque<Integer> s1;
    private final Deque<Integer> s2;

    public MyQueue() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        if (s2.isEmpty()) {
            throw new RuntimeException();
        }
        return s2.peek();
    }

    public boolean empty() {
        return s2.isEmpty() && s1.isEmpty();
    }
}

Stack注释中有这么一段话，告诉我们应该优先使用Deque接口及其实现。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

For example: Deque<Integer> stack = new ArrayDeque<Integer>();

在Java中，Stack类是基于Vector实现的，而Vector是一个线程安全的、可动态增长的数组。虽然Stack也是数组实现的，但由于Vector的一些内部机制（例如，每次增长时都会分配更大的数组，并将旧数组的内容复制到新数组中），它可能在某些操作上不如ArrayDeque高效。

相比之下，ArrayDeque是基于循环数组实现的，它避免了不必要的内存分配和复制操作。循环数组意味着当数组的一端达到容量限制时，元素会从另一端开始填充，从而充分利用了数组空间。这种实现方式通常比Vector或Stack更高效。

因此，即使Stack也是数组实现的，但由于Deque（如ArrayDeque）使用了不同的内部机制和优化，它在某些情况下可能会提供更好的性能。

另外，值得注意的是，在Java中，Stack类已经被标记为遗留（legacy），不建议在新的代码中使用。相反，应该使用Deque接口及其实现，如ArrayDeque，因为它们提供了更完整、更一致的操作集合，并且通常具有更好的性能。

性能

时间复杂度：push（数组赋值），empty为O(1)，pop与peek虽然涉及到移动数据，但只有在出栈为空的时候才执行，均摊后为O(1)。

空间复杂度为O(n)。

目标

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

说明：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

思路

这道题的目的是只使用标准库的部分API实现栈，即后进先出。

Java中可以使用Queue接口，offer插入队尾，peek获取队首元素，poll从队首获取并删除元素。

官网给出了两种方法，一种是使用两个队列，offer总是将新元素放到空队列q中，然后将另一队列q1从头至尾放入q，这样就实现了顺序的反转。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

q1：
----------------------------
offer(2)：

q： 1

q1： 2

q1.offer(q.poll())：

q： 

q1： 1 2
----------------------------
offer(3)：

q： 3

q1： 1 2

while(!q1.isEmpty){q.offer(q1.poll())}：

q： 1 2 3

q1：
----------------------------
offer(4)：

q： 1 2 3

q1： 4

while(!q.isEmpty){q1.offer(q.poll())}：

q：

q1： 1 2 3 4

另一种只用一个队列的方法是：每次offer前先记录队列数据数量n，然后再offer，之后将前面n个数依次poll并offer到队尾。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

----------------------------
n = 1

offer(2)：

q： 2 1

p.offer(p.poll())：

q： 1 2

----------------------------
n = 2

offer(3)：

q： 3 1 2

循环2次：p.offer(p.poll())

q： 1 2 3

----------------------------
n = 3

offer(4)：

q： 4 1 2 3

循环3次：p.offer(p.poll())

q：1 2 3 4

性能

这两种方法的性能基本相同。

时间复杂度：入栈操作均为O(n)，其余为O(1)。

空间复杂度：O(n)