睡醒刷几题清醒头脑~
189、 Rotate Array（数组整体右移，没难度的。。。）
public class Solution {
public void rotate(int[] nums, int k) {
k%=nums.length;
int tmp[] = new int[k];
for(int i=0;i<k;i++){
tmp[i]=nums[nums.length-1-i];
}
for(int i=nums.length-k-1;i>=0;i--){
nums[i+k]=nums[i];
}
for(int i=tmp.length-1,j=0;i>=0;i--){
nums[j++]=tmp[i];
}
}
}
101、 Symmetric Tree(二叉树对称判断，二叉树一般想到递归。。。。)
/**
- Definition for a binary tree node.
- public class TreeNode {
-
int val; -
TreeNode left; -
TreeNode right; -
TreeNode(int x) { val = x; } - }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
else{
return isSymmetric(root.left,root.right);
}
}
boolean isSymmetric(TreeNode left,TreeNode right){
if(left==null&&right==null)return true;//都为空，对称
if((left!=null&&right==null)||(left==null&&right!=null))return false;//一个不为空，不对称
//两个都不为空，判断一下~
//要两个节点的值都想等，并且左子树的左子树和右子树的右子树对称，左子树的右子树和右子树的左子树对称
if(left.val==right.val&&isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left))
return true;
else return false;
}
}
71、 Simplify Path(坑爹的Unix风格的路径特殊情况很多啊，做这道题也好好了解了Unix的路径书写和解析方式。。。)
对了，字符串匹配开始用的==，未知的错误啊。。。换成equals就没问题了，应该是和字符串常量池等内存分配有关，原谅我还没好好看jvm。。。
上代码：
public class Solution {
public String simplifyPath(String path) {<br/>
String ps[] = path.split("/");
String current[] = new String[256];
int pos = 0;
for (int i = 0; i < ps.length; i++) {
if(ps[i].equals("")){
}
else if (ps[i].equals(".")) {
} else if (ps[i].equals("..")) {
if (pos > 0)
pos--;
} else {
current[pos++] = ps[i];
}
}
String result = "/";
for (int i = 0; i < pos; i++) {
if (i < pos - 1)
result += current[i] + "/";
else
result += current[i];
}
return result;
}<br/>
}
44、 Wildcard Matching(通配符匹配实现，据说要用回溯法或动态规划，先把他过了再来研究。。。) 代码如下：
public class Solution {
/**
* 将多个连续*转换成一个*
*
* @param t
* @return
*/
public String simplifyStar(String t) {
String r = "";
for (int i = 0; i < t.length(); i++) {
r += t.charAt(i);
if (t.charAt(i) == '*') {
int pos = i + 1;
while (pos < t.length() && t.charAt(pos) == '*') {
i++;
pos++;
}
}
}
return r;
}
/**
* 匹配入口
*
* @param s
* @param p
* @return
*/
public boolean isMatch(String s, String p) {
// p = simplifyStar(p);
if (!p.contains("*"))
return equals(s, p);
else {
return isMatchStar(s, p);
}
}
/**支持?通配符的equals
* @param s1
* @param s2
* @return
*/
public boolean equals(String s1, String s2) {
int i = 0, j = 0;
for (; i < s1.length() && j < s2.length(); i++, j++) {
if (s1.charAt(i) != s2.charAt(j) && s2.charAt(j) != '?')
return false;
}
if (i < s1.length() || j < s2.length())
return false;
else
return true;
}
/**支持?通配符的startsWith
* @param s
* @param p
* @return
*/
public boolean startsWith(String s, String p) {
int pos = 0;
for (int i = 0; i < p.length(); i++) {
if (pos >= s.length())
return false;
if (s.charAt(pos++) != p.charAt(i) && p.charAt(i) != '?')
return false;
}
return true;
}
/**
* 带*的匹配入口
*
* @param s
* @param p
* @return
*/
private boolean isMatchStar(String s, String p) {
if (p.equals("*"))
return true;
String[] str = handleStar(p);
int pPos = 0;
if (!str[pPos].equals("")) {
if (!startsWith(s, str[pPos]))
return false;
else {
s = s.substring(str[pPos].length());
pPos++;
}
}
String tmp = s;
while (pPos < str.length - 1) {
int t = indexOf(tmp, str[pPos]);
if (t < 0)
return false;
tmp = tmp.substring(t + str[pPos].length());
pPos++;
}
if (str[pPos].equals(""))
return true;
else {
return endsWith(tmp, str[pPos]);
}
}
/**支持?通配符的endsWith
* @param tmp
* @param p
* @return
*/
private boolean endsWith(String tmp, String p) {
if (tmp.length() < p.length())
return false;
for (int i = p.length() - 1, j = tmp.length() - 1; i >= 0; i--, j--) {
if (p.charAt(i) != tmp.charAt(j) && p.charAt(i) != '?')
return false;
}
return true;
}
/**
* 支持?通配符的 indexOf方法
*
* @param str
* @param sub
* @return
*/
public int indexOf(String str, String sub) {
for (int i = 0; i < str.length(); i++) {
int pos = i;
boolean flag = true;
for (int j = 0; j < sub.length(); j++) {
if (pos>=str.length()||(str.charAt(pos) != sub.charAt(j) && sub.charAt(j) != '?')) {
flag = false;
break;
}
pos++;
}
if (flag)
return i;
}
return -1;
}
/**处理多个*连续出现的问题，并把模式字符串按照*分割成各个关键子串，*开头或结尾的话，分别在数组开头或结尾放置一个""标明
* @param s
* @return
*/
public String[] handleStar(String s) {
String str[] = s.split("\\*");
List<String> list = new ArrayList<String>();
for (int i = 0; i < str.length; i++) {
if (!str[i].equals(""))
list.add(str[i]);
}
int length = list.size();
boolean f1 = false, f2 = false;
if (s.startsWith("*")) {
length++;
f1 = true;
}
if (s.endsWith("*")) {
length++;
f2 = true;
}
int pos = 0;
String[] str1 = new String[length];
if (f1) {
str1[pos++] = "";
}
for (int i = 0; i < list.size(); i++) {
str1[pos++] = list.get(i);
}
if (f2) {
str1[pos] = "";
}
return str1;
}
}
106、 Construct Binary Tree from Inorder and Postorder Traversal(从二叉树中序遍历数组和后序遍历数组来还原二叉树) 思路：这种相对复杂的题目人脑不好想啊。。。神人不画图，反正我是普通人，画图啊。。。很好分析的，总结出递归规律。。开始码代码 代码如下：
/**
- Definition for a binary tree node.
- public class TreeNode {
-
int val; -
TreeNode left; -
TreeNode right; -
TreeNode(int x) { val = x; } - }
*/
public class Solution {
/*
* 基本思想：
* 1.后序的最后一个是根节点，再通过根节点值找到在中序的根节点位置
* 2.截取中序的根节点之前的部分，后序数组也截取相同的长度，这两段分别是根节点左子树的中序和后序，后半部分是右子树的
* 3.递归啊。。。
* 4.想好递归结束条件
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
//数组为空呵呵
if(inorder.length==0)
return null;
// root值
int rootValue = postorder[postorder.length - 1];
// 当前传入的数组的root
TreeNode root = new TreeNode(rootValue);
//递归结束条件，数组中只有一个元素的时候
if (inorder.length == 1) {
if (postorder.length == 1 && inorder[0] == postorder[0])
return root;
else
throw new RuntimeException("数组有错哦！");
}
// 找到rootValue在中序的下标
int rootIndex = 0;
while (inorder[rootIndex] != rootValue)
rootIndex++;
//用数组左半边递归构造左子树
int[] leftIn = Arrays.copyOfRange(inorder, 0, rootIndex);
int[] leftPost = Arrays.copyOfRange(postorder, 0, rootIndex);
TreeNode left = buildTree(leftIn, leftPost);
//数组右半边递归构造右子树
int[] rightIn = Arrays.copyOfRange(inorder, rootIndex + 1,
inorder.length);
int[] rightPost = Arrays.copyOfRange(postorder, rootIndex,
postorder.length - 1);
TreeNode right = buildTree(rightIn, rightPost);
//连接根节点和左右子树
root.left = left;
root.right = right;
//返回当前的根节点
return root;
}<br/>
}
28、 Implement strStr()(查询子串在母串的下标位置，就是Java的String的indexOf的实现) 主要是边界条件考虑清楚，调试几遍肯定过。 代码如下：
public class Solution {
public int strStr(String haystack, String needle) {
if(haystack.length()<needle.length())
return -1;
if(haystack.equals(needle))
return 0;
for(int i=0;i<haystack.length()-needle.length()+1;i++){
int pos=i;
boolean flag = true;
for(int j=0;j<needle.length();j++){
if(haystack.charAt(pos)!=needle.charAt(j)){
flag=false;
break;
}
pos++;
}
if(flag)
return i;
}
return -1;
}<br/>
}