资料来源:https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation/2
问:确定数组中出现最多的元素.我能够解决它,但很想看别人的解决方案.所以我遇到了使用位操作的解决方案.
public int majorityElement(int[] nums) {
int[] bit = new int[32];
for (int num: nums)
for (int i=0; i<32; i++)
if ((num>>(31-i) & 1) == 1)
bit[i]++;
int ret=0;
for (int i=0; i<32; i++) {
bit[i]=bit[i]>nums.length/2?1:0;
ret += bit[i]*(1<<(31-i));
}
return ret;
}
当我更换线路
ret += bit[i]*(1<<(31-i));
同
ret += bit[i]*(1<<i);
我最终得到一个负数.
考虑输入数组 - [2,5,5,5,3],在第一个for循环之后,bit [0]将包含4,bit [1] = 2,bit [3] = 3,所有其他位将是0.
根据我的理解,第二个for循环将导致其位位置31和29设置为1的数字(与5不同).在我的理解中,我显然遗漏了一些东西.
有人可以解释这段代码是如何工作的？谢谢.
我正在解决问题https://leetcode.com/problems/path-sum-iii/ 我还会在这里简单提一下:找到二叉树中sum = sum的路径数.该路径不一定必须在根(叶)处开始(结束).只要路径向下,就应该将其视为有效路径.
这是我的解决方案:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
int path = 0;
if(root.val == sum)
return 1;
else if(root.left == null && root.right == null)
return 0;
if(root.left != null){
path += pathSum(root.left, sum - root.val);
path += …我正在解决Leetcode 上的回文分区问题。
我编写了一个递归解决方案，它打印正确的子字符串列表，但对于其中一个测试用例，列表中的顺序与预期的输出不匹配。
输入：
bbbbcc
输出：
[["c","b","b","b","c","c"],["b","b","b","c","cc"],[ "b","c","bb","c","c"],["b","bb","c","cc"],["c","bb","b ","c","c"],["bb","b","c","cc"],["c","bbb","c","c"],["bbb ","c","cc"],["cbbbc","c"]]
预期的：
[["c","b","b","b","c","c"],["c","b","b","b","cc"],[ "c","b","bb","c","c"],["c","b","bb","cc"],["c","bb","b ","c","c"],["c","bb","b","cc"],["c","bbb","c","c"],["c ","bbb","cc"],["cbbbc","c"]]
我无法弄清楚为什么我的递归调用在这个例子中移动了第一个元素“c”。
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backTrack(result, new ArrayList<String>(), s);
return result;
}
private void backTrack(List<List<String>> result, List<String> cur, String s){
if(s.length() == 0)
result.add(new ArrayList<>(cur));
/* length = i+1 */
for(int i = 0; i < s.length(); i++){
if(isPalindrome(s.substring(0, i+1))){
cur.add(s.substring(0, i+1));
backTrack(result, cur, s.substring(i+1, s.length()));
cur.remove(s.substring(0, i+1));
}
}
} …