Tag: algorithm

确定数独是否具有唯一解决方案

我正在努力使用回溯算法来确定数独有一个独特的解决方案，或者它是否有多个解决方案。 这是我使用的回溯代码： static boolean solve(int i, int j, int[][] cells) { if (i == 9) { i = 0; if (++j == 9) return true; } if (cells[i][j] != 0) // skip filled cells return solve(i+1,j,cells); for (int val = 1; val <= 9; ++val) { if (legal(i,j,val,cells)) { cells[i][j] = val; if (solve(i+1,j,cells)) return […]

确定作为n的函数，执行增加变量计数的语句的频率

好的，我是分析算法的新手，非常感谢任何有用的技巧，可以分享如何解决这个问题。 我试图确定计数增加的次数是n的函数。 我在一个ide中运行它，对于值1-7，输出为1,3,6,10,15,21,28。 我只是不确定如何写这个作为n的函数？ 谢谢。 循环如下： for(int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= i ; j++) { count++; } }

检查二叉树是否也是二叉搜索树的问题

我正试图解决这个问题，但我遇到了一些麻烦： 在二叉搜索树（BST）中： 节点左子树中每个节点的数据值小于该节点的数据值。 节点右子树中每个节点的数据值大于该节点的数据值。 给定根节点： class Node { int data; Node left; Node right; } 确定二叉树是否也是二叉搜索树 我有这个代码： boolean check(Node root) { //node doesn’t have any children if (root.left == null && root.right == null) { return true; } boolean leftIsBst = true; boolean rightIsBst = true; if (root.left != null) { leftIsBst = (root.left.data root.data) […]

如何生成-complete-sudoku板？ 算法错误

我正在尝试生成一个完整的（即每个单元格中填充一个数字）类似Sudoku的板。 这是与sudokus无关的其他东西，所以我对达到可以解决的白色方块或与sudokus有关的任何东西都不感兴趣。 不知道你是否知道我的意思。 我在java中完成了这个： private int sudokuNumberSelector(int x, int y, int[][] sudoku) { boolean valid = true; String validNumbers = new String(); int[] aValidNumbers; int squarexstart = 0; int squareystart = 0; int b = 0; // For random numbers Random randnum = new Random(); randnum.setSeed(new Date().getTime()); // Check numbers one by one for(int n […]

计算链表中的值的总和

我最近在接受采访时得到了编程问题。 有2个链接列表。 每个节点存储1到9的值（表示数字的一个索引）。 因此123将是链接列表1-> 2-> 3 任务是创建一个函数： static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) 这将返回2个链表列表中的值的总和。 如果arraysa是：1-> 2-> 3-> 4 并且arraysb是：5-> 6-> 7-> 8 答案应该是：6-> 9-> 1-> 2 这是我的算法： 遍历a和b中的每个节点，将值作为整数获取并添加它们。 使用这些值创建新的链接列表。 这是代码：它大概是我假设的复杂度为O（n）。 一旦通过每个数组输入并一次创建输出数组。 任何改进？ 更好的算法……或代码改进 public class LinkedListNode { LinkedListNode next; int value; public LinkedListNode(int value) { this.value = value; this.next = null; } static int getValue(LinkedListNode […]

如何撤消链表？

Node reverse(Node head) { Node previous = null; Node current = head; Node forward; while (current != null) { forward = current.next; current.next = previous; previous = current; current = forward; } return previous; } 究竟是如何扭转名单的呢？ 我知道它首先将第二个节点设置为forward 。 然后它说current.next等于前一个null节点。 然后它说previous现在是current 。 最后current变得forward ？ 我似乎无法掌握这一点以及它的逆转方式。 有人可以解释这是如何工作的？

未加权图的最短路径（最少节点）

我正在尝试构建一个方法，在未加权的图形中返回从一个节点到另一个节点的最短路径。 我考虑过使用Dijkstra，但这似乎有点矫枉过正，因为我只想要一对。 相反，我已经实现了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 – 如何修改我的代码以实现我的目标？ public List getDirections(Node start, Node finish){ List directions = new LinkedList(); Queue q = new LinkedList(); Node current = start; q.add(current); while(!q.isEmpty()){ current = q.remove(); directions.add(current); if (current.equals(finish)){ break; }else{ for(Node node : current.getOutNodes()){ if(!q.contains(node)){ q.add(node); } } } } if (!current.equals(finish)){ System.out.println(“can’t reach destination”); } return directions; }

LCP如何帮助查找模式的出现次数？

我已经读过最长公共前缀（LCP）可用于查找字符串中模式的出现次数。 具体来说，您只需要创建文本的后缀数组，对其进行排序，然后不进行二进制搜索以找到范围，以便您可以计算出现次数，只需计算每个连续条目的LCP即可。后缀数组。 虽然使用二进制搜索来查找模式的出现次数是显而易见的，但我无法弄清楚LCP如何帮助找到此处出现的次数。 例如，对于banana这个后缀数组： LCP Suffix entry N/A a 1 ana 3 anana 0 banana 0 na 2 nana LCP如何帮助找到像“banana”或“na”这样的子字符串的出现次数对我来说并不明显。 有什么帮助搞清楚LCP如何帮助吗？

找到所有作为回文的子串

如果输入是“abba”，则可能的回文是a，b，b，a，bb，abba。 我知道确定字符串是否是回文很容易。 这将是： public static boolean isPalindrome(String str) { int len = str.length(); for(int i=0; i<len/2; i++) { if(str.charAt(i)!=str.charAt(len-i-1) { return false; } return true; } 但找到回文子串的有效方法是什么？

StackOverflowError计算BigInteger的阶乘？

我正在尝试编写一个Java程序来计算大数的阶乘。 似乎BigInteger无法容纳这么大的数字。 以下是我写的（直截了当的）代码。 public static BigInteger getFactorial(BigInteger num) { if (num.intValue() == 0) return BigInteger.valueOf(1); if (num.intValue() == 1) return BigInteger.valueOf(1); return num.multiply(getFactorial(num.subtract(BigInteger.valueOf(1)))); } 上述程序在5022中处理的最大数量，之后程序抛出StackOverflowError 。 有没有其他方法来处理它？