剑指offer java刷一遍
https://www.jianshu.com/p/010410a4d419
image.png
清晰 https://www.zhihu.com/question/36914829
StringBuffer 和 StringBuilder
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
两个栈实现队列
import java.util.Stack;
public class stack_queue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}else {
return stack2.pop();
}
}
}
旋转数组的最小元素
用二分法，二分法为了简便可以一直使用 start + 1 < end，但需要判断最后两个元素值。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array==null||array.length==0){
return 0;
}
int start = 0;
int end = array.length - 1;
int mid = 0;
while (start + 1 < end){
mid = start + (end - start) / 2;
if(array[mid] > array[end]){
start = mid + 1;
}else{
end = mid;
}
}
if(array[start] < array[end])
return array[start];
else
return array[end];
}
}
跳台阶问题
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
int pre = 2;
int prepre = 1;
int temp = 0;
for(int i=3;i<target+1;i++){
temp = pre;
pre = pre + prepre;
prepre = temp;
}
return pre;
}
}
1的个数
public int NumberOf1(int n) {
int count = 0;
if(n >= 0){
while(n!=0){
count = count + (n & 1);
n = (n>>1);
}
}else {
n = ~n;
while(n!=0){
count = count + (n & 1);
n = (n>>1);
}
count = 32 - count;
}
return count;
}
另一种巧妙方法
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
}
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
算法提升篇
求连续子数组的最大和--动态规划
public class maxSumofContinueArray {
public static int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
int preMax = 0;
for(int i=0;i<array.length;i++){
if(preMax >= 0)
preMax = preMax + array[i];
else
preMax = array[i];
if(preMax > max)
max = preMax;
}
return max;
}
public static void main(String [] args){
int[] data = {1,-2,3,10,-4,7,2,-5};
System.out.println(FindGreatestSumOfSubArray(data));
}
}
剪绳子
public class cutRope {
public static int maxCutting(int length){
if(length <= 1) return 0;
if(length < 4) return length - 1;
int []res = new int[length+1];
res[0] = 0;
res[1] = 1;
res[2] = 2;
res[3] = 3;
int max = 0;
int temp = 0;
for(int i=4; i<=length; i++){
max = 0;
for(int j=1;j<=i/2;j++){
temp = res[j]*res[i-j];
if(temp > max) max = temp;
}
res[i] = max;
}
return res[length];
}
}
数组翻译成字符串
0对应a，25对应z，给定一个整数，看有多少种对应方式。动态规划的典型问题。
public class numberToString {
public static int getTranslationCount(int number){
if(number < 0) return 0;
return getTranslationCount(Integer.toString(number));
}
public static int getTranslationCount(String number){
int pre = 1;
int prepre = 1;
int temp = 0, g = 1;
for(int i=number.length()-2;i>=0;i--){
if(Integer.parseInt(number.charAt(i)+""+number.charAt(i+1))<26 && number.charAt(i) != '0'){
g = 1;
} else{
g = 0;
}
temp = pre;
pre = pre + g*prepre;
prepre = temp;
}
return pre;
}
public static void main(String[] args){
System.out.println(getTranslationCount(1204));
}
}
最长不重复子串
public class maxLengthOfNoDup {
public static int longestSubstringWithoutdup(String str){
if(str==null || str.length()==0)
return 0;
int[] dp = new int[str.length()];
dp[0] = 1;
int max = 1;
for(int i=1;i<dp.length;i++){
int j=i-1;
for(;j>=i-dp[i-1];j--){
if(str.charAt(i) == str.charAt(j))
break;
}
dp[i] = i - j;
if(dp[i]>max)
max = dp[i];
}
return max;
}
public static void main(String[] args){
System.out.println(longestSubstringWithoutdup("arabcadecefr"));
}
}
关键在于这句的理解 (;j>=i-dp[i-1];j--)。
这道题还是需要认真理解，首先为什么不能够直接从j=i-1一直遍历到j=0,因为要保证遍历的范围是不重复的，比如[2,3,2,4,5,6]，对4来说和前面三个都不相等，但是里面就有2重复，需要根据前面一个的最大范围确定所能遍历的范围。遍历到j=m时加入相等，则会停止，计算元素个数是i-j+1，这里没有+1，因为for循环先对j进行了减1操作。
矩阵中的路径（回溯）
public class PathInArray {
public static boolean hasPath(char[][] data, String str){
if(data==null || data.length==0 || str==null || str.length()==0)
return false;
int m = data.length;
int n = data[0].length;
boolean[][] visted = new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
visted[i][j] = false;
}
}
boolean res;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
res = dfs(data,visted,i,j,str,0);
if(res)
return true;
}
}
return false;
}
private static boolean dfs(char[][] data,boolean[][] visted,int m, int n , String str, int pos){
if(pos==str.length()) return true;
if(m<0 || m >= data.length || n < 0 || n >= data[0].length)
return false;
if(visted[m][n] || data[m][n] != str.charAt(pos)) return false;
visted[m][n] = true;
boolean res = dfs(data,visted,m+1,n,str,pos+1) ||
dfs(data,visted,m-1,n,str,pos+1) ||
dfs(data,visted,m,n-1,str,pos+1) ||
dfs(data,visted,m,n+1,str,pos+1);
visted[m][n] = false;
return res;
}
public static void main(String[] args){
char[][] data = {
{'a','b','t','g'},
{'c','f','c','s'},
{'j','d','e','h'}
};
System.out.println(hasPath(data,"bfce"));
System.out.println(hasPath(data,"abfb"));
}
}
机器人的运动范围
public class robotMoveRange {
public static int movingCount(int threshold, int cow, int row){
if(threshold < 0 || cow < 0 || row < 0)
return 0;
boolean[][] visted = new boolean[cow][row];
for(int i=0;i<cow;i++){
for(int j=0;j<row;j++){
visted[i][j] = false;
}
}
int count = 0;
dfs(count,threshold, visted, cow, row, 0, 0);
// 返回的count=0，出现问题。整数是传值
return count;
}
public static void dfs(int count, int threshold, boolean[][] visted, int cow, int row, int m, int n){
if( m < 0 || m>=cow || n<0 || n>=row) return;
if(visted[m][n]) return;
visted[m][n] = true;
if(getDigitSum(m) + getDigitSum(n) <= threshold) {
count += 1;
System.out.println(count); //最终结果正确
}
dfs(count, threshold, visted, cow, row, m-1, n);
dfs(count, threshold, visted, cow, row, m+1, n);
dfs(count, threshold, visted, cow, row, m, n+1);
dfs(count, threshold, visted, cow, row, m, n-1);
}
public static int getDigitSum(int number){
int sum = 0;
while(number!=0){
sum += number % 10;
number /= 10;
}
return sum;
}
public static void main(String[] args){
System.out.println(movingCount(9,2,20));
}
}
上面的程序有一点问题。如何去改进。
public class robotMoveRange {
public static int movingCount(int threshold, int cow, int row){
if(threshold < 0 || cow < 0 || row < 0)
return 0;
boolean[][] visted = new boolean[cow][row];
for(int i=0;i<cow;i++){
for(int j=0;j<row;j++){
visted[i][j] = false;
}
}
int count = 0;
count = dfs(threshold, visted, cow, row, 0, 0);
// 返回的count=0，出现问题。整数是传值
return count;
}
public static int dfs( int threshold, boolean[][] visted, int cow, int row, int m, int n){
if( m < 0 || m>=cow || n<0 || n>=row) return 0;
if(visted[m][n] || (getDigitSum(m) + getDigitSum(n) > threshold)) return 0;
visted[m][n] = true;
return dfs(threshold, visted, cow, row, m-1, n) +
dfs( threshold, visted, cow, row, m+1, n) +
dfs( threshold, visted, cow, row, m, n+1) +
dfs(threshold, visted, cow, row, m, n-1) + 1;
}
public static int getDigitSum(int number){
int sum = 0;
while(number!=0){
sum += number % 10;
number /= 10;
}
return sum;
}
public static void main(String[] args){
System.out.println(movingCount(9,2,20));
}
}
一个数的整数次方
public class xPowerN {
public static double mypower(double number, int n){
if(n==0) return 1;
if(n < 0){
double res = mypower(number,-n);
return 1.0/res;
}else {
double temp = mypower(number,n>>1);
if((n & 1)==1){
return temp * temp * number;
}else
return temp * temp;
}
}
public static double mypower2(double number, int n){
double res = 1;
int abs_n = Math.abs(n);
while(abs_n!=0){
if((abs_n & 1) == 1)
res *= number;
abs_n >>= 1;
number *= number;
}
if(number < 0) return 1.0/res;
else return res;
}
public static void main(String[] args){
double base = 2;
int n = 10;
System.out.println(mypower2(base, n));
}
}
递归和循环两种基本思路。
排序链表删除重复元素
import com.ListNode;
import java.util.List;
// 删除排序链表重复节点，不保留
public class DeleteNodeInLinklist {
public static ListNode DeleteDupNode(ListNode node){
if(node==null || node.next==null)
return node;
ListNode dummy = new ListNode(-1);
dummy.next = node;
ListNode ptr = dummy;
while(node != null && node.next != null){
if(node.val != node.next.val){
node = node.next;
ptr = ptr.next;
}else {
while((node != null) && (node.next != null) && (node.val==node.next.val)){
node = node.next;
}
node = node.next;
ptr.next = node;
}
}
return dummy.next;
}
// 删除重复节点但保留一个
public static ListNode DeleteDupNodeWithOne(ListNode node){
if(node==null || node.next==null)
return node;
ListNode current = node;
while(current != null && current.next != null){
if(current.val == current.next.val)
current.next = current.next.next;
else
current = current.next;
}
return node;
}
}
BFS
树的按层遍历
队列相关知识 https://juejin.im/post/5a3763ed51882506a463b740
public class BTlevelOrderTravelsal {
public List<List<Integer>> levelOrder(TreeNode root){
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
// LinkedList ?
Queue<TreeNode> nodes = new LinkedList<>();
nodes.offer(root);
while(!nodes.isEmpty()){
List<Integer> subres = new ArrayList<>();
int levelNum = nodes.size();
for(int i=0;i<levelNum;i++){
TreeNode node = nodes.poll();
subres.add(node.val);
if(node.left != null) nodes.offer(node.left);
if(node.right != null) nodes.offer(node.right);
}
res.add(subres);
}
return res;
}
}
之字形层次打印二叉树
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean order = true;
int size = 1;
while(!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {
tmp.add(n.val);
} else {
tmp.add(0, n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
res.add(tmp);
size = q.size();
order = order ? false : true;
}
return res;
}
}
Remove Invalid Parentheses (leetcode 301)
https://leetcode.com/problems/remove-invalid-parentheses/description/
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if (s == null){
return res;
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
visited.add(s);
boolean found = false;
while (!queue.isEmpty()){
String item = queue.poll();
if(isVaild(item)){
res.add(item);
found = true;
}
if(found) continue;
for(int i=0; i<item.length();i++){
if(item.charAt(i) != '(' && item.charAt(i) !=')') continue;
String t = item.substring(0,i) + item.substring(i+1);
if(!visited.contains(t)){
queue.offer(t);
visited.add(t);
}
}
}
return res;
}
public static boolean isVaild(String s){
int count = 0;
for(int i=0; i<s.length();i++){
if(s.charAt(i)=='(') count += 1;
if(s.charAt(i)==')' && count-- == 0) return false;
}
return count == 0;
}
}
