1.负数左边，正数右边，且相对位置不变
解决办法，冒泡+从右向左,大段大段的交换
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)
{//后序遍历非递归实现
intleft =1;//在辅助栈里表示左节点
intright =2;//在辅助栈里表示右节点
Stack stack =newStack();
Stack stack2 =newStack();//辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
while(biTree !=null|| !stack.empty())
{
while(biTree !=null)
{//将节点压入栈1，并在栈2将节点标记为左节点
stack.push(biTree);
stack2.push(left);
biTree = biTree.left;
}
while(!stack.empty() && stack2.peek() == right)
{//如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
stack2.pop();
System.out.println(stack.pop().value);
}
if(!stack.empty() && stack2.peek() == left)
{//如果是从左子节点返回父节点，则将标记改为右子节点
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.比原有数字大，但是最小的数字，1234->1243
递归，注意本身数组，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.生产者-消费者
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.连续子串和最大
记录当前最大，和最终最大
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)删除链表指定节点
区分头部和尾部
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.字符串最多字符和最大次数
replace得到最大数量即可
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.排序链表
