# LeetCode 2022
# 2022. 将一维数组转变成二维数组
class Solution {
public int[][] construct2DArray(int[] original, int m, int n) {
int[][] res = new int[m][n];
if (m*n != original.length) return new int[][]{};
for (int i = 0; i < original.length; i++) {
res[i/n][i%n] = original[i];
}
return res;
}
}
拷贝数组的方式
class Solution {
public int[][] construct2DArray(int[] original, int m, int n) {
if (original.length != m * n) {
return new int[0][];
}
int[][] ans = new int[m][n];
for (int i = 0; i < original.length; i += n) {
System.arraycopy(original, i, ans[i / n], 0, n);
}
return ans;
}
}
# 390. 消除游戏
等差数列
class Solution {
public int lastRemaining(int n) {
int cnt = n, k = 0, a = 1, step = 1;
while (cnt > 1) {
if (k % 2 == 0) {
a = a + step;
} else {
if (cnt % 2 != 0) {
a += step;
}
}
k++;
cnt >>= 1;
step <<= 1;
}
return a;
}
}
# 1185. 一周中的第几天
# 71. 简化路径
class Solution {
public String simplifyPath(String path) {
path = path + "/";
Stack<String> s = new Stack<>();
int n = path.length();
StringBuilder pre = new StringBuilder();
for (int i = 0; i < n; i++) {
if (path.charAt(i) == '/') {
if (pre.toString().equals("..")) {
if (!s.empty()) s.pop();
} else if (pre.toString().equals(".") || pre.length() == 0) {
} else {
s.push(pre.toString());
}
pre.delete(0, pre.length());
} else {
pre.append(path.charAt(i));
}
}
StringBuilder res = new StringBuilder("");
while (!s.empty()) {
res.insert(0, s.pop()).insert(0, "/");
}
if (res.length() == 0) res.append("/");
return res.toString();
}
}
# 1576. 替换所有的问号
class Solution {
public String modifyString(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
for (int i = 0; i < n; i++) {
if (cs[i] == '?') {
int pre = -1, next = -1;
if (i > 0 && cs[i-1] != '?') {
pre = cs[i-1]-'a';
}
if (i < n-1 && cs[i+1] != '?') {
next = cs[i+1]-'a';
}
for (int j = 0; j < 26; j++) {
if (j != pre && j != next) {
cs[i] = (char) (j+'a');
break;
}
}
}
}
return String.valueOf(cs);
}
}
# 913. 猫和老鼠
# 747. 至少是其他数字两倍的最大数
class Solution {
public int dominantIndex(int[] nums) {
int max = -1;
int index = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
index = i;
}
}
int max2 = max / 2;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != max && nums[i] > max2) {
return -1;
}
}
return index;
}
}
# 1716. 计算力扣银行的钱
class Solution {
public int totalMoney(int n) {
int w1 = 28, week = 7;
int rem = n / week, mod = n % week;
int r = 0;
for (int i = 1; i < rem; i++) {
r += i;
}
return (w1*rem) + (rem > 0 ? r*week : 0) + (rem+1+rem+mod)*mod/2;
}
}
# 710. 黑名单中的随机数
class Solution {
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
int m;
Random random = new Random();
public Solution(int n, int[] blacklist) {
m = n - blacklist.length;
for (int b : blacklist) {
set.add(b);
}
int w = m;
for (int b : blacklist) {
if (b < m) {
while (set.contains(w)) w++;
map.put(b, w++);
}
}
}
public int pick() {
int x = random.nextInt(m);
return map.getOrDefault(x, x);
}
}
# 674. 最长连续递增序列
class Solution {
public int findLengthOfLCIS(int[] nums) {
int count = 1;
int max = 1;
if (nums.length == 1) return max;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i-1]) {
count++;
max = Math.max(max, count);
} else {
count = 1;
}
}
return max;
}
}
# 919. 完全二叉树插入器
class CBTInserter {
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
LinkedList<TreeNode> z = new LinkedList<TreeNode>();
TreeNode r = null;
public CBTInserter(TreeNode root) {
r = root;
q.offer(r);
while (!q.isEmpty()) {
TreeNode cur = q.peekFirst();
int cnt = 0;
if (cur.left != null) {
z.offer(cur.left);
cnt++;
}
if (cur.right != null) {
z.offer(cur.right);
cnt++;
}
if (cnt == 2) {
q.pollFirst();
if (q.isEmpty() && !z.isEmpty()) {
q = z;
z = new LinkedList<TreeNode>();
}
} else {
break;
}
}
}
public int insert(int val) {
TreeNode i = new TreeNode(val);
int parent = 0;
z.offer(i);
if (!q.isEmpty()) {
TreeNode cur = q.peekFirst();
parent = cur.val;
if (cur.left == null) {
cur.left = i;
} else if (cur.right == null) {
cur.right = i;
q.pollFirst();
if (q.isEmpty() && !z.isEmpty()) {
q = z;
z = new LinkedList<TreeNode>();
}
}
}
return parent;
}
public TreeNode get_root() {
return r;
}
}
# 622. 设计循环队列
class MyCircularQueue {
int[] arr;
int front, rear, count, n = 0;
public MyCircularQueue(int k) {
arr = new int[k];
n = k;
}
public boolean enQueue(int value) {
if (count == n) return false;
arr[rear % n] = value;
rear++;
count++;
return true;
}
public boolean deQueue() {
if (count == 0) return false;
front++;
count--;
return true;
}
public int Front() {
if (count == 0) return -1;
return arr[front % n];
}
public int Rear() {
if (count == 0) return -1;
return arr[(rear-1) % n];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == n;
}
}
# 剑指 Offer II 029. 排序的循环链表
class Solution {
public Node insert(Node head, int insertVal) {
Node insert = new Node(insertVal);
if (head == null) {
insert.next = insert;
return insert;
}
// val equal head or only one Node.
if (head.val == insertVal || head.next == head) {
Node n = head.next;
head.next = insert;
insert.next = n;
return head;
}
Node max = head;
Node cur = head;
Node next = head.next;
do {
if (insertVal >= cur.val && insertVal <= next.val) {
cur.next = insert;
insert.next = next;
return head;
}
if (cur.val >= max.val) {
max = cur;
}
cur = next;
next = next.next;
} while (cur != head);
Node ne = max.next;
max.next = insert;
insert.next = ne;
return head;
}
}
# 899. 有序队列
class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
String min = s;
int n = s.length();
for (int i = 0; i < n; i++) {
s = s.substring(1).concat(s.substring(0, 1));
if (s.compareTo(min) < 0) {
min = s;
}
}
return min;
}
char[] cs = s.toCharArray();
Arrays.sort(cs);
return new String(cs);
}
}
# 1403. 非递增顺序的最小子序列
class Solution {
public List<Integer> minSubsequence(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int n : nums) {
sum += n;
}
List<Integer> res = new ArrayList<>();
int len = nums.length;
sum = sum / 2 + 1;
int s = 0;
for (int i = len-1; i >= 0; i--) {
res.add(nums[i]);
s += nums[i];
if (s >= sum) {
return res;
}
}
return res;
}
}
# 1408. 数组中的字符串匹配
brute force
class Solution {
public List<String> stringMatching(String[] words) {
Arrays.sort(words, (a, b) -> {
if (a.length() < b.length()) {
return -1;
} else if (a.length() == b.length()) {
return 0;
}
return 1;
});
List<String> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
ggg: for (int j = i+1; j < words.length; j++) {
if (words[i].length() < words[j].length()) {
for (int k = 0; k <= words[j].length()-words[i].length(); k++) {
if (words[j].substring(k, words[i].length()+k).equals(words[i])) {
res.add(words[i]);
break ggg;
}
}
}
}
}
return res;
}
}
# 1413. 逐步求和得到正数的最小值
class Solution {
public int minStartValue(int[] nums) {
int min = Integer.MAX_VALUE;
int sum = 0;
for (int n : nums) {
sum += n;
min = Math.min(min, sum);
}
return min >= 1 ? 1 : -min + 1;
}
}
# 1417. 重新格式化字符串
写得很破碎。。
class Solution {
public String reformat(String s) {
List<Integer> letter = new ArrayList<>();
List<Integer> number = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) >= 97) {
letter.add(i);
} else {
number.add(i);
}
}
int ls = letter.size();
int ns = number.size();
if ((ls == 0 && ns == 0) || (ls - ns != 1 && ns - ls != 1 && ls != ns) ) {
return "";
} else if (ns - ls == 1) {
List<Integer> temp = letter;
letter = number;
number = temp;
}
StringBuilder result = new StringBuilder();
int li = 0, ni = 0;
boolean next = true;
while (next) {
if (li == letter.size()) {
next = false;
} else {
result.append(s.charAt(letter.get(li++)));
}
if (ni == number.size()) {
next = false;
} else {
result.append(s.charAt(number.get(ni++)));
}
}
if (!next && ni == number.size() && li == letter.size()) {
return result.toString();
}
return "";
}
}
# 1422. 分割字符串的最大得分
class Solution {
public int maxScore(String s) {
int left = 0, right = 0;
for (char c : s.toCharArray()) {
if (c == '1') {
right++;
}
}
int max = 0;
for (int i = 0; i < s.length()-1; i++) {
char c = s.charAt(i);
if (c == '0') {
left++;
} else if (c == '1') {
right--;
}
max = Math.max(max, left + right);
}
return max;
}
}
# 1656. 设计有序流
class OrderedStream {
String[] store;
int ptr;
public OrderedStream(int n) {
store = new String[n+1];
ptr = 1;
}
public List<String> insert(int idKey, String value) {
store[idKey] = value;
if (ptr != idKey) return new ArrayList<>();
List<String> res = new ArrayList<>();
while (ptr <= store.length-1 && store[ptr] != null) {
res.add(store[ptr++]);
}
return res;
}
}
← LeetCode 6 OJ模式 →