1、NC1 大数加法
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ public String solve (String s, String t) { // write code here } }
实现
// 没不出来，这个不对 import java.util.*; public class Solution { public String solve (String s, String t) { // long num1 = Long.parseLong(s); // long num2 = Long.parseLong(t); // return "" + (num1 + num2); String res = ""; int flag = 0; for(int i=s.length()-1, j=t.length()-1; i>=0 && j>=0; i--, j--){ int numS = s.charAt(i); //自动转换 int numT = s.charAt(j); if(numS + numT + flag >= 10){ flag = 1; res += (numS + numT + flag) / 10; }else{ flag = 0; res += (numS + numT); } } System.out.println(res); return res; } }
参考
import java.math.BigInteger; import java.util.*; public class Solution { public String solve (String s, String t) { BigInteger bigInteger1 = new BigInteger(s); BigInteger bigInteger2 = new BigInteger(t); return bigInteger1.add(bigInteger2).toString(); } }
import java.util.*; public class Solution { public String solve (String s, String t) { int sum = 0; StringBuilder result = new StringBuilder(); int si = s.length() - 1; int ti = t.length() - 1; while (si >= 0 || ti >= 0) { if (si >= 0) { sum += s.charAt(si) - '0'; si--; } if (ti >= 0) { sum += t.charAt(ti) - '0'; ti--; } result.append(sum % 10); sum = sum >= 10 ? 1 : 0; } if (sum > 0) { result.append(sum); } return result.reverse().toString(); } }
import java.util.*; public class Solution { public String solve (String s, String t) { int len1 = s.length(); int len2 = t.length(); int max = len1; if (max < len2) { max = len2; s = padding(s, max); } else { t = padding(t, max); } StringBuilder sb = new StringBuilder(max + 1); int add = 0; for (int i=max-1; i>=0; i--) { int num1 = s.charAt(i) - '0'; int num2 = t.charAt(i) - '0'; int sum = num1 + num2 + add; sb.append(sum % 10); add = sum / 10; } if (add > 0) { sb.append(add); } return sb.reverse().toString(); } private String padding(String s, int max) { if (s.length() == max) { return s; } StringBuilder sb = new StringBuilder(max); int gap = max - s.length(); while (gap > 0) { sb.append('0'); gap--; } sb.append(s); return sb.toString(); } }
2、NC127 最长公共子串
import java.util.*; public class Solution { /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ public String LCS (String str1, String str2) { // write code here } }
参考
//参考1：动态规划 import java.util.*; public class Solution { public String LCS (String str1, String str2) { int m = str1.length(); int n = str2.length(); int[][] dp = new int[m][n]; int maxLength = 0; int lastIndex = 0; //用来记录str1中最长公共串的最后一个字符的下标 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(str1.charAt(i) == str2.charAt(j)){ //判断str1中第i个字符是否和str2中第j个字符相等 if(i == 0 || j == 0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i - 1][j - 1] + 1; } if(dp[i][j] > maxLength){ //判断是否需要更新最长公共子串 maxLength = dp[i][j]; lastIndex = i; } } } } //通过str1来截取长度为maxLength, 最后字符坐标为lastIndex的子串 return str1.substring(lastIndex - maxLength + 1, lastIndex + 1); } }
//参考2 import java.util.*; public class Solution { public String LCS (String str1, String str2) { int start = 0; int end = 1; //初始条件：subString(0, 1)，左闭右开，即只取第一个第0个字符 String result = ""; while(end <= str2.length()){ //subString左闭右开，所以可以取到等于 String subStr = str2.substring(start, end); if(str1.contains(subStr)){ result = subStr; // str1包含str2的该子串，例如:ab，继续右移看是否继续包含abc，所以end右移 }else{ start++; //str1不包含str2的该子串，例如:13，不必再找以13开头的子串了，因为不包含13，肯定也不包含134，所以start右移；因为需要找最长子串，start右移后，end也需要右移，保证长度不会缩短 } end++; //上述两种情况，均需要end右移 } return result; } }
3、NC40 两个链表生成相加链表
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // write code here } }
参考
//参考1：朴素解法（哨兵技巧） import java.util.*; public class Solution { ListNode reverse(ListNode root) { ListNode prev = null, cur = root; while (cur != null) { ListNode tmp = cur.next; cur.next = prev; prev = cur; cur = tmp; } return prev; } public ListNode addInList (ListNode head1, ListNode head2) { ListNode l1 = reverse(head1), l2 = reverse(head2); ListNode dummy = new ListNode(0); ListNode tmp = dummy; int t = 0; while (l1 != null || l2 != null) { int a = l1 != null ? l1.val : 0; int b = l2 != null ? l2.val : 0; t = a + b + t; tmp.next = new ListNode(t % 10); t /= 10; tmp = tmp.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (t > 0) tmp.next = new ListNode(t); return reverse(dummy.next); } }
//参考2：Java用栈存储节点，通过头插法生成目标链表 import java.util.*; public class Solution { public ListNode addInList (ListNode head1, ListNode head2) { if (head1 == null) return head2; if (head2 == null) return head1; Stack<Integer> stack1 = initStack(head1); Stack<Integer> stack2 = initStack(head2); ListNode head = initListNode(stack1,stack2); return head; } public Stack initStack(ListNode node){ Stack<Integer> stack = new Stack(); while(node != null){ stack.add(node.val); node = node.next; } return stack; } public ListNode initListNode(Stack<Integer> stack1,Stack<Integer> stack2){ ListNode head = null; int k = 0; while(!stack1.isEmpty() || !stack2.isEmpty()){ int i1 = !stack1.isEmpty()?stack1.pop():0; int i2 = !stack2.isEmpty()?stack2.pop():0; int i = (i1 + i2 + k) % 10; k = (i1 + i2 + k) / 10; ListNode node = new ListNode(i); if(head == null){ head = node; }else{ node.next = head; head = node; } } if(k == 1){ ListNode node = new ListNode(k); node.next = head; head = node; } return head; } }
4、NC102 在二叉树中找到两个节点的最近公共祖先
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here } }
参考
//参考1：递归 import java.util.*; public class Solution { public int lowestCommonAncestor (TreeNode root, int o1, int o2) { return CommonAncestor(root, o1, o2).val; } public TreeNode CommonAncestor (TreeNode root, int o1, int o2) { if (root == null || root.val == o1 || root.val == o2) { // 如果root为空，或者root为o1、o2中的一个，则它们的最近公共祖先就为root return root; } TreeNode left = CommonAncestor(root.left,o1,o2); // 递归遍历左子树，只要在左子树中找到了o1或o2，则先找到谁就返回谁 TreeNode right = CommonAncestor(root.right,o1,o2); // 递归遍历右子树，只要在右子树中找到了o1或o2，则先找到谁就返回谁 if (left == null) { // 如果在左子树中o1和o2都找不到，则o1和o2一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先） return right; }else if (right == null) { // 否则，如果left不为空，在左子树中有找到节点（o1或o2），这时候要再判断一下右子树中的情况， // 如果在右子树中，o1和o2都找不到，则 o1和o2一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先） return left; }else{ return root; // 否则，当 left和 right均不为空时，说明 o1、o2节点分别在 root异侧, 最近公共祖先即为 root } } }
//参考2：递归 import java.util.*; public class Solution { public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // root为空则说明越过了叶子节点 if(root == null) return -1; // 如果root为o1或o2中任意一个，则root就是公共祖先 if(root.val == o1 || root.val == o2) return root.val; //root不为o1或o2 int left = lowestCommonAncestor(root.left, o1, o2); int right = lowestCommonAncestor(root.right, o1, o2); //如果left=-1，说明在左子树中一直找到叶子节点，也没找到最近公共祖先 //所以最近公共祖先，必在右子树中，right即为最近公共祖先 if(left == -1) return right; //同理，最近公共祖先必在左子树中，left即为最近公共祖先 else if(right == -1) return left; //若left和right都不为-1，则说明o1,o2节点在root的异侧，则root为最近公共祖先 else return root.val; } }
5、NC17 最长回文子串
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here } }
参考
【数据结构和算法】中心扩散，暴力，动态规划3种方式解决_牛客博客 (nowcoder.net)
//参考1：中心扩散法 import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { //边界条件判断 if (n < 2) return A.length(); //maxLen表示最长回文串的长度 int maxLen = 0; for (int i = 0; i < n; ) { //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环 // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断） if (n - i <= maxLen / 2) break; int left = i; int right = i; while (right < n - 1 && A.charAt(right + 1) == A.charAt(right)) ++right; //过滤掉重复的 //下次在判断的时候从重复的下一个字符开始判断 i = right + 1; //然后往两边判断，找出回文子串的长度 while (right < n - 1 && left > 0 && A.charAt(right + 1) == A.charAt(left - 1)) { ++right; --left; } //保留最长的 if (right - left + 1 > maxLen) { maxLen = right - left + 1; } } //截取回文子串 return maxLen; } }
//参考2：暴力破解 import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { //边界条件判断 if (n < 2) return A.length(); int maxLen = 0; for (int i = 0; i < n - 1; i++) { for (int j = i; j < n; j++) { //截取所有子串，然后在逐个判断是否是回文的 if (isPalindrome(A, i, j)) { if (maxLen < j - i + 1) { maxLen = j - i + 1; } } } } return maxLen; } //判断是否是回文串 private boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start++) != s.charAt(end--)) return false; } return true; } }
//参考3：动态规划 import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { //边界条件判断 if (n < 2) return A.length(); //start表示最长回文串开始的位置， //maxLen表示最长回文串的长度 int maxLen = 1; boolean[][] dp = new boolean[n][n]; for (int right = 1; right < n; right++) { for (int left = 0; left <= right; left++) { //如果两种字符不相同，肯定不能构成回文子串 if (A.charAt(left) != A.charAt(right)) continue; //下面是s.charAt(left)和s.charAt(right)两个 //字符相同情况下的判断 //如果只有一个字符，肯定是回文子串 if (right == left) { dp[left][right] = true; } else if (right - left <= 2) { //类似于"aa"和"aba"，也是回文子串 dp[left][right] = true; } else { //类似于"a******a"，要判断他是否是回文子串，只需要 //判断"******"是否是回文子串即可 dp[left][right] = dp[left + 1][right - 1]; } //如果字符串从left到right是回文子串，只需要保存最长的即可 if (dp[left][right] && right - left + 1 > maxLen) { maxLen = right - left + 1; } } } //最长的回文子串 return maxLen; } }