tt2767

tt2767
5个月前
/**
1. 先倒着找到第一个字母, 然后统计连续的字母个数即可

*/

class Solution {
public int lengthOfLastWord(String s) {
if (s == null || s.length() == 0) return 0;
int p = s.length() - 1, n = s.length();
while (0 <= p && s.charAt(p) == ' ') p--;
if (p < 0) return 0;
int result = 0;
while (0 <= p && s.charAt(p) != ' ') {
p--;
result++;
}
return result;
}
}


tt2767
5个月前
/**
1. 模拟 + 进位
*/

class Solution {
public int[] plusOne(int[] digits) {

int n = digits.length;
digits[n-1] += 1;
for (int i = n - 1 ; i > 0; i--){
if (digits[i] < 10 ) break;
digits[i - 1] ++;
digits[i] -= 10;
}

if (digits[0] >= 10) {
int[] res = new int[n + 1];
res[0] = 1;
digits[0] -= 10;
for (int i = 1 ;i <= n ; i++){
res[i] = digits[i-1];
}
return res;
}

return digits;
}
}


tt2767
5个月前
/**
1. 范围>=s, 双指针去找值
*/

class Solution {

public int minSubArrayLen(int s, int[] nums) {
return doublePoint(s, nums);
}

public int doublePoint(int s, int[] nums){
int sum = 0, left = 0, right = 0, n = nums.length, result = Integer.MAX_VALUE;
while (left < n && right < n){
while (right < n && sum < s){
sum += nums[right++];
}

while (left < n && sum >= s){
result = Math.min(result, right - left);
sum -= nums[left++];
}
}
if (sum >= s) result = Math.min(result, right - left);
return result == Integer.MAX_VALUE ? 0 : result;
}
}


tt2767
5个月前
/**
1. 环状数组的一个经典处理方法是, 复制一份相同的追加到后面
2. 找一侧恰好比当前数大可以用单调栈
*/

class Solution {
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) return nums;
int n = nums.length;
int[] range = new int[n * 2];
for (int i = 0 ; i < n; i++){
range[i] = nums[i];
range[i + n] = nums[i];
}

Stack<Integer> stack = new Stack<>();
for (int i = 2 * n - 1; i >= 0; i--){
int num = range[i];
while (!stack.isEmpty() && num >= stack.peek()) stack.pop();
range[i] = stack.isEmpty() ? -1 :stack.peek();
stack.push(num);
}

for (int i = 0; i < n ;i ++) nums[i] = range[i];
return nums;
}
}


tt2767
5个月前
/**
1. 其实就是下一个排列, 找到恰好比它大且元素相同的数, 那么肯定要是低位较大的数和高位较小的数swap,
1.1 高位满足恰好大于n : 从后向前找到恰好第一个相邻逆序对(a,b), a < b , 然后在a后面找一个恰好大于a的最小和数c, swap(a, c)
1.2 低位满足恰好大于n : 对a后面的数排序

2. 特判:
2.1 特判掉前导零的情况
2.2 特判掉没找到的情况
2.3 特判掉超出int的情况
*/

class Solution {
public int nextGreaterElement(int n) {
if (n < 10) return -1;
char[] num = String.valueOf(n).toCharArray();
int p1 = num.length - 2, p2 = num.length - 1;
while (0 <= p1 && 0 <= p2 && num[p1] >= num[p2]){
p1 --;
p2 --;
}

if (p1 < 0 || p2 < 0) return -1;
int p3 = p2;
while (p3 < num.length && num[p1] < num[p3] && num[p3] <= num[p2]) p3++;
p3 --;
if (p1 == 0 && num[p3] == '0') return -1;

char temp = num[p1];
num[p1] = num[p3];
num[p3] = temp;
Arrays.sort(num, p2, num.length);

long next = Long.parseLong(new String(num));
if(next > Integer.MAX_VALUE) return -1;

return (int)next;
}
}


tt2767
5个月前
/**
1. 2^n 一定大于0
2. 2^n 的二进制表示一定只有一个1 -> x == lowbit(x)
*/

class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && n == (n & (-n));
}
}


tt2767
5个月前
/**
1. 左开右闭区间的范围维护:
1.1 因为边界范围是 1e9, 所以不可能存每个数来查,
1.2 但是查询和写入次数较少所以可以维护顺序的二元组[left, right) 列表, 通过二分查找确定位置
1.3 怎么快速二分查找, 并且动态添加删除 -> 平衡二叉查找树 -> TreeSet

2. 各操作
1. 确定区间范围 [left, right) 区间应该扫描[-∞, left) 到 [right+1, +∞) 之间的所有区间
3. del: in.left < left ,   说明原区间前面有切割剩余, 加入 [in.left, left)
right < in.right , 说明原区间后面有切割剩余, 加入 [right, in.righ)
4. query: [left, right) 只可能和两个区间相交: [left, right)  前面的区间a, 和 a后面的区间b ,如果a,b都不包含[left, right) ,返回 false
*/

class RangeModule {

class Node{
int left, right;
public Node(int left, int right){
this.left = left;
this.right = right;
}
}

TreeSet<Node> data;
public RangeModule() {
data = new TreeSet<>((a,b)->(a.right == b.right ? a.left - b.left : a.right - b.right));
}

public void addRange(int left, int right) {
Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
while (it.hasNext()){
Node node = it.next();
if (right < node.left) break;
left = Math.min(left, node.left);
right = Math.max(right, node.right);
it.remove();
}
}

public boolean queryRange(int left, int right) {
if (data.isEmpty()) return false;
Node node = new Node(left, right);
Node prev = data.lower(node);
if (prev != null && prev.left <= left && right <= prev.right) return true;
Node next = prev == null ? data.first() : data.higher(prev);
if (next != null && next.left <= left && right <= next.right) return true;
return false;
}

public void removeRange(int left, int right) {
Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
List<Node> buffer = new ArrayList<>();
while (it.hasNext()){
Node node = it.next();
if (right < node.left) break;
if (node.left < left)   buffer.add(new Node(node.left, left));
if (right < node.right) buffer.add(new Node(right,  node.right));
it.remove();
}
}
}

/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule obj = new RangeModule();
* boolean param_2 = obj.queryRange(left,right);
* obj.removeRange(left,right);
*/


tt2767
5个月前
/**
1. 怎么找递增路径? 怎么找最长的?
2. 搜索: 从起点集合中找一个点, bfs 按严格升序遍历所有情况,  返回达到的最远距离
3. 剪枝:
3.1 一个路径中a->b, a能到达b, 则a点能到达的最长路径必定大于b点能达到的, 所以应该把能到达的点都从起点集合中删除
*/

class Solution {

static final int[] dx = {0, 0, 1, -1};
static final int[] dy = {1, -1, 0, 0};

class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}

public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int n = matrix.length , m = matrix[0].length;
boolean[][] notStart = new boolean[n][m];
int result = 1;
for (int i = 0;  i < n ; i ++){
for (int j = 0; j < m ; j++){
if (notStart[i][j]) continue;
result = Math.max(result, bfs(i, j, matrix, queue, notStart));
}
}
return result;
}

private int bfs(int x, int y, int[][] matrix, Queue<Node> queue, boolean[][] notStart){
queue.clear();
Node start = new Node(x, y);
int n = matrix.length , m = matrix[0].length, result = 1;
int[][] dis = new int[matrix.length][matrix[0].length];
queue.offer(start);
dis[x][y] = 1;
while (!queue.isEmpty()){
Node node = queue.poll();
for (int i = 0 ; i < 4 ; i++){
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if (!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
if (dis[node.x][node.y] >= dis[nx][ny] && matrix[nx][ny] > matrix[node.x][node.y]){
dis[nx][ny] = dis[node.x][node.y] + 1;
result = Math.max(result, dis[nx][ny]);
notStart[nx][ny] = true;
queue.offer(new Node(nx, ny));
}
}
}
return result;
}
}


tt2767
5个月前
/**
1. 深搜不断累加路径上的值, 当累加到叶子节点时, 合并结果
2. 搜索顺序: 不断累加路径上的值
3. 搜索状态: cur, prev_value | result
4. 剪枝: cur == null 跳出
*/

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
int[] result = new int[1];
dfs(root, 0, result);
return result[0];
}

public void dfs(TreeNode cur, int prev, int[] result){
if (cur == null) return;
int value = prev * 10 + cur.val;
if (cur.left == null && cur.right == null) result[0] += value;
dfs(cur.left, value, result);
dfs(cur.right, value, result);
}
}


tt2767
5个月前
/**
1. 将左右子树都转移到右子树上形成一条链, 关键的问题是把左子节点赋值给右子节点时, 怎么保存右子节点
2. 看一下先序遍历, 右子树应该接到左子树的最右的右儿子上
3. 注意要把左儿子置为null
*/

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
for (; root != null ; root = root.right){
if (root.left == null) continue;
TreeNode cur = root.left;
while (cur.right != null) cur = cur.right;
cur.right = root.right;
root.right = root.left;
root.left = null;
}
}
}