1.負(fù)數(shù)左邊，正數(shù)右邊咕宿，且相對位置不變
解決辦法币绩，冒泡+從右向左,大段大段的交換
public class Solution {
? public void sortArray(int[] nums){
if(nums.length == 0 || nums.length == 1){
return;
}
int end = nums.length-1;
while(end > 0){
if(nums[end] >= 0){
end--;
} else {
break;
}
}
if(end <= 0) {
return;
}
int start = end -1;
while(start >= 0){
if(nums[start]<0){
start--;
} else {
swapPartArray(nums,start,end);
end--;
start --;
}
}
? }
? public void swapPartArray(int[] nums, int i, int j){
int start = i;
while(start<j){
swapArray(nums,start,start + 1);
start++;
}
? }
? public void swapArray(int[] nums, int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
? }
}
2.二叉樹后序遍歷（非遞歸）
https://blog.csdn.net/coder__666/article/details/80349039
publicstaticvoidpostOrder(TreeNode biTree)
{//后序遍歷非遞歸實現(xiàn)
intleft =1;//在輔助棧里表示左節(jié)點
intright =2;//在輔助棧里表示右節(jié)點
Stack stack =newStack();
Stack stack2 =newStack();//輔助棧蜡秽，用來判斷子節(jié)點返回父節(jié)點時處于左節(jié)點還是右節(jié)點。
while(biTree !=null|| !stack.empty())
{
while(biTree !=null)
{//將節(jié)點壓入棧1缆镣，并在棧2將節(jié)點標(biāo)記為左節(jié)點
stack.push(biTree);
stack2.push(left);
biTree = biTree.left;
}
while(!stack.empty() && stack2.peek() == right)
{//如果是從右子節(jié)點返回父節(jié)點芽突，則任務(wù)完成，將兩個棧的棧頂彈出
stack2.pop();
System.out.println(stack.pop().value);
}
if(!stack.empty() && stack2.peek() == left)
{//如果是從左子節(jié)點返回父節(jié)點董瞻，則將標(biāo)記改為右子節(jié)點
stack2.pop();
stack2.push(right);
biTree = stack.peek().right;
}
}
}
public static List<Integer> lastorderTraversal(TreeNode root) {
// write your code here
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) {
return list;
}
stack.push(root);
TreeNode cur = root.left;
TreeNode temp = null;
TreeNode pre = cur;
while (!stack.empty()) {
if (cur == null) {
temp = stack.peek();
if (temp.left == pre) {
System.out.println("temp.left == pre");
if (temp.right == null) {
list.add(temp.val);
stack.pop();
pre = temp;
} else {
stack.push(temp.right);
}
} else if (temp.right == pre) {
System.out.println("temp.right == pre");
temp = stack.pop();
list.add(temp.val);
pre = temp;
System.out.println("temp.val:" + temp.val);
} else if (temp.left != null) {
System.out.println("temp.left != null");
System.out.println("temp.left.val:"? + temp.left.val);
stack.push(temp.left);
cur = temp.left.left;
} else if (temp.right != null) {
System.out.println("temp.right != null");
System.out.println("temp.right.val:"? + temp.right.val);
stack.push(temp.right);
cur = temp.right.left;
}? else {
System.out.println("else");
System.out.println("temp.val:"? + temp.val);
list.add(temp.val);
stack.pop();
pre = temp;
}
} else {
stack.push(cur);
System.out.println("cur.val:" + cur.val);
cur = cur.left;
}
}
return list;
}
3.比原有數(shù)字大寞蚌，但是最小的數(shù)字，1234->1243
遞歸钠糊，注意本身數(shù)組挟秤，index從0開始
static int cur = 0;
static int min = 0;
public? static int getMinNum(int num){
int len = 0;
int temp = num;
while(temp > 0) {
temp? = temp / 10;
len++;
}
if(len <= 1) {
return num;
}
System.out.println("len:" + len);
cur = num;
min = num;
int i = 0;
int[] nums = new int[len];
while(num > 0) {
nums[i] = num % 10;
num? = num / 10;
i++;
}
recursion(nums, 0);
return min;
}
private? static? void recursion(int[] nums, int index) {
System.out.println("index:" + index);
if(index == nums.length-1) {
int temp = numsToInt(nums);
System.out.println("temp:" + temp);
if(temp > cur) {
if(min == cur) {
min = temp;
} else if(min > temp){
min = temp;
}
}
return;
}
for(int i=index;i<nums.length;i++){
swapArray(nums,index, i);
System.out.println("nums[0]:" + nums[0]);
recursion(nums, index + 1);
swapArray(nums, index, i);
System.out.println("nums[0]:" + nums[0]);
}
}
private static void swapArray(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static int numsToInt(int[] nums){
int i=0;
int result = 0;
while(i< nums.length){
result += nums[i] * (int)Math.pow(10,i);
i++;
}
return result;
}
4.生產(chǎn)者-消費者
package normal;
import java.util.LinkedList;
public class CurrentComm {
private int max? = 5;
private int cur = 0;
LinkedList<Integer> list = new LinkedList<Integer>();
public void product(){
synchronized(list){
if(list.size() >= 5) {
System.out.println("滿了");
try {
list.wait();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
list.add(cur++);
System.out.println("add:" + cur);
list.notify();
}
}
public void customer(){
synchronized(list){
if(list.size() == 0) {
System.out.println("空了");
try {
list.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
int result = list.poll();
System.out.println("remove:" + result);
list.notify();
}
}
}
5.連續(xù)子串和最大
記錄當(dāng)前最大，和最終最大
public static int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int tempMax = nums[0];
int max = nums[0];
for(int i=1;i<nums.length;i++){
tempMax += nums[i];
tempMax = tempMax>nums[i]?tempMax:nums[i];
max = tempMax>max?tempMax:max;
}
return max;
}
6.O(1)刪除鏈表指定節(jié)點
區(qū)分頭部和尾部
public static void deleteNode(ListNode pHead, ListNode pDelNode){
if(pDelNode == null || pHead == null) {
return;
}
if(pHead == pDelNode) {
pHead = pHead.next;
} else if(pDelNode.next != null) {
pDelNode.val = pDelNode.next.val;
pDelNode.next = pDelNode.next.next;
} else {
ListNode temp = pHead;
while(temp.next != pDelNode) {
temp = temp.next;
}
temp.next = null;
}
}
7.字符串最多字符和最大次數(shù)
replace得到最大數(shù)量即可
public static void getMax(String strs){
int maxNum = 0;
String maxStr = "";
while(strs.length() > 0){
int startLength = strs.length();
String head = strs.substring(0, 1);
strs = strs.replace(head,"");
int endLength = strs.length();
if((startLength-endLength)>maxNum) {
maxNum = startLength-endLength;
maxStr = head;
}
}
System.out.println(maxStr + " " + maxNum);
}
8.二維矩陣搜索target
二分法搜索抄伍，注意邊界
public class Solution {
? ? public boolean searchMatrix(int[][] matrix, int target) {
? ? ? ? // write your code here
int row = matrix.length;
if(row == 0) {
return false;
}
int col = matrix[0].length;
if( col == 0) {
return false;
}
int start=0,end=row-1;
int middle = (start + end)/2;
while(middle>= start && middle <= end && start < col? && end >= 0){
if(matrix[middle][0] == target) {
return true;
} else if(matrix[middle][0] > target){
end = middle - 1;
} else if(matrix[middle][0] < target){
start = middle +1;
}
middle = (start + end) /2;
}
if(end<0) return false;
return searchOneLine(matrix,start-1,col-1,target);
}
public boolean searchOneLine(int[][] matrix,int i,int end,int target){
int col = end;
int start=0;
int j=(start+end)/2;
while(j>=start&&j<=end&&start<=col&&end>=0){
if(matrix[i][j] == target){
return true;
} else if(matrix[i][j] > target){
end = j -1;
} else if(matrix[i][j] < target){
start = j + 1;
}
j=(start+end)/2;
}
return false;
}
}
9.排序鏈表
