编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
示例 1: 输入: 11 输出: 3 解释: 整数 11 的二进制表示为 00000000000000000000000000001011 示例 2: 输入: 128 输出: 1 解释: 整数 128 的二进制表示为 00000000000000000000000010000000
public int HammingWeight(uint n) { if(n == 0) return 0; uint num = 0; while(n != 1) { num += n % 2; n /= 2; } return (int)(num + 1); }
余2表示的是取n最左位的值,而除2是表示n右移一位。最后剩下一位1,所以结果+1。
等同于:
public int HammingWeight(uint n) { if(n == 0) return 0; uint num = 0; while(n != 1) { num += (n & 1); n = (n>>1); } return (int)(num + 1); }
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public int MaxDepth(TreeNode root) { if(root == null) { return 0; } else { //递归实现,先进入到最深最深的左节点或右节点,然后慢慢加上来 int left = MaxDepth(root.left); int right = MaxDepth(root.right); return left > right ? left + 1 : right + 1; } } }
我原本的思路是,用一个List来存储每一层的所有节点,然后取出来遍历(清空list),如果不为空就将他们的子节点添加到list中并将深度加1,直到list中的为空为止。
public class Solution { public int MaxDepth(TreeNode root) { List<TreeNode> list = new List<TreeNode>(); list.Add(root); int height = 0; while(list.Count > 0) { bool isHeight = false; TreeNode[] all = list.ToArray(); list.Clear(); foreach(TreeNode node in all) { if(node != null) { isHeight = true; list.Add(node.left); list.Add(node.right); } } if(isHeight) { height++; } } return height; } }
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例: 输入:nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
public void Merge(int[] nums1, int m, int[] nums2, int n) { //合并排序,但是是在合并的数组中存储结果,所以可以先从后面开始,找最大的 int index = m + n - 1; while(m > 0 && n > 0) { if(nums1[m-1] > nums2[n-1]) { nums1[index] = nums1[m-1]; m--; } else { nums1[index] = nums2[n-1]; n--; } index--; } //剩下的m本来就是在nums1中的,所以不需要对剩余m的填充 while(n > 0) { nums1[index] = nums2[n-1]; index--; n--; } }
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3
public ListNode DeleteDuplicates(ListNode head) { if(head == null) return null; ListNode h = head; while(head.next != null) { if(head.next.val != head.val) { head = head.next; }else{ //相同,直接去除掉 head.next = head.next.next; } } return h; }
假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1: 输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 步 + 1 步 2. 2 步
示例 2: 输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 步 + 1 步 + 1 步 2. 1 步 + 2 步 3. 2 步 + 1 步
public int ClimbStairs(int n) { //动态规划 if(n == 0) return 0; if(n == 1) return 1;//固定两个 if(n == 2) return 2;//后面结果由这两个转移而来 int fi = 1; int fj = 2; for(int i = 3;i<=n;i++) { fj = fj + fi;//状态转移 fi = fj - fi; } return fj; }
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
public int MySqrt(int x) { int l = 1; int r = x; int mid = 0; while(l <= r) { mid = l + (r - l) / 2; if(mid == x / mid) return mid; else if(mid > x / mid) r = mid - 1; else l = mid + 1; } return r; }
public int MySqrt(int x) { long r = x; while(r * r > x) r = (r + x / r) / 2; return (int)r; }
给定一个非负整数组成的非空数组,在该数的基础上加一,返回一个新的数组。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。
public int[] PlusOne(int[] digits) { int[] datas = new int[digits.Length]; int up = 1; int index = digits.Length - 1; //第一部分,将+1进行到底,表示为index位+up while(up == 1 && index >= 0) { datas[index] = (digits[index] + up) % 10; up = (digits[index] + up) / 10; index--; } if(index == -1 && up == 1) { //一直有进位到了头部,要加多一位1在头部 int[] temp = datas; datas = new int[digits.Length + 1]; datas[0] = 1; for(int i = 1;i<digits.Length + 1;i++) { datas[i] = temp[i-1]; } }else { //将剩下的部分复制过来 for(int i = index;i>=0;i--) { datas[i] = digits[i]; } } return datas; }
给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。
如果不存在最后一个单词,请返回 0 。
说明:一个单词是指由字母组成,但不包含任何空格的字符串。
示例: 输入: "Hello World" 输出: 5
public int LengthOfLastWord(string s) { if(s == null || s.Length == 0) return 0; //去除两边空格 s = s.Trim(); //从后面遍历到空格 int length = 0; int index = s.Length - 1; while(index >= 0 && s[index] != ' ') { length++; index--; } return length; }
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
public int MaxSubArray(int[] nums) { if(nums == null || nums.Length == 0) return 0; int curValue = nums[0]; int maxValue = nums[0]; for(int i =1;i < nums.Length;i++) { //将前面的最大子序列值和自己相加,看看是不是比自己大,找出自身位置的最大子序列值 if(curValue + nums[i] > nums[i]) { curValue= curValue + nums[i]; } else { curValue = nums[i]; } //每个位置的最大子序列值和全局最大的对比 if(curValue > maxValue) { maxValue = curValue; } } return maxValue; }
curValue表示为当前位置最大的值(相对前面的序列),从一个位置开始不断的推断下去的,动态规划
利用每个位置当前最大的子序列值和全局的最大值对比,更新全局最大值,这样只需要遍历一次数组就可以找出来了。
报数序列是指一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:
1. 1 2. 11 3. 21 4. 1211 5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"), 即 21。
21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211。
给定一个正整数 n ,输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串
示例 1: 输入: 1 输出: "1" 示例 2: 输入: 4 输出: "1211"
public string CountAndSay(int n) { if(n == 0) return ""; string res = "1";//初始化第一个报数 StringBuilder tempRes;//临时计算报数的串 for(int i = 2;i <= n;i++) { int index = 1;//有几个当前个体 int targetIndex = 0;//当前个体 tempRes = new StringBuilder(); for(int j = 1;j < res.Length; j++) { //和前面的比较 if(res[j-1] == res[j]) { index++; } else { tempRes.Append( index.ToString() ); tempRes.Append( res[targetIndex] ); targetIndex = j;//更改当前个体为这个不相等的字符 index = 1;//多少个,当然是1个了 } } //收尾,最后一次的数数还没有算进来的 tempRes.Append( index.ToString() ); tempRes.Append( res[targetIndex] ); res = tempRes.ToString(); } return res; }
没有办法的事了,只能不断的利用前一个数去推下一个数,直到推到指定位置的报数了