You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) {
return false;
}
int n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && i >= 0 && j < n && j >= 0) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
j = j - 1;
} else {
i = i + 1;
}
}
return false;
}
}
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
class Solution {
public String replaceSpace(String s) {
return s.replace(" ","%20");
}
}
class Solution {
public int[] reversePrint(ListNode head) {
List<Integer> list = new LinkedList();
while (head != null) {
list.add(head.val);
head = head.next;
}
int[] ans = new int[list.size()];
int index = ans.length - 1;
for (int i : list) {
ans[index--] = i;
}
return ans;
}
}
class CQueue {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
public CQueue() {
}
public void appendTail(int value) {
s1.push(value);
}
public int deleteHead() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
if (s2.isEmpty()) {
return -1;
}
return s2.pop();
}
}
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,F(1)= 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
class Solution {
int mod = 1000000007;
public int fib(int n) {
int[] dp = new int[2];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i & 1] = (dp[(i - 1) & 1] % mod + dp[(i - 2) & 1] % mod) % mod;
}
return dp[n & 1];
}
}
剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
class Solution {
int mod = 1000000007;
public int numWays(int n) {
int[] dp = new int[2];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i & 1] = (dp[(i - 1) & 1] % mod + dp[(i - 2) & 1] % mod) % mod;
}
return dp[n & 1];
}
}
class Solution {
public int minArray(int[] nums) {
int n = nums.length;
int r = n - 1;
if (nums[r] > nums[0]) {
return nums[0];
}
while (r >= 0 && nums[r] == nums[0]) {
r--;
}
if (r == -1) {
return nums[0];
}
if (nums[r] > nums[0]) {
return nums[0];
}
int l = 0;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[0]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[r];
}
}
剑指 Offer 12. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution {
char[][] board;
boolean[][] visited;
public boolean exist(char[][] board, String word) {
this.board = board;
visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0) && dfs(word, 0, i, j)) {
return true;
}
}
}
return false;
}
public boolean dfs(String word, int index, int i, int j) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
return false;
}
if (visited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
visited[i][j] = true;
boolean ans = dfs(word, index + 1, i + 1, j) || dfs(word, index + 1, i - 1, j)
|| dfs(word, index + 1, i, j + 1) || dfs(word, index + 1, i, j - 1);
visited[i][j] = false;
return ans;
}
}
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
visited[0][0] = true;
int ans = 0;
Queue<int[]> queue = new LinkedList();
queue.offer(new int[]{0, 0});
int[] x = {1, -1, 0, 0};
int[] y = {0, 0, 1, -1};
while (!queue.isEmpty()) {
int size = queue.size();
ans += size;
for (int i = 0; i < size; i++) {
int[] poll = queue.poll();
for (int K = 0; K < 4; K++) {
int newX = poll[0] + x[K];
int newY = poll[1] + y[K];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
visited[newX][newY] = true;
int num = 0;
int temp = newX;
while (temp != 0) {
num += temp % 10;
temp = temp / 10;
}
temp = newY;
while (temp != 0) {
num += temp % 10;
temp = temp / 10;
}
if (num <= k) {
queue.offer(new int[]{newX, newY});
}
}
}
}
}
return ans;
}
}
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int mod = n % 3;
int cnt = n / 3;
if (mod == 1) {
return (int) (Math.pow(3.0, cnt - 1) * 4);
}
return (int) (Math.pow(3.0, cnt) * (mod == 0 ? 1 : mod));
}
}
剑指 Offer 14- II. 剪绳子 II
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
class Solution {
int mod = 1000000007;
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
long ans = 1;
while (n > 4) {
ans = ans * 3 % mod;
n -= 3;
}
ans = ans * n % mod;
return (int) (ans);
}
}
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans = 0;
while(n != 0) {
n = n & (n-1);
ans++;
}
return ans;
}
}
剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
输入：x = 2.00000, n = 10
输出：1024.00000
class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 1 / (myPow(x, -(n + 1)) * x);
}
int halfN = n / 2;
double val = myPow(x, halfN);
double ans = val * val;
if (n % 2 == 1) {
ans *= x;
}
return ans;
}
}
剑指 Offer 17. 打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
class Solution {
public int[] printNumbers(int n) {
int max = (int) Math.pow(10, n) - 1;
int[] ans = new int[max];
for (int i = 0; i < max; i++) {
ans[i] = i + 1;
}
return ans;
}
}
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (solve(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean solve(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null || A.val != B.val) {
return false;
}
return solve(A.left, B.left) && solve(A.right, B.right);
}
}
class Solution {
public int[] spiralOrder(int[][] matrix) {
int m = matrix.length;
if (m == 0) {
return new int[0];
}
int n = matrix[0].length;
if (n == 0) {
return new int[0];
}
int round = Math.min((m + 1) / 2, (n + 1) / 2);
int[] ans = new int[m * n];
int index = 0;
int l = 0, t = 0, r = n - 1, b = m - 1;
for (int x = 0; x < round; x++) {
for (int i = l; i <= r; i++) {
ans[index++] = matrix[t][i];
}
for (int i = t + 1; i <= b; i++) {
ans[index++] = matrix[i][r];
}
for (int i = r - 1; i >= l && b != t; i--) {
ans[index++] = matrix[b][i];
}
for (int i = b - 1; i > t && l != r; i--) {
ans[index++] = matrix[i][l];
}
l++;
t++;
r--;
b--;
}
return ans;
}
}
剑指 Offer 30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
class MinStack {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
public MinStack() {
}
public void push(int x) {
s1.push(x);
if (s2.empty() || s2.peek() >= x) {
s2.push(x);
}
}
public void pop() {
if (s1.pop().equals(s2.peek())) {
s2.pop();
}
}
public int top() {
return s1.peek();
}
public int min() {
return s2.peek();
}
}
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> s = new Stack();
int i = 0;
for (int num : pushed) {
s.push(num);
while (i < popped.length && !s.isEmpty() && popped[i] == s.peek()) {
s.pop();
i++;
}
}
return s.isEmpty();
}
}
剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
class Solution {
public int[] levelOrder(TreeNode root) {
List<Integer> ans = new ArrayList();
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
ans.add(node.val);
}
}
int[] array = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
array[i] = ans.get(i);
}
return array;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList();
List<List<Integer>> ans = new ArrayList();
if (root == null) {
return ans;
}
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ans.add(list);
}
return ans;
}
}
class Solution {
public int majorityElement(int[] nums) {
int c = nums[0];
int cnt = 1;
for (int i = 1; i < nums.length; i++) {
if (cnt == 0) {
c = nums[i];
cnt++;
} else if (nums[i] == c) {
cnt++;
} else {
cnt--;
}
}
return c;
}
}
剑指 Offer 40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int i : arr) {
pq.offer(i);
if (pq.size() > k) {
pq.poll();
}
}
int[] ans = new int[k];
int index = 0;
for (int i : pq) {
ans[index++] = i;
}
return ans;
}
}
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
if (sum >= 0) {
sum += nums[i];
} else {
sum = nums[i];
}
ans = Math.max(ans, sum);
}
return ans;
}
}
剑指 Offer 43. 1～n 整数中 1 出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
class Solution {
public int countDigitOne(int n) {
int ans = 0;
int range = 1;
int l = n / 10;
int cur = n % 10;
int r = 0;
while (!(l == 0 && cur == 0)) {
if (cur == 0) {
// 301 -> *1*
ans += l * range;
} else if (cur == 1) {
// 311
ans += l * range + r + 1;
} else {
// 321
ans += (l + 1) * range;
}
r += cur * range;
cur = l % 10;
l /= 10;
range *= 10;
}
return ans;
}
}
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
long cnt = 9;
long l = 1, r = 9, c = 1;
while (cnt < n) {
r = r * 10 + 9;
l = l * 10;
c++;
cnt += c * (r - l + 1);
}
long s = cnt - c * (r - l + 1);
long gap = n - s - 1;
long gapC = gap / c;
long modC = gap % c;
long num = l + gapC;
String str = String.valueOf(num);
char ch = str.charAt((int) (modC));
return ch - '0';
}
}
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for(int i=0; i < m; i++) {
for(int j=0; j < n; j++) {
int left = j>=1 ? grid[i][j-1] : 0;
int right = i>=1 ? grid[i-1][j] : 0;
grid[i][j] = Math.max(grid[i][j] + left, grid[i][j] + right);
}
}
return grid[m-1][n-1];
}
}
