1、NC9 二叉树中是否存在节点和为指定值的路径

题目

 

 

 

 

 

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
    }
}

View Code

解决

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left==null && root.right==null && root.val==sum){
            return true;
        }
        if(root.left==null && root.right==null && root.val!=sum){
            return false;
        }
        //利用深度优先遍历，依次找到二叉树每条路径，求出路径和，依次对比目标值
        //https://blog.csdn.net/weixin_39912556/article/details/82852749
        //https://blog.csdn.net/qq_41807489/article/details/88565837
    }
}

参考1

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        return preOrder(root, sum, 0); //利用前序遍历
    }
    boolean preOrder(TreeNode root, int sum, int current) {
        if(root == null){
            return false;
        }
        current += root.val;
        if (root.left==null && root.right==null && sum == current){
            return true;
        }
        return preOrder(root.left, sum, current) || preOrder(root.right, sum, current);
    }
}

参考2

【数据结构和算法】递归和非递归解路径总和问题_牛客博客 (nowcoder.net)

 

 

 

 

 

 

 

 

 

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //如果根节点为空，或者叶子节点也遍历完了也没找到这样的结果，就返回false
        if(root == null){
            return false;
        }
        //如果到叶子节点了，并且剩余值等于叶子节点的值，说明找到了这样的结果，直接返回true
        if(root.left==null && root.right==null && root.val==sum){
            return true;
        }
        //分别沿着左右子节点走下去，然后顺便把当前节点的值减掉
        //左右子节点只要有一个返回true，说明存在这样的结果
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }
}

 

 

 

import java.util.*;
public class Solution {
    
    
    public boolean hasPathSum (TreeNode root, int sum) {
        //如果根节点为空，或者叶子节点也遍历完了也没找到这样的结果，就返回false
        if(root == null){
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); //根节点入栈
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop(); //出栈
            //累加到叶子节点之后，结果等于sum，说明存在这样的一条路径
            if(cur.left==null && cur.right==null){
                if(cur.val == sum){
                    return true;
                }
            }
            //右子节点累加，然后入栈
            if (cur.right != null) {
                cur.right.val = cur.val + cur.right.val;
                stack.push(cur.right);
            }
            //左子节点累加，然后入栈
            if (cur.left != null) {
                cur.left.val = cur.val + cur.left.val;
                stack.push(cur.left);
            }
        }
        return false;
    }
    
    
}

2、NC55 最长公共前缀

题目

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
    }
}

View Code

解决

//17/20 组用例通过  运行超时
import java.util.*;
public class Solution {
    public String longestCommonPrefix (String[] strs) {
        if(strs.length == 0){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }
        
        int minLen = Integer.MAX_VALUE;
        for(int i=0; i<strs.length; i++){
            if(strs[i].length() < minLen){
                minLen = strs[i].length();
            }
        }
        
        String res = "";
        String first = strs[0];
        for(int i=1; i<strs.length; i++){
            String before = strs[i];
            for(int j=0; j<minLen; j++){
                if(first.charAt(j) == before.charAt(j)){
                    res += first.charAt(j);
                }else{
                    break;
                }
                
            }
        }
        
        int len1 = res.length();
        int len2 = strs.length - 1;
        return res.substring(0, len1/len2);
    }
}

参考1

//参考
import java.util.*;
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        String pre = strs[0]; //默认第一个字符串是他们的公共前缀
        int i = 1;
        while (i < strs.length) {
            while (strs[i].indexOf(pre) != 0){ //不断的截取
                pre = pre.substring(0, pre.length() - 1);
            }
            i++;
        }
        return pre;
    }
}

参考2

//参考
import java.util.*;
public class Solution {
    public String longestCommonPrefix (String[] strs) {
        if(strs.length == 0){
            return "";
        }
        Arrays.sort(strs);
        String first = strs[0];
        String last = strs[strs.length-1];
        String res = "";
        int i = 0;
        while(true){
            if(i==first.length() || i==last.length()){
                break;
            }else if(first.charAt(i) == last.charAt(i)){
                res = res + first.charAt(i);
                i++;
            }else{
                break;
            }
        }
        return res;
    }
}

参考3

//参考
public class Solution {
    public String longestCommonPrefix (String[] strs) {
        if (strs.length == 0){
            return ""; 
        }
        StringBuffer sb = new StringBuffer(strs[0]);
        for (int i=1; i<strs.length; i++) {
            sb = helper(sb.toString(), strs[i]);
        }
        return sb.toString();
    }
    
    public StringBuffer helper(String s1, String s2) {
        int i;
        int j;
        for (i=0, j=0; i<s1.length() && j<s2.length(); i++, j++) {
            if (s1.charAt(i) != s2.charAt(j)){
                return new StringBuffer(s1.substring(0, i));
            }
        }
        if (i == s1.length()){
            return new StringBuffer(s1); // s1是s2的子串
        }else{
            return new StringBuffer(s2); // 包括s2是s1的子串，以及s1和s2相同两种情况
        }
    }
}

3、NC56 回文数字

题目

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        // write code here
    }
}

View Code

参考1

//参考
import java.util.*;
public class Solution {
    public boolean isPalindrome (int x) {
        if(x < 0){
            return false;
        }
        int count = 0;
        int temp = x;
        while(temp != 0){
            count = count*10 + temp%10;
            temp = temp / 10;
        }
        return x == count;
    }
}

参考2（使用了String，不符合题目要求）

//参考
import java.util.*;
public class Solution {
    public boolean isPalindrome (int x) {
        StringBuffer sb = new StringBuffer(String.valueOf(x));
        String str = sb.reverse().toString();
        if( str.equals(String.valueOf(x)) ){
            return true;
        }else{
            return false;
        }
    }
}

参考3

//参考
public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int div = 1;
        while (x / div >= 10) {
            div *= 10;
        }
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) {
                return false;
            }
            x = x % div / 10;
            div /= 100;
        }
        return true;
    }
}

4、NC81 二叉搜索树的第k个结点

题目

 

 

 

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        
    }
}

View Code

参考1（非递归，中序遍历，栈）

import java.util.Stack;
public class Solution {
    public TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k == 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = pRoot;
        while(!stack.isEmpty() || cur!=null){ //while 部分为中序遍历
            if(cur != null){
                stack.push(cur); //当前节点不为null，应该寻找左儿子
                cur = cur.left;
            }else{
                cur = stack.pop(); //当前节点null则弹出栈内元素，相当于按顺序输出最小值
                if(--k == 0){ //计数器功能
                    return cur;
                }
                cur = cur.right;
            }
        }
        return null;
    }
}

参考2

import java.util.ArrayList;
public class Solution {
    
    ArrayList<TreeNode> res=new ArrayList();
    
    //直接中序遍历得到结果集，再从结果集取第k-1的数
    public TreeNode KthNode(TreeNode pRoot, int k) {
        fun(pRoot);
        TreeNode result=null;
        //如果k合法
        if(k-1>=0 && res.size()>=k){
           result=res.get(k-1);
        }
        return result;
    }
    
    //中序遍历
    public void fun(TreeNode root){
        if(root!=null){
            fun(root.left);
            res.add(root);
            fun(root.right);
        }
    }
    
}

二叉搜索树的中序遍历就等于对二叉树所有节点排序，排好直接查k-1的元素就完事了

5、NC89 字符串变形

题目

import java.util.*;

public class Solution {
    public String trans(String s, int n) {
        // write code here
    }
}

View Code

解决

//14/20 组用例通过 运行超时
import java.util.*;
public class Solution {
    
    public String trans(String s, int n) {
        if(s==null || s.length()==0){
            return "";
        }
        String[] strArr = s.split(" ");
        String result = "";
        for(int i=strArr.length-1; i>=0; i--){
            if(i != 0){
                result = result + strArr[i] + " ";
            }else{
                result = result + strArr[i];
            }
        }
        if(s.charAt(s.length()-1) == ' '){
            return " " + convert(result);
        }else{
            return convert(result);
        }
    }
    
    public static String convert(String s) {
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(Character.isLowerCase(c)) {
                c = Character.toUpperCase(c);
            }else if(Character.isUpperCase(c)) {
                c = Character.toLowerCase(c);
            }else {
                c = ' ';
            }
            sb.append(c);
        }    
        return sb.toString();
    }
    
}

参考1

//参考
public class Solution {
    public String trans(String s, int n) {
        // 本题实际就是把字符串s反转(单词中的字符位置不反转)，遇到空格不变，遇到大写字母变成小写，小写字母变成大写
        StringBuffer sb = new StringBuffer();
        int index = 0; // 记录字母应插入的位置
        for (int i=n-1; i>=0; i--) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                sb.append(" ");
                index = sb.length();
            } else {
                // 当前字符是字母
                if (ch>='A' && ch<='Z') {
                    sb.insert(index, (char)(ch + 32)); // 大写字母变为小写，每次都插在index位置
                } else {
                    sb.insert(index, (char)(ch - 32)); // 小写字母变为大写，每次都插在index位置
                }
            }
        }
        return sb.toString();
    }
}

参考2

//参考
import java.util.*;
public class Solution {
    public String trans(String s, int n) {
        //找出每个单词来，然后反序加入结果集
       StringBuilder sb = new StringBuilder();
       int i = n-1;
      while(i>=0){//如果是空格就直接加入
           while(i>=0 && s.charAt(i)==' ') {
               sb.append(" ");
               i--;
           }
           //直到找到空格或0，将该单词放进结果集里
           if(i >= 0){
              StringBuilder s1 = new StringBuilder();
               while(i>=0 && s.charAt(i)!=' '){
                  char cha = s.charAt(i);
                  if(cha < 'a'){
                      s1.append((char)(cha-'A'+'a'));  //大写转小写
                  }
                  else{
                      s1.append((char)(cha-'a'+'A'));  //小写转大写
                  }
                  i--;
               }
               sb.append(s1.reverse().toString());//将单词正过来
           }   
       }
        return sb.toString();
    }
}