编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。 示例 3：
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
输入必须是长度为 32 的 二进制串 。
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
解法一：
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n!=0){
count += n&1;
n >>>=1;
}
return count;
}
}
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
提示：
a, b 均可能是负数或 0 结果不会溢出 32 位整数
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
解法一：位运算
class Solution {
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
}
作者：jyd
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
解法一：位运算
class Solution {
public int[] singleNumbers(int[] nums) {
int ret = 0;
// 遍历异或
for (int n:nums){
ret ^= n;
}
// 对于任意整数a，有a&0001=1得a得第一位为1，a&0010=1得a得第二位为1
// 找到任意为 1 的位，根据这一位对所有的数字进行分组
int div = 1;
// 循环左移
while ((div & ret) == 0) {
div <<= 1;
}
int a=0,b=0;
// 遍历分组
for (int n:nums){
if ((div&n)!=0){
a ^= n;
}else{
b ^=n;
}
}
return new int[]{a,b};
}
}
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000 1 <= nums[i] < 2^31
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
解法一：哈希表
class Solution {
Map<Integer,Integer> map = new HashMap<>();
public int singleNumber(int[] nums) {
for (int n:nums){
if (map.get(n)!=null){
map.put(n,-1);
}else{
map.put(n,1);
}
}
for (Integer key:map.keySet()){
if (map.get(key)==1){
return key;
}
}
return nums[0];
}
}
解法二：位运算
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
解法一：排序取中
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
解法二：摩尔投票法
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数 a.length <= 100000
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
解法一：错位从左乘到右再从右乘到左
class Solution {
public int[] constructArr(int[] a) {
int[] res = new int[a.length];
if (a.length==0){
return a;
}
res[0]=1;
// 从左乘到右
// 得到[1,a,ab,abc,abcd]
for (int i=1;i<a.length;i++){
res[i] = res[i-1]*a[i-1];
}
int tmp = 1;
// 从右乘到左
// 得到[bcde,acde,abde,abce,abcd]
for(int i = a.length - 2; i >= 0; i--) {
tmp *= a[i + 1];
res[i] *= tmp;
}
return res;
}
}
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
解法一：动态规划
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n+1];
dp[2] = 1;
for (int i=3;i<n+1;i++){
for (int j=2;j<i;j++){
dp[i] = Math.max(dp[i],Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
解法一：滑动窗口
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
int i=1,j=2,s=3;
while (i<j){
if (s==target){
int[] ans = new int[j-i+1];
for (int k=i;k<=j;k++){
ans[k-i] = k;
}
res.add(ans);
}
if (s>target){
// 左收缩
s = s-i;
i++;
}else{
// 右扩张
j++;
s = s+j;
}
}
return res.toArray(new int[0][]);
}
}
##剑指 Offer 62. 圆圈中最后剩下的数字 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^5 1 <= m <= 10^6
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
解法一：
长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n - 1 的序列。只要知道长度为n-1的数列留下的是哪些元素就可以知道长度为n的数列留下哪个元素
x = f(n-1,m)
f(n,m) = (m%n+x)%n = (m+x)%n = (m + f(n-1,m)) % n
class Solution {
public int lastRemaining(int n, int m) {
int f = 0;
// 最后剩2个元素，从2开始反推
for (int i = 2; i <= n ; i++) {
f = (m + f) % i;
}
return f;
}
}
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 100 0 <= matrix[i].length <= 100
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
解法一：模拟从左到右，从上到下，从右到左，从下到上复制元素
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length==0){
return new int[0];
}
int[] res = new int[matrix.length*matrix[0].length];
int left = 0, right = matrix[0].length-1;
int top = 0, bottom = matrix.length-1;
int k = 0;
while (true){
for (int i=left;i<=right;i++){
res[k++] = matrix[top][i];
}
if (++top > bottom){
break;
}
for (int i=top;i<=bottom;i++){
res[k++] = matrix[i][right];
}
if (left > --right){
break;
}
for(int i = right; i >= left; i--){
res[k++] = matrix[bottom][i];
}
if(top > --bottom){
break;
}
for(int i = bottom; i >= top; i--){
res[k++] = matrix[i][left];
}
if(++left > right){
break;
}
}
return res;
}
}
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000 0 <= pushed[i], popped[i] < 1000 pushed 是 popped 的排列。
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
解法一：模拟
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int k=0;
for (int j : pushed) {
stack.push(j);
while (!stack.isEmpty() && stack.peek() == popped[k]) {
stack.pop();
k++;
}
}
return k>=popped.length;
}
}
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
小数（按顺序）可以分成以下几个部分：
整数（按顺序）可以分成以下几个部分：
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1：
输入：s = "0"
输出：true
示例 2：
输入：s = "e"
输出：false
示例 3：
输入：s = "."
输出：false
示例 4：
输入：s = " .1 "
输出：true
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
解法一：确定有限状态自动机
class Solution {
public boolean isNumber(String s) {
Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();
Map<CharType, State> initialMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_INITIAL);
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
}};
transfer.put(State.STATE_INITIAL, initialMap);
Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
}};
transfer.put(State.STATE_INT_SIGN, intSignMap);
Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_POINT, State.STATE_POINT);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_INTEGER, integerMap);
Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_POINT, pointMap);
Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
}};
transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_FRACTION, fractionMap);
Map<CharType, State> expMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
}};
transfer.put(State.STATE_EXP, expMap);
Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
}};
transfer.put(State.STATE_EXP_SIGN, expSignMap);
Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_EXP_NUMBER, expNumberMap);
Map<CharType, State> endMap = new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_END);
}};
transfer.put(State.STATE_END, endMap);
int length = s.length();
State state = State.STATE_INITIAL;
for (int i = 0; i < length; i++) {
CharType type = toCharType(s.charAt(i));
if (!transfer.get(state).containsKey(type)) {
return false;
} else {
state = transfer.get(state).get(type);
}
}
return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
}
public CharType toCharType(char ch) {
if (ch >= '0' && ch <= '9') {
return CharType.CHAR_NUMBER;
} else if (ch == 'e' || ch == 'E') {
return CharType.CHAR_EXP;
} else if (ch == '.') {
return CharType.CHAR_POINT;
} else if (ch == '+' || ch == '-') {
return CharType.CHAR_SIGN;
} else if (ch == ' ') {
return CharType.CHAR_SPACE;
} else {
return CharType.CHAR_ILLEGAL;
}
}
enum State {
STATE_INITIAL,
STATE_INT_SIGN,
STATE_INTEGER,
STATE_POINT,
STATE_POINT_WITHOUT_INT,
STATE_FRACTION,
STATE_EXP,
STATE_EXP_SIGN,
STATE_EXP_NUMBER,
STATE_END
}
enum CharType {
CHAR_NUMBER,
CHAR_EXP,
CHAR_POINT,
CHAR_SIGN,
CHAR_SPACE,
CHAR_ILLEGAL
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/biao-shi-shu-zhi-de-zi-fu-chuan-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
歪门邪道的解法：try-catch面向用例
class Solution {
public boolean isNumber(String s) {
try{
Double num = Double.parseDouble(s);
}catch(Exception e){
return false;
}
if (s.charAt(s.length()-1)!=' '&&(s.charAt(s.length()-1)<'0'||s.charAt(s.length()-1)>'9')&&s.charAt(s.length()-1)!='.'){
return false;
}
return true;
}
}
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/
解法一：状态机
class Solution {
public int strToInt(String str) {
Automaton automaton = new Automaton();
int length = str.length();
for (int i = 0; i < length; ++i) {
automaton.get(str.charAt(i));
}
return (int) (automaton.sign * automaton.ans);
}
}
class Automaton {
public int sign = 1;
public long ans = 0;
private String state = "start";
private Map<String, String[]> table = new HashMap<String, String[]>() {{
put("start", new String[]{"start", "signed", "in_number", "end"});
put("signed", new String[]{"end", "end", "in_number", "end"});
put("in_number", new String[]{"end", "end", "in_number", "end"});
put("end", new String[]{"end", "end", "end", "end"});
}};
public void get(char c) {
state = table.get(state)[get_col(c)];
if ("in_number".equals(state)) {
ans = ans * 10 + c - '0';
ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
} else if ("signed".equals(state)) {
sign = c == '+' ? 1 : -1;
}
}
private int get_col(char c) {
if (c == ' ') {
return 0;
}
if (c == '+' || c == '-') {
return 1;
}
if (Character.isDigit(c)) {
return 2;
}
return 3;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solution/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-sh-epeo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。