从0开始刷剑指Offer

剑指Offer题解

剑指 Offer 11. 旋转数组的最小数字

思路: 二分O(logn)

class Solution {public int stockManagement(int[] stock) {int l = 0;int r = stock.length - 1;while(l < r && stock[0] == stock[r]) r --;if(stock[r] >= stock[l]) return stock[0];while(l < r) {int mid = l + r >> 1;if(stock[mid] < stock[0]) r = mid;else l = mid + 1;}return stock[l];}
}

剑指 Offer 12. 矩阵中的路径

思路: 回溯O(n²3^k)

class Solution {int[] dx = new int[] {-1, 0, 1, 0};int[] dy = new int[] {0, 1, 0, -1};public boolean wordPuzzle(char[][] grid, String target) {char[] words = target.toCharArray();for(int i = 0; i < grid.length; i ++) {for(int j = 0; j < grid[i].length; j ++) {if(dfs(grid, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] grid, char[] target, int i, int j, int k) {if(i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != target[k]) {return false;}if(k == target.length - 1) return true;grid[i][j] = '.';for(int num = 0; num < 4; num ++) {int a = i + dx[num];int b = j + dy[num]; if(dfs(grid, target, a, b, k + 1)) return true;}grid[i][j] = target[k];return false;}
}

剑指 Offer 13. 机器人的运动范围

思路一: 宽搜O(nm)

class Solution {int[] dx = new int[]{-1, 0, 1, 0};int[] dy = new int[]{0, 1, 0, -1};public int wardrobeFinishing(int m, int n, int k) {if(m == 0 || n == 0) return 0;Queue<int[]> q = new LinkedList<>();boolean[][] visited = new boolean[m][n];q.add(new int[]{0, 0});int cnt = 0;while(!q.isEmpty()) {int[] t = q.poll();int x = t[0];int y = t[1];if(visited[x][y] || getSum(x, y) > k) continue;cnt ++;visited[x][y] = true;for(int i = 0; i < 4; i ++) {int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n) {q.add(new int[]{a, b});}}}return cnt;}int getSum(int x, int y) {int s = 0;while(x != 0) {s += x % 10;x = x / 10;}while(y != 0) {s += y % 10;y = y / 10;}return s;}
}

思路二: 深搜O(nm)

class Solution {int m, n, cnt;boolean[][] visited;public int wardrobeFinishing(int m, int n, int cnt) {this.m = m;this.n = n;this.cnt = cnt;this.visited = new boolean[m][n];return dfs(0, 0, 0, 0);}public int dfs(int i, int j, int si, int sj) {if(i >= m || j >= n || cnt < si + sj || visited[i][j]) return 0;visited[i][j] =true;return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);}
}

剑指 Offer 14- I. 剪绳子

思路: 贪心O(n)

class Solution {public int cuttingBamboo(int n) {if(n <= 3) return n - 1;int res = 1;if(n % 3 == 1) {res = 4;n -= 4;}else if(n % 3 == 2) {res = 2;n -= 2;}while(n > 0) {res = (res * 3) % 1000000007;n -= 3;}return res;}
}

剑指 Offer 14- II. 剪绳子 II

思路: 贪心O(n) 同上

class Solution {public int cuttingBamboo(int n) {if(n < 4) return n - 1;long res = 1;if(n % 3 == 1) {res = 4;n -= 4;}else if(n % 3 == 2) {res = 2;n -= 2;}while(n > 0) {res = (res * 3) % 1000000007; //循环求余n -= 3;}return (int)res;}
}

剑指 Offer 15. 二进制中1的个数

思路一: 逐位判断O(logn)

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int res = 0;while(n != 0) {res += n & 1;n >>>= 1; //无符号右移}return res;}
}

思路二: 末位置0法O(logn)

public class Solution {public int hammingWeight(int n) {int res = 0;while(n != 0) {res++;n &= n - 1;}return res;}
}

思路三: 末位移除法O(logn)

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int res = 0;while(n != 0) {n -= n & -n;res ++;}return res;}
}

剑指 Offer 16. 数值的整数次方

思路一：暴力O(n) 超出时间限制

class Solution {public double myPow(double x, int n) {if(n == 0) return 1.0;long N = n;return N >= 0 ? Mul(x, N) * 1.0 : 1.0 / Mul(x, -N);}public double Mul(double x, long b) {double temp = x;while(b -- > 1) {x *= temp;}return x;}
}

思路二：快速幂O(logn)

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) * 1.0 : 1.0 / quickMul(x, -N);}public double quickMul(double x, long b) {double res = 1;while (b > 0) {if((b & 1) > 0) {res *= x;} b >>= 1;x *= x;}return res;}
}

剑指 Offer 17. 打印从1到最大的n位数

思路一：模拟O(n)

class Solution {public int[] countNumbers(int cnt) {int end = (int)Math.pow(10, cnt) - 1;int[] res = new int[end];for(int i = 0; i < end; i ++) {res[i] = i + 1;}return res;}
}

思路二：递归全排列O(10^cnt)

class Solution {int[] res;int nine = 0; int count = 0; int start; int cnt;char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public int[] countNumbers(int cnt) {this.cnt = cnt;res = new int[(int)Math.pow(10, cnt) - 1];num = new char[cnt];start = cnt - 1;dfs(0);return res;}void dfs(int x) {// if (x == cnt) { //x是指的是num数组的位数String s = String.valueOf(num).substring(start);if(!s.equals("0")) res[count ++] = Integer.parseInt(s);if(cnt - start == nine) start --;//刚开始，cnt - start = 1, 当个位等于9时，nine = 1, start --;return;//因为这一步返回了，所以dfs继续下去，nine --;}for(char i : loop) {if(i == '9') nine ++;num[x] = i;dfs(x + 1);}nine --;}
}

剑指 Offer 18. 删除链表的节点

思路: (链表， 遍历) O(n)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode deleteNode(ListNode head, int val) {ListNode dummy = head;if(dummy.val == val) dummy = dummy.next;while (head != null && head.next != null) {if(head.next.val == val) {head.next = head.next.next;}head = head.next;} return dummy;}
}

剑指 Offer 19. 正则表达式匹配

思路: 动态规划O(nm)

class Solution {public boolean articleMatch(String s, String p) {int m = s.length() + 1, n = p.length() + 1;boolean[][] dp = new boolean[m][n];dp[0][0] = true;for(int j = 2; j < n; j += 2)dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';//第一行初始化为0,因为s初始化是0for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = p.charAt(j - 1) == '*' ?dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));}}return dp[m - 1][n - 1];}
}

剑指 Offer 20. 表示数值的字符串

**思路: (模拟，字符串处理)O(n) **

class Solution {public boolean validNumber(String s) {if(s.length() <= 0 || s == null ) {return false;}char[] res = s.trim().toCharArray();int len = res.length;boolean isNumber = false;boolean isE = false;boolean isDot = false;for(int i = 0; i < len; i ++ ){if(res[i] >= '0' && res[i] <= '9') {isNumber = true;}else  if(res[i] == '.') {if(isDot == true || isE == true) {return false;}isDot = true;}else if(res[i] == 'e' || res[i] == 'E') {if(isE == true || !isNumber ) {return false;}isE = true;isNumber = false;}else  if(res[i] == '-' || res[i] == '+') {if(i!=0 && res[i-1] != 'e' && res[i-1] != 'E'){return false;}}else  return false;}return isNumber;}
}